How many associative binary operations on the integers does $+$ distribute over?

Question

I am interested in binary operations $\mid: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ which satisfy:

• Associativity: $a \mid (b \mid c) = (a \mid b) \mid c$
• $+$ distributes over $\mid$: $(a \mid b) + c = (a + c) \mid (b + c)$.

I know of the following such operations: $\max, \min, (x, y) \mapsto x,$ and $(x, y) \mapsto y$. Are there others?

---

Over the reals, there is also an infinite family of such operations $(x, y) \mapsto \log_a (a^x + a^y)$, for any base $a$. But this operation doesn't restrict to the integers.

Answer 1

Answering my own question: I prove that there are only the four such operations: $\max(x, y)$, $\min(x, y)$, $\text{first}(x, y) = x$, and $\text{last}(x, y) = y$.

In the following lemmas, we first show idempotence $x \mid x = x$, with some work. Then we look at chains of sums of $(0 \mid 1)$ to find $0 \mid n = n (0 \mid 1)$, and finally we determine that $(0 \mid 1)$ is either $0$ or $1$. Combining this with the symmetric observation that $(1 \mid 0)$ is either $0$ or $1$ will give us the four cases.

Lemma 1: $x \mid x = x$.

Since $x \mid x = x + (0 \mid 0)$, it suffices to show $0 \mid 0 = 0$. Consider the map $\phi: \mathbb{Z}^+ \to \mathbb{Z}$ defined by $\phi(n) = \underbrace{0 \mid 0 \mid \cdots \mid 0}_{n \text{ zeros}}$. Then I claim $$ \phi(mn) = \phi(m) + \phi(n) $$ This is by rewriting the right-hand side as $$ \underbrace{0 \mid 0 \mid \cdots \mid 0}_{m} + \phi(n) = \underbrace{\phi(n) \mid \cdots \mid \phi(n)}_{m} $$ and expanding. In particular, we have that $\phi(p^a) = a \phi(p)$ for any prime $p$.

Now I claim that $\phi(x) = \phi(y)$ for some $0 \le x < y$. If $\phi(p) = 0$ for any prime, then $\phi(1) = \phi(p)$. Otherwise, there must be primes $p_1$ and $p_2$ such that $\phi(p_1)$ and $\phi(p_2)$ have the same sign. Examining $\phi(p_1^a) = a \phi(p_1)$ and $\phi(p_2^b) = b \phi(p_2)$, we see that we can choose $a, b > 0$ to make these equal: in particular, $a = |\phi(p_2)|$ and $b = |\phi(p_1)|$.

To complete the proof of Lemma 1, $\phi(x) = \phi(y)$ implies that $\phi(n)$ is periodic for $n$ sufficiently large, since $\phi(n) = \phi(n - x) \mid \phi(x) = \phi(n - x) \mid \phi(y) = \phi(n - x + y)$, and hence bounded. But $\phi(2^a) = a \phi(2)$ is not bounded unless $\phi(2) = 0$, so $\phi(2) = 0 \mid 0 = 0$, and in fact, $\phi(n) = 0$ for all $n$.

Lemma 2: for $n \ge 0$, $0 \mid 1 \mid \cdots \mid n = n (0 \mid 1)$.

Proof by induction: \begin{align*} 0 \mid 1 \mid \cdots \mid (n + 1) &= 0 \mid (1 \mid 1) \mid (2 \mid 2) \mid \cdots \mid (n \mid n) \mid (n + 1) \quad\text{by Lemma 1} \\ &= (0 \mid 1) \mid (1 \mid 2) \mid \cdots \mid (n \mid (n + 1)) \\ &= (0 + (0 \mid 1)) \mid (1 + (0 \mid 1) \mid (2 + (0 \mid 1)) + \cdots \\ &= (0 \mid 1 \mid \cdots \mid n) + (0 \mid 1). \end{align*}

Lemma 3: for $n \ge 0$, $0 \mid n = n (0 \mid 1)$.

Note that: \begin{align*} (0 \mid n) + (0 \mid 1 \mid 2 \mid ... \mid n) &= (0 + (0 \mid 1 \mid 2 \mid ... \mid n)) \mid (n + (0 \mid 1 \mid 2 \mid ... \mid n)) \\ &= 0 \mid 1 \mid 2 \mid ... \mid (2n) \quad\text{by Lemma 1: } n \mid n = n \end{align*} Applying Lemma 2, $(0 \mid n) + n (0 \mid 1) = 2n (0 \mid 1)$, and the result follows.

Lemma 4: $(0 \mid 1) \in \{0, 1\}$.

Let $k = (0 \mid 1)$. By idempotence, $0 \mid 1 = 0 \mid 0 \mid 1 \mid 1$, and we consider different ways to evaluate this associatively. First, $(0 \mid 1) \mid 1 = k \mid 1$, and second, $0 \mid (0 \mid 1) = 0 \mid k$. Thus, $$ k = k \mid 1 = 0 \mid k $$ Now we have two cases. If $k \ge 0$, then $$ 0 \mid k = k (0 \mid 1) = k^2, $$ so $k = k^2$ and $k \in \{0, 1\}$. Second, if $k < 0$, then subtracting $k$ from $k = k \mid 1$ we get $$ 0 = (k - k) \mid (1 - k) = 0 \mid (1 - k) = (1 - k) (0 \mid 1) = (1 - k) k $$ so again $k = 0$ or $k = 1$ (actually a contradiction since $k < 0$), and we are done.

Putting things together

All of lemmas 2-4 can be proven identically for the symmetric case of $b \mid a$ instead of $a \mid b$, from which we get that $1 \mid 0 \in \{0, 1\}$. So there are two cases for $0 \mid 1$ and two cases for $1 \mid 0$. Together with Lemma 3 we can then calculate $m \mid n$ for any $m, n$: $$ m \mid n = \begin{cases} m + (0 \mid (n - m)) = m + (n - m) (0 \mid 1) \text{ if } n \ge m \\ n + ((m - n) \mid 0) = n + (m - n) (1 \mid 0) \text{ if } m \ge n. \end{cases} $$

In particular:

• If $0 \mid 1 = 1 \mid 0 = 1$, this gives the max operation $\max(x, y)$.
• If $0 \mid 1 = 1 \mid 0 = 0$, this gives the min operation $\min(x, y)$.
• If $0 \mid 1 = 0$ and $1 \mid 0 = 1$, this gives the first projection $\text{first}(x, y) = x$.
• Finally, if $0 \mid 1 = 1$ and $1 \mid 0 = 0$, this gives the second projection $\text{last}(x, y) = y$.

Answer 2

Partial result: I find only the four know operations, and other examples seem hard to find.

In what follows, $\Bbb N=\{1,2,3,\ldots\}$ and $\Bbb N_0=\{0,1,2,3,\ldots\}$.

Preliminary remark: If $A\subseteq \Bbb Z$ is closed under addition ($A+A\subseteq A$), then one of the following holds:

A1: $A=\emptyset$

A2: $A=\{0\}$

A3: $A=m\Bbb Z$ for some positive integer $m$

A4: $A$ is a submonoid of $\Bbb N_0$. More explicitly, there are integers $r\ge 1$ and $0<m_1<\cdots <m_r$ with $A=m_1\Bbb N_0+\cdots+m_r\Bbb N_0$

A5: as A4, but negated, i.e., $A$ is a submonoid of $-\Bbb N_0$

A6: $A$ is a sub-semigroup of $\Bbb N$. Equivalently, as in A4, but with $0$ removed

A7: $A$ is a sub-semigroup of $-\Bbb N$. Equivalently, as in A5, but with $0$ removed

Proof: Exercise. $\square$

Note that under the stronger condition $A+A=A$, options A6 and A7 are excluded. Also note: If two such sets both have positive[negative] elements, then they have positive[negative] elements in common.

---

We can convert the problem at hand into an investigation of the functional equation $$\tag0 f(f(y)+x)=f(x+y-f(x))+f(x).$$ With every binary operation $\star\in\Bbb Z^{\Bbb Z\times \Bbb Z}$, we associate a map $f_\star\in\Bbb Z^{\Bbb Z}$ given by $f_\star(x)=0\star x$, and with every map $f\in\Bbb Z^{\Bbb Z}$, we can associate a binary operation $\star_f\in\Bbb Z^{\Bbb Z\times \Bbb Z}$ given by $x\star_f y = x+f(y-x)$. Let $$\mathscr R=\{\,\star\colon\Bbb Z\times \Bbb Z\to\Bbb Z\mid a\star(b\star c)=(a\star b)\star c, (a+c)\star(b+c)=(a\star b)+c\,\} $$ and $$\mathscr F=\{\,f\colon \Bbb Z\to \Bbb Z\mid (0)\text{ holds for all }x,y\in\Bbb Z\,\}.$$ Consider $\star \in \mathscr R$. Then by distributivity, $x\star y = 0\star(y-x)+x$, i.e., $\star_{f_\star}=\star$. By equating $$ 0\star(x\star (x+y))=0\star(f_\star(y)+x) = f_\star(f_\star(y)+x)$$ and $$ (0\star x)\star(x+y) = f_\star(x)\star (x+y)=f_\star(x+y-f_\star(x))+f_\star(x)$$ we see that $f_\star\in \mathscr F$.

Conversely, consider $f\in\mathscr F$. Then $ (a+c)\star_f(b+c)=a+c+f(b-a)=c+a\star_fb$, i.e., $+$ distributes over $\star_f$. Moreover, the same computation as above shows that $0\star_f(x\star_f (x+y))=(0\star_f x)\star_f(x+y)$. Then by substituting $x\leftarrow b-a$, $y\leftarrow c-b$ and distributivity, $$ a\star_f(b\star_f c)=a+0\star_f(b\star_f c-a) = a+0\star_f((b-a)\star_f(c-a))=a+(0\star_f(b-a))\star_f(c-a)=(0\star_f(b-a)+a)\star_fc=(a\star_f b)\star_f c,$$ i.e., $\star_f\in\mathscr R$.

We conclude that the associations $\star\mapsto f_\star$ and $f\mapsto \star_f$ are inverse bijections $\mathscr R\leftrightarrow\mathscr F$. This allows us to investigate $\mathscr F$ instead of $\mathscr R$.

For $\star\in\mathscr R$, then $\star^T$ given by $x\star^T y=y\star x$ is also $\in\mathscr R$. Via our bijective associations, for $f\in\mathscr F$, we set $f^T=f_{\star_f^T}$, which amounts to $$f^T(x)=0\star^Tx=x\star 0 = 0\star (-x)+x=f(-x)+x.$$ Note that $\star^{TT}=\star$ (or direct computation) implies $f^{TT}=f$. Moreover, for $f\in\mathscr F$, define $f^C(x)=-f(-x)$. One verifies immediately that also $f^C\in\mathscr F$. Via our bijective associations, for $\star\in\mathscr R$, we set $\star^C=\star_{f_\star^C}$, which amounts to $x\star^Cy = x+y-y\star x$. Clearly, $f^{CC}=f$ Note that $f^{TC}(x)=-f^T(-x)= x-f(x)=f^C(-x)+x=f^{CT}(x)$, which motivates us to define $f^D=f^{TC}=f^{CT}$. Clearly, $f^{DD}=f$.

For $f\in \mathscr F$, we define image $I(f)$, difference set $D(f)$, fixpoint set $F(f)$, and "kernel" $Z(f)$ as $$ \begin{align} I(f)&=\{\,f(x)\mid x\in\Bbb Z\,\},\\ D(f)&=\{\,x-f(x)\mid x\in\Bbb Z\,\},\\ F(f)&=\{\,x\in\Bbb Z\mid f(x)=x\,\},\\ Z(f)&=\{\,x\in\Bbb Z\mid f(x)=0\,\}.\end{align}$$ Note that we have some "duality": $$\tag1D(f) = I(f^{D}),\quad F(f) = Z(f^{D}),\quad F(f)\subseteq I(f),\quad Z(f)\subseteq D(f).$$

Lemma 1. $I(f)$, $F(f)$, $D(f)$, $Z(f)$ are closed under addition.

Proof. For $x,y\in F(f)$, we have $$ f(x+y)=f(f(y)+x)=f(x+y-f(x))+f(x)=f(y)+f(x)=y+x$$ and so $x+y\in F(f)$, i.e., $F(f)$ is closed under addition. By $(1)$, $Z(f)=F(f^D)$ is also closed under addition. By substituting $y\leftarrow y+f(x)-x$ in $(0)$, we obtain $$ f(y)+f(x)=f(f(y+f(x)-x)+x),$$ i.e., $I(f)$ is closed under addition. By $(1)$, $D(f)=I(f^D)$ is also closed under addition. $\square$

Lemma 2. $I(f)=I(f)+I(f)$, $D(f)=D(f)+D(f)$.

Proof. By substituting $x\leftarrow x-f(y)$ in $(0)$, we obtain $$ f(x)=f(x-f(y)+y-f(x-f(y)))+f(x-f(y)),$$ showing the first part. The second follows from $D(f)=I(f^D)$. $\square$

Corollary. $Z(f)$ and $F(f)$ are not empty.

Proof. Clearly $I(f)\ne \emptyset$. If $I(f)$ is as in A6 or A7 of the preliminary remark, we obtain a contradiction with lemma 2. It follow sthat $I(f)$ falls under A2, A3, A4, or A5. In particular, $0\in I(f)$ and hence $Z(f)\ne\emptyset$. By duality, $F(f)\ne\emptyset$. $\square$.

Lemma 3. $F(f)+I(f)=F(f)$ and $Z(f)+D(f)=Z(f)$.

Proof. From $0\in I(f)$, we have $F(f)\subseteq F(f)+I(f)$. If $x\in F(f)$ and $z=f(y)\in I(f)$, then $$ f(z+x)=f(f(y)+x)=f(x+y-f(x))+f(x)=f(y)+x=z+x$$ so that also $F(f)+I(f)\subseteq F(f)$. The second part follows by duality. $\square$

We investigate the possible case for $F(f)$ as given by the preliminary remark, noting that in the cases where $0\in F(f)$, lemma 3 implies $F(f)=I(f)$, i.e., that $f$ is idempotent.

Case A1: is not possible as per the corollary above.

Case A2: $F(f)=\{0\}=I(f)$. So $f(x)=0$ for all $x$ and the corresponding binary operation is $$\fbox{$x\star y=x.$}$$ Note that this makes $Z(f)=D(f)=\Bbb Z$ so that $f^D$ falls under case A3.

Case A3: $F(f)=m\Bbb Z=I(f)$ for some $m>0$. Then $Z(f)$ (and also $D(f)$) falls under A2 because otherwise $F(f)$ and $Z(f)$ or $D(f)$ woulda have a non-zero element in common. We conclude that $D(f)=\{0\}$ and $f$ is the identity. The corresponding binary operation is $$\fbox{$x\star y=y$.}$$

Case A4+A5: From the observations in the other cases, we know that $f^D$ cannot fall under A1, A2, A3. As $0\in Z(f)=F(f^D)$, $f'D$ cannot fall under case A6+A7 below, either. Hence $f^D$ falls under A4+A5. To avoid non-trivial intersection between $F(f)$ and $Z(f)$, we either have $f$ under subcase A4 and $f^D$ under subcase A5, or vice versa. First consider subcase A4. If $x\in I(f)$, say $x=f(y)$, then $$ 0=f(0)= f(f(y)-x) = f(-x+y-f(-x)) + f(-x)$$ and as both values on the right are non-negative, we have $f(-x)=0$. Thus $-I(f)\subseteq Z(f)\subseteq D(f)$. In subcase A5, the same argument yields the same inclusion $-I(f)\subseteq Z(f)\subseteq D(f)$. As $f^D$ falls under A4+A5 as well, we also have $-D(f)\subseteq F(f)\subseteq I(f)$. Combined, this makes $$ Z(f)=D(f)=-I(f).$$ Restricting to subcase A4 again, assume $a:=f(-1)>0$. Then $$ a = f(f(0)-1) = f(-1+0-f(-1))+f(-1)=f(-a-1)+a$$ so that $-a-1\in Z(f)$ and $a+1\in I(f)$. From $a,a+1\in I(f)$ it follows that $I(f)$ contains almost all naturals. Let $N$ be minimal with $N+\Bbb N_0\subseteq I(f)$ as well as $-N-\Bbb N_0\subseteq Z(f)$. Then for $x\le -N$, $$ f(a+x) = f(x-1-f(x))+f(x)=f(x-1)+f(x)=0$$ hence also $a-N-\Bbb N_0\subseteq Z(f)$, $N-a+\Bbb N_0\subseteq I(f)$, contradicting minimality of $N$. We conclude that $f(-1)$ cannot be positive. Then $Z(f)=D(f)=-\Bbb N_0$, $I(f)=F(f)=\Bbb N_0$, which implies $f(x)=\max\{x,0\}$ and $$\fbox{$x\star y=\max\{x,y\}$.}$$ The same argument in subcase A5 leads to $f(x)=\min\{x,0\}$ and $$\fbox{$x\star y=\min\{x,y\}$.}$$

Case A6+A7: Here be dragons. I suspect that this case is impossible, but cannot capture this completely. So from here on, I'm just spouting some simple conclusions: Already from $0\in I(f)$, we see that now $I(f)\ne F(f)$. As all other candidate cases wer already matched in the previous cases, we find that $f^D$ also fall sunder A6+A7. More specifically, either $F(f)$ is A6 and $F(f^D)=Z(f)$ is A7, or vice versa. Assume $I(f)\ne F(f)\cup\{0\}$ and let $a=\min(I(f)\setminus (F(f)\cup\{0\})$, say $a=f(b)$. So $f(a)\ne a$ and if $f(x)<a$ then $f(x)=0$ for $f(f(x))=f(x)$. $$f(f(y)+b) = f(b+y-f(b)) + f(b)= f(b+y-a)+a $$ $$a = f(f(y)+b-f(y)) = f(b-f(y)+y-f(b-f(y))) + f(b-f(y))$$ If both values on the right are positive, they must be in $F(f)$, but then by lemma 1, $a\in F(f)$, contradiction. Hence one of the values is $=0$, i.e., either $f(b-f(y))=0$ and $f(b-f(y)+y)=a$ or $f(b-f(y))=a$ and $f(b-f(y)+y-a)=0$. Specifically, for $y=0$, the fist alternative is contradictory, hence $f(b-f(0))=a$ and $f(b-f(0)-a)=0$. By induction, $f(b-nf(0))=a$ and $f(b-nf(0)-a)=0$ for all $n\in\Bbb N$.