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 ${\mathcal{F}}$ be a free group with generating set $\Sigma$. We call a word $w \equiv w_1 \ldots w_k$, $w_i \in {\mathcal{F}}$, reduced, in case $w = w_1 \circ\ldots \circ w_k$, i.e., $\vert w\vert = \sum_{i=1}^{k} \vert w_i\vert$. Subsets of ${\mathcal{F}}$ are written as $U = \{ u_i \mid i \in \mathbb{N}\}$ or $U = \{ u_1, \ldots , u_n \}$ depending on whether they are finite or not. The subgroup generated by U is the set $\{ s_1 \circ\ldots \circ s_k \mid k \in \mathbb{N} , s_i \in U \cup U^{-1} \}$ where $U^{-1} = \{ u^{-1} \mid u \in U \}$. Then we can define elementary Nielsen transformations on a set U as follows:

(T1)

Replace some $u_i \in U$ by u_i^-1, where u_i^-1 denotes the inverse of u_i.

(T2)

Replace some $u_i \in U$ by $u_i \circ u_j$ where $j \neq i$.

(T3)

Delete some $u_i \in U$ where $u_i = \lambda$.

In all three cases it is understood that the u_l remain unchanged for $l \neq i$. A product of such elementary transformations is called a  Nielsen transformation.

Lemma 1   If a subset U of ${\mathcal{F}}$ 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 $v_1,v_2,v_3 \in U \cup U^{-1}$ we have :

(N0)

$v_1 \neq \lambda$;

(N1)

$v_1 \circ v_2 \neq \lambda$ implies $\vert v_1 \circ v_2\vert \geq \max \{ \vert v_1\vert, \vert v_2\vert \}$;

(N2)

$v_1 \circ v_2 \neq \lambda$ and $v_2 \circ v_3 \neq \lambda$ imply $\vert v_1 \circ v_2 \circ v_3\vert > \vert v_1\vert - \vert v_2\vert + \vert v_3\vert$.

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 $u \in U \cup U^{-1}$ there are words a(u) and m(u) with $m(u) \neq \lambda$ such that $u \equiv a(u)m(u)(a(u^{-1}))^{-1}$ and if $w = u_1 \circ\ldots \circ u_n$ for some $u_i \in U \cup U^{-1}$, $u_{i} \circ u_{i+1} \neq \lambda$, then the words m(u_i) remain uncanceled in the reduced form of w. In particular we get $\vert w\vert \geq n$.

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 $U \subseteq {\mathcal{F}}$ 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.