number theory – 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!

The proof presented below, giving an (almost) complete characterisation of constructible regular polygons, is such a beautiful gem of a proof that I can’t help but record it here so that I might not forget it. I’ll go over far more details than is usually done, simply because it amuses me how many different areas of undergraduate mathematics are touched upon.

Theorem 1 The regular ${n}$ -gon is constructible by ruler and compass if and only if ${n}$ has the form ${2^k p_1 \cdots p_l}$ , where ${p_1,\ldots,p_l}$ are distinct primes of the form ${2^{2^m} + 1}$ .

Primes of this form are called Fermat primes. The only known Fermat primes are ${3,5,17,257,65537}$ , and heuristics suggest that there may be no others, though this is an open problem.

We must say what we mean by “constructible”. We assume we are given a plane (a sheet of paper, say), with two points already labelled. We parameterise the plane by points of ${\mathbf{C}}$ , and we rotate and scale so that the two labelled points are ${0}$ and ${1}$ . There are three things we are allowed to do:

Whenever we have two labelled points we can draw the straight line through them.
Whenever we have two labelled points we can draw the circle with one as centre and the other on the circumference.
We can label any point of intersection (of two lines, two circles, or a line and a circle).

Any point of the plane (considered as an element of ${\mathbf{C}}$ ) that can be labelled through a sequence of the above operations is called constructible. Denote by ${\mathbf{E} \subset \mathbf{C}}$ the set of constructible numbers.

Lemma 2 The set ${\mathbf{E}}$ is the smallest subfield of ${\mathbf{C}}$ closed under taking square roots.

The lemma can be proved as follows.

Show closure under ${(x,y)\mapsto x+y}$ by constructing the parallelogram with vertices ${0,x,y,x+y}$ .
Show closure under the rotation ${x\mapsto ix}$ .
Show closure under taking real parts. Hence ${\mathbf{E} = \mathcal{R}\mathbf{E} + i \mathcal{R}\mathbf{E}}$ , where ${\mathcal{R}\mathbf{E} = \mathbf{E}\cap\mathbf{R}}$ .
Show closure under ${(x,y)\mapsto xy}$ for ${x,y\in\mathcal{R}\mathbf{E}}$ by constructing the right triangle with leg lengths ${1,x}$ and the similar right triangle with base ${y}$ . Deduce that ${\mathbf{E}}$ is a ring.
Show that if ${0\neq x\in\mathbf{E}}$ then ${1/x\in\mathbf{E}}$ by doing so first for ${x\in\mathcal{R}\mathbf{E}}$ (another right triangle construction) and then using ${1/x = \bar{x}/|x|^2}$ . Thus ${\mathbf{E}}$ is a field.
Show that ${\mathcal{R}\mathbf{E}}$ is closed under taking square roots (yet another right triangle construction). Thus show that ${\mathbf{E}}$ is closed under taking square roots by bisecting an appropriate angle.
Finally show that any subfield ${K}$ of ${\mathbf{C}}$ closed under taking square roots is closed under the “constructing” rules we listed when defining ${\mathbf{E}}$ . The idea here is that one never has to solve an equation worse than a quadratic (when intersecting two circles, first construct the perpendicular bisector to the segment connecting the two centres, and then compute the intersection of this line with one of the circles).

The following is our algebraic characterisation of constructibility.

Lemma 3 We have ${x\in\mathbf{E}}$ if and only if the degree ${[K:\mathbf{Q}]}$ of the normal closure ${K}$ of ${\mathbf{Q}(x)}$ is a power of ${2}$ .

Proof: By the previous lemma, ${\mathbf{E}}$ can be described as the union of all fields ${\mathbf{Q}(\alpha_1,\ldots,\alpha_m)}$ such that ${\alpha_k^2\in\mathbf{Q}(\alpha_1,\ldots,\alpha_{k-1})}$ for all ${k=1,\ldots,m}$ . Let ${x\in\mathbf{E}}$ . Thus ${x}$ lies in some such field ${L = \mathbf{Q}(\alpha_1,\ldots,\alpha_m)}$ . But note by the tower law that

$\displaystyle [L:\mathbf{Q}] = \prod_{k=1}^{m} [\mathbf{Q}(\alpha_1,\ldots,\alpha_k):\mathbf{Q}(\alpha_1,\ldots,\alpha_{k-1})],$

where each factor ${[\mathbf{Q}(\alpha_1,\ldots,\alpha_k):\mathbf{Q}(\alpha_1,\ldots,\alpha_{k-1})]\leq 2}$ . Thus ${[L:\mathbf{Q}]}$ is a power ${2}$ , and by another application of the tower law so is ${[K:\mathbf{Q}]}$ . $\Box$

Conversely suppose that ${[K:\mathbf{Q}]}$ is a power of ${2}$ . Then the Galois group ${\text{Gal}(K/\mathbf{Q})}$ is a ${2}$ -group. Recall that any ${p}$ -group ${G}$ (except the trivial group) has nontrivial centre: by counting conjugacy class sizes, the size of ${Z(G)}$ must be divisible by ${p}$ . Thus by induction (and classifying abelian ${p}$ -groups) it follows that in every ${p}$ -group ${G}$ there is a sequence of normal subgroups ${G_i \triangleleft G}$ such that ${G_0 = \{e\}}$ , ${G_n = G}$ , and ${|G_k/G_{k-1}| = p}$ for each ${k=1,\ldots,n}$ . Specialising to ${p=2}$ , Galois theory now implies that ${K}$ is the top of a tower of quadratic extensions starting from ${\mathbf{Q}}$ , so ${x\in K\subset\mathbf{E}}$ .

By saying “the ${n}$ -gon is constructible” we mean that the vertices of some regular ${n}$ -gon are constructible. Clearly this is equivalent to saying ${\zeta_n = \exp(i2\pi/n)}$ is an element of ${\mathbf{E}}$ . Note that ${\Phi_n(\zeta_n) = 0}$ , where the ${n}$ th cyclotomic polynomial ${\Phi_n}$ is defined by

$\displaystyle \Phi_n(X) = \prod_{(k,n)=1} (X-\zeta_n^k).$

Note that ${\prod_{d|n} \Phi_d(X) = X^n-1 \in \mathbf{Z}[X]}$ , so by the uniqueness of polynomial division and induction we have that ${\Phi_n(X) \in \mathbf{Z}[X]}$ .

Lemma 4 ${\Phi_n}$ is irreducible over ${\mathbf{Q}}$ .

Proof: Suppose ${\Phi_n(X) = f(X) g(X)}$ where ${f}$ is irreducible and ${\deg f\geq 1}$ . We must show that each ${\zeta_n^k}$ is a root of ${f}$ . Since some ${\zeta_n^k}$ is a root of ${f}$ , it suffices to show that ${f(z)=0}$ implies ${f(z^p)=0}$ whenever ${p}$ is a prime not dividing ${n}$ . Towards this end, suppose that ${p}$ is such a prime and ${f(z)=0}$ but ${f(z^p)\neq 0}$ . Then ${g(z^p) = 0}$ since ${\Phi_n(z^p)=0}$ . Since ${f}$ is irreducible this implies that ${f(X)}$ divides ${g(X^p)}$ . Denoting reductions modulo ${p}$ by a tilde and using Freshman’s dream, ${\tilde{f}}$ divides ${\tilde{g}(X^p) = \tilde{g}(X)^p}$ . Thus ${\tilde{f}}$ and ${\tilde{g}}$ are not coprime, so ${\tilde{\Phi_n}}$ , and thus ${X^n-1}$ , has a multiple root over ${\mathbf{F}_p}$ . But this is a contradiction since ${X^n-1}$ and its formal derivative ${nX^{n-1}}$ are coprime. $\Box$

Thus ${\zeta_n}$ has minimal polynomial ${\Phi_n}$ , and moreover ${\mathbf{Q}(\zeta_n)/\mathbf{Q}}$ is a normal extension. We have therefore reduced our task to finding those ${n}$ for which ${[\mathbf{Q}(\zeta_n):\mathbf{Q}] = \deg\Phi_n = \varphi(n)}$ is a power of ${2}$ .

Writing ${n}$ as a product of primes ${n=p_1^{e_1}\cdots p_m^{e_m}}$ with each ${e_i>0}$ , we have (OK, the details must stop somewhere)

$\displaystyle \varphi(n) = p_1^{e_1 - 1}(p_1 - 1) \cdots p_m^{e_m-1} (p_m-1).$

This is a power of ${2}$ iff every ${p_i\neq 2}$ which occurs has ${e_i = 1}$ and ${p_i - 1}$ a power of ${2}$ . But if ${p = 2^k + 1}$ is prime, then ${k}$ itself must be a power of ${2}$ , since for every odd ${q}$ we have