groups – Random Permutations

Happy new year!

Updates from me: As of September I have taken up a new position at the University of Warwick. We’ve bought new wellies and we are enjoying the Warwickshire countryside, which has been pretty frosty so far. Mathematically, I am mentoring a postdoc and a new PhD student. As of the new year I have also just become an editor for Discrete Analysis.

Time for some numerical facts about the number ${2025}$ , and there are some good ones this year! First of all, ${2025}$ is a square: it is ${45^2}$ . Nice year to be ${45}$ ! The last square year was ${1936}$ and the next is ${2116}$ , so unless you are almost ${90}$ or younger than about ${10}$ this will be the only square year in your lifetime. Not only that, but ${45}$ is a triangular number, which makes 2025 a squared triangular number, so as observed on reddit and elsewhere we have

$\displaystyle 2025 = (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)^2 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 7^3 + 8^3 + 9^3.$

An even more profound and important discovery was made by the Alex Bellos of the Guardian: in fact ${2025 = (20 + 25)^2}$ . I will leave it to you to reflect on whether that’s as interesting.

My own personal nerdy exercise of the new year the past few years is to find all groups of order ${n}$ in year ${n}$ , where this year ${n = 2025 = 3^4 5^2}$ . This year is a step up in difficulty due to the presence of the large power ${3^4}$ .

The first step is to find the possibilities for the Sylow subgroups ${P}$ and ${Q}$ of order ${3^4}$ and ${5^2}$ respectively. There are just two groups of order ${5^2}$ , namely ${C_5^2}$ and ${C_{25}}$ , but actually ${15}$ different groups of order ${3^4}$ : ${5}$ abelian, ${6}$ of class ${2}$ , and ${4}$ of class ${3}$ . This is a calculation of Burnside, the first of three times Burnside will be mentioned in this post.

Next, I claim that every group ${G}$ of order ${2025}$ has the split structure either ${3^4 : 5^2}$ or ${5^2 : 3^4}$ , i.e., either ${P}$ or ${Q}$ is normal. This is a marginally more difficult version of a standard exercise in the use of Sylow’s theorem. By Burnside’s theorem, ${G}$ is solvable. By considering a minimal quotient of ${G}$ it follows that ${G}$ has a normal subgroup ${N}$ of index ${|G:N| \in \{3, 5\}}$ . Suppose ${|G:N| = 3}$ . Then ${Q \le N}$ , and since ${|N| = 3^3 5^2}$ and ${3, 3^2, 3^3 \not\equiv 1 \pmod 5}$ it follows from Sylow’s third theorem that ${Q}$ is the unique Sylow ${5}$ -subgroup of ${N}$ . Therefore ${Q}$ is characteristic in ${N}$ , so normal in ${G}$ . An analogous argument applies if ${|G:N| = 5}$ , since symmetrically ${5}$ mod ${3}$ has order ${2}$ .

Thus the problem reduces to classifying extensions of the form ${P \rtimes Q}$ and ${Q \rtimes P}$ . There are ${2 \cdot 15 = 30}$ possible direct products ${P \times Q}$ , so we may focus on the non-direct semidirect products.

First consider the extensions of the form ${Q \rtimes_\alpha P}$ where ${\alpha : P \to \mathrm{Aut}(Q)}$ is a nontrivial homomorphism. In particular ${|\mathrm{Aut}(Q)|}$ should be divisible by ${3}$ . Since ${|\mathrm{Aut}(C_{25})| = 20}$ it follows that ${Q = C_5^2}$ and ${\mathrm{Aut}(Q) \cong \mathrm{GL}_2(5)}$ . Note that ${\mathrm{GL}_2(5)}$ has order ${480}$ and its quotient ${\mathrm{PGL}_2(5)}$ is isomorphic to ${S_5}$ . Therefore the Sylow ${3}$ -subgroups of ${\mathrm{GL}_2(5)}$ have order ${3}$ , they are all conjugate, and moreover the nontrivial automorphism of ${C_3}$ is also realized an inner automorphism of ${\mathrm{GL}_2(5)}$ (since that is true in ${S_5}$ ). As discussed last year, we often have ${P \rtimes_\alpha Q \cong P \rtimes_\beta Q}$ for different ${\alpha, \beta}$ , and we really only care about equivalence classes of homomorphism ${\alpha \in \mathrm{Hom}(P, \mathrm{Aut}(Q))}$ up to the natural action of ${\mathrm{Aut}(P) \times \mathrm{Aut}(Q)}$ (where ${\mathrm{Aut}(P)}$ acts by precomposition and ${\mathrm{Aut}(Q)}$ acts by conjugation). Since the image of ${\alpha}$ must be contained in a Sylow ${3}$ -subgroup of ${\mathrm{Aut}(Q)}$ , we get a unique equivalence class ${[\alpha]}$ for each automorphism class of maximal subgroups of ${P}$ . We now have to go through the list of possibilities for the Sylow ${3}$ -subgroup ${P}$ and count the automorphism classes of index- ${3}$ subgroups. This can be done in GAP with a bit of torment, which I will spare you, but the result is that each of the groups of order ${3^4}$ have ${1}$ , ${2}$ , or ${3}$ classes of maximal subgroup, and altogether there are ${31}$ essentially different pairs ${(P, M)}$ where ${P}$ is a group of order ${3^4}$ and ${M < P}$ is a maximal subgroup, and thus there are ${31}$ isomorphism classes of extensions of the form ${C_5^2 \rtimes P}$ .

It is similar with extensions of the form ${P \rtimes Q}$ . In this case ${|\mathrm{Aut}(P)|}$ has to be divisible by ${5}$ , and I claim this happens only for ${P = C_3^4}$ . Indeed, otherwise, ${P / \Phi(P) \cong C_3^d}$ for some ${d \le 3}$ and therefore ${Q}$ acts trivially on ${P / \Phi(P)}$ , which implies by a lemma of Burnside that ${Q}$ acts trivially on ${P}$ (see (24.1) in Aschbacher’s Finite Group Theory). Now ${\mathrm{GL}_4(3)}$ has order- ${5}$ Sylow ${5}$ -subgroups, so similarly to the previous paragraph we find that the number of classes of homomorphisms ${\alpha : Q \to \mathrm{Aut}(P)}$ is just the number of automorphism classes of maximal subgroups of ${Q}$ . Both ${C_{25}}$ and ${C_5^2}$ have a unique such class, so the number of nontrivial extensions of the form ${P \rtimes Q}$ is just ${2}$ : there is one of the form ${C_3^4 \rtimes C_{25}}$ and one of the form ${C_3^4 \rtimes C_5^2 = (C_3^4 \rtimes C_5) \times C_5}$ .

Thus altogether there are ${30 + 31 + 2 = 63}$ groups of order ${2025}$ ! Happy new year!

1. Boston–Shalev for conjugacy classes

Last week Daniele Garzoni and I uploaded to the arxiv a preprint on the Boston–Shalev conjecture for the conjugacy class weighting. The Boston–Shalev conjecture in its original form predicts that, in any finite simple group $G$ , in any transitive action, the proportion of elements acting as derangements is at least some universal constant $c > 0$ . This conjecture was proved by Fulman and Guralnick in a long series of papers. Daniele and I looked at conjugacy classes instead, and we found an analogous result to be true: the proportion of conjugacy classes containing derangements is at least some universal constant $c' > 0$ .

Our proof depends on the correspondence between semisimple conjugacy classes in a group of Lie type and polynomials over a finite field possibly with certain restrictions: either symmetry or conjugate-symmetry. We studied these sets of polynomials from an “anatomical” perspective, and we needed to prove several nontrivial estimates, e.g., for

the number of polynomials with a factor of a given degree (which is closely related the “multiplication table problem”),
the number of polynomials with an even or odd number of irreducible factors,
the number of polynomials with no factors of small degree,
or the number of polynomials factorizing in a certain way (e.g., as $f = gg^*$ , $g$ irreducible, $g^*$ the reciprocal polynomial).

For a particularly neat example, we found that, if the order of the ground field is odd, exactly half the self-reciprocal polynomials have an even number of irreducible factors — is there a simple proof of this fact?

2. Growth in Linear Groups

Yesterday Brendan Murphy, Endre Szabo, Laci Pyber, and I uploaded a substantial update to our preprint Growth in Linear Groups, in which we prove one general form of the “Helfgott–Lindenstrauss conjecture”. This conjecture asserts that if a symmetric subset $A$ of a general linear group $\mathrm{GL}_n(F)$ ( $n$ bounded, $F$ an arbitrary field) exhibits bounded tripling, $|A^3| \le K|A|$ , then $A$ suffers a precise structure: there are subgroup $H \trianglelefteq \Gamma \le \langle A \rangle$ such that $\Gamma / H$ is nilpotent of class at most $n-1$ , $H$ is contained in a bounded power $A^{O_n(1)}$ , and $A$ is covered by $K^{O_n(1)}$ cosets of $\Gamma$ . Following prodding by the referee and others, we put a lot more work in and proved one additional property: $\Gamma$ can be taken to be normal in $\langle A \rangle$ . This seemingly technical additional point is actually very subtle, and I strongly doubted whether it was true late into the project, more-or-less until we actually proved it.

We also added another significant “application”. This is not exactly an application of the result, but rather of the same toolkit. We showed that if $G \le \mathrm{GL}_n(F)$ (again $F$ an arbitrary field) is any finite subgroup which is $K(n)$ -quasirandom, for some quantity $K(n)$ depending only on $n$ , then the diameter of any Cayley graph of $G$ is polylogarithmic in the order of $|G|$ (that is, Babai’s conjecture holds for $G$ ). This was previously known for $G$ simple (Breuillard–Green–Tao, Pyber–Szabo, 2010). Our result establishes that it is only necessary that $G$ is sufficiently quasirandom. (There is a strong trend in asymptotic group theory of weakening results requiring simplicity to only requiring quasirandomness.)

The intention of our paper is more-or-less to “polish off” the theory of growth in bounded rank. By contrast, growth in high-rank simple groups is still poorly understood.

3. The Kelley–Meka result

Not my own work, but it cannot go unmentioned. There was a spectacular breakthrough in additive combinatorics last week. Kelley and Meka proved a Behrend-like upper bound for the density of a subset $A \subset \{1, \dots, n\}$ free of three-term arithmetic progressions (Roth’s theorem): the density of $A$ is bounded by $\exp(-c (\log n)^\beta)$ for some constants $c, \beta > 0$ . Already there are other expositions of the method which are also worth looking at: see the notes by Bloom and Sisask and Green (to appear, possibly).

Until this work, density $1 /\log n$ was the “logarithmic barrier”, only very recently and barely overcome by Bloom and Sisask. Now that the logarithmic barrier has been completely smashed, it seems inevitable that the new barometer for progress on Roth’s theorem is the exponent $\beta$ . Kelley and Meka obtain $\beta = 1/11$ , while the Behrend construction shows $\beta \le 1/2$ .