Nielsen transformation

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, Nielsen transformations, named after Jakob Nielsen, are certain automorphisms of a free group which are a non-commutative analogue of row reduction and one of the main tools used in studying free groups, (Fine, Rosenberger & Stille 1995). They were introduced in (Nielsen 1921) to prove that every subgroup of a free group is free (the Nielsen–Schreier theorem), but are now used in a variety of mathematics, including computational group theory, k-theory, and knot theory. The textbook (Magnus, Karrass & Solitar 2004) devotes all of chapter 3 to Nielsen transformations.

Definitions

One of the simplest definitions of a Nielsen transformation is an automorphism of a free group, but this was not their original definition. The following gives a more constructive definition.

A Nielsen transformation on a finitely generated free group with ordered basis [ x1, …, xn ] can be factored into elementary Nielsen transformations of the following sorts:

These transformations are the analogues of the elementary row operations. Transformations of the first two kinds are analogous to row swaps, and cyclic row permutations. Transformations of the third kind correspond to scaling a row by an invertible scalar. Transformations of the fourth kind correspond to row additions.

Transformations of the first two types suffice to permute the generators in any order, so the third type may be applied to any of the generators, and the fourth type to any pair of generators.

When dealing with groups that are not free, one instead applies these transformations to finite ordered subsets of a group. In this situation, compositions of the elementary transformations are called regular. If one allows removing elements of the subset that are the identity element, then the transformation is called singular.

The image under a Nielsen transformation (elementary or not, regular or not) of a generating set of a group G is also a generating set of G. Two generating sets are called Nielsen equivalent if there is a Nielsen transformation taking one to the other. If the generating sets have the same size, then it suffices to consider compositions of regular, elementary Nielsen transformations.

Examples

The dihedral group of order 10 has two Nielsen equivalence classes of generating sets of size 2. Letting x be an element of order 2, and y being an element of order 5, the two classes of generating sets are represented by [ x, y ] and [ x, yy ], and each class has 15 distinct elements. A very important generating set of a dihedral group is the generating set from its presentation as a Coxeter group. Such a generating set for a dihedral group of order 10 consists of any pair of elements of order 2, such as [ x, xy ]. This generating set is equivalent to [ x, y ] via the complicated:

Unlike [ x, y ] and [ x, yy ], the generating sets [ x, y, 1 ] and [ x, yy, 1 ] are equivalent.[1] A transforming sequence using more convenient elementary transformations (all swaps, all inverses, all products) is:

Applications

Nielsen–Schreier theorem

In (Nielsen 1921), a straightforward combinatorial proof is given that finitely generated subgroups of free groups are free. A generating set is called Nielsen reduced if there is not too much cancellation in products. The paper shows that every finite generating set of a subgroup of a free group is (singularly) Nielsen equivalent to a Nielsen reduced generating set, and that a Nielsen reduced generating set is a free basis for the subgroup, so the subgroup is free. This proof is given in some detail in (Magnus, Karrass & Solitar 2004, Ch 3.2).

Automorphism groups

In (Nielsen 1924), it is shown that the automorphism defined by the elementary Nielsen transformations generate the full automorphism group of a finitely generated free group. Nielsen, and later Neumann used these ideas to give finite presentations of the automorphism groups of free groups. This is also described in the textbook (Magnus, Karrass & Solitar 2004, p. 131, Th 3.2).

For a given generating set of a finite group (not necessarily free), not every automorphism is given by a Nielsen transformation, but for every automorphism, there is a generating set where the automorphism is given by a Nielsen transformation, (Rapaport 1959).

Word problem

A particularly simple case of the word problem for groups and the isomorphism problem for groups asks if a finitely presented group is the trivial group. This is known to be intractable in general, even though there is a finite sequence of elementary Tietze transformations taking the presentation to the trivial presentation if and only if the group is trivial. A special case is that of "balanced presentations", those finite presentations with equal numbers of generators and relators. For these groups, there is a conjecture that the required transformations are quite a bit simpler (in particular, do not involve adding or removing relators). If one allows taking the set of relators to any Nielsen equivalent set, and one allows conjugating the relators, then one gets an equivalence relation on ordered subsets of a relators of a finitely presented group. The Andrews–Curtis conjecture is that the relators of any balanced presentation of the trivial group are equivalent to a set of trivial relators, stating that each generator is the identity element.

In the textbook (Magnus, Karrass & Solitar 2004, pp. 131–132), an application of Nielsen transformations is given to solve the generalized word problem for free groups, also known as the membership problem for subgroups given by finite generating sets in free groups.

Isomorphism problem

Main article: Alexander polynomial

A particularly important special case of the isomorphism problem for groups concerns the fundamental groups of three-dimensional knots, which can be solved using Nielsen transformations and a method of Alexander (Magnus, Karrass & Solitar 2004, Ch 3.4).

Product replacement algorithm

In computational group theory, it is important to generate random elements of a finite group. Popular methods of doing this apply markov chain methods to generate random generating sets of the group. The "product replacement algorithm" simply uses randomly chosen Nielsen transformations in order to take a random walk on the graph of generating sets of the group. The algorithm is well studied, and survey is given in (Pak 1999). One version of the algorithm, called "shake", is:

The generating set used during the course of this algorithm can be proved to vary uniformly over all Nielsen equivalent generating sets. However, this algorithm has a number of statistical and theoretical problems. For instance, there can be more than one Nielsen equivalence class of generators. Also, the elements of generating sets need be uniformly distributed (for instance, elements of the Frattini subgroup can never occur in a generating set of minimal size, but more subtle problems occur too).

Most of these problems are quickly remedied in the following modification called "rattle", (Leedham-Green & Murray 2002):

K-theory

To understand Nielsen equivalence of non-minimal generating sets, module theoretic investigations have been useful, as in (Evans 1989). Continuing in these lines, a K-theoretic formulation of the obstruction to Nielsen equivalence was described in (Lustig 1991) and (Lustig & Moriah 1993). These show an important connection between the Whitehead group of the group ring and the Nielsen equivalence classes of generators.

See also

References

Notes

  1. ↑ Indeed all 840 ordered generating sets of size three are equivalent. This is a general feature of Nielsen equivalence of finite groups. If a finite group can be generated by d generators, then all generating sets of size d + 1 are equivalent. There are similar results for polycyclic groups, and certain other finitely generated groups as well.

Textbooks and surveys

Primary sources

This article is issued from Wikipedia - version of the Wednesday, February 03, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.