Enumerating all subgroups of the symmetric group

Question

Is there an efficient way to enumerate the unique subgroups of the symmetric group? Naïvely, for the symmetric group $S_n$ of order $\left | S_n \right | = n!$, there are $2^{n!}$ subsets of the group members that could potentially form a subgroup. In addition, many of these subgroups are going to be isomorphic to each other. I feel that the question has an easy answer in terms of the conjugacy classes, but I don't see how. If the answer generalizes to all finite groups, please elaborate!

Answer 1

The number of distinct subgroups of the symmetric group on $n$ points are given for $n \leq 18$ in oeis:A005432, the number of conjugacy classes of subgroups is oeis:A000638 for $n \leq 18$, and the number of (abstract) isomorphism classes amongst the subgroups is oeis:A174511 for $n \leq 13$ (I think 7872 for $n=14$).

To give a feel for these numbers, I include them in a table below for $n \leq 15$. I also include the number of transitive subgroups of $S_n$, since this is a very different number. The number of conjugacy classes is also known as the number of permutation groups (transitive and intransitive alike). As far as I know, combining the transitive groups to form intransitive groups involves an enormous amount of book-keeping and calculation and so has not been done (the number of transitive groups are known up into the 30s and maybe up to $n \leq 63$ by now). I do not include the naive estimate of $2^{n!}$ since for $n=5$ one gets 1329227995784915872903807060280344576, which is quite a bit bigger than the number of subgroups, which is 156.

$$\begin{array}{r|rrrrrrrrrr} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \#sub & 1 & 2 & 6 & 30 & 156 & 1455 & 11300 & 151221 & 1694723 & 29594446 \\ \#ccs & 1 & 2 & 4 & 11 & 19 & 56 & 96 & 296 & 554 & 1593 \\ \#iso & 1 & 2 & 4 & 9 & 16 & 29 & 55 & 137 & 241 & 453 \\ \#trn & 1 & 1 & 2 & 5 & 5 & 16 & 7 & 50 & 34 & 45 \\ \end{array}$$ $$\begin{array}{r|rrrrr} n & 11 & 12 & 13 & 14 & 15 \\ \hline \#sub & 404126228 & 10594925360 & 175238308453 & 5651774693595 & 117053117995400 \\ \#ccs & 3094 & 10723 & 20832 & 75154 & 159129 \\ \#iso & 894 & 2065 & 3845 & 7872 & ? \\ \#trn & 8 & 301 & 9 & 63 & 104 \\ \end{array}$$

---

No known method is particularly "efficient" in n, otherwise one would have calculated these quite a bit further. To find the number of subgroups given the conjugacy classes of subgroups, one takes a representative of each conjugacy class of subgroups, and sums the indices of the normalizers. In particular, #sub is not much harder than #ccs to calculate, but it is much much larger and less useful.

---

Asymptotics on these numbers are fairly different than these early terms, but are given in Pyber (1993) and Pyber-Shalev (1997):

• $2^{\left(\tfrac1{16}+o(1)\right)n^2} \leq \#\text{sub} \leq 24^{\left(\tfrac16+o(1)\right)n^2}$ with the lower bound conjectured to be tight.
• $\log(\#\text{sub}) = \Theta(n^2)$, in other words
• $\log(\#\text{ccs}) = \Theta(n^2)$, because a subgroup can have at most $n!$ conjugates, and $n!$ is so tiny
• $C^{n^2/\log(n)} \leq \#\text{iso}$ for some $C>1$

The lower bounds are mostly obtained by considering p-subgroups which dominate once n is sufficiently large. The upper bound requires the CFSG to control the insoluble subgroups. I didn't see the upper bound for #iso, but of course one can use #iso ≤ #ccs.