10
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Did you compute the number of cycle types for various H and n using tools like GAP ? What's the result ? $\endgroup$
    – tj_
    Nov 20, 2013 at 15:11
  • $\begingroup$ 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. $\endgroup$
    – Olga
    Nov 20, 2013 at 16:29
  • $\begingroup$ @Olga thanks, though no need to be ashamed... $\endgroup$
    – Igor Rivin
    Nov 20, 2013 at 17:23
  • $\begingroup$ @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. $\endgroup$
    – Nick Gill
    Nov 20, 2013 at 22:22
  • $\begingroup$ @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? $\endgroup$
    – Igor Rivin
    Nov 21, 2013 at 0:17

1 Answer 1

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Nov 20, 2013 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.