Next: 2.2 The Todd-Coxeter Coset Up: 2. The Subgroup Problem Previous: 2. The Subgroup Problem

## 2.1 Nielsen Reduction

Let us start by giving a short description of Nielsen's method, which can be found in more detail e.g. in [14]. Let be a free group with generating set . We call a word , , reduced, in case , i.e., . Subsets of are written as or depending on whether they are finite or not. The subgroup generated by U is the set where . Then we can define elementary Nielsen transformations on a set U as follows:
(T1)
Replace some by ui-1, where ui-1 denotes the inverse of ui.
(T2)
Replace some by where .
(T3)
Delete some where .
In all three cases it is understood that the ul remain unchanged for . A product of such elementary transformations is called a  Nielsen transformation.

Lemma 1   If a subset U of is carried into a set U' by a Nielsen transformation, then U and U' generate the same subgroup.

We call a set U Nielsen reduced, if for all we have :
(N0)
;
(N1)
implies ;
(N2)
and imply .
Nielsen reduced sets play an important role, as they are free generating sets for the subgroup they generate. The following theorem due to Zieschang states that freely reducing a product of elements of a Nielsen reduced set cannot result in arbitrary cancellations on the elements involved.

Theorem 2   Let U be a Nielsen reduced set. Then for every there are words a(u) and m(u) with such that and if for some , , then the words m(ui) remain uncanceled in the reduced form of w. In particular we get .

This property can be used to solve the subgroup problem using Nielsen reduced sets by computing Schreier coset representatives by prefix rewriting.

Theorem 3   Let be a finite set. Then there is a Nielsen transformation from U into some Nielsen reduced set V.

The proof of this theorem provided in [14] is constructive and gives rise to a procedure for transforming a finite generating set of a subgroup into a Nielsen reduced set. There are well-known algorithms for performing this task and Avenhaus and Madlener have provided one which works in polynomial time (see [1]). We will see later on how this can be done using prefix Gröbner bases.

Next: 2.2 The Todd-Coxeter Coset Up: 2. The Subgroup Problem Previous: 2. The Subgroup Problem
| ZCA Home | Reports |