Todd–Coxeter algorithm

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. 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 ${\displaystyle G=\langle X\mid R\rangle }$, where ${\displaystyle X}$ is a set of generators and ${\displaystyle R}$ is a set of relations and denote by ${\displaystyle X'}$ the set of generators ${\displaystyle X}$ and their inverses. Let ${\displaystyle H=\langle h_{1},h_{2},\ldots ,h_{s}\rangle }$ where the ${\displaystyle h_{i}}$ are words of elements of ${\displaystyle X'}$. There are three types of tables that will be used: a coset table, a relation table for each relation in ${\displaystyle R}$, and a subgroup table for each generator ${\displaystyle h_{i}}$ of ${\displaystyle H}$. Information is gradually added to these tables, and once they are filled in, all cosets have been enumerated and the algorithm terminates.

...
Wikipedia