4. The Todd-Coxeter Coset Enumeration Procedure

Todd-Coxeter coset enumeration (TC) is a famous method from combinatorial group theory for studying finitely presented groups. It is based on the following fundamental observations: Presenting a group ${\cal G}$ in terms of generators $\Sigma$ and relators R corresponds to viewing it as the quotient of the free group ${\cal F}$ (generated by $\Sigma$) by the normal subgroup $\mathcal{N}$ generated by R. $\mathcal{N}$ can be viewed as the subgroup of ${\cal F}$ generated by $N(R) = \{ w \circ r \circ w^{-1} \mid w \in {\cal F}, r \in R \}$. Notice that if R is finite, $\mathcal{N}$, while finitely generated as a normal subgroup of ${\cal F}$, need not be finitely generated as a subgroup.

Now given a subgroup ${\cal H}$ of ${\cal G}$ generated by a set $S \subseteq {\cal G}$ the index of ${\cal H}$ in ${\cal G}$ is the same as the index of the subgroup $\mathcal{U}$ generated by $S \cup N(R)$ in ${\cal F}$. While it is undecidable whether a subgroup has finite index in a group, TC attempts to verify whether the index is finite.

In the following we will always assume that the group ${\cal G}$ and the subgroup ${\cal H}$ are finitely presented respectively generated, i.e. the sets $\Sigma$, R and S are finite. Detailed descriptions of TC procedures can be found e. g. in [11,3,15]. We only list some of the properties and their interpretations here: If the index of ${\cal H}$ in ${\cal G}$ is finite the procedure halts and produces a set of coset representatives and a coset table with entries $c \circ a$ for each coset c and each $a \in\bar{\Sigma}$. The (unique) coset representative for any word in $\bar{\Sigma}^*$ can be computed by tracing it through the coset table starting with $\lambda$. Moreover, given a total well-founded ordering > on $\bar{\Sigma}^*$ which is additionally compatible with right concatenation, we can associate to each coset c the representative $w \in \bar{\Sigma}^*$ of minimal length⁴. The coset table gives rise to a convergent prefix string rewriting system as follows: To each coset w, each $a \in\bar{\Sigma}$ and the respective coset w_a corresponding to $w \circ a$, associate a rule⁵ of the form $wa \longrightarrow w_a$. This prefix string rewriting system then can be used to determine the coset of a word in $\bar{\Sigma}^*$ by prefix reduction.

Let us illustrate these findings with an example from [3], page 71:

Example 2   Let ${\cal G}$ be the Dyck group D(3,3,2) presented by $\Sigma = \{ a,b \}$ and $R = \{ aaa, bbb, abab \}$, and ${\cal H}$ the subgroup of ${\cal G}$ generated by $\{ a \}$. The index of ${\cal H}$ in ${\cal G}$ is 4 and TC (using the length lexicographical ordering induced by $a \prec b \prec a^{-1} \prec b^{-1}$) computes the coset representatives $\{ \lambda, b, b^{-1}, ba^{-1} \}$ and the coset table

	a	b	a-1	b-1
$\lambda$	$\lambda$	b	$\lambda$	b-1
b	b-1	b-1	ba-1	$\lambda$
b-1	ba-1	$\lambda$	b	b
ba-1	b	ba-1	b-1	ba-1

giving rise to the prefix string rewriting system $R_{TC} = \{$ $a \longrightarrow\lambda$, $a^{-1} \longrightarrow\lambda$, $ba \longrightarrow b^{-1}$, $bb \longrightarrow b^{-1}$, $bb^{-1} \longrightarrow\lambda$, $b^{-1}a \longrightarrow b a^{-1}$, $b^{-1}b \longrightarrow\lambda$, $b^{-1}a^{-1} \longrightarrow b$, $b^{-1}b^{-1} \longrightarrow b$, $ba^{-1}a \longrightarrow b$, $ba^{-1}b \longrightarrow ba^{-1}$, $ba^{-1}a^{-1} \longrightarrow b^{-1}$, $ba^{-1}b^{-1} \longrightarrow ba^{-1}$ $\}$.

The coset representative of the word aba can be deduced by either tracing the coset table: $\lambda \circ{\bf a} = \lambda$, $\lambda \circ{\bf b} = b$ and $b \circ{\bf a} = b^{-1}$, or by prefix reduction: $\underline{a}ba \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{a \... ...}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{ba \longrightarrow b^{-1}}\,$ } b^{-1}$ In both cases we find that aba lies in the coset represented by b^-1 which is in fact the minimal representative of this coset with respect to the chosen ordering.