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 u_{i}^{-1}, where u_{i}^{-1} denotes the inverse of u_{i}.

(T2)

Replace some
by
where .

(T3)

Delete some
where
.

In all three cases it is understood that the u_{l} 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 UNielsen 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(u_{i}) 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 |