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!
$\begingroup$
$\endgroup$
14
-
2$\begingroup$ Have you looked at the software called GAP? It has such an enumeration routine and it seems to be reasonably fast. $\endgroup$– Ryan BudneyCommented Oct 26, 2011 at 20:55
-
9$\begingroup$ 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. $\endgroup$– Arturo MagidinCommented Oct 26, 2011 at 20:57
-
12$\begingroup$ @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$. $\endgroup$– Arturo MagidinCommented Oct 26, 2011 at 21:15
-
3$\begingroup$ @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$). $\endgroup$– Alex B.Commented Oct 27, 2011 at 0:13
-
3$\begingroup$ @Arturo The problem of enumerating all subgroups of a given $S_n$ is not at all the same as classifying all groups, it's classifying all transitive permutation groups on at most $n$ letters. There are of course algorithms that enumerate subgroups of a given group, some are more efficient than others. The present question asks if there are algorithms that work particularly efficiently in the special case of $S_n$. The only sensible way of making sense of "particularly efficiently" is to compare their running time on $S_n$ with running times of generic algorithms on groups of comparable size. $\endgroup$– Alex B.Commented Oct 27, 2011 at 4:48
|
Show 9 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
answered Nov 5, 2011 at 5:44
-
3$\begingroup$ The numbers in the row #trn are the numbers of conjugacy classes of transitive subgroups (see this answer for the count for $S_4$). $\endgroup$– jorikiCommented Mar 30, 2012 at 8:37
$\begingroup$
$\endgroup$
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.
answered Apr 11, 2018 at 13:00