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.

Description of the algorithm

is a set of generators is a set of relations. Information is gradually added to these tables, and once they are filled in, all cosets have been enumerated and the algorithm terminates.

denote the coset of the i denote generator of the jth column. The entry of the coset table in row i, column j is defined to be (if known) k, where k.

, as in the coset table. It has t columns, and the entry in the ith row and jth column is defined to be (if known) k'th entry is initially i.

itself. It has t columns, and the entry in the jth column is defined (if known) to be k. In particular, the last entry is H.

, is found. This is known as a deduction.

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. We replace all instances of j in the tables with i. Then, we fill in all possible entries of the tables, possibly leading to more deductions and coincidences.

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 is finite.)

.

See also

• Coxeter group

References