recreation – 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!

A famous result: Two positive integers chosen at random will be coprime with probability ${6/\pi^2}$ .

One has to say what one means by this, since there is no uniform distribution on the positive integers. What we mean is that if we choose ${x}$ and ${y}$ uniformly and independently at random from the integers ${\{1,\ldots,N\}}$ , then ${x}$ and ${y}$ will be coprime with probability tending to ${6/\pi^2}$ as ${N\rightarrow\infty}$ .

Here is one classic proof: Consider the points ${(x,y)\in\{1,\ldots,N\}^2}$ such that ${\gcd(x,y)=1}$ . If we scale this picture by ${M}$ , we will have exactly the points ${(X,Y)\in\{1,\ldots,MN\}^2}$ such that ${\gcd(X,Y)=M}$ . Therefore, whatever the limiting probability ${P}$ of being coprime is, the probability of having ${\gcd = M}$ is exactly ${P/M^2}$ . The law of total probability then implies

$\displaystyle 1 = \lim_{N\rightarrow\infty}\mathbf{P}(\gcd(x,y)\in\mathbf{N}) = P \sum_{M=1} \frac{1}{M^2} = P\,\zeta(2).$

Another way of imagining a random element on a noncompact group ${G}$ is to look at the profinite completion ${\hat{G}}$ , which is always compact so always possesses a uniform distribution. Now by the Chinese Remainder Theorem,

$\displaystyle \hat{\mathbf{Z}} = \prod_p \mathbf{Z}_p,$

so choosing an element at random from ${\hat{\mathbf{Z}}}$ is the same as choosing an element at random from ${\mathbf{Z}_p}$ for each ${p}$ . The probability that a random element of ${\mathbf{Z}_p}$ is divisible by ${p}$ is precisely ${1/p}$ , so the probably that two elements from ${\hat{\mathbf{Z}}}$ are coprime is precisely

$\displaystyle \prod_p (1-1/p^2) = 1/\zeta(2).$

This does not imply the asymtotic result in ${\mathbf{Z}}$ mentioned above, but it is a nice way of thinking about it.

EDIT (28/4/12): As pointed out to me by Freddie Manners, the “classic proof” suggested above suffers from the fatal defect of not proving that the limit exists. Here is an alternative proof which does prove that the limit exists. More generally, let ${d>1}$ and consider positive integers ${x_1,\ldots,x_d\leq X}$ chosen uniformly at random. Let ${G(X)}$ be the number of ${(x_1,\ldots,x_d)\in[1,X]^d}$ such that ${\gcd(x_1,\ldots,x_d)=1}$ , and observe that the number of ${(x_1,\ldots,x_d)\in[1,X]^d}$ such that ${\gcd(x_1,\ldots,x_d) = n}$ is precisely ${G(X/n)}$ . Then

$\displaystyle \lfloor X\rfloor^d = \sum_{n\geq1} G(X/n)$

for all ${X}$ . Inverting this relationship,

$\displaystyle G(X) = \sum_{n\geq1} \mu(n) \lfloor X/n\rfloor^d.$

Thus, the probability that ${d}$ randomly and uniformly chosen integers ${x_1,\ldots,x_d\leq X}$ are all coprime is exactly

$\displaystyle P(X) = \sum_{n\geq1} \mu(n) \left(\frac{\lfloor X/n\rfloor}{\lfloor X\rfloor}\right)^d.$

The ${n}$ th term here is bounded by ${n^{-d}}$ , so by the dominated convergence theorem ${P(X)\rightarrow\sum_{n\geq1} \mu(n) n^{-d} = \zeta(d)^{-1}}$ .

Tag: recreation

Groups of order 2025

The probability of coprimality