A coset enumeration algorithm that computes the action of a finitely presented group on the cosets of a specified subgroup by building a coset table, identifying cosets via relators, and thereby determining the index of the subgroup and a permutation representation when the enumeration terminates finitely.

Principle

Systematically create and extend a table of coset representatives, apply generators and relators to deduce identifications and coincidences, and close the table by propagating consequences until either the table stabilizes (finite index found) or the process grows without bound (likely infinite index or impractical complexity).

Demonstration

Given a group presentation and a subgroup H generated by a finite set, start with the coset H as coset 1, apply generators to produce new coset names and impose relators to force identifications; record these in the coset table. If the process terminates with a finite fully consistent table, the number of cosets gives the index [G:H] and the action of generators on coset names yields a permutation representation.

Misapplication

Attempting naive Todd–Coxeter enumeration when the subgroup has infinite index, or failing to implement coincidence processing or proper closure rules, leads to nontermination or incorrect tables; interpreting a partial table as complete without verifying closure is a common mistake.

Consequence

When successful, the algorithm yields the subgroup index, an explicit permutation representation of G on the cosets, and often a practical tool for computing subgroup structure, but success depends on finiteness and computational resources.

Reversal

The inverse problem—recovering a presentation from a given permutation representation—is possible but different in nature (it may require Reidemeister–Schreier or coset stabilizer methods); Todd–Coxeter enumerates cosets, it does not directly produce minimal presentations.

Boundary

Applicable to finitely presented groups and subgroups given by generators; effectiveness requires that the subgroup has finite index or that truncation heuristics are acceptable. It is not guaranteed to terminate for infinite-index subgroups and can be computationally expensive even when index is finite but large.

Semantic Tension

Often contrasted with Reidemeister–Schreier (which produces subgroup presentations) and with low-index subgroup enumeration strategies; tension arises in choosing between enumerating cosets to obtain permutation actions and constructing explicit subgroup presentations.

Synthesis

The Todd–Coxeter Algorithm is a systematic coset-enumeration procedure that builds and closes a coset table via generators and relators to determine subgroup index and produce permutation representations when enumeration terminates; it is powerful for finite-index problems but limited by nontermination and computational cost in challenging cases.