Next: 3. Towards Gröbner Bases Up: 2. The Subgroup Problem Previous: 2.1 Nielsen Reduction

## 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 in terms of generators and relators R corresponds to viewing it as the quotient of the free group (generated by ) by the normal subgroup generated by R. can be viewed as the subgroup of generated by . Notice that if R is finite, , while finitely generated as a normal subgroup of , need not be finitely generated as a subgroup.

Now given a subgroup of for we can study the cosets of in . Since for either or the group is a disjoint union of cosets and the number of different cosets is called the index of in . We know that if is generated by a set the index of in is the same as the index of the subgroup generated by in . 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 and the subgroup are finitely presented respectively generated, i.e. the sets , 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 in using the following two facts for cosets: For we have and for and any coset , we have .

The procedure proceeds by filling two different kinds of tables with coset representatives, (one row) tables for the subgroup generators of the form

 x1 ... xk
and (possibly infinite row) tables for the relators of the form
 y1 ... ym
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 , where wi, wj are words representing cosets and , lead to word equations wia = wj or wi' = wj depending on whether the last letter of wi is a-1 or not. If or (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 reduction7) 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 in is finite the procedure halts and produces a prefix closed set of coset representatives and a multiplication table with entries for each coset w and each . The (unique) coset representative for any word in can be computed by tracing it through the multiplication table starting with or equivalently by using the multiplication table as a prefix string rewriting system as follows: To each coset w, each and the respective coset wa corresponding to , associate a rule8 which is either of the form or 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 be the Dyck group D(3,3,2) presented by and and the subgroup of generated by . The index of in is 4 and TC (using the length lexicographical ordering induced by ) computes the coset representatives , the multiplication table

 a b a-1 b-1 b b-1 b b-1 b-1 ba-1 b-1 ba-1 b b ba-1 b ba-1 b-1 ba-1

which corresponds to the prefix string rewriting system (omitting trivial rules) , , , , , , , , and .

The coset representative of the word aba can be deduced by either tracing the multiplication table: , and , or by prefix reduction: 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.

Next: 3. Towards Gröbner Bases Up: 2. The Subgroup Problem Previous: 2.1 Nielsen Reduction
| ZCA Home | Reports |