How can we find the number of subgroups of order $n$, where $n$ is prime, in the symmetric group $S_n$? Typically, I am interested in, say $S_{17}$. I am stuck at this problem. I think it has something to do with the conjugacy classes of the symmetric group. Any ideas. Thanks beforehand.
[Math] number of subgroups of order $ n $ in $S_n$
abstract-algebragroup-theorysymmetric-groups
Related Solutions
(i) Conjugacy classes are certainly useful, since a normal subgroup must be a union of conjugacy classes. There are other ideas that can come into play: once you know a proper normal subgroup $N$, by taking the quotient you can obtain information about $G$ from information you may find in $G/N$, which will hopefully be easier than working directly in $G$ because $G/N$ will be smaller than $G$.
(ii) In fact, that is one important reason for finding all normal subgroups: being able to look at the quotient, and thus obtain information about $G$ by looking at groups that are smaller than $G$. Another is that the normal subgroups are closely associated with all possible images of $G$ under homomorphisms. Both of these facts are part of the Isomorphism Theorems.
Right now you are probably engaged in computation and getting familiar with techniques for working with groups in general, and $D_n$ in particular; the importance of normal subgroups will likely emerge as you start using groups. For example, normal subgroups are extremely important when you are considering Galois groups (which help you study fields and field extensions).
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.
Best Answer
This question is over 2 years old, and has been discussed in the comments. So that this question does not remain listed as unanswered I will provide an approach.
We consider $S_{p}$, the symmetric group on $p$ letters, with order $p!$.
Subgroups of order $p$ must be cyclic. Notice that a subgroup of order $p$ contains $p-1$ elements of order $p$ and then also the identity element. On the other hand, given an element of order $p$, say $x$, then $\langle x \rangle $ is a group of order $p$. In particular every element of order $p$ is contained in precisely one subgroup of order $p$. (To put this another way, the intersection of any two subgroups of order $p$ is trivial).
So, to find the number of subgroups of order $p$, we can find the number of elements of order $p$ and divide this number by $p-1$ (Since each subgroup is being counted $p-1$ times).
How many elements of order $p$ are there in $S_{p}$? The number of ways we can arrange $p$ letters in a cycle is $p!$, but we are overcounting by a factor of $p$ since all shifts of a cycle are equal (for example in $S_{3}, (1,2,3)=(2,3,1)=(3,1,2)$). Hence the number of elements of order $p$ is $p! / p = (p-1)!$.
Then the number of subgroups of order $p$ is $(p-1)!/(p-1) = (p-2)!$.
For some further reading take a look at: Applying this result in $S_{7}$. Note the top answer here has an interesting aside about Sylow theory.