# 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

## 1 Answer

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$).

• Derek, yes, of course, transitivity assumption is necessary to get any sort of sensible result, on the other hand, it is not clear (but obviously tractable) how much restricting partitions from having long prime cycles reduces the number, and then probably very hard to tell whether the bound you get can come anywhere closed to being achieved by a subgroup. – Igor Rivin Nov 20 '13 at 17:07