# Maximal $k$-transitivity for a proper subgroup of $S_n$

Let $S_n$ be the permutation group on $n$ elements. Denote by $K(n)$ the largest $k$ s.t. $S_n$ has a $k$-transitive subgroup (w.r.t. its action on the $n$-element set on which $S_n$ acts) different from $S_n,A_n$.

I heard that it has been proved that $K(n)\le 7$ for all $n$ but the proof uses the classification of finite groups (please correct me if I am wrong on this). But I am also interested in the exact value of $K(n)$ for small $n$ (or even all $n$ if there is a simple description).

Also I wonder what can be proved in a more elementary way (even weak bounds like $K(n)<n/3$ are interesting).

• I think you mean "classification of finite simple groups" (not of "finite groups")... – Arturo Magidin Aug 1 '13 at 16:12
• I am also interested in the similar problem for subgroups of $S_n\times S_n$ ($S_n\times S_n\times S_n$ etc.) acting on two separate $n$-element sets and $k$-transitive in the sense that each $k$-tuple of elements can be sent to any other with each corresponding element in the same of the two $n$-element sets. – Alex Aug 2 '13 at 11:06
• @Alex: Comments on the own question are not the right way to raise new questions. – Peter Mueller Aug 2 '13 at 12:47

Actually $K(n)\le5$, with equality only for $n=12$ and $n=24$ and subgroup the Mathieu group $M_n$. If $G\le S_n$ is at least $2$-transitive, then an old theorem of Burnside shows that either $G$ has a regular elementary abelian normal subgroup, or $G$ has a simple non-abelian normal subgroup.

In the former case, it is an easy exercise to see that $G$ is at most $3$-transitive,

To treat the latter case indeed requires the classification of the finite simple groups. There isn't even any bound $c$ with $K(n)\le c$ available without the classification.

A nice overview is in Peter Cameron's article.

• Equality holds in exactly one other case: $n = 12$ and the subgroup is the Mathieu group $M_{12}$. – DavidLHarden Aug 1 '13 at 19:49

Wielandt was able to obtain an upper bound on $K(n)$ which grows logarithmically. He did this in (umlauts suppressed, and I hope I otherwise didn't screw this up)

Wielandt, H.: Abschatzungen fur den Grad einer Permutationsgruppe yon vorgeschriebenem Transitivitatsgrad. Dissertation, Berlin 1934. Schriften des Math. Seminars und des Instituts fur angew. Math. der Universitat Berlin 2, 151-174 (1934)

If you don't need asymptotic results, but only results which apply to small values of $n$, recall Jordan's theorem which says if $p$ is a prime, a primitive permutation group on $p+3$ or more points containing a $p$-cycle will contain the whole $A_{n}$. Then supplement that with information on gaps in the primes (for example, from A002386 in the OEIS) and you could be off to a good start.
To the extent you don't mind the analytic number theory needed to obtain effective upper bounds on ratios of consecutive primes, this method can give you bounds better than $K(n) < n/3$ for large enough $n$.

• Thanks for the answer, but I don't quite see how to show – Alex Aug 2 '13 at 10:55
• that a cycle of any order exists in a general multiply transitive group. Is there an easy way to do this? – Alex Aug 2 '13 at 11:01
• My point is that $K(n) \leq n-p$, if $p$ is a prime such that $p < n-2$. To prove this, suppose we had $K(n) > n-p$. Then an $n-p$-point stabilizer is transitive on the remaining $p$ points, so it contains a $p$-cycle. Jordan's Theorem applies so we conclude the group is $A_{n}$ or $S_{n}$. Of course, this means we apply the inequality with $p$ being the largest prime such that $p \leq n-3$. That means if $p$ isn't the largest prime satisfying $p \leq n$, $n-2$, $n-1$ or $n$ is prime. So we get transitivity degrees bounded from above by differences of consecutive primes plus 2. – DavidLHarden Aug 14 '13 at 3:19
• One more note: Using $p = 7$ with $n = 12$ or $p = 19$ with $n = 24$ establishes 5 as an upper bound on $K(12)$ and $K(24)$. Knowing the Mathieu groups establishes it as a lower bound, so we obtain $K(12) = K(24) = 5$. – DavidLHarden Aug 15 '13 at 12:15