Symmetric Group – Enumerating All Subgroups

finite-groupsgroup-theorysymmetric-groups

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!

Best Answer

The number of distinct subgroups of the symmetric group on n points are given for n ≤ 13 in oeis:A005432, the number of conjugacy classes of subgroups is oeis:A000638 for n ≤ 18, and the number of (abstract) isomorphism classes amongst the subgroups is oeis:A174511 for n ≤ 10 (I get 894 for n=11, 2065 for n=12, 3845 for n=13, and I think 7872 for n=14).

To give a feel for these numbers, I include them in a table below for n ≤ 15. I also include the number of transitive subgroups of Sn, 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 ≤ 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 & ? \\ \#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.

Related Question