Implementation and analysis of the ToddCoxeter algorithm
Authors:
John J. Cannon, Lucien A. Dimino, George Havas and Jane M. Watson
Journal:
Math. Comp. 27 (1973), 463490
MSC:
Primary 2004
MathSciNet review:
0335610
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A recent form of the ToddCoxeter 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 HaselgroveLeechTrotter algorithms. Some findings from an experimental study of the behaviour of ToddCoxeter programs in a variety of situations are given.
 [1]
M.
J. Beetham, A set of generators and relations for the group
𝑃𝑆𝐿(2,𝑞),𝑞 odd, J. London
Math. Soc. (2) 3 (1971), 554–557. MR 0285588
(44 #2806)
 [2]
A. Brunner, Personal communication.
 [3]
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
(40 #7341)
 [4]
H. S. M. Coxeter, "The abstract groups and ," Proc. London Math. Soc. (2), v. 41, 1936, pp. 278301.
 [5]
H.
S. M. Coxeter, The abstract groups
𝐺^{𝑚,𝑛,𝑝}, Trans. Amer. Math. Soc. 45 (1939), no. 1, 73–150. MR
1501984, http://dx.doi.org/10.1090/S00029947193915019849
 [6a,b]
H.
S. M. Coxeter and W.
O. J. Moser, Generators and relations for discrete groups,
SpringerVerlag, Berlin, 1957. MR 0088489
(19,527d)
 [7]
L. A. Dimino, "A graphical approach to coset enumeration," SIGSAM Bulletin, v. 19, 1971, pp. 843.
 [8]
H.
Felsch, Programmierung der Restklassenabzählung einer Gruppe
nach Untergruppen, Numer. Math. 3 (1961),
250–256 (German). MR 0134435
(24 #B488)
 [9]
M. J. T. Guy, Coset Enumeration, Lecture delivered at the Conference on Computational Problems in Abstract Algebra, Oxford, 29 August2 September, 1967.
 [10]
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 0246955
(40 #224)
 [11]
John
Leech, Coset enumeration on digital computers, Proc. Cambridge
Philos. Soc. 59 (1963), 257–267. MR 0146994
(26 #4513)
 [12]
John
Leech, Generators for certain normal subgroups of (2,3,7),
Proc. Cambridge Philos. Soc. 61 (1965), 321–332. MR 0174621
(30 #4821)
 [13]
John
Leech, Coset enumeration, Computational Problems in Abstract
Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970,
pp. 21–35. MR 0254133
(40 #7343)
 [14]
John
Leech, Note on a conjecture of Coxeter, Proc. Glasgow Math.
Assoc. 5 (1960), 25–29 (1961) (French). MR 0150193
(27 #196)
 [15]
I.
D. Macdonald, On a class of finitely presented groups, Canad.
J. Math. 14 (1962), 602–613. MR 0140574
(25 #3992)
 [16]
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 0274577
(43 #340)
 [17]
N.
S. Mendelsohn, An algorithmic solution for a word problem in group
theory, Canad. J. Math. 16 (1964), 509–516. MR 0163949
(29 #1248)
 [18]
Dietmar
Garbe and Jens
L. Mennicke, Some remarks on the Mathieu groups, Canad. Math.
Bull. 7 (1964), 201–212. MR 0162846
(29 #150)
 [19]
B. H. Neumann, Personal communication.
 [20]
J. A. Todd & H. S. M. Coxeter, "A practical method for enumerating cosets of a finite abstract group," Proc. Edinburgh Math. Soc., v. 5, 1936, pp. 2634.
 [21]
H.
F. Trotter, A machine program for coset enumeration, Canad.
Math. Bull. 7 (1964), 357–368. MR 0168151
(29 #5415)
 [22]
J. M. Watson, An Extended ToddCoxeter Algorithm, Department of Mathematics, Institute of Advanced Studies, Australian National University, Canberra, 1971, 15 pages.
 [1]
 M. J. Beetham, "A set of generators and relations for the groups , q odd," J. London Math. Soc., v. 3, 1971, pp. 544557. MR 44 #2806. MR 0285588 (44:2806)
 [2]
 A. Brunner, Personal communication.
 [3]
 C. M. Campbell, "Some examples using coset enumeration," in Computational Problems in Abstract Algebra (Edited by John Leech), Pergamon Press, New York, 1970, pp. 3741. MR 40 #7341. MR 0254131 (40:7341)
 [4]
 H. S. M. Coxeter, "The abstract groups and ," Proc. London Math. Soc. (2), v. 41, 1936, pp. 278301.
 [5]
 H. S. M. Coxeter, "The abstract groups ," Trans. Amer. Math. Soc., v. 45, 1939, pp. 73150. MR 1501984
 [6a,b]
 H. S. M. Coxeter & W. O. J. Moser, Generators and Relations for Discrete Groups, SpringerVerlag, Berlin, 1957; 2nd ed., Ergebnisse der Mathematik und ihrer Grenzgebiete, Neue Folge, Band 14, SpringerVerlag, Berlin and New York, 1965. MR 19, 527; MR 30 #4818. MR 0088489 (19:527d)
 [7]
 L. A. Dimino, "A graphical approach to coset enumeration," SIGSAM Bulletin, v. 19, 1971, pp. 843.
 [8]
 H. Felsch, "Programmierung der Restklassenabzählung einer Gruppe nach Untergruppen," Numer. Math., v. 3, 1961, pp. 250256. MR 24 #B488. MR 0134435 (24:B488)
 [9]
 M. J. T. Guy, Coset Enumeration, Lecture delivered at the Conference on Computational Problems in Abstract Algebra, Oxford, 29 August2 September, 1967.
 [10]
 G. Higman & J. McKay, "On Janko's simple group of order 50,232,960," Bull. London Math. Soc., v. 1, 1969, pp. 8994. MR 40 #224. MR 0246955 (40:224)
 [11]
 J. Leech, "Coset enumeration on digital computers," Proc. Cambridge Philos. Soc., v. 59, 1963, pp. 257267. MR 26 #4513. MR 0146994 (26:4513)
 [12]
 J. Leech, "Generators for certain normal subgroups of (2,3,7)," Proc. Cambridge Philos. Soc., v. 61, 1965, pp. 321332. MR 30 #4821. MR 0174621 (30:4821)
 [13]
 J. Leech, "Coset enumeration," in Computational Problems in Abstract Algebra (Edited by John Leech), Pergamon Press, New York and Oxford, 1970, pp. 2135. MR 40 #7343. MR 0254133 (40:7343)
 [14]
 J. Leech & J. Mennicke, "Note on a conjecture of Coxeter," Proc. Glasgow Math. Assoc., v. 5, 1961, pp. 2529. MR 27 #196. MR 0150193 (27:196)
 [15]
 I. D. Macdonald, "On a class of finitely presented groups," Canad. J. Math., v. 14, 1962, pp. 602613. MR 25 #3992. MR 0140574 (25:3992)
 [16]
 J. McKay & D. Wales, "The multipliers of the simple groups of order 604,800 and 50,232,960," J. Algebra, v. 17, 1971, pp. 262272. MR 43 #340. MR 0274577 (43:340)
 [17]
 N. S. Mendelsohn, "An algorithmic solution for a word problem in group theory," Canad. J. Math., v. 16, 1964, pp. 509516; Correction, Canad. J. Math., v. 17, 1965, p. 505. MR 29 #1248; 31 #237. MR 0163949 (29:1248)
 [18]
 J. L. Mennicke & D. Garbe, "Some remarks on the Mathieu groups," Canad. Math. Bull., v. 7, 1964, pp. 201212. MR 29 #150. MR 0162846 (29:150)
 [19]
 B. H. Neumann, Personal communication.
 [20]
 J. A. Todd & H. S. M. Coxeter, "A practical method for enumerating cosets of a finite abstract group," Proc. Edinburgh Math. Soc., v. 5, 1936, pp. 2634.
 [21]
 H. F. Trotter, "A machine program for coset enumeration," Canad. Math. Bull., v. 7, 1964, pp. 357368; Program listing in Mathematical Algorithms, v. 1, 1966, pp. 1218. MR 29 #5415. MR 0168151 (29:5415)
 [22]
 J. M. Watson, An Extended ToddCoxeter Algorithm, Department of Mathematics, Institute of Advanced Studies, Australian National University, Canberra, 1971, 15 pages.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
2004
Retrieve articles in all journals
with MSC:
2004
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197303356105
PII:
S 00255718(1973)03356105
Keywords:
ToddCoxeter algorithm,
generators and relations,
group theory
Article copyright:
© Copyright 1973 American Mathematical Society
