# Order-increasing bijection from arbitrary groups to cyclic groups

In his answer to this previous MO question, Gjergji Zaimi referred to the statement that for every finite group $G$ of order $n$, there is a bijection $\sigma \colon G \to \mathbb{Z}/n\mathbb{Z}$ satisfying $$o(\sigma(g))\geq o(g)$$ for all $g\in G$. However, as Marty Isaacs pointed out, the "proof" of this fact that appeared in the Amer. Math. Monthly is flawed (or at least incomplete).

Does anyone know of a valid proof (or counterexample) of this fact?

The "proof" in loc. cit. goes as follows: Let $G_k = \{\,g \in G: g^k = 1\,\}$. For $d \mid n$, we inductively define a set $S_d$ consisting of $\phi(d)$ elements in $G_d$, where $\phi$ is Euler's totient function. These sets will be pairwise disjoint; since $\sum_{d \mid n} \phi(d) = n$, they thus partition $G$.

Let $S_1 = \{1\}$. Suppose that $k$ divides $n$ and that $S_d$ has been constructed for all $d < k$. By a theorem of Frobenius (see M. Hall, The Theory of Groups, Macmillan, 1959, p. 137), $|G_k|$ is a multiple of $k$. Also $G_k$ contains $S_d$ for each $d$ dividing $k$. Since $|G_k| > k$ and $\sum_{d \mid k} \phi(d) = k$, there remain at least $\phi(k)$ other elements in $G_k$, and we take $\phi(k)$ of them to form $S_k$.

The cyclic group $Z_n$ of order $n$ has exactly $\phi(d)$ elements of order $d$ for each $d$ that properly divides $n$. We construct a bijection $\sigma\colon G \to Z_n$ that maps $S_d$ into the elements of order $d$ in $Z_n$. Thus $o(\sigma(g)) > o(g)$ for all $g \in G$. $\quad\square$

The mistake in the proof is in the last sentence of the second paragraph, where the authors overlooked the fact that some of the sets $S_d$ where $d$ does not divide $k$ (but still $\gcd(d,k) \neq 1$) might have used some of the elements of $G_k$, leaving less than $\phi(k)$ elements left in $G_k$.

As F. Ladisch (I think, I hope I'm giving proper credit) pointed out in a comment to an earlier answer by G. Zaimi that was deleted, the proof is fundamentally incorrect, in the sense that only using the combinatorial data implied by Frobenius's Theorem cannot be sufficient to prove the result. For example, let $n=12$, and let

$$|G_1| = 1, |G_2| = 4, |G_3| = 3, |G_4| = 4, |G_6| = 6, |G_{12}| = 12.$$

(This would correspond to a non-existing group with $1$ element of order $1$, $3$ elements of order $2$, $2$ elements of order $3$, and $6$ elements of order $12$.)

Then the sets $G_k$ fulfill the requirements given by Frobenius's Theorem, but still there is no bijection to $Z_n$ satisfying the required statement.

Any ideas are welcome!

-
I deleted my "answer" and will think about this some more when I get some time. I hope this doesn't turn out to be another false belief :) –  Gjergji Zaimi Aug 11 '12 at 22:54
Shouldn't that be '6 elements of order 6'? –  HJRW Aug 23 '12 at 17:05
I think it was Ladisch who mentioned the Hall marriage theorem. In fact, using Hall's theorem, the problem is equivalent to the following: Given a set S of divisors of n = |G|, show that the total number of elements of G having order dividing some member of S is at least as large as for a cyclic group of order n. For example, if S = {a}, then for a cyclic group with order divisible by a the count is a, and by Frobenius' theorem, the count for G is a multiple of a. The inequality thus holds if |S| = 1. I have now found a proof in the case |S| = 2, but I don't (yet) see a general argument. –  Marty Isaacs Aug 23 '12 at 22:09
For any finite group $G$, let $f(G)$ denote the average order of an element of $G$. If the fact you've stated is true, then for any group $G$ with $n$ elements, we'd have $f(G) \leq f(\mathbb{Z}/n\mathbb{Z})$. This alone should have been enough of a tip-off that the short solution linked to in AMM 10775 was incomplete: the above conclusion about $f$ does indeed hold, but it's AMM 6636(ii), and took a fair bit of work to prove. Source: 6636, F. Schmidt, Amer. Math. Monthly, Vol. 98, No. 10 (Dec., 1991), pp. 970-972, jstor.org/stable/2324168. –  Benjamin Dickman Aug 25 '12 at 8:54
I had not known about Lindsey's theorem that among groups of order n, the cyclic group has the largest possible average (equivalently sum) of element orders. This appeared (as mentioned by Dickman) as a solution to a Monthly problem in Dec. 1991. Independently, and very much later, I found a different proof of this result. (See my paper with Amiri and Amiri in Comm. in Alg. 37 (2009).) Of course, if the Lemma that is the subject of this posting is true, it provides a third proof. It would also prove the corresponding result about the geometric mean. (I have an unpublished proof of that.) –  Marty Isaacs Aug 28 '12 at 20:29

This is only a partial answer:

The assertion is true for solvable groups. In fact, when $N$ is a normal elementary abelian $p$-subgroup of $G$ and $\sigma\colon G/N \to C_{|G/N|}$ an "order multiplying bijection" (that is, $o(\bar{g})$ divides $o(\sigma(\bar{g}))$ for all $\bar{g}\in G/N$), then one can lift $\sigma$ to an order multiplying bijection $\hat{\sigma}\colon G\to C_{|G|}$. This means that for every $g\in G$ we find an order multiplying bijection between cosets $gN \to cC_{|N|}$, where $\bar{c}= \sigma(\bar{g})$ (I use overbars to denote the canonical epi's $G\to G/N$ and $C_{|G|}\to C_{|G/N|}$). To see this, first an easy observation:

$(*)\qquad$ For any $g\in G$, the order $o(g)$ divides $po(\bar{g})$.

Indeed, $\langle g \rangle \cap N$ is cyclic, so has order $p$ or $1$.
It follows that the orders of elements in the coset $gN$ are $o(\bar{g})$ or $po(\bar{g})$.

For $c\in C_{|G|}$, the situation is this: if $p$ does not divide $o(\bar{c})$, then in $cC_{|N|}$ the orders $o(\bar{c})p^k$ occur, where $p^k$ divides $|N|$, and $o(\bar{c})$ occurs exactly once. If $p$ divides $o(\bar{c})$, then all elements in $cC_{|N|}$ have order $o(\bar{c}) |N|$.

It follows from these observations that whenever $o(\bar{g}) \mid o(\bar{c})$, we find an order multiplying bijection $gN \to c C_{|N|}$. When $p \mid o(\bar{c})$, in fact any bijection does, and if $p$ does not divide $o(\bar{c})$, then $p$ does not divide $o(\bar{g})$, and there is at least one pre-image $g$ of $\bar{g}$ such that $p$ does not divide $o(g)$ (Schur-Zassenhaus or more elementary). We map such a $g$ to the unique element in $cC_{|N|}$ having order $o(\bar{c})$, and then map the rest of $gN$ onto the rest of $cC_{|N|}$.

### Remarks

1. It follows that a minimal counterexample to the assertion of the question has trivial Fitting subgroup. One could try to reduce to simple groups, but I don't see how, since we don't have something like $(*)$ for arbitrary normal subgroups.
2. Write $H\preceq G$ if there is an order multiplying bijection from $H$ to $G$. This defines a prae-order on the class of finite groups of fixed order, and we want to show that $G\preceq C_{|G|}$ for all $G$. Now at least examples of small size suggest that nonsolvable groups are minimal or close to minimal with respect to this prae-order. For example, $S_5$ and $A_5\times C_2$ are minimal with respect to $\preceq$ among groups of order 120, and $SL(2,5)$ covers both with respect to $\preceq$. Moreover, there are quite a few groups 'between' these groups and $C_{120}$. This supports the intuition that there are "more degrees of freedom" in choosing an order multiplying bijection when the group is non-solvable, since such groups have in general few elements of (arithmetically) large order and many of small order.
-