Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Short presentations for alternating and symmetric groups


Authors: J. N. Bray, M. D. E. Conder, C. R. Leedham-Green and E. A. O’Brien
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
Published electronically: January 14, 2011
MathSciNet review: 2775807
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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), 79-112. MR 1461483 (98h:20044)
  • 2. L. Babai, W.M. Kantor and A. Lubotzky, Small-diameter Cayley graphs for finite simple groups. European J. Combin. 10 (1989), no. 6, 507-522. MR 1022771 (91a:20038)
  • 3. 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.
  • 4. László Babai, Randomization in group algorithms: conceptual questions. Groups and Computation, II (New Brunswick, NJ, 1995), 1-17, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 28, Amer. Math. Soc., Providence, RI, 1997. MR 1444127 (98k:68092)
  • 5. 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), 2097-2113. MR 1953539 (2003k:20002)
  • 6. W. Burnside,
    Theory of Groups of Finite Order, 2nd ed.,
    Dover Publications, Inc., New York, 1955, xxiv+512 pp. MR 0069818 (16:1086c)
  • 7. C.M. Campbell, G. Havas, C. Ramsay, and E.F. Robertson,
    Nice efficient presentations for all small simple groups and their covers.
    London Math. Soc. J. Comput. Math. 7 (2004), 266-283. MR 2118175 (2006g:20046)
  • 8. H.S.M. Coxeter and W.O.J. Moser,
    Generators and Relations for Discrete Groups, 4th ed.,
    Springer-Verlag (Berlin), 1980, ix+169 pp. MR 562913 (81a:20001)
  • 9. H. Frasch, Die Erzeugenden der Hauptkongruenzgruppen für Primzahlstufen. Math. Ann. 108 (1933), 229-252. MR 1512847
  • 10. 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), 711-774. MR 2393425
  • 11. 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.
  • 12. Alexander Hulpke and Ákos Seress,
    Short presentations for three-dimensional unitary groups.
    J. Algebra, 245 (2001), 719-729. MR 1863898 (2002m:20079)
  • 13. G. A. Miller,
    Abstract definitions of all the substitution groups whose degrees do not exceed seven,
    Amer. J. Math. 33 (1911), 363-372. MR 1506130
  • 14. E.H. Moore,
    Concerning the abstract groups of order $ k!$ and $ \frac{1}{2} k!$,
    Proc. London Math. Soc. 28 (1897), 357-366.
  • 15. E.A. O'Brien,
    Towards effective algorithms for linear groups.
    Finite Geometries, Groups and Computation, Colorado, September, 2004. De Gruyter, Berlin, 163-190, 2006. MR 2258009 (2008c:20022)
  • 16. O. Ramaré,
    On Šnirelman's constant.
    Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) 22 (1995), 645-706. MR 1375315 (97a:11167)
  • 17. Hartmut Sass, Eine abstrakte Definition gewisser alternierender Gruppen. Math. Z. 128 (1972), 109-113. MR 0323875 (48:2228)
  • 18. Charles C. Sims,
    Computation with finitely presented groups.
    Cambridge University Press, 1994, xiii+604 pp. MR 1267733 (95f:20053)
  • 19. J.G. Sunday,
    Presentations of the groups $ \operatorname{SL}(2,m)$ and $ \operatorname{PSL}(2,m)$.
    Canad. J. Math. 24 (1972), 1129-1131. MR 0311782 (47:344)
  • 20. Michio Suzuki,
    On a class of doubly transitive groups.
    Ann. of Math. (2) 75 (1962), 105-145. MR 0136646 (25:112)
  • 21. J.A. Todd,
    A note on the linear fractional group.
    J. London Math. Soc. 7 (1932), 195-200.
  • 22. I.M. Vinogradov,
    The method of trigonometrical sums in the theory of numbers (Russian).
    Trav. Inst. Math. Stekloff 23 (1947), 109 pp. MR 0029417 (10:599a)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20F05, 20B30

Retrieve articles in all journals with MSC (2000): 20F05, 20B30


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

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

DOI: https://doi.org/10.1090/S0002-9947-2011-05231-1
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.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society