# Effective Camille Jordan

It is a well-known (and frequently used) theorem of C. Jordan that a proper subgroup $H$ of a finite group $G$ can not intersect every conjugacy class. This is used most frequently for $G=S_n.$ Now, the question: for $H$ a subgroup of $S_n$ what are the possible numbers of cycle types $H$ can have? One might conjecture that there is $A_n$ which has a lot of cycle types, and then there is a big drop, and then there are some sort of further "phase transitions". There might also be big difference between transitive and intransitive and primitive and imprimitive subgroups. Is there?

• Did you compute the number of cycle types for various H and n using tools like GAP ? What's the result ? – tj_ Nov 20 '13 at 15:11
• This is such a nice question -- how do the objects which we are soo used to grow? I feel ashamed I've never thought of it. – Olga Nov 20 '13 at 16:29
• @Olga thanks, though no need to be ashamed... – Igor Rivin Nov 20 '13 at 17:23
• @Igor, you might be interested in work of Maroti - renyi.hu/~maroti/conj4.pdf - that bounds the maximal number of conjugacy classes of a subgroup of $S_n$. This bound is obviously also an (extremely crude) upper bound for the number of cycle types. If you add assumptions to the subgroup (e.g. nilpotency), then you get stronger bounds. – Nick Gill Nov 20 '13 at 22:22
• @NickGill that is a very interesting paper, but the first result in the most interesting (primitive) case is trivial for my question (his theorem is that the number of conjugacy classes is at most $p(n),$ but we already knew that.... Part (b) of theorem 1.3 is certainly interesting (it gives a polynomial bound), but how restrictive is the hypothesis on the socle? – Igor Rivin Nov 21 '13 at 0:17

It's difficult to come up with precise results for general subgroups. For example $S_{n-1}$ has lots of cycle types!
You can say more for transitive groups, and even more for primitive groups. Jordan proved in 1873 that, if $G \le S_n$ is primitive and contains a $p$-cycle with $p$ prime and $p<n-2$, then $A_n \le G$.
If you make the condition $n/2 < p < n-2$, then the result applies to all transitive groups. (This provides a very fast probabilistic algorithm for deciding whether a subgroup of $S_n$ defined by given generators is $A_n$ or $S_n$. First test for transitivity, and then choose random elements and look for $p$-cycles of this form. If, after a certain number of choices, you find no such elements, then the hypothesis that the group contains $A_n$ becomes staistically improbable in a precise sense.)
There are more modern results on the minimal degree $m(G)$ of primitive groups $G$ (the size of the smallest support of a non-identity element of $G$), some of which use CFSG. These of course imply restrictions on possible cycle-types. For a general primitive group $G \le S_n$ that does not contain $A_n$, it is known that $m(G) \ge \sqrt{n}/2$, and for 2-transitive groups, $m(G) \ge n/8$ (or $n/4$ for $n>216$).