Enumerating all subgroups of the symmetric group

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!

• Have you looked at the software called GAP? It has such an enumeration routine and it seems to be reasonably fast. – Ryan Budney Oct 26 '11 at 20:55
• By "unique", do you mean "up to isomorphism"? Given that every group of order $n$ is isomorphic to a subgroup of $S_n$, I would expect it to be hard, not easy, to enumerate all subgroups of $S_n$ up to isomorphism. Enumerating all subgroup of, say, $S_{64}$, would include enumerating all groups of order up to $64$; given that there are 294 groups of order 64, it seems like a tall order. – Arturo Magidin Oct 26 '11 at 20:57
• @Bill: It's actually more than enumerating all groups of order $n$ and less, because you also have subgroups of $S_n$ of order more than $n$. – Arturo Magidin Oct 26 '11 at 21:15
• @Arturo The group $S_{64}$ has considerably more elements than there are atoms in the universe. The fact that there are 294 groups of size 64 is going to be your least problem, and does not preclude the possibility of efficient subgroup enumeration algorithms (where the running time should be measured as a function of $|S_n|$ and not of $n$). – Alex B. Oct 27 '11 at 0:13
• I think conjugacy classes would be relevant if you were interested in normal subgroups (which are necessarily unions of conjugacy classes). – Joel Cohen Oct 27 '11 at 1:02

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.

• The numbers in the row #trn are the numbers of conjugacy classes of transitive subgroups (see this answer for the count for $S_4$). – joriki Mar 30 '12 at 8:37

If you are interested in classifying and identifying the possible subgroups of $S_n$ Wilson's Finite Simple Groups has an analysis in Chapter 2 - covering Intransitive subgroups, transitive imprimitive subgroups, primitive wreath products, affine subgroups, subgroups of diagonal type and almost simple groups. From this classification you can see that there is some complexity involved, and that counting will be hard.