groups – Page 2 – Random Permutations

Happy new year!

Group theory warm-up exercise for the year: what are all the groups of order 2024?

Last year we did 2023, which was rather boring because all groups of order ${2023}$ are abelian. This year the possibilities are much more numerous and the calculation is somewhat involved.

There are some easy initial reductions using Sylow’s theorem. Let ${G}$ be a group of order ${2024 = 2^3 \cdot 11 \cdot 23}$ . Sylow’s theorem implies that there must be a unique subgroup ${P}$ of order ${23}$ . Similarly, in the quotient ${G/P}$ of order ${2^3 \cdot 11}$ there must be a unique subgroup of order ${11}$ . Therefore ${G}$ has a unique subgroup ${N}$ of order ${11 \cdot 23}$ . Let ${Q}$ be a Sylow ${2}$ -subgroup of ${G}$ . Then ${G = NQ \cong N \rtimes_\alpha Q}$ for some homomorphism ${\alpha : Q \to \mathrm{Aut}(N)}$ .

We can easily list the possibilities for ${N}$ and ${Q}$ . There are just two possibilities for ${N}$ : the cyclic group ${C_{253}}$ and the unique nonabelian semidirect product ${C_{23} \rtimes C_{11}}$ . There are five possibilities for ${Q}$ : ${C_8}$ , ${C_4 \times C_2}$ , ${C_2^3}$ , the dihedral group ${D_4}$ , and the quaternion group ${Q_8}$ .

Next, for each choice of ${N}$ and ${Q}$ , we must consider all possibilities for ${\alpha : Q \to \mathrm{Aut}(N)}$ . However, in order to avoid duplication, we must determine when two homomorphisms ${\alpha, \beta : Q \to \mathrm{Aut}(N)}$ induce isomorphic semidirect products.

A quick word about notation. Following standard practice in group theory, we denote group actions on the right. If ${x}$ and ${y}$ are elements of a common group ${G}$ , we denote by ${x^y}$ the conjugate ${y^{-1} x y}$ . We also denote by ${x^\alpha}$ the image of ${x}$ under a given homomorphism ${\alpha}$ . We can then say that the semidirect product ${N \rtimes_\alpha Q}$ is generated by copies of ${N}$ and ${Q}$ subject to the natural-looking relation

$\displaystyle n^q = n^{q^\alpha}.$

This relation asserts that the conjugation action of ${Q}$ on ${N}$ is given by ${\alpha}$ .

Suppose ${f}$ is an isomorphism from ${G_\alpha = N \rtimes_\alpha Q}$ to ${G_\beta = N \rtimes_\beta Q}$ such that ${f(N) = N}$ . Then ${f}$ induces an automorphism ${f_1}$ of ${N}$ as well as an automorphism ${f_2}$ of ${G/N \cong Q}$ . These automorphisms are not arbitrary: they satisfy a certain compatibility relation. Namely, for all ${n \in N}$ and ${q \in Q}$ we have

$\displaystyle (n^{q^\alpha})^{f_1} = (n^q)^f = (n^f)^{q^f} = (n^{f_1})^{(q^{f_2})^\beta}.$

In other words, for all ${q \in Q}$ we have, in ${\mathrm{Aut}(N)}$ ,

$\displaystyle f_1^{-1} q^\alpha f_1 = (q^{f_2})^\beta.$

Written a third way, we have, as elements of ${\mathrm{Hom}(Q, \mathrm{Aut}(N))}$ ,

$\displaystyle \alpha f_1^\iota = f_2 \beta,$

where ${f_1^\iota}$ denotes the inner automorphism of ${\mathrm{Aut}(N)}$ induced by ${f_1}$ . (Alternatively, if somewhat more traditionally we denote function composition in a right-to-left manner, the compatibility relation is ${f_1 \cdot \alpha \cdot f_1^{-1} = \beta \circ f_2}$ .)

Let us denote by ${I_{\alpha,\beta}}$ the set of all isomorphisms ${G_\alpha \to G_\beta}$ such that ${f(N) = N}$ , and by ${C_{\alpha, \beta}}$ the set of all compatible isomorphism pairs ${(f_1, f_2) \in \mathrm{Aut}(N) \times \mathrm{Aut}(Q)}$ , i.e.,

$\displaystyle C_{\alpha,\beta} = \{(f_1, f_2) \in \mathrm{Aut}(N) \times \mathrm{Aut}(Q) : \alpha f_1^\iota = f_2 \beta\}.$

The import of the previous paragraph is that there is a natural map ${I_{\alpha,\beta} \to C_{\alpha,\beta}}$ . Moreover this map is surjective (though typically not injective), because if ${(f_1, f_2)}$ is a compatible isomorphism pair then the map ${f :G_\alpha \to G_\beta}$ defined by ${(nq)^f = n^{f_1} q^{f_2}}$ is an isomorphism (easy exercise). In particular, there is an isomorphism ${f}$ from ${N \rtimes_\alpha Q}$ to ${N \rtimes_\beta Q}$ such that ${f(N) = N}$ if and only if ${C_{\alpha,\beta} \ne \emptyset}$ , i.e., if and only if there is a pair of compatible automorphisms ${(f_1, f_2) \in \mathrm{Aut}(N) \times \mathrm{Aut}(Q)}$ .

We can phrase this conclusion another way. Observe that ${\mathrm{Aut}(N) \times \mathrm{Aut}(Q)}$ acts naturally on ${\mathrm{Hom}(Q, \mathrm{Aut}(N))}$ . The ${\mathrm{Aut}(Q)}$ factor acts by precomposition, while the ${\mathrm{Aut}(N)}$ factor acts by conjugation. Isomorphism classes of split extensions ${N \rtimes Q}$ are in bijection with orbits of ${\mathrm{Aut}(N) \times \mathrm{Aut}(Q)}$ in ${\mathrm{Hom}(Q, \mathrm{Aut}(N))}$ . (Here we consider ${N \rtimes_\alpha Q}$ and ${N \rtimes_\beta Q}$ to be isomorphic as extensions if and only if there is an isomorphism ${f : N \rtimes_\alpha Q \to N \rtimes_\beta Q}$ such that ${f(N) = N}$ . In general this is more restrictive than mere isomorphism as groups.)

Now consider the special case in which ${\alpha = \beta}$ . In this case ${I_{\alpha,\alpha}}$ is a subgroup of ${\mathrm{Aut}(N \rtimes_\alpha Q)}$ and ${C_{\alpha,\alpha}}$ is a subgroup of ${\mathrm{Aut}(N) \times \mathrm{Aut}(Q)}$ , and the natural map ${I_{\alpha,\alpha} \to C_{\alpha,\alpha}}$ is a homomorphism. Let ${K}$ be the kernel. Then ${K}$ consists of all isomorphism ${f : G \to G}$ that restrict to the identity on ${N}$ and induce the identity on ${G/N \cong Q}$ . This implies that there is a map ${h : Q \to N}$ such that ${q^f = q q^h}$ for all ${q \in Q}$ . Since ${f}$ restricts to the identity on ${N}$ , we have

$\displaystyle n^q = (n^q)^f = n^{q^f} = n^{q q^h},$

which implies that ${h}$ takes values in the centre ${Z(N)}$ of ${N}$ . Moreover, ${q^f = qq^h}$ is a homomorphism ${Q \to G}$ , so we must have the relation

$\displaystyle (q_1q_2)^h = (q_1^h)^{q_2^\alpha} (q_2^h).$

This relation means that ${h}$ is a crossed homomorphism from ${Q}$ to ${Z(N)}$ . The group of crossed homomorphisms ${G \to M}$ is usually denoted ${Z^1_\alpha(G, M)}$ . Thus we have a short exact sequence

$\displaystyle Z^1_\alpha(Q, Z(N)) \to I_{\alpha,\alpha} \to C_{\alpha,\alpha}.$

In particular, if ${N}$ is a characteristic subgroup of ${N \rtimes_\alpha Q}$ , ${I_{\alpha,\alpha}}$ is the full automorphism group, so we have a short exact sequence

$\displaystyle Z^1_\alpha(Q, Z(N)) \to \mathrm{Aut}(N \rtimes_\alpha Q) \to C_{\alpha,\alpha}.$

In fact ${C_{\alpha,\alpha}}$ can be identified with the subgroup of automorphisms of ${N \rtimes_\alpha Q}$ preserving ${Q}$ , so this sequence splits and we find that

$\displaystyle \mathrm{Aut}(N \rtimes_\alpha Q) \cong Z_\alpha^1(Q, Z(N)) \rtimes C_{\alpha,\alpha}.$

Let us put all this into practice. Recall that we have two possibilities for ${N}$ : ${N \cong C_{253}}$ or ${N \cong C_{23} \rtimes C_{11}}$ . Let us consider the case ${N \cong C_{253}}$ first. We have

$\displaystyle \mathrm{Aut}(C_{253}) \cong \mathrm{Aut}(C_{23}) \times \mathrm{Aut}(C_{11}) \cong C_{22} \times C_{10} \cong C_2^2 \times C_5 \times C_{11}.$

For each choice of ${Q}$ among ${C_8, C_4 \times C_2, C_2^3, D_4, Q_8}$ we must tabulate the homomorphisms ${Q \to \mathrm{Aut}(C_{253})}$ up to the action of ${\mathrm{Aut}(Q)}$ by precomposition and the conjugation action of ${\mathrm{Aut}(C_{253})}$ . Since ${\mathrm{Aut}(C_{253})}$ is abelian, the latter action is trivial. Any such homomorphism must take values in the Sylow ${2}$ -subgroup ${C_2^2}$ , so we are reduced to tabulating homomorphisms ${Q \to C_2^2}$ up to automorphisms of ${Q}$ .

Case ${Q = C_8}$ : There are four. Among these are groups with the structures ${C_{2024}}$ , ${C_{23} \times (C_{11} \rtimes C_8)}$ , ${C_{11} \times (C_{23} \rtimes C_8)}$ . The last has the structure ${C_{253} \rtimes C_8}$ , and the action of ${C_8}$ on ${C_{253}}$ is fixed-point-free.

Case ${Q = C_4 \times C_2}$ : Write ${Q = \langle x, y \mid x^4 = y^2 = [x,y] = 1\rangle}$ . Any homomorphism ${Q \to C_2^2}$ must kill ${x^2}$ , so factors through ${Q / \langle x^2 \rangle \cong \langle x, y \mid x^2 = y^2 = [x,y] = 1\rangle \cong C_2^2}$ . Naively are ${4^2}$ homomorphisms ${Q/\langle x^2\rangle \to C_2^2}$ , but ${\mathrm{Aut}(Q)}$ acts by swapping ${x}$ and ${xy}$ (while ${y}$ is fixed) and the number of orbits of homomorphisms ${Q \to C_2^2}$ is ${1 \cdot 4 + 3 \cdot 2 = 10}$ . These groups include ${C_{253} \times C_4 \times C_2}$ , ${(C_{253} \rtimes C_4) \times C_2}$ , ${(C_{11} \rtimes C_4) \times C_{23} \times C_2}$ , ${(C_{23} \rtimes C_4) \times C_{11} \times C_2}$ , ${D_{253} \times C_4}$ , ${D_{11} \times C_{23} \times C_4}$ , ${D_{23} \times C_{11} \times C_4}$ , and ${3}$ others.

Case ${Q = C_2^3}$ : There are ${4^3}$ homomorphisms ${C_2^3 \to C_2^2}$ , but only ${5}$ up to the action of ${\mathrm{Aut}(Q) \cong \mathrm{GL}_3(2)}$ . They are in bijection with subgroups of ${C_2^2}$ . The corresponding groups of order ${2024}$ are ${C_{23} \times C_{11} \times C_2^3}$ , ${D_{11} \times C_{23} \times C_2^2}$ , ${D_{23} \times C_{11} \times C_2^2}$ , ${D_{253} \times C_2^2}$ , and ${D_{11} \times D_{23} \times C_2}$ .

Case ${Q = D_4}$ : Any homomorphism ${D_4 \to C_2^2}$ factors through ${D_4 / D_4' \cong C_2^2}$ . Just as in the case of ${C_4 \times C_2}$ there are ${10}$ homomorphisms ${D_4 \to C_2^2}$ up to the action of ${\mathrm{Aut}(D_4)}$ . The groups of order ${2024}$ include ${C_{253} \times D_4}$ and ${9}$ in which ${D_4}$ acts nontrivially on ${C_{253}}$ by conjugation.

Case ${Q = Q_8}$ : Any homomorphism ${Q_8 \to C_2^2}$ factors through ${Q_8 / Q_8' \cong C_2^2}$ . In this case ${\mathrm{Aut}(Q_8)}$ acts on ${C_2^2}$ as ${S_3}$ , so as in the case of ${C_2^3}$ there are just ${5}$ homomorphisms ${Q_8 \to C_2^2}$ up to automorphisms of ${Q_8}$ . Thus there are ${5}$ semidirect products of the form ${C_{253} \rtimes Q_8}$ .

Now consider the case in which ${N \cong C_{23} \rtimes_\alpha C_{11}}$ is nonabelian. Since ${C_{23}}$ is a characteristic subgroup of ${N}$ (being the only subgroup of order ${23}$ ), we have

$\displaystyle \mathrm{Aut}(C_{23} \rtimes C_{11}) \cong Z^1_\alpha(C_{11}, C_{23}) \rtimes C_{\alpha,\alpha},$

where ${C_{\alpha,\alpha}}$ is the subgroup of ${\mathrm{Aut}(C_{23}) \times \mathrm{Aut}(C_{11})}$ consisting of compatible pairs. Consider the compatibility relation ${\alpha f_1^\iota = f_2 \alpha}$ . Since ${\mathrm{Aut}(C_{23}) \cong C_{22}}$ is abelian, ${f_1^\iota}$ is trivial, so the relation reduces to ${\alpha = f_2 \alpha}$ . Since ${\alpha}$ is injective, this implies that ${f_2}$ is trivial. Therefore ${C_{\alpha,\alpha} = \mathrm{Aut}(C_{23}) \cong C_{22}}$ . Meanwhile one checks that ${Z^1_\alpha(C_{11}, C_{23}) \cong C_{23}}$ . Therefore ${\mathrm{Aut}(C_{23} \rtimes C_{11}) \cong C_{23} \rtimes C_{22}}$ . Now if ${Q}$ has order ${8}$ then any homomorphism ${Q \to C_{23} \rtimes C_{22}}$ takes values in a Sylow ${2}$ -subgroup isomorphic to ${C_2}$ , which are all conjugate. Tabulating homomorphisms ${Q \to \mathrm{Aut}(N)}$ up to the natural action of ${\mathrm{Aut}(N) \times \mathrm{Aut}(Q)}$ is therefore equivalent to tabulating homomorphisms ${Q \to C_2}$ up to automorphisms of ${Q}$ , which just amounts to tabulating automorphism classes of subgroups of ${Q}$ of index at most ${2}$ . This case is therefore somewhat easier than the previous one.

Case ${Q = C_8}$ : There are just two. The corresponding groups of order ${2024}$ have the forms ${(C_{23} \rtimes C_{11}) \times C_8}$ and ${C_{23} \rtimes (C_{11} \times C_8)}$ .

Case ${Q = C_4 \times C_2}$ : There are three, corresponding to subgroups isomorphic to ${Q}$ , ${C_4}$ , and ${C_2 \times C_2}$ . The corresponding groups of order ${2024}$ include ${(C_{23} \rtimes C_{11}) \times C_4 \times C_2}$ , ${(C_{23} \rtimes C_{22}) \times C_4}$ , ${(C_{23} \rtimes C_{44}) \times C_2}$ .

Case ${Q = C_2^3}$ : There are two, since all index- ${2}$ subgroups are essentially the same. The corresponding groups of order ${2024}$ are ${(C_{23} \rtimes C_{11}) \times C_2^3}$ and ${(C_{23} \rtimes C_22) \times C_2^2}$ .

Case ${Q = D_4}$ : There are three, since there is a unique subgroup isomorphic to ${C_4}$ while the two subgroups isomorphic to ${C_2 \times C_2}$ are equivalent by an automorphism. There are three corresponding groups with structure ${(C_{23} \rtimes C_{11}) \rtimes D_4}$ .

Case ${Q = Q_8}$ : There are two, since the three subgroups of ${Q_8}$ isomorphic to ${C_4}$ are equivalent by automorphisms. Thus there are just two groups with the structure ${(C_{23} \rtimes C_{11}) \rtimes Q_8}$ .

Thus altogether there are ${34+12 = 46}$ groups of order ${2024}$ .

I just uploaded to the arxiv my paper Diameter of classical groups generated by transvections. This paper is a small further step in the direction of Babai’s conjecture on the diameter of simple groups, which predicts for any (nonabelian) finite simple group ${G}$ and for any generating set ${S}$ , the number of elements of ${S}$ needed to represent any element of ${G}$ is bounded by ${(\log |G|)^C}$ for some constant ${C}$ . Roughly this means that finite simple groups are “well-connected”, and starting from any generators you can “find” any element of the group rapidly.

The “Pyber programme” suggests that Babai’s conjecture is really three problems. Assume ${G}$ is either ${A_n}$ or a classical group with defining module ${\mathbf F_q^n}$ , say ${\mathrm{SL}_n(q)}$ . The degree of an element ${g \in G}$ is the size of its support if ${G = A_n}$ or the rank of ${g - 1}$ if ${G}$ is classical. Now the three problems are:

Given arbitrary generators, find an element of degree at most ${0.9 n}$ .
Given a set of generators including an element of degree at most ${0.9 n}$ , find an element of minimal degree.
Given a set of generators including an element of minimal degree, find everything.

(In each problem, “find” really means “establish the existence of an element whose length in the generators is bounded by ${(\log |G|)^C}$ ”.)

The third problem is actually trivial for ${A_n}$ . Note that ${\log |A_n| = \log n! \approx n \log n}$ , so “polynomial in ${\log |G|}$ ” = “polynomial in ${n}$ ”. Now suppose a set of generators includes a ${3}$ -cycle (an element of minimal degree in the alternating group). There are fewer than ${n^3}$ such ${3}$ -cycles, and ${G}$ acts on the ${3}$ -cycles transitively by conjugation, so all ${3}$ -cycles have length at most ${n^3}$ in the generators. Every element of ${A_n}$ can be written as the product of at most ${n}$ such ${3}$ -cycles, so every element of ${A_n}$ has length at most ${n^4}$ in the generators.

But for classical groups the third problem is highly nontrivial. In the case of ${G = \mathrm{SL}_n(q)}$ , the elements of minimal degree are the transvections. The number of transvections is comparable to ${q^{2n}}$ , i.e., exponential in ${n}$ , so such a cheap argument is not available. But, the third problem is now solved anyway (with the exception of orthogonal groups — see below!). This is what my paper is about. The case of odd characteristic had been done already by Garonzi, Halasi, and Somlai (omitting some cases in characteristic ${3}$ ), but the (most complicated) case of characteristic ${2}$ is covered in my paper.

The basic approach, following the previous work of Garonzi, Halasi, and Somlai, is to reduce as much of the algebra as possible to combinatorics. We can make an analogy with the symmetric group ${S_n}$ . Let ${T \subset S_n}$ be a set of transpositions ${(ij)}$ (where ${1 \le i < j \le n}$ ). The transposition graph ${\Gamma}$ is defined to have vertex set ${\{1, \dots, n\}}$ and an edge ${i \sim j}$ whenever ${(ij) \in T}$ . Let ${G}$ be the group generated by ${T}$ . Then the following are equivalent:

${\Gamma}$ is connected,
${G}$ is transitive,
${G = S_n}$ .

This illustrates one simple way in which algebra can be reduced to combinatorics. There is an analogous object for transvections called the transvection graph (though really it is a directed graph), and it can be used to understand when a set of transvections in ${\mathrm{SL}_n(q)}$ generates an irreducible subgroup, but it is necessary to introduce several more gadgets (mostly combinatorial) to understand whether they actually generate ${\mathrm{SL}_n(q)}$ .

Most of the work in the paper involves leveraging a theorem of Kantor classifying the irreducible subgroups generated by transvections. For each type of such subgroup, we try to build a combinatorial “certificate” that our set of transvections is not trabbed in that type of subgroup. For example, if our transvections are not trapped in a symplectic group then there must be a “nonsymplectic cycle” in the transvection graph. This industrial use of Kantor’s theorem is the novel idea of my paper.

What about orthogonal groups? What I really mean is ${\Omega_n^\varepsilon(q)}$ , the index-2 subgroup of ${\mathrm{SO}_n(q)}$ . These groups do not contains transvections! The elements of minimal degree have degree ${2}$ ; they are called “long root elements”. Kantor’s theorem also classifies subgroups generated by long root elements, so in principle this problem can be approached in broadly the same way, but we need a suitable variant of the transvection graph (the “long root element graph”?). Even more generally, it does not seem out of reach to prove Babai’s conjecture under the hypothesis that the generators contain an element of bounded degree.

Do these problems sound interesting to you? Are you looking for PhD opportunities in algebra or combinatorics? Consider coming to Belfast to do your PhD! Write to me by email if you are interested (with an introduction and CV).

On a personal note, this paper was quite a slog, and slowly came together over the course of about 8 months of off-and-on effort. That time is not proportionally reflected in the length of the paper but it may be in the technicality of some of the arguments. A particularly challenging part was coming up with a certificate (as described above) for symmetric-type subgroups, i.e., irreducible subgroups of ${\mathrm{SL}_n(q)}$ isomorphic to either ${S_{n+1}}$ or ${S_{n+2}}$ (acting on the deleted permutation module). In the end the argument is not especially difficult but it took a lot of care getting everything right.

By contrast, another paper I recently put on the arxiv was the result of a moment of inspiration and only a day or so of working out the details and writing up. Which paper will get into a better journal I wonder?

Category: groups

Groups of order 2024

Babai’s conjecture for generating sets containing transvections