Assume that ($\oplus$, $\otimes$) is a semiring over the non-negative reals.


If $\otimes$ is +, what are the possible operators for $\oplus$?


So far I have proven that `max` and `softmax` (`logsumexp`) are solutions. Can we characterize all possible $\oplus$?


I'd also appreciate references to relevant papers.



($\oplus$, $\otimes$) is a semiring. If $\otimes$ = +, what are the possible operators $\oplus$?
I'll give two answers. The first one just echoes the comments and saying that there are no such semirings, and the other saying that `max` gives the only continuous such semiring, if you take a nonstandard definition of semiring.


The standard definition of a (commutative) semiring is a set $R$ equipped with two operations $\otimes$ and $\oplus$, so that $(R,\otimes)$ and $(R,\oplus)$ are commutative monoids, so that $\otimes$ distributes over $\oplus$, and so that the unit of $\oplus$ annihilates $R$ under $\otimes$. I focus on the commutative case because you always want $\otimes$ to be addition, which is commutative.


Let $R$ denote the non-negative reals.




---


It's basically been pointed out in the comments that with this definition, there can be no such semiring structure on $R$ with addition as $\otimes$. This is because of the annihilation condition. Let $e$ be the unit of $\oplus$; then $e+a=e$ for all $a$ in $R$, which is not possible.




---


Next, drop the annihilation condition. I'll show that `max` is the only continuous choice for $\oplus$ in this less restrictive definition. I will not assume that the additive unit is $0$. Note that choosing `softmax` for $\oplus$ (and addition for $\otimes$) does not yield a semiring structure on $R$ with this definition because $\oplus$ does not have an identity element.


First, note that $a + (0\oplus 0) = (a + 0) \oplus (a+0) = a\oplus a$ for all $a$ by distributivity. This is true for the additive unit so $(0\oplus 0)=0$ and thus $(a\oplus a)=a$ for all $a$.


Then define $f(a)= 0\oplus a$. Using distributivity, $(b\oplus (a+b))= f(a)+b$ for all $a$ and $b$. So $\oplus$ is totally determined by $f$. 


By associativity of $\oplus$, we have $f(a) = 0\oplus a=(0\oplus 0)\oplus a=0\oplus (0\oplus a)=f(f(a))$, so $f$ is a retract. Decompose $R$ as $F\sqcup G$ where $a$ is in $F$ if $f(a)=a$. 


If $G$ is empty, then $(b\oplus (a+b))=a+b=\max\{a,a+b\}$. This gives the answer of `max` for $\oplus$ that we already know. Then instead we can assume that $G$ is nonempty. Now let $z$ be the infimum of $G$. $F$ is closed and contains $0$ so $z\in F$. Then $(z\oplus 2z) = z + (0\otimes z)= 2z$ by distributivity. But then by associativity 


$$2z = z\oplus 2z = (0\oplus z)\oplus 2z = 0\oplus (z\oplus 2z)= 0\oplus 2z = f(2z)$$ so $2z\in F$.


Now assume that $f$ is continuous. We will derive a contradiction. First suppose $a\in G$ and $b\in F$ with $a < b$. Then since $f(0)=0$ and $f(b)=b$, by the intermediate value theorem there is some $c$ with $f(c)=a$. But this implies $f(a)=f^2(c)=f(c)=a$, a contradiction since $a\in G$. Then we have shown that if $a\in G$ then all $b>a$ are also in $G$. In particular, if $z>0$ then $2z$ is in both $F$ (by the explicit calculation above) and $G$ (by this paragraph, by the definition of infimum), a contradiction. 


The only remaining possibility is $\inf G=0$. But then the connectedness of $F$ implies that $F=\{0\}.$ But in this case, since $f(R)=F$, necessarily $f(R)=0$ which implies that $a\oplus (a+b)= a = \min\{a,a+b\}$. But $\min$ does not have a unit in $R$.




---


Maybe this can be modified to show that in the case that one also drops the assumption that $\oplus$ have a unit, that `min` and `softmax` are the only other continuous options. I'll leave that to someone else.


