Order-increasing bijection from arbitrary groups to cyclic groups

2012-08-07T09:03:25Z

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 : 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?

Added: Since this question has been without answer for about 2 weeks now, I'm adding some more details that might help (perhaps not everyone has access to the paper in Amer. Math. Monthly.)

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: 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!

Answer by F. Ladisch for Order-increasing bijection from arbitrary groups to cyclic groups

2012-09-17T15:34:37Z

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

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

Order-increasing bijection from arbitrary groups to cyclic groups - MathOverflow

Order-increasing bijection from arbitrary groups to cyclic groups

Answer by F. Ladisch for Order-increasing bijection from arbitrary groups to cyclic groups

Remarks