Random Permutations

Since the current year commonly features in math competition problems, it seems useful to begin the year by noting that ${2023 = 7 \cdot 17^2}$ .

The past couple years around this time I have set myself the further puzzle of working out the groups of that order. Usually it is not difficult, but occasionally it will be essentially impossible (e.g., in ${2048}$ ).

This year is not very interesting actually, group-theoretically. This is an abelian year in the sense that all groups of order ${2023}$ are abelian, and the only possibilities are ${C_{2023}}$ and ${C_7 \times C_{17} \times C_{17}}$ . This is an easy consequence of Sylow’s theorem. Let ${G}$ be a group of order ${2023}$ . The number of Sylow ${7}$ -subgroups must divide ${17^2}$ and be ${\equiv 1 \pmod 7}$ , so it must be ${1}$ , and similarly the number of Sylow ${17}$ -subgroups must also be ${1}$ , so ${G \cong C_7 \times H}$ where ${H}$ has order ${17^2}$ . A group of order ${p^2}$ must be abelian (standard exercise), so ${H \cong C_{289}}$ or ${C_{17} \times C_{17}}$ .

To make it more challenging, can we actually characterize the positive integers ${n}$ such that all groups of order ${n}$ are abelian? Call such an integer abelian.

Proposition 1 Let ${n}$ be a positive integer. Then ${n}$ is abelian if and only if
(1) ${n}$ is cube-free,
(2) if ${p, q}$ are distinct primes such that ${pq \mid n}$ then ${p}$ does not divide ${q-1}$ ,
(3) if ${p, q}$ are distinct primes such that ${pq^2 \mid n}$ then ${p}$ does not divide ${q+1}$ .

Let us first show that the conditions are necessary. Suppose (1) fails. Then ${p^3 \mid n}$ for some prime ${p}$ . There is a nonabelian group ${H}$ of order ${p^3}$ (see extraspecial groups), so ${H \times C_{n / p^3}}$ is a nonabelian group of order ${n}$ . Similarly if (2) fails then there is a nonabelian semidirect product ${C_q : C_p}$ , so we can again form a nonabelian group of order ${n}$ . Finally if (3) fails then note that ${\mathrm{Aut}(C_q^2) \cong \mathrm{GL}_2(q)}$ , and ${\mathrm{GL}_2(q)}$ contains an element of order ${q^2 - 1}$ (since the finite field of order ${q^2}$ has a primitive root), so we have another nonabelian semidirect product ${(C_q \times C_q) : C_p}$ .

Now we show that the conditions are sufficient. We use induction on ${n}$ . Let ${G}$ be a group of order ${n}$ , where ${n}$ satisfies conditions (1), (2), and (3). Assume first ${G}$ is not simple. Let ${N}$ be a maximal normal subgroup of ${G}$ . Then ${|N|}$ and ${|G/N|}$ are both integers smaller than ${n}$ satisfying (1), (2), and (3), so ${N}$ and ${G/N}$ are abelian by induction. Since all subgroups of ${G/N}$ are normal and ${N}$ was chosen to be maximal normal, ${G/N}$ must be cyclic of prime order, say ${p}$ . Let ${P \le G}$ be a Sylow ${p}$ -subgroup and let ${H \le N}$ be the product of the Sylow ${q}$ -subgroups for ${q \ne p}$ . Then it follows that ${G}$ is the semidirect product ${G = H : P}$ .

Next consider the conjugation action of ${P}$ on ${H}$ . Let ${Q \le H}$ be a Sylow ${q}$ -subgroup. Then ${Q}$ is isomorphic to one of ${C_q, C_{q^2}, C_q \times C_q}$ , and ${\mathrm{Aut}(Q)}$ is respectively isomorphic to one of ${C_{q-1}, C_{q(q-1)}, \mathrm{GL}_2(q)}$ . Note that ${|\mathrm{GL}_2(q)| = q (q-1)^2(q+1)}$ . By the given conditions, none of these has order divisible by ${p}$ , so ${P}$ acts trivially on ${Q}$ . Hence ${P}$ acts trivially on ${H}$ and ${G = H \times P}$ is abelian, as claimed.

To finish we must rule out the possibility that ${G}$ is simple. This seems to require some nontrivial group theory. One lazy method is to note that condition (2) implies that ${n}$ is odd (or a power of ${2}$ ), so we are done by the Feit–Thompson theorem. An easier argument is to use Burnside’s transfer theorem, which states that if ${P}$ is a Sylow ${p}$ -subgroup and ${C_G(P) = N_G(P)}$ then ${G}$ has a normal subgroup of order ${|G:P|}$ (in particular ${G}$ is not simple). In our case, let ${p}$ be the smallest prime dividing ${n}$ and let ${P}$ be a Sylow ${p}$ -subgroup. Let ${C = C_G(P)}$ and ${N = N_G(P)}$ . Then ${N / C}$ is isomorphic to a subgroup of ${\mathrm{Aut}(P)}$ . As before ${\mathrm{Aut}(P)}$ is one of ${C_{p-1}}$ , ${C_{p(p-1)}}$ , or ${\mathrm{GL}_2(p)}$ . The orders of these groups have no prime factor larger than ${p+1}$ . Since ${p}$ is the smallest prime dividing ${n}$ and ${p > 2}$ , it follows that ${N / C}$ is trivial, so we are done.

It is also possible to characterize nilpotent numbers in general, and even solvable numbers. See Pakianathan, J., & Shankar, K. (2000). Nilpotent Numbers. The American Mathematical Monthly, 107(7), 631–634. https://doi.org/10.2307/2589118.

Tomorrow morning (9am GMT) I am giving a seminar in Novosibirsk (virtually of course). The abstract is below. If you are interested in attending let me know I will give you the Zoom link.

Title: Nonschurian primitive association schemes with many automorphisms

Abstract: This talk is about primitive coherent configurations $X$ of degree $n$ with more than $\exp(n^\epsilon)$ automorphisms, for constant $\epsilon > 0$ . Babai conjectured that all such are so-called Cameron schemes, the orbital configurations of large primitive groups $\mathrm{Sym}(m)^{(k)} \wr G$ for $G \le \mathrm{Sym}(d)$ . We will describe several families of examples that show Babai’s conjecture is actually wrong, strictly interpretted. In particular there is a primitive association scheme $X$ of degree $n = m^8$ for any $m \ge 3$ such that $\mathrm{Aut}(X)$ is imprimitive and $|\mathrm{Aut}(X)| > \exp(m)$ . But a slightly revised form of Babai’s conjecture is still plausible.