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 and hence for determining all transitive permutation representations of 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 . Significant recent applications of these are also described in some detail.

**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 -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 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*, 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 -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,`http://www.math.auckland.ac.nz/~peter`.**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*, 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**

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

Email:
conder@math.auckland.ac.nz

**Peter Dobcsányi**

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

Email:
peter@math.auckland.ac.nz

DOI:
http://dx.doi.org/10.1090/S0025-5718-04-01647-3

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