Means

Means and tallies

Averaging numbers and even locations is a familiar task. For example, the arithmetic mean of $m$ values is computed by this standard formula: $$\text{ the mean of } x_1,...,x_m :=\tfrac{1}{m}(x_1+...+x_m).$$

Since the arithmetic mean is not always appropriate for angles, the following method can be used to obtain both a mean value and measure for the variance of the angles:

• convert all angles to corresponding points on the unit circle;
• compute the mean of these points in ${\bf R}^2$;
• the resulting point will lie within the unit disk;
• convert that point back to the circle.

The angle is the mean of the input angles. The result may be $0$, which suggests that it is impossible to define a continuous mean on the circle.

Thus, the formula might not work in a more complex setting. If these are just elements of a group, the group may have no division. If these are points in a subset of a vector space, the set may be non-convex.

Generalized means were started in a paper by Kolmogorov in 1930 and continued by various authors. The axiomatic approach comes from the thesis of G.Aumann (1933, under Caratheodory). In his paper (1935) he formulated the following conditions, limited mainly for subsets of number spaces.

Definition. For a set $X$ and integer $m>1$, a function $f:X^m\to X$ is called a mean of degree $m$ on $X$ if $$f(s(u))=f(u),\ \forall u\in X^m,\ \forall s\in \mathcal{S}_m;$$ and $$f(x,x, ...,x)=x,\ \forall x \in X.$$

For $X$ a group, a mean is algebraic if it is a homomorphism. For $X$ a topological space, a mean is topological if it is a continuous map.

The following is given by Eckmann in his 2003 lecture.

Mean Theorem. There is an algebraic mean of degree $m$ on a group $G$ if and only if $G$ allows division by $m$. In that case, $G$ is Abelian, the mean is unique, and is given by the standard formula above.

Let $d:G\to G^m$ be the diagonal function: $$d(x):=(x, ...,x).$$ Then the theorem states that we can't complete this diagram with a homomorphism that is also symmetric: $$ \newcommand{\ra}[1]{\!\!\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{cccccccccccc} & G \ & \ra{d} & G^m \\ & _{\operatorname{Id}} & \searrow &\quad \da{g=?} \\ & & & G \end{array} $$

We will generalize this theorem. This generalization, however slight, is necessary to prove some of our impossibility results about voting.

What happens to the theorem if we weaken the diagonality condition?

We will use the multiplicative notation.

The Tally Theorem

Theorem. Suppose $G$ is a set with two binary operations:

• first, $\cdot :G^2\to G$ is associative with an identity element $e$; i.e., $(G,\cdot)$ is a monoid:

$$e\cdot x= x \cdot e =x, \ \forall x\in G.$$ (we will also write $x\cdot y=xy,\ x\cdot x=x^2,$ etc.);

• second, $+:G^2\to G$ is commutative:

$$x+y=y+x, \ \forall x\in G.$$ We assume that the two are compatible:

• Homomorphy: For all $x,y,a,b\in G$, we have

$$(x+a) \cdot (y+b) = (x \cdot y)+(a \cdot b),\ \forall x,y,a,b\in G.$$

• Diagonality: There is such a positive integer $q$ that for all $x\in G$ we have

$$x+x=x^q.$$ Then

• (1) $(G,\cdot)$ allows $q/2$ power; and
• (2) the operations satisfy the formula:

$$(x+y)^2=\big( x\cdot y \big)^{q}.$$

Homomorphy says that either operation is a homomorphism with respect to the other.

Lemma 1. Function $g:G\to G$ given by $$g(x):=x+e=e+x$$ is a well-defined homomorphism on $(G,\cdot)$ and it satisfies $$g(x)^2 =x^q.$$

Proof. First, we have $$x+e=e+x$$ by commutativity of $(G,+)$. Next, consider: $$\begin{array}{llllll} g(x)\cdot g(y)&=(x+e)\cdot (y+e) & \text{ ...by definition of } g\\ &=(xy)+(ee) & \text{ ...by Homomorphy }\\ &=x\cdot y+e & \\ &=g(x\cdot y) & \text{ ...by definition of } g. \end{array}$$ Similarly, $$\begin{array}{llllll} g(x)^2&=g(x)\cdot g(x)\\ &=(x+e)\cdot (e+x) & \text{ ...by definition of } g\\ &=(xe)+(ex) & \text{ ...by Homomorphy }\\ &=x+x & \\ &=x^q & \text{ ...by Diagonality. }\ \blacksquare \end{array}$$

Lemma 2. The following values commute in $(G,\cdot)$: $$\begin{array}{lll} (x+e) \cdot (e+y) =(e+y) \cdot (x+e) . \end{array}$$

Proof. By Homomorphy, the sides are equal to $x+y$ and $y+x$ respectively. Then, the conclusion follows from commutativity of $(G,+)$. $\blacksquare$

Proof of the theorem. Let $a$ be any element of $G$; then let $b:=g(a)\in G$. Then, we have: $$\begin{array}{llllll} a^q&=a+a& \text{ ...by Diagonality }\\ &=(ae)+(ea) & \\ &=(a+e)(e+a) & \text{ ...by Homomorphy}\\ &=g(a)\cdot g(a) & \text{ ...by definition of } g\\ &=b^2. \end{array}$$

Next, we compute: $$\begin{array}{llllllll} &\big( x\cdot y \big)^q&=& (x\cdot y) +(x\cdot y)& \text{ ...by Diagonality }\\ &&=&\big( (xe)\cdot (ey) \big) + \big((ex)\cdot (ye) \big) & \\ &&=&\big( (xe)+(ex) \big) \cdot \big( (ey) + (ye) \big) & \text{ ...by Homomorphy}\\ &&=&\big((x+e)\cdot (e+x)\big) \cdot \big((e+y)\cdot (y+e)\big) & \text{ ...by Homomorphy}\\ &&=&\big((x+e)\cdot (x+e)\big) \cdot \big((e+y)\cdot (e+y) \big)& \text{ ...by commutativity of } (G,+)\\ &&=&(x+e)\cdot \big( (x+e)\cdot (e+y)\big) \cdot (e+y)& \text{ ...by associativity of } (G,\cdot)\\ &&=&(x+e)\cdot (e+y)\cdot (x+e)\cdot (e+y)& \text{ ...by Lemma 2}\\ &&=&((xe)+(ey))\cdot ((xe)+(ey))& \text{ ...by Homomorphy}\\ &&=&(x+y)\cdot (x+y)& \\ \hspace{.19in}&&=&(x+y)^2.&\hspace{.19in}\blacksquare \end{array}$$

Definition. A tally space $(G,+)$ is a commutative semigroup, i.e., a set with an associative and commutative binary operation $+ :G^2\to G$. The tally of degree $m$ is the function $$f:G^m\to G,\ m=1,2,...$$ defined by $$f(x_1,...,x_m):=x_1+...+x_m.$$

Proposition. (1) If $(G,+)$ has division, there is a mean of degree $m$ given by $$M(x_1,...,x_m):=\frac{1}{m}(x_1+...+x_m).$$ (2) If $(G,\cdot)$ has a mean $M$, then it is a tally space with: $$x\cdot y=2M(x,y).$$

Corollary (Tally Theorem). Under the conditions of the theorem,

• (1) when $q=1$, $(G,\cdot)$ is a tally space with the mean of degree $2$ well-defined: $M(x,y)=(x\cdot y)^{1/2}$;
• (2) when $q=2$, if $(G,\cdot)$ is an Abelian group with no elements of order $2$, then $(G,\cdot)=(G,+)$ is a tally space.

Proof. (1) We just need to prove commutativity for $(G,\cdot)$. First, we have: $$\begin{array}{lll} g(x)\cdot g(y)&=(x+e)\cdot (e+y)& \text{ ...by definition of } g\\ &=(y+e)\cdot (e+x)& \text{ ...by commutativity of } (G,+) \text{ and Lemma 2}\\ &=g(y)\cdot g(x)& \text{ ...by definition of } g. \end{array}$$ Furthermore, by definition of $g$ and Lemma 1 we have: $$x\cdot y=g(x \cdot y)^2=(g(x)\cdot g(y))^2=(g(y)\cdot g(x))^2=g(y \cdot x)^2=y\cdot x.$$ (2) We compute using the formula from the theorem: $$\begin{array}{lll} e&=(x+y)^2\cdot (x\cdot y)^{-2}\\ &=\big( (x+y)\cdot (x\cdot y)^{-1} \big)^2\\ \end{array}$$ It follows that $(x+y)\cdot (x\cdot y)^{-1} =e$. Therefore, the two operations are the same. $\blacksquare$

Since every Abelian group is a tally space, part (2) of the theorem may be seen as a necessary condition of uniqueness of tally.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Appendix: tally as a function

Below, $G$ is a monoid with the identity element $e$.

Definition. We say that a homomorphism $f:G^m\to G$ is a tally if it is symmetric:

• for any permutation $s$ and any $x\in G$ we have:

$$f(s(x_1,...,x_m))=f(x_1,...,x_m).$$ and diagonal:

• there is such a positive integer $q$ that for all $x\in G$ we have:

$$f(x,...,x)=x^q.$$

Tally Theorem. If $f:G^m\to G$ is a tally, then $G$ allows $q/m$ power and $f$ is given by the formula: $$f(x_1,...,x_m)=\big( x_1\cdot ...\cdot x_m \big)^{q/m}.$$

It is written in multiplicative notation...

Lemma 1. If $f:G^m\to G$ is a tally, then $g:G\to G$ given by $$g(x):=f(x,e,...,e,e)=f(e,x,...,e,e)=... =f(e,e,...,e,x)$$ is a well-defined homomorphism that satisfies $$g(x)^m =x^q.$$

Proof. First, we have $$f(x,e,...,e,e)=f(e,x,...,e,e)=... =f(e,e,...,e,x)$$ by symmetry. Next, consider: $$\begin{array}{llllll} g(x)^m&=g(x)\cdot ... \cdot g(x)\\ &=f(x,e, ...,e,e)\cdot ... \cdot f(e,e, ...,e,x)\\ &=f(x,x, ...,x,x)\\ &=x^q& \text{ ...by diagonality.}\ \blacksquare \end{array}$$

Lemma 2. If $f:G^m\to G$ is a tally, then these values of $f$ commute: $$\begin{array}{lll} f(e,...,x_i,...,e,...,e) \cdot f(e,...,e,...,x_j,...,e)\\ \qquad\qquad\qquad =f(e,...,e,...,x_j,...,e) \cdot f(e,...,x_i,...,e,...,e). \end{array}$$

Proof. Both sides are equal to $f(e,...,x_i,...,x_j,...,e)$. $\blacksquare$

Proposition. If $G$ allows an algebraic mean ($q=1$) then $G$ is commutative.

Proof. We have, by definition of $g$, $$g(x)\cdot g(y)=f(x,e,e,...,e)\cdot f(e,y,e,...,e)=f(x,y,e,...,e)=g(y)\cdot g(x).$$ Furthermore, by Lemma 1 we have: $$x\cdot y=g(x \cdot y)^m=(g(x)\cdot g(y))^m=(g(y)\cdot g(x))^m=g(y \cdot x)^m=y\cdot x.\ \blacksquare$$

Proof of the Tally Theorem. Let $a$ be any element of $G$; then let $b:=g(a)\in G$. We compute: $$\begin{array}{llllll} a^q&=f(a,a, ...,a,a)& \text{ ...by diagonality }\\ &=f((a,e, ...,e,e)\cdot (e,a, ...,e,e)\cdot...\cdot(e,e, ...,e,a)) & \text{ ...by }a\cdot e=e\cdot a=a\\ &=g(a)\cdot g(a)\cdot...\cdot g(a)\\ &=b^m. \end{array}$$

Next, the uniqueness. We compute: $$\begin{array}{llllllll} &\big( x_1\cdot ...\cdot x_m \big)^q&=&f(x_1\cdot ...\cdot x_m, ...,x_1\cdot... \cdot x_m)& \text{ ...by diagonality }\\ &&=&f\big( (x_1,e, ...,e,e)\cdot ...\cdot (e,e, ...,e,x_1) \cdot\\ &&&...\\ &&&\cdot (x_m,e, ...,e,e)\cdot ...\cdot (e,e, ...,e,x_m) \big)& \text{ ...by }a\cdot e=e\cdot a=a\\ &&=&f(x_1,e, ...,e,e)\cdot ...\cdot f(e,e, ...,e,x_1) \cdot\\ &&&...\\ &&&\cdot f(x_m,e, ...,e,e)\cdot ...\cdot f(e,e, ...,e,x_m) & \text{ ...by additivity}\\ &&=&f(x_1,e, ...,e,e)\cdot ...\cdot f(x_1,e, ...,e,e)\\ &&&...\\ &&&\cdot f(e,e, ...,e,x_m)\cdot ...\cdot f(e,e, ...,e,x_m)& \text{ ...by symmetry}\\ &&=&f(x_1,e, ...,e,e)\cdot ...\cdot f(e,e, ...,e,x_m)\\ &&&...\\ &&&\cdot f(x_1,e, ...,e,e)\cdot ...\cdot f(e,e, ...,e,x_m)& \text{ ...by Lemma 2}\\ &&=&f(x_1, ...,x_m)\cdot \\ &&&...\\ &&&\cdot f(x_1, ...,x_m)& \text{ ...by additivity}\\ \hspace{.19in}&&=&f(x_1, ...,x_m)^m.&\hspace{.19in}\blacksquare \end{array}$$