# Associative mean

Can there be a function $m(a,b)$ that is both associative and a mean, i.e., $\min (a,b) \leq m(a,b) \leq \max (a,b)$? The obvious solutions are $m(a,b) = \max(a,b)$ or $\min(a,b)$, but are there more?

• If $a<c:=m(a,b)<b$ then $m(a,c)=c$ because $m(a,a)=a$ and associativity, and likewise $m(c,b)=c$. This is already a bit suspicious. It would probably help to go further if you are willing to assume some or all of the following about the function $m$: (1) commutativity (I mean $m(a,b)=m(b,a)$), (2) continuity, and/or (3) monotonicity in each variable. Nov 13, 2017 at 21:59
• If it is a mean, then it is idempotent, and is locally finite. On any finite subset I can imagine a total ordering of the terms freely generated from that subset such that the ordering respects your restrictions, however the longest terms essentially absorb the rest, so there won't be a strict mean on this finite sub algebra. Gerhard "See Arthur Gerhard For More" Paseman, 2017.11.13. Nov 13, 2017 at 22:00
• ? first one in the list? $m(a,b) = a$. Not commutative, but is continuous and monotone. Nov 13, 2017 at 22:40
• A function defined where and valued in what? I guess one should understand a binary law on the reals, but it should have been explicit.
– YCor
Nov 14, 2017 at 19:20
• A beautiful monotonic, symmetric, discontinuos example, which is a limit case of Goldstern's constructs: define $m(a,b)$ as the unique (!) number in $[a,b]\cap\mathbb{Z}[1/2]$ with the smallest 2−adic norm (or $m(a,a)=a$). Nov 20, 2017 at 16:49

Yes there are more such functions, even if we require them to be symmetric, monotonic and continuous. For example pick any $C$ and take

$m_C(a,b)=\min(a,b)$ if $a,b\ge C$,

$m_C(a,b)=\max(a,b)$ if $a,b\le C$,

$m_C(a,b)=C$ otherwise.

The following are easily verified: $m_{-\infty}=\min$, $m_{+\infty}=\max$, $m_A(m_B,m_C)=m_{m_A(B,C)}$, $f^{−1}(m_C(f(a),f(b)))=m_{f^{−1}(C)}(a,b)$ if $f:\mathbb{R}\rightarrow \mathbb{R}$ is invertible.

UPDATE.

Slightly Stronger Claim. If $m$ is monotonic, continuous and weakly associative (that is $m(a,m(a, b))=m(a,b)=m(m(a,b), b)$), then there are $U,L\in \mathbb{R}\cup \{\pm \infty\}$ such that $m=m_U$ if $a\le b$ and $m=m_L$ if $a\ge b$. Consequently $m$ is also fully associative. $m$ is symmetric iff $U=L$.

Lemma. Working in the upper-left half plane $a\le b$, pick $M\in \mathbb{R}$. Then either $(-\infty,M]\times \{M\}\subseteq m^{-1}(M)$ or $\{M\}\times [M,+\infty)\subseteq m^{-1}(M)$.

Proof.

Assume $(-\infty,M]\times \{M\}\nsubseteq m^{-1}(M)$. This implies $\exists x\lt M$ such that $m(x,M) < M$.

$m(x,M)\ne M \implies m(x,N)\ne M$ for $N>M$, otherwise weak associativity would imply $m(x,M)=m(x,m(x,N))=m(x,N)=M$.

$m(x,M) < M$, $m(x,N)\ne M$ and continuity $\implies m(x,N)\lt M$ for all $N>M$.

$m(x,N)\lt M$, $m(M,N)\ge M$ and continuity $\implies$ $\exists x_N \in (x,M]$ such that $m(x_N,N)=M$.

Weak associativity $\implies m(M,N)=m(m(x_N,N),N)=m(x_N,N)=M$ for all $N\gt M$.

This proves that $\{M\}\times [M,+\infty)\subseteq m^{-1}(M)$ $\square$

Proof of Claim. Again working in the upper-left half plane, define

$S=\{M\in \mathbb{R} \mid (-\infty,M]\times \{M\}\subseteq m^{-1}(M)\}$ and $T=\{M\in \mathbb{R} \mid \{M\}\times [M,+\infty)\subseteq m^{-1}(M)\}$.

By the lemma $S\cup T=\mathbb{R}$. Also $x\in S$ and $y\in T$ $\implies x\le y$ because otherwise $m^{-1}(x)\cap m^{-1}(y)\ne \emptyset$. All this implies that one of these 3 cases holds:

1) $S=\mathbb{R}$ and $T=\emptyset$,

2) $S=\emptyset$ and $T=\mathbb{R}$,

3) $\exists ! U\in \mathbb{R}$ such that $S=(-\infty,U]$ and $T= [U,+\infty)$, with $U$ contained in both sets by continuity. In this case monotonicity (only used here!) forces $m^{-1}(U)=(-\infty,U]\times [U,+\infty)$.

Clearly the 3 cases correspond to $m=m_{+\infty}$, $m=m_{-\infty}$ and $m=m_U$.

Similarly one can prove that $m=m_L$ in the lower-right half plane $a\ge b$. It's then a tedious but trivial exercise to show that $m$ is fully associative (and continuous, monotonic) for all pairs $U,L$ $\square$ Graph of $m$ for some $U<L$.

LAST. Two interesting fully associative counterexamples:

$m(a,b)=\min(\text{sign}(a),\text{sign}(b))\times \min(|a|,|b|)$ is continuous non-monotonic!

$m(a,b)=\min(a,b)$ if $a+b<0$, $m(a,b)=\max(a,b)$ if $a+b\ge 0$ is monotonic discontinuous.

• I believe there are other finite examples which can be extended in a similar fashion, see my comment above on idempotent semigroups. I may expand on this later. Gerhard "If You Don't Do It" Paseman, 2017.11.14. Nov 14, 2017 at 19:58

Let $(L, <)$ be any linear order. Fix an arbitrary well-order $\sqsubset$ on $L$. For any $a\le b$ define $m(a,b)=m(b,a):=$ the $\sqsubset$-least element in the interval $[a,b]$.

Then $m$ is associative and commutative. (But rather uninteresting from the point of view of the relation $<$.)

Notation: Write $\langle x,y\rangle:=\{ z: x\le z\le y \text{ or } y\le z \le x\}$.

Proof of associativity: Let $a,b,c$ be arbitrary, and let $d$ be the $\sqsubset$-least element in the interval $J:=[\min(a,b,c),\max(a,b,c)]$. I claim that $m(m(a,b),c)=d$. As $m$ is commutative, and $\min$ and $\max$ are commutative and associative, this also implies $m(a,m(b,c))=d$.

• Case 1: $d\in \langle a,b\rangle$. Then $m(a,b)=d$ (as $\langle a,b\rangle \subseteq J$), and $m(m(a,b),c)=m(d,c)=d$, as also $\langle d,c\rangle \subseteq J$.
• Case 2: $d\notin \langle a,b\rangle$. Wlog $a\le b$. We must have $c\notin [a,b]$, wlog $b< c$. So $d\in [b,c]$.
Let $d':=m(a,b)$, then $d\sqsubset d'$, and $m(m(a,b),c) = m(d',c) = d$, as $d\in [b,c]\subseteq [d',c] = \langle d',c\rangle \subseteq J$.

QED.

(Edit:) It is also easy to see that $m$ is monotone. But in general not continuous.

• NIce! A visualization of $m$ in the upper-left half plane $a\le b$: let $L_1$ the least $\sqsubset$-element of $\mathbb{R}$, $L_2$ the 2nd least etc. Then $R_1=m^{-1}(L_1)$ is the largest possible rectangle rooted in $(L_1,L_1)$, i.e. a rectangle with $(L_1,L_1)$ as lower-right corner, possibly extending to infinity in the up and/or left direction. $R_2=m^{-1}(L_2)$ will then be the largest possible rectangle rooted on $(L_2,L_2)$ not overlapping with $R_1$. And so on for $R_3$ etc. This picture also shows that not all monotonic means can arise from your construct. Nov 19, 2017 at 16:07
• Even more: no continuous mean at all can arise from this construct. Nov 19, 2017 at 16:51
• See my comment to the OP for a very nice concrete example. Nov 20, 2017 at 14:28

Let us, indeed, describe "monotone, continuous, associative means" on $[0,1]^2$. I'll just write $a*b$ instead of $m(a,b)$ to make long expressions easier to comprehend. Let $c=0*1,d=1*0$. Then, for every $x\le c\le y$, we have $c\le c*y=(0*1)*y=0*(1*y)\le 0*y\le 0*1=c$ and, thereby, $c=0*y\le x*y\le c*y=c$, i.e., $x\le c\le y$ implies $x*y=c$. Let now $a$ be any number with $q=0*a<a$. Repeating the same argument on $[0,a]$ instead of $[0,1]$, we see that for every $x\le q\le y$, we have $x*y=q$. Thus the function $y\mapsto 0*y$ is identically $q$ on $(q,a)$. If we have $a'>a$ such that $q'=0*a'>q$ at all, then, by continuity we can find such $a'$ with $q'<a$. But then $0*y$ should be simultaneously $q$ and $q'$ on $(q',a)$, which is impossible. Thus, if $q=0*a<a$, then $q=0*a'$ for all $a'\ge a$, i.e., $y\mapsto 0*y=y$ up to a certain point $y_0$ and then constant $y_0$, i.e., $0*y=\min(y,y_0)$. But then this constant must be $0*1=c$. Similarly we can conclude that $x*1=\max(x,c)$. Thus, if $x\le y$, then $$x\le x*y\le x*1=\max(x,c), \min(y,c)= 0*y\le x*y\le y$$ But for $x\le y$ on one side of $c$ one of these double inequalities is a tight squeeze, so if $x\le y\le c$, then $x*y=y$, if $c\le x\le y$, then $x*y=x$, and we have already seen that if $x\le c\le y$, then $x*y=c$. Thus we have the full description of $x*y$ for $x\le y$. The case $x\ge y$ is treated in the same way using $d$.

• Could you please spell out the conclusion? For brakes like me it is VERY difficult to find out what it is. Nov 19, 2017 at 6:35
• The conclusion is: If $m$ is monotone, associative, continuous and symmetric on the closed unit interval, then $m$ is already determined by the value $c:=m(0,1)$. Namely, as suggested by Yaakov Baruch, $m$ is the $\max$ function when both arguments are below $c$, $\min$ when both are above $c$, and constantly $c$ when one argument is below $c$ and one above. -- When $m$ is not symmetric, there is a similar description using the two parameters $c:=m(0,1)$ and $d:=m(1,0)$. Nov 19, 2017 at 10:16