14
$\begingroup$

Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties:

  1. $M(a,a)=a\qquad$ (identity)

  2. $M(a,b)=M(b,a)\qquad$ (commutativity).

and possibly

  1. $M(M(a,b),M(a,c))=M(a,M(b,c))\qquad$ (weak associativity)

  2. $M(M(a,b),M(c,d))=M(M(a,c),M(b,d))\qquad$ (strong associativity)

  3. $a\ne b \implies a\ne M(a,b)\ne b\qquad$ (sharpness).

When $S$ is an abelian groupoid or an ordered set or a topological space, $M$ can have additional specific requirements, such as:

  1. $M(ac,bc)=cM(a,b)\qquad$ (homogeneousness - see UPDATE)

  2. $a < b \implies a\le M(a,b) \le b\qquad$ (order preservation - see UPDATE)

  3. continuity.

This counteraxample is wrong. After fixing my gawk code I found that there (3) always implies (4) in a set of 5. Thanks to Eric Wofsey for noticing.

In general (3) does not imply (4) as can be seen in this example for $S=\{a,b,c,d,e\}$:

$$ \begin{array}{c|ccccc} M & a & b & c & d & e\\ \hline a & a & a & a & a & a\\ b & a & b & d & c & a\\ c & a & d & c & b & a\\ d & a & c & b & d & e\\ e & a & a & a & e & e\\ \end{array}$$

where $M(M(b,c),M(d,e)) \ne M(M(b,d),M(c,e))$.

Here are some of the questions that come to mind.

Q1. Is there a finite example where (3) and (5) hold, but not (4)? I know that $S$ will need to have at least 6 elements.

Q2. Does $M$ in the above example naturally extend to a mean in $\mathbb{R}[a,b,c,d,e]$ where both (3) and (6) hold?

Another example: if $A$ and $G$ are the arithmetic and geometric means on $\mathbb{R}^+$, it's easy to check that the mean function $M(x,y)=G(A(x,y),G(x,y))$ satisfies all the properties except (3) and (4).

Q3. Assuming all of the above properties except (4) hold for $M$ on $\mathbb{R}^+$, does (4) follow?

Q4. My starting point leading to this post: if all the above properties, including (4), hold for $M$ on $\mathbb{R}^+$, does it follow that $M$ is equivalent to the arithmetic mean, in the sense that $M(x,y)=f^{-1}\big(\frac{f(x)+f(y)}{2}\big)$ for some continous strictly monotonic function $f: \mathbb{R}^+ \to \mathbb{R}$?

I welcome suggestions for improvements to this post and references to relevant work.

UPDATE. It turns out that neither (6) nor (7) are needed anywhere, at least for the questions explored in this thread.

This is superseded by Eric Wofsey's answer

UPDATE. If $M(x,y):=f^{-1}\big(\frac{f(x)+f(y)}{2}\big)$ then notice that we can translate and rescale $f$ and the equality still holds. Now we try to build $f$. To start, we are allowed to assume $f(1/2)=1/2$ and $f(2)=2$. The graph of $f$ can then be constructed in the following way, as per Eric Wofsey's comment below: for each 2 consecutive known points $(x_1, y_1=f(x_1))$ and $(x_2, y_2=f(x_2))$ build an intermediate point $\big(M_f(x_1,x_2), \frac{y_1+y_2}{2}\big)$. By density of the dyadics in $\mathbb{R}$ and properties (5), (7) and (8) of $M$, this procedure defines $f$ in the interval $I=[1/2,2]$. Associativity (hopefully in its weak form) should then be used to prove that the same procedure applied to 2 overlapping subintervals of $I$ yields identical results on the intersection. Finally, if that worked, conclude the proof by defining a second $f$ on $[1/4,4]$. This second $f$ can be translated and rescaled to satisfy $f(1/2)=1/2, f(2)=2$ and must then match the original $f$ in $[1/2,2]$. Repeating this step will extend $f$ to $\mathbb{R}^+$.

$\endgroup$
  • 1
    $\begingroup$ Isn't Q4 pretty much immediate by starting with two arbitrary points and iterating $M$ on them and then comparing that with the dyadic rationals? $\endgroup$ – Eric Wofsey Dec 23 '14 at 3:57
  • 1
    $\begingroup$ When condition 5 holds then one may say that $\ M\ $ is sharp. $\endgroup$ – Włodzimierz Holsztyński Dec 23 '14 at 7:16
  • 2
    $\begingroup$ I considered conditions 1.2.4. together with the cancellation law in 1961/2, to prove that such algebras can be embedded in the modules over the binary rational ring. Of course abelian groups such that the order of every element is odd provide examples. Soon after, Siemion Fatlowicz answered my question about 1.2.3 not implying condition 4. by providing a beautiful finite example where the operation $\ M\ $ was a byproduct of a non-commutative group operation. The group itself has provided the space of points. $\endgroup$ – Włodzimierz Holsztyński Dec 24 '14 at 3:06
  • 1
    $\begingroup$ @YaakovBaruch -- the cancellation law: $\ M(x\ y) = M(x\ z)\Rightarrow y=z.\ $ Also, should I use term "degree" rather than "order"? Anyway, using commutative group + language, the order/degree of $\ x\ $ is the smallest positive integer $\ d\ $ such that $\ d\cdot x=0.\ $ When all elements of the group are odd in this sense then we may define $ W(x\ y) := \frac{d+1}2\cdot (x+y),\ $ where $\ d\ $ is the order/degree of $\ x+y.\ $ Of course $\ \frac {d+1}2\ $ is so to speak $\ \frac 12\ $ with respect to $\ x+y$. $\endgroup$ – Włodzimierz Holsztyński Dec 24 '14 at 8:58
  • 2
    $\begingroup$ I should mention that what is called here strong associativity is known as the medial identity or the entropic identity and algebras which satisfy this identity are called modes. Furthermore, algebras which satisfy the "weak associativity" condition are commonly called self-distributive algebras, LD-systems, shelves and other names. See this question mathoverflow.net/questions/154550/… for information on algebras satisfying $(ab)(cd)=(ac)(bd)$. $\endgroup$ – Joseph Van Name Dec 24 '14 at 15:53
11
$\begingroup$

Define a mean algebra to be a set $S$ with an binary operation $M$ satisfying (1), (2), and (4). We can define $M(a,b,c,d)=M(M(a,b),M(c,d))$ and this will depend only on the multiset $\{a,b,c,d\}$. More generally, we can think of $M$ as an operation defined on multisets of size $2^n$ for any $n>0$ (and this is well-defined by an easy induction on $n$ using (2) and (4)). The free mean algebra on two generators can be identified with the dyadic rationals between $0$ and $1$ with the arithmetic mean (the generators being $0$ and $1$); freeness of this algebra is easy to see when you write $k/2^n$ as $M(0,0,\dots,0,1,1,\dots,1)$ (with $k$ $0$s and $2^n-k$ $1$s). Denote this algebra by $Q$. Write $I$ for the algebra $[0,1]$ with the arithmetic mean; this can be thought of as a sort of completion of $Q$.

Suppose $A$ is a mean algebra with underlying set $[0,1]$ that further satisfies (5), (7), and (8). There is a unique mean-preserving map $f_0:Q\to A$ satisfying $f_0(0)=0$ and $f_0(1)=1$, and it follows easily from (5) and (7) that it is injective and order-preserving. The inverse of $f_0$ extends uniquely to an order-preserving surjection $g:A\to I$ (every element of $A$ defines a Dedekind cut in $Q$ via $f_0$). By (7) and (8) $g$ will also be mean-preserving, and so (5) implies $g$ is injective. We thus conclude that $A$ is isomorphic to $I$ as an ordered mean algebra, and furthermore this isomorphism is unique.

Now suppose $A$ is a mean algebra with underlying set $\mathbb{R}$ satisfying (5), (7), and (8). Every compact subinterval of $A$ these has a unique order-preserving isomorphism to $I$, and by uniqueness we can glue these isomorphisms together to get an order-preserving isomorphism between $A$ and an open subinterval of $\mathbb{R}$ with the arithmetic mean. Note that there are actually 4 distinct isomorphism classes of such structures (with respect to both the order and the mean): $(-\infty,\infty)$, $(-\infty, 0)$, $(0,\infty)$, and $(0,1)$. In particular, this gives an affirmative answer to Q4 (without assuming (6)). Furthermore, the isomorphism in question is clearly unique up to composition with affine maps $\mathbb{R}\to\mathbb{R}$.

As for your desire to only assume (3) and not (4), the only place where I used (4) is in asserting that $Q$ is free. Let $F$ be the free algebra on $\{0,1\}$ assuming (3) instead of (4); we wish to prove that the canonical map $F\to Q$ is an isomorphism. Every element of $F$ can be represented as a full binary tree of some height $n$ where each of the $2^n$ leaves is labelled by $0$ or $1$, and at each juncture of the tree we apply $M$. It suffices to show that if two such trees have the same number of leaves that are 1, then they represent equal elements of $F$. We prove this by induction on $n$; the cases $n\leq 1$ are trivial.

Let $x\in F$ be represented by such a tree of height $n>1$ that has $i$ leaves that are $1$. WLOG $i\leq 2^{n-1}$ (otherwise we can just swap the roles of $0$ and $1$). Let $y$ be represented by a tree that looks the same as $x$'s, except that all the $0$s are on the left and all the $1$s are on the right. For instance, if $n=i=3$ and $$x=M(M(M(1,0),M(0,1)),M(M(0,1),M(0,0))),$$ then $$y=M(M(M(0,0),M(0,0)),M(M(0,1),M(1,1))).$$ It suffices to prove that $x=y$, since $y$ depends only on $n$ and $i$. Furthermore, by induction, it suffices to prove that $y=M(z,w)$ where $z$ and $w$ each have as many $1$s as the left and right halves of $x$, respectively (since $z$ and $w$ can then be transformed to look the same as the two halves of $x$). Let $j$ be the number of $1$s in the left half of $x$; WLOG $j\leq 2^{n-2}$ (if not, switch the two halves of $x$). By the induction hypothesis, we can write the right half of $y$ as $M(b,c)$, where $b$ has $j$ $1s$. Also, the left half of $y$ is $M(a,a)$, where $a$ is the tree of height $n-2$ consisting entirely of $0$s. We thus have $y=M(a,M(b,c))$, and so by (3) we can rewrite it as $y=M(M(a,b),M(a,c))$. Setting $z=M(a,b)$ and $w=M(a,c)$, the proof is complete.

As a final remark, I'm not sure what happens when you additionally assume (6). Certainly most functions $f$ as in your Q4 will not give rise to a mean satisfying (6); the only ones I know of that do are $f(x)=x^p$ for $p\neq0$ and $f(x)=\log x$, up to composition with affine maps. Note that $f(x)=\log x$ (corresponding to the geometric mean) can be thought of as the $p=0$ case; indeed, the mean obtained from it is equal to the limit of the $x^p$ means as $p\to 0$, and these functions $f$ (including their compositions with affine maps) are exactly the solutions of the differential equation $(xf''/f')'=0$. Perhaps if you assume $f$ is sufficiently differentiable you could prove it must be of this form by differentiating the functional equation you get from associativity.

EDIT: Here's a proof that if (6) holds, then $f(x)$ must be of the form $ax^p+b$ or $a\log x+b$ and hence $M$ is either $((x^p+y^p)/2)^{1/p}$ or $\sqrt{xy}$. Suppose that (6) holds and $f:\mathbb{R}_+\to U\subseteq\mathbb{R}$ is an isomorphism from $M$ to the arithmetic mean on some open interval $U$. For $c>0$, consider the map $x\mapsto f(cf^{-1}(x))$. This is a mean-preserving automorphism of $U$, so it must be of the form $x\mapsto A(c)x+B(c)$ for some constants $A(c)$ and $B(c)$ depending on $c$. That is, we have $f(cx)=A(c)f(x)+B(c)$.

Write $r=A(e)$; then it is easy to show that if $c=e^q$ for $q\in\mathbb{Q}$, we have $A(c)=r^q$. By continuity, it follows that $A(c)=r^{\log c}=c^p$ for all $c$, where $p=\log r$. Suppose that $p=0$, so $f(cx)=f(x)+B(c)$. Then $B(cd)=B(c)+B(d)$ and it follows by continuity that $B(c)=a\log c$ for some $a$. Setting $b=f(1)$, we then get $f(c)=a\log c +b$, as desired.

Now suppose that $p\neq 0$. Let $s=B(e)$; then by induction we have $$B(e^n)=s\frac{r^{n+1}-1}{r-1}$$ for $n\in \mathbb{N}$. But by the same argument using $e^{1/m}$ instead of $e$ for some integer $m>0$, we must have $$B(e^n)=B(e^{1/m})\frac{r^{n+1}-1}{r^{1/m}-1}.$$ It follows that the first formula is also valid when $n=1/m$, and it is now easy to show that it is valid for all rational $n$. By continuity, it holds for all real $n$, and we can rewrite it to get $$B(c)=s\frac{e^pc^p-1}{r-1}=tc^p+b$$ for some constants $t$ and $b$. Thus we have $f(cx)=c^pf(x)+tc^p+b$, and setting $x=1$ and $a=f(1)+t$ we get $f(c)=ac^p+b$, as desired.

$\endgroup$
  • $\begingroup$ Awesome and eye-opening proof! In regards to weak associativity, I knew that (3) and (4) are equivalent in the free algebra on 2 generators (and I suspect they might be even in the free algebra on 3 generators!) What I hadn't realized until now was that (5), (7), (8) and the density of dyadics meant that one only needed equivalence in the free algebra on 2 generators! $\endgroup$ – Yaakov Baruch Dec 23 '14 at 12:51
  • $\begingroup$ I was lost in a small computational nightmare trying to prove equivalence with 4 generators (which then would imply equivalence with any number, since strong associativity is defined on a set of 4 variables) and that's why I eventually started looking for the finite counterexample shown in my original post. - Thank you $\endgroup$ – Yaakov Baruch Dec 23 '14 at 12:52
  • 1
    $\begingroup$ It's more complicated than that: you can go from aaabbccc to aaabbcccaaabbccc to (some work) to aaccacbbaaccacbb to aaccacbb and many other places in a similar way - just by using (1), (2) and (3). (1) is essential here. $\endgroup$ – Yaakov Baruch Dec 23 '14 at 13:41
  • 1
    $\begingroup$ Oh, I see, that makes it a lot trickier than I thought. Incidentally, I think (7) follows from (5) and (8), at least on a closed interval. For instance, if $a<b<M(a,b)$, then by continuity and (5) $M(a,c)>c$ for all $c>a$. But now we get a contradiction by taking the limit of iterating $c\mapsto M(a,c)$. $\endgroup$ – Eric Wofsey Dec 23 '14 at 13:49
  • 1
    $\begingroup$ Or actually, more simply: (7) automatically holds for the endpoints of the interval, and it holds for all other values of $a$ and $b$ by continuity and (5) (since $M(a,b)-a$ and $M(a,b)-b$ must have constant sign if we stay away from the diagonal). I guess this argument is slightly weaker than the one in my previous comment because it also requires (2). But assuming (2), it shows that (7) also follows from (5) and (8) in an open interval as long as you know that (7) holds for any single $a$ and $b$. $\endgroup$ – Eric Wofsey Dec 23 '14 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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