In group theory, the Todd–Coxeter algorithm, created by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group G by generators and relations and a subgroup H of G, the algorithm enumerates the cosets of H on G and describes the permutation representation of G on the space of the cosets (given by the left multiplication action). If the order of a group G is relatively small and the subgroup H is known to be uncomplicated (for example, a cyclic group), then the algorithm can be carried out by hand and gives a reasonable description of the group G. Using their algorithm, Coxeter and Todd showed that certain systems of relations between generators of known groups are complete, i.e. constitute systems of defining relations.
The Todd–Coxeter algorithm can be applied to infinite groups and is known to terminate in a finite number of steps, provided that the index of H in G is finite. On the other hand, for a general pair consisting of a group presentation and a subgroup, its running time is not bounded by any computable function of the index of the subgroup and the size of the input data.
One implementation of the algorithm proceeds as follows. Suppose that
G=\langleX\midR\rangle
X
R
X'
X
H=\langleh1,h2,\ldots,hs\rangle
hi
X'
R
hi
H
The coset table is used to store the relationships between the known cosets when multiplying by a generator. It has rows representing cosets of
H
X'
Ci
gj\inX'
Ck=Cigj
The relation tables are used to detect when some of the cosets we have found are actually equivalent. One relation table for each relation in
R
1=
g | |
n1 |
g | |
n2 |
…
g | |
nt |
R
g | |
ni |
\inX'
H
Ck=Ci
g | |
n1 |
g | |
n2 |
…
g | |
nj |
(i,t)
g | |
n1 |
g | |
n2 |
…
g | |
nt |
=1
Finally, the subgroup tables are similar to the relation tables, except that they keep track of possible relations of the generators of
H
hn=
g | |
n1 |
g | |
n2 |
…
g | |
nt |
H
g | |
ni |
\inX'
H
Ck=H
g | |
n1 |
g | |
n2 |
…
g | |
nj |
When a row of a relation or subgroup table is completed, a new piece of information
Ci=Cjg
g\inX'
Ci=Cjg
Cj=Cig-1
However, when filling in the coset table, it is possible that we may already have an entry for the equation, but the entry has a different value. In this case, we have discovered that two of our cosets are actually the same, known as a coincidence. Suppose
Ci=Cj
i<j
If there are empty entries in the table after all deductions and coincidences have been taken care of, add a new coset to the tables and repeat the process. We make sure that when adding cosets, if Hx is a known coset, then Hxg will be added at some point for all
g\inX'
|G:H|
When all the tables are filled, the algorithm terminates. We then have all needed information on the action of
G
H