Pairwise Generating Sets for the Symmetric and Alternating Groups

by Linda Stringer

RHUL-MA-2009-14

Abstract:

For all sufficiently large odd integers n, there exists a set of 2^{n-1} permutations
that pairwise generate the symmetric group S_n, and there is no larger set
having this property. This was proved by Blackburn in 2006. He proved a
similar result for A_n, that is, for all sufficiently large even integers n such that
n \equiv 2 (mod 4), there exists a set of 2^{n-2} permutations that pairwise generate
the symmetric group A_n, and there is no larger set having this property. We
give explicit versions of these results. We prove that the result for S_n holds
for all odd integers n except for 5, 9 and possibly 15. We prove that the result
for A_n holds for all even integers n such that n \equiv 2 (mod 4), except for 6 and
possibly 10, 14 and 18.

For n \geq 21, our proofs extend and refine the proofs given by Blackburn;
we use a similar probabilistic method. Whereas those proofs use an asymptotic upper
bound for the number of conjugacy classes of primitive maximal subgroups of S_n, we determine and use an explicit upper bound. Also, we develop theory concerning
imprimitive maximal subgroups of S_n which we use in GAP programs, and we use
detailed information about primitive maximal subgroups of S_n which we obtain from
the GAP data library. For n < 21 we use constructive proofs.

We also answer the following question of Mar\'oti in the affirmative: For
all sufficiently large integers n, does there exist a set of n^3 permutations that
pairwise generate A_n ? In fact we prove a stronger result for most values of n.