3
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think you mean "classification of finite simple groups" (not of "finite groups")... $\endgroup$
    – Arturo Magidin
    Aug 1, 2013 at 16:12
  • $\begingroup$ 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. $\endgroup$
    – Alex
    Aug 2, 2013 at 11:06
  • 1
    $\begingroup$ @Alex: Comments on the own question are not the right way to raise new questions. $\endgroup$
    – Peter Mueller
    Aug 2, 2013 at 12:47

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Equality holds in exactly one other case: $n = 12$ and the subgroup is the Mathieu group $M_{12}$. $\endgroup$
    – DavidLHarden
    Aug 1, 2013 at 19:49
3
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the answer, but I don't quite see how to show $\endgroup$
    – Alex
    Aug 2, 2013 at 10:55
  • $\begingroup$ that a cycle of any order exists in a general multiply transitive group. Is there an easy way to do this? $\endgroup$
    – Alex
    Aug 2, 2013 at 11:01
  • $\begingroup$ 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. $\endgroup$
    – DavidLHarden
    Aug 14, 2013 at 3:19
  • $\begingroup$ 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$. $\endgroup$
    – DavidLHarden
    Aug 15, 2013 at 12:15

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.