Short presentations for alternating and symmetric groups
HTML articles powered by AMS MathViewer
- by J. N. Bray, M. D. E. Conder, C. R. Leedham-Green and E. A. O’Brien PDF
- Trans. Amer. Math. Soc. 363 (2011), 3277-3285 Request permission
Abstract:
We construct two kinds of presentations for the alternating and symmetric groups of degree $n$: the first are on two generators in which the number of relations is $O(\log n)$ and the presentation length is $O(\log ^2 n)$; the second have a bounded number of generators and relations and length $O(\log n)$.References
- L. Babai, A. J. Goodman, W. M. Kantor, E. M. Luks, and P. P. Pálfy, Short presentations for finite groups, J. Algebra 194 (1997), no. 1, 79–112. MR 1461483, DOI 10.1006/jabr.1996.6980
- L. Babai, W. M. Kantor, and A. Lubotsky, Small-diameter Cayley graphs for finite simple groups, European J. Combin. 10 (1989), no. 6, 507–522. MR 1022771, DOI 10.1016/S0195-6698(89)80067-8
- László Babai and Endre Szemerédi, On the complexity of matrix group problems, I. In Proc. $25$th IEEE Sympos. Foundations Comp. Sci., pages 229–240, 1984.
- László Babai, Randomization in group algorithms: conceptual questions, Groups and computation, II (New Brunswick, NJ, 1995) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, RI, 1997, pp. 1–17. MR 1444127
- Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger, and Ákos Seress, A black-box group algorithm for recognizing finite symmetric and alternating groups. I, Trans. Amer. Math. Soc. 355 (2003), no. 5, 2097–2113. MR 1953539, DOI 10.1090/S0002-9947-03-03040-X
- W. Burnside, Theory of groups of finite order, Dover Publications, Inc., New York, 1955. 2d ed. MR 0069818
- Colin M. Campbell, George Havas, Colin Ramsay, and Edmund F. Robertson, Nice efficient presentations for all small simple groups and their covers, LMS J. Comput. Math. 7 (2004), 266–283. MR 2118175, DOI 10.1112/S1461157000001121
- H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, 4th ed., Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], vol. 14, Springer-Verlag, Berlin-New York, 1980. MR 562913, DOI 10.1007/978-3-662-21943-0
- Hermann Frasch, Die Erzeugenden der Hauptkongruenzgruppen für Primzahlstufen, Math. Ann. 108 (1933), no. 1, 229–252 (German). MR 1512847, DOI 10.1007/BF01452835
- R. M. Guralnick, W. M. Kantor, M. Kassabov, and A. Lubotzky, Presentations of finite simple groups: a quantitative approach, J. Amer. Math. Soc. 21 (2008), no. 3, 711–774. MR 2393425, DOI 10.1090/S0894-0347-08-00590-0
- R.M. Guralnick, W.M. Kantor, M. Kassabov and A. Lubotzky, Presentations of finite simple groups: a computational approach. To appear J. European Math. Soc.
- Alexander Hulpke and Ákos Seress, Short presentations for three-dimensional unitary groups, J. Algebra 245 (2001), no. 2, 719–729. MR 1863898, DOI 10.1006/jabr.2001.8943
- G. A. Miller, Abstract Definitions of all the Substitution Groups Whose Degrees do not Exceed Seven, Amer. J. Math. 33 (1911), no. 1-4, 363–372. MR 1506130, DOI 10.2307/2369998
- E.H. Moore, Concerning the abstract groups of order $k!$ and $\frac {1}{2}\,k!$, Proc. London Math. Soc. 28 (1897), 357–366.
- E. A. O’Brien, Towards effective algorithms for linear groups, Finite geometries, groups, and computation, Walter de Gruyter, Berlin, 2006, pp. 163–190. MR 2258009
- Olivier Ramaré, On Šnirel′man’s constant, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) 22 (1995), no. 4, 645–706. MR 1375315
- Hartmut Sass, Eine abstrakte Definition gewisser alternierender Gruppen, Math. Z. 128 (1972), 109–113 (German). MR 323875, DOI 10.1007/BF01111472
- Charles C. Sims, Computation with finitely presented groups, Encyclopedia of Mathematics and its Applications, vol. 48, Cambridge University Press, Cambridge, 1994. MR 1267733, DOI 10.1017/CBO9780511574702
- J. G. Sunday, Presentations of the groups $\textrm {SL}(2,\,m)$ and $\textrm {PSL}(2,\,m)$, Canadian J. Math. 24 (1972), 1129–1131. MR 311782, DOI 10.4153/CJM-1972-118-x
- Michio Suzuki, On a class of doubly transitive groups, Ann. of Math. (2) 75 (1962), 105–145. MR 136646, DOI 10.2307/1970423
- J.A. Todd, A note on the linear fractional group. J. London Math. Soc. 7 (1932), 195–200.
- I. M. Vinogradov, The method of trigonometrical sums in the theory of numbers, Trav. Inst. Math. Stekloff 23 (1947), 109 (Russian). MR 0029417
Additional Information
- J. N. Bray
- Affiliation: School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United Kingdom
- M. D. E. Conder
- Affiliation: Department of Mathematics, University of Auckland, Auckland, New Zealand
- MR Author ID: 50940
- ORCID: 0000-0002-0256-6978
- C. R. Leedham-Green
- Affiliation: School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United Kingdom
- E. A. O’Brien
- Affiliation: Department of Mathematics, University of Auckland, Auckland, New Zealand
- MR Author ID: 251889
- Received by editor(s): September 21, 2009
- Received by editor(s) in revised form: October 1, 2009
- Published electronically: January 14, 2011
- Additional Notes: This work was supported in part by the Marsden Fund of New Zealand via grant UOA 0412. We thank Bob Guralnick and Bill Kantor for discussions on this topic in 2005. We thank the referee for detailed commentary, and George Havas and Igor Pak for their feedback. We are particularly grateful to Bill Kantor for his extensive and most helpful suggestions on drafts of this paper.
- © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 363 (2011), 3277-3285
- MSC (2000): Primary 20F05, 20B30
- DOI: https://doi.org/10.1090/S0002-9947-2011-05231-1
- MathSciNet review: 2775807