9
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gro-Tsen
    Nov 13, 2017 at 21:59
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 13, 2017 at 22:00
  • 4
    $\begingroup$ ? first one in the list? $m(a,b) = a$. Not commutative, but is continuous and monotone. $\endgroup$ Nov 13, 2017 at 22:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – YCor
    Nov 14, 2017 at 19:20
  • 1
    $\begingroup$ 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$). $\endgroup$ Nov 20, 2017 at 16:49

3 Answers 3

12
$\begingroup$

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

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Nov 14, 2017 at 19:58
12
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 19, 2017 at 16:07
  • $\begingroup$ Even more: no continuous mean at all can arise from this construct. $\endgroup$ Nov 19, 2017 at 16:51
  • $\begingroup$ See my comment to the OP for a very nice concrete example. $\endgroup$ Nov 20, 2017 at 14:28
3
$\begingroup$

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$.

$\endgroup$
2
  • 4
    $\begingroup$ Could you please spell out the conclusion? For brakes like me it is VERY difficult to find out what it is. $\endgroup$ Nov 19, 2017 at 6:35
  • 3
    $\begingroup$ 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)$. $\endgroup$
    – Goldstern
    Nov 19, 2017 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.