Linda Stringer (2009) Pairwise Generating Sets for the Symmetric and Alternating Groups.
Full text access: Open
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.
This is a Published version This version's date is: 23/04/2009 This item is peer reviewed
https://repository.royalholloway.ac.uk/items/d5534922-fe82-7e15-5267-3bc2e0aebb41/1/
Deposited by () on 24-Jun-2010 in Royal Holloway Research Online.Last modified on 15-Dec-2010
[1] Noga Alon and Joel H. Spencer, The probabilistic method, second ed.,Wiley-Interscience Series in Discrete Mathematics and Optimization,Wiley-Interscience [John Wiley & Sons], New York, 2000, With an ap-pendix on the life and work of Paul Erd}os. MR MR1885388 (2003f:60003)
[2] Simon R. Blackburn, Sets of permutations that generate the symmetricgroup pairwise, J. Combin. Theory Ser. A 113 (2006), no. 7, 1572{1581.MR MR2259081 (2007e:20005)
[3] Peter J. Cameron, Peter M. Neumann, and David N. Teague, On thedegrees of primitive permutation groups, Math. Z. 180 (1982), no. 2, 141{149. MR MR661693 (83i:20004)
[4] J. H. E. Cohn, On n-sum groups, Math. Scand. 75 (1994), no. 1, 44{58.MR MR1308936 (95k:20026)
[5] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson,Atlas of ¯nite groups, Oxford University Press, Eynsham, 1985, Maximalsubgroups and ordinary characters for simple groups, With computationalassistance from J. G. Thackray. MR MR827219 (88g:20025)
[6] Bruce N. Cooperstein, Minimal degree for a permutation representationof a classical group, Israel J. Math. 30 (1978), no. 3, 213{235. MRMR0506701 (58 #22255)
[7] John D. Dixon and Brian Mortimer, Permutation groups, GraduateTexts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MRMR1409812 (98m:20003)
[8] Walter Feit and John G. Thompson, Solvability of groups of odd order,Paci¯c J. Math. 13 (1963), 775{1029. MR MR0166261 (29 #3538)
[9] Robert M. Guralnick, Subgroups of prime power index in a simple group,J. Algebra 81 (1983), no. 2, 304{311. MR MR700286 (84m:20007)
[10] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers,Oxford, at the Clarendon Press, 1954, 3rd ed. MR MR0067125 (16,673c)
[11] Wolfgang Kimmerle, Richard Lyons, Robert Sandling, and David N.Teague, Composition factors from the group ring and Artin's theorem onorders of simple groups, Proc. London Math. Soc. (3) 60 (1990), no. 1,89{122. MR MR1023806 (91c:20030)
[12] Peter Kleidman and Martin Liebeck, The subgroup structure of the ¯-nite classical groups, London Mathematical Society Lecture Note Series,vol. 129, Cambridge University Press, Cambridge, 1990. MR MR1057341(91g:20001)
[13] Martin W. Liebeck, Cheryl E. Praeger, and Jan Saxl, A classi¯cation ofthe maximal subgroups of the ¯nite alternating and symmetric groups, J.Algebra 111 (1987), no. 2, 365{383. MR MR916173 (89b:20008)
[14] Martin W. Liebeck and Jan Saxl, Maximal subgroups of ¯nite simplegroups and their automorphism groups, Proceedings of the InternationalConference on Algebra, Part 1 (Novosibirsk, 1989) (Providence, RI),Contemp. Math., vol. 131, Amer. Math. Soc., 1992, pp. 243{259. MRMR1175777 (93g:20032)
[15] Martin W. Liebeck and Aner Shalev, Maximal subgroups of symmet-ric groups, J. Combin. Theory Ser. A 75 (1996), no. 2, 341{352. MRMR1401008 (98b:20005)
[16] , Simple groups, permutation groups, and probability, J. Amer.Math. Soc. 12 (1999), no. 2, 497{520. MR MR1639620 (99h:20004)
[17] Attila Mar¶oti, On the orders of primitive groups, J. Algebra 258 (2002),no. 2, 631{640. MR MR1943938 (2003j:20004)
[18] , Covering the symmetric groups with proper subgroups, J. Combin.Theory Ser. A 110 (2005), no. 1, 97{111. MR MR2128968 (2005m:20009)
[19] E. T. Whittaker and G. N. Watson, A course of modern analysis. An in-troduction to the general theory of in¯nite processes and of analytic func-tions: with an account of the principal transcendental functions, Fourthedition. Reprinted, Cambridge University Press, New York, 1962. MRMR0178117 (31 #2375)
[20] Robert A. Wilson, The ¯nite simple groups, In preparation. Version 077available on line at www.maths.qmul.ac.uk, 2007.