Next: 3. Towards Gröbner Bases
Up: 2. The Subgroup Problem
Previous: 2.1 Nielsen Reduction
2.2 The ToddCoxeter Coset Enumeration Procedure
The ToddCoxeter 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
x_{1} 
... 
x_{k} 





and (possibly infinite row) tables for the relators
of the form
y_{1} 
... 
y_{m} 










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 w_{i}, w_{j} are words representing cosets and
,
lead to word equations
w_{i}a = w_{j} or
w_{i}' = w_{j} depending
on whether the last letter of w_{i} 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 wellfounded 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^{7}) 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 w_{a}
corresponding to ,
associate a rule^{8}
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
T
C (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 