2.2 The Todd-Coxeter Coset Enumeration Procedure

The Todd-Coxeter coset enumeration (TC) is a famous method from combinatorial group theory for studying finitely presented groups (see e.g. [21,10,25] for detailed descriptions). 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 ${\mathcal{F}}$ (generated by $\Sigma$) by the normal subgroup $\mathcal{N}$ generated by R. $\mathcal{N}$ can be viewed as the subgroup of ${\mathcal{F}}$ generated by $N(R) = \{ w \circ r \circ w^{-1} \mid w \in {\mathcal{F}}, r \in R \}$. Notice that if R is finite, $\mathcal{N}$, while finitely generated as a normal subgroup of ${\mathcal{F}}$, need not be finitely generated as a subgroup.

Now given a subgroup $\mathcal{U}$ of ${\cal G}$ for $g \in {\cal G}$ we can study the cosets $\mathcal{U}g = \{ u \circ g \mid u \in \mathcal{U} \}$ of $\mathcal{U}$ in ${\cal G}$. Since for $g,h \in {\cal G}$ either $\mathcal{U}g = \mathcal{U}h$ or $\mathcal{U}g \cap \mathcal{U}h = \emptyset$ the group ${\cal G}$ is a disjoint union of cosets and the number of different cosets is called the index $\vert{\cal G}: \mathcal{U}\vert$ of $\mathcal{U}$ in ${\cal G}$. We know that if $\mathcal{U}$ is generated by a set $U \subseteq {\cal G}$ the index of $\mathcal{U}$ in ${\cal G}$ is the same as the index of the subgroup ${\mathcal{H}}$ generated by $U \cup N(R)$ in ${\mathcal{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 $\mathcal{U}$ are finitely presented respectively generated, i.e. the sets $\Sigma$, R and U are finite. Moreover, TC requires that each generator should occur in at least one relator. TC tries to compute the index of $\mathcal{U}$ in ${\cal G}$ using the following two facts for cosets: For $u \in U$ we have $\mathcal{U}u=\mathcal{U}$ and for $r \in R$ and any coset $\mathcal{U}g$, $g \in {\cal G}$ we have $\mathcal{U}(g \circ r \circ g^{-1}) = \mathcal{U}$.

The procedure proceeds by filling two different kinds of tables with coset representatives, (one row) tables for the subgroup generators $u \equiv x_1 \ldots x_k$ of the form

x1		...	xk
$\lambda$				$\lambda$

and (possibly infinite row) tables for the relators $y_1 \ldots y_m$ of the form

y1		...	ym
$\lambda$				$\lambda$

Depending on the strategy used for choosing the next slot in the tables different types of equations (called defining, bonus and collapse) are deduced. While most versions of TC simply use numbers to represent the cosets, it is possible to describe them using appropriate words as coset representatives. Then the deduced equations $w_i \circ a = w_j$, where w_i, w_j are words representing cosets and $a \in \bar{\Sigma}$, lead to word equations w_ia = w_j or w_i' = w_j depending on whether the last letter of w_i is a^-1 or not. If $w_ia \equiv w_j$ or $w_i' \equiv w_j$ (i.e. the words of the left and right side are identical) the equations are called trivial. Otherwise they are ordered with respect to a well-founded ordering (in our case the length lexicographical ordering defined in the previous section) and used as a prefix string rewriting system (modulo free group reduction⁷) to simplify the existing equations. Of course such a simplification can lead to new rules and to a new simplification and so on. More details of this strategy can be found in [2,24]. We only list some of the properties and their interpretations here: If the index of $\mathcal{U}$ in ${\cal G}$ is finite the procedure halts and produces a prefix closed set of coset representatives and a multiplication table with entries $w \circ a$ for each coset w and each $a \in \bar{\Sigma}$. The (unique) coset representative for any word in $\bar{\Sigma}^*$ can be computed by tracing it through the multiplication table starting with $\lambda$ or equivalently by using the multiplication table as a 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⁸ $w \circ a \longrightarrow w_a$ which is either of the form $wa \longrightarrow w_a$ or $w' \longrightarrow w_a$ depending on whether the last letter of w is a^-1.

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

Example 4    
Let ${\cal G}$ be the Dyck group D(3,3,2) presented by $\Sigma = \{ a,b \}$ and $R = \{ aaa, bbb, abab \}$ and $\mathcal{U}$ the subgroup of ${\cal G}$ generated by $\{ a \}$. The index of $\mathcal{U}$ 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} \}$, the multiplication 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

which corresponds to the prefix string rewriting system (omitting trivial rules) $a \longrightarrow\lambda$, $a^{-1} \longrightarrow\lambda$, $ba \longrightarrow b^{-1}$, $bb \longrightarrow b^{-1}$, $b^{-1}a \longrightarrow b a^{-1}$, $b^{-1}a^{-1} \longrightarrow b$, $b^{-1}b^{-1} \longrightarrow b$, $ba^{-1}b \longrightarrow b$, $ba^{-1}a^{-1} \longrightarrow b^{-1}$ and $ba^{-1}b^{-1} \longrightarrow ba^{-1}$.

The coset representative of the word aba can be deduced by either tracing the multiplication table: $\lambda \circ{\bf a} = \lambda$, $\lambda \circ{\bf b} = b$ and $b \circ{\bf a} = b^{-1}$, or by prefix reduction: $aba \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{a \longrightarr... ...}{\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.