Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Applications and adaptations of the low index subgroups procedure

Authors: Marston Conder and Peter Dobcsányi
Journal: Math. Comp. 74 (2005), 485-497
MSC (2000): Primary 20-04, 20F05
Published electronically: May 7, 2004
MathSciNet review: 2085903
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The low-index subgroups procedure is an algorithm for finding all subgroups of up to a given index in a finitely presented group $G$ and hence for determining all transitive permutation representations of $G$ of small degree. A number of significant applications of this algorithm are discussed, in particular to the construction of graphs and surfaces with large automorphism groups. Furthermore, three useful adaptations of the procedure are described, along with parallelisation of the algorithm. In particular, one adaptation finds all complements of a given finite subgroup (in certain contexts), and another finds all normal subgroups of small index in the group $G$. Significant recent applications of these are also described in some detail.

References [Enhancements On Off] (What's this?)

  • 1. W. Bosma and J. J. Cannon, Handbook of Magma Functions, University of Sydney, 1996.
  • 2. J. J. Cannon, L. A. Dimino, G. Havas and J. M. Watson, Implementation and analysis of the Todd-Coxeter algorithm, Mathematics of Computation 27 (1973), 463-490. MR 49:390
  • 3. M. D. E. Conder, An infinite family of $5$-arc-transitive cubic graphs, Ars Combinatoria 25A (1988), 95-108. MR 89f:05092
  • 4. M. D. E. Conder, The symmetric genus of the Mathieu groups, Bull. London Math. Soc. 23 (1991), 445-453. MR 92k:20023
  • 5. M. D. E. Conder, Asymmetric combinatorially regular maps, J. Algebraic Combinatorics 5 (1996), 323-328. MR 97h:57006
  • 6. M. D. E. Conder and P. Dobcsányi, Normal subgroups of low index in the modular group and other Hecke groups, University of Auckland Mathematics Department Research Report Series, No. 496, 23 pp., 2003.
  • 7. M. D. E. Conder and P. Dobcsányi, Determination of all regular maps of small genus, J. Combinatorial Theory, Series B 81 (2001), 224-242. MR 2002f:05088
  • 8. M. D. E. Conder and P. Dobcsányi, Trivalent symmetric graphs on up to $768$ vertices, J. Combinatorial Mathematics and Combinatorial Computing, 40 (2002), 41-63. MR 2002m:05105
  • 9. M. D. E. Conder and B. J. Everitt, Regular maps on non-orientable surfaces, Geometriae Dedicata 56 (1995), 209-219. MR 96g:05046
  • 10. M. D. E. Conder and P. J. Lorimer, Automorphism groups of symmetric graphs of valency $3$, J. Combinatorial Theory Ser. B 47 (1989), 60-72. MR 90g:05097
  • 11. M. D. E. Conder, C. Maclachlan, S. Todorovic-Vasiljevic and S. E. Wilson, Bounds for the number of automorphisms of a compact non-orientable surface, J. London Math. Soc. 68 (2003), 65-82.
  • 12. M. D. E. Conder and G. J. Martin, Cusps, triangle groups and hyperbolic $3$-folds, J. Austral. Math. Soc. (Series A) 55 (1993), 149-182. MR 94e:57018
  • 13. H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups, 4th ed., Springer-Verlag (Berlin), 1980. MR 81a:20001
  • 14. A. Dietze and M. Schaps, Determining subgroups of a given finite index in a finitely presented group, Canadian J. Mathematics 26 (1974), 769-782. MR 53:10942
  • 15. P. Dobcsányi, Adaptations, Parallelisation and Applications of the Low-index Subgroups Algorithm, PhD thesis, University of Auckland, 142 pp., 1999.
  • 16. P. Dobcsányi, home page,
  • 17. B. J. Everitt, Images of Hyperbolic Reflection Groups, PhD thesis, University of Auckland, 153 pp., 1994.
  • 18. G. Havas, A Reidemeister-Schreier program, Proc. Second International Conference on the Theory of Groups, Canberra 1973 (Lect. Notes in Math. 372, Springer-Verlag, 1974), 347-356. MR 51:13002
  • 19. D. F. Holt and W. Plesken, A cohomological criterion for a finitely presented group to be infinite, J. London Math. Soc. 45 (1992), 469-480. MR 94c:20057
  • 20. D. L. Johnson, Presentations of Groups, Cambridge University Press, 1990. MR 91h:20001
  • 21. P. J. Lorimer, Hyperbolic pyritohedra constructed from the Coxeter group $[4,3,5]$, Computational Algebra and Number Theory (Sydney, 1992), Kluwer, 1995, 303-321. MR 96d:20037
  • 22. J. Neubüser, An elementary introduction to coset-table methods in computational group theory, Groups - St. Andrews 1981, London Math. Soc. Lecture Note Series, vol. 71, 1982, pp. 1-45. MR 84f:20004
  • 23. C. C. Sims, Computation with Finitely Presented Groups (Cambridge University Press, 1994). MR 95f:20053

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 20-04, 20F05

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

Additional Information

Marston Conder
Affiliation: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

Peter Dobcsányi
Affiliation: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

Keywords: Finitely presented groups, algorithms, low index subgroups
Received by editor(s): July 25, 2000
Received by editor(s) in revised form: June 16, 2003
Published electronically: May 7, 2004
Article copyright: © Copyright 2004 American Mathematical Society