## Implementation and analysis of the Todd-Coxeter algorithm

HTML articles powered by AMS MathViewer

- by John J. Cannon, Lucien A. Dimino, George Havas and Jane M. Watson PDF
- Math. Comp.
**27**(1973), 463-490 Request permission

## Abstract:

A recent form of the Todd-Coxeter algorithm, known as the lookahead algorithm, is described. The time and space requirements for this algorithm are shown experimentally to be usually either equivalent or superior to the Felsch and Haselgrove-Leech-Trotter algorithms. Some findings from an experimental study of the behaviour of Todd-Coxeter programs in a variety of situations are given.## References

- M. J. Beetham,
*A set of generators and relations for the group $\textrm {PSL}(2,\,q),\,q$ odd*, J. London Math. Soc. (2)**3**(1971), 554–557. MR**285588**, DOI 10.1112/jlms/s2-3.3.554
A. Brunner, Personal communication.
- C. M. Campbell,
*Some examples using coset enumeration*, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 37–41. MR**0254131**
H. S. M. Coxeter, "The abstract groups ${R^m} = {S^m} = {({R^j}{S^j})^{{p_j}}} = 1,{S^m} = {T^2} = {({S^j}T)^{2pj}} = 1$ and ${S^m} = {T^2} = {({S^{ - j}}T{S^j}T)^{{p_j}}} = 1$," - H. S. M. Coxeter,
*The abstract groups $G^{m,n,p}$*, Trans. Amer. Math. Soc.**45**(1939), no. 1, 73–150. MR**1501984**, DOI 10.1090/S0002-9947-1939-1501984-9 - H. S. M. Coxeter and W. O. J. Moser,
*Generators and relations for discrete groups*, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957. MR**0088489**
L. A. Dimino, "A graphical approach to coset enumeration," - H. Felsch,
*Programmierung der Restklassenabzählung einer Gruppe nach Untergruppen*, Numer. Math.**3**(1961), 250–256 (German). MR**134435**, DOI 10.1007/BF01386025
M. J. T. Guy, - Graham Higman and John McKay,
*On Janko’s simple group of order $50,232,960$*, Bull. London Math. Soc.**1**(1969), 89–94; correction, ibid. 1 (1969), 219. MR**246955**, DOI 10.1112/blms/1.1.89 - John Leech,
*Coset enumeration on digital computers*, Proc. Cambridge Philos. Soc.**59**(1963), 257–267. MR**146994**, DOI 10.1017/s0305004100036872 - John Leech,
*Generators for certain normal subgroups of $(2,\,3,\,7)$*, Proc. Cambridge Philos. Soc.**61**(1965), 321–332. MR**174621**, DOI 10.1017/s0305004100003923 - John Leech,
*Coset enumeration*, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 21–35. MR**0254133** - John Leech,
*Note on a conjecture of Coxeter*, Proc. Glasgow Math. Assoc.**5**(1960), 25–29 (1961) (French). MR**150193** - I. D. Macdonald,
*On a class of finitely presented groups*, Canadian J. Math.**14**(1962), 602–613. MR**140574**, DOI 10.4153/CJM-1962-051-5 - John McKay and David Wales,
*The multipliers of the simple groups of order $604,800$ and $50,232,960$*, J. Algebra**17**(1971), 262–272. MR**274577**, DOI 10.1016/0021-8693(71)90033-0 - N. S. Mendelsohn,
*An algorithmic solution for a word problem in group theory*, Canadian J. Math.**16**(1964), 509–516. MR**163949**, DOI 10.4153/CJM-1964-052-3 - Dietmar Garbe and Jens L. Mennicke,
*Some remarks on the Mathieu groups*, Canad. Math. Bull.**7**(1964), 201–212. MR**162846**, DOI 10.4153/CMB-1964-018-3
B. H. Neumann, Personal communication.
J. A. Todd & H. S. M. Coxeter, "A practical method for enumerating cosets of a finite abstract group," - H. F. Trotter,
*A machine program for coset enumeration*, Canad. Math. Bull.**7**(1964), 357–368. MR**168151**, DOI 10.4153/CMB-1964-033-x
J. M. Watson,

*Proc. London Math. Soc.*(2), v. 41, 1936, pp. 278-301.

*SIGSAM Bulletin*, v. 19, 1971, pp. 8-43.

*Coset Enumeration*, Lecture delivered at the Conference on Computational Problems in Abstract Algebra, Oxford, 29 August-2 September, 1967.

*Proc. Edinburgh Math. Soc.*, v. 5, 1936, pp. 26-34.

*An Extended Todd-Coxeter Algorithm*, Department of Mathematics, Institute of Advanced Studies, Australian National University, Canberra, 1971, 15 pages.

## Additional Information

- © Copyright 1973 American Mathematical Society
- Journal: Math. Comp.
**27**(1973), 463-490 - MSC: Primary 20-04
- DOI: https://doi.org/10.1090/S0025-5718-1973-0335610-5
- MathSciNet review: 0335610