Nielsen transformation
In
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:
- Switch x1 and x2
- Cyclically permute x1, x2, ..., xn, to x2, ..., xn, x1.
- Replace x1 with x1−1
- Replace x1 with x1·x2
These transformations are the analogues of the
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 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:
- [ x−1, y ], type 3
- [ y, x−1 ], type 1
- [ y−1, x−1 ], type 3
- [ y−1x−1, x−1 ], type 4
- [ xy, x−1 ], type 3
- [ x−1, xy ], type 1
- [ x, xy ], type 3
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:
- [ x, y, 1 ]
- [ x, y, y ], multiply 2nd generator into 3rd
- [ x, yy, y ], multiply 3rd generator into 2nd
- [ x, yy, yyy ], multiply 2nd generator into 3rd
- [ x, yy, 1 ], multiply 2nd generator into 3rd
Applications
Nielsen–Schreier theorem
This section needs expansion. You can help by adding to it. (July 2008) |
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
This section needs expansion. You can help by adding to it. (July 2008) |
In (
For a given generating set of a given finitely generated group, it is not necessarily true that 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
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
A particularly important special case of the
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 2001). One version of the algorithm, called "shake", is:
- Take any ordered generating set and append some copies of the identity element, so that there are n elements in the set
- Repeat the following for a certain number of times (called a burn in)
- Choose integers i and j uniformly at randomfrom 1 to n, and choose e uniformly at random from { 1, -1 }
- Replace the ith generator with the product of the ith generator and the jth generator raised to the eth power
- Choose integers i and j
- Every time a new random element is desired, repeat the previous two steps, then return one of the generating elements as the desired random element
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):
- In addition to the generating set, store an additional element of the group, initialized to the identity
- Every time a generator is replaced, choose k uniformly at random, and replace the additional element by the product of the additional element with the kth generator.
K-theory
This section needs expansion. You can help by adding to it. (July 2008) |
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
- Tietze transformation
- Automorphism group of a free group
References
Notes
- ^ 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. [citation needed] There are similar results for polycyclic groups, and certain other finitely generated groups as well.
Textbooks and surveys
- Cohen, Daniel E. (1989), Combinatorial group theory: a topological approach, London Mathematical Society Student Texts, vol. 14, MR 1020297
- Fine, Benjamin; Rosenberger, Gerhard; Stille, Michael (1995), "Nielsen transformations and applications: a survey", in Kim, Ann Chi; Kim, A.C.; Johnson, D.L. (eds.), Groups—Korea '94: Proceedings of the International Conference Held at Pusan National University, Pusan, Korea, August 18–25, 1994, Walter de Gruyter, pp. 69–105, MR 1476950
- MR 0577064
- MR 0207802
Primary sources
- JSTOR 1989123
- Evans, Martin J. (1989), "Primitive elements in free groups", Proceedings of the American Mathematical Society, 106 (2): 313–6, MR 0952315
- Fenchel, Werner; Nielsen, Jakob (2003), Schmidt, Asmus L. (ed.), Discontinuous groups of isometries in the hyperbolic plane, De Gruyter Studies in mathematics, vol. 29, Berlin: Walter de Gruyter & Co.
- MR 1929718
- Lustig, Martin (1991), "Nielsen equivalence and simple-homotopy type", Proceedings of the London Mathematical Society, 3rd Series, 62 (3): 537–562, MR 1095232
- Lustig, Martin; Moriah, Yoav (1993), "Generating systems of groups and Reidemeister-Whitehead torsion", Journal of Algebra, 157 (1): 170–198, MR 1219664
- JFM 48.0123.03
- JFM 50.0078.04
- MR 1829489
- Rapaport, Elvira Strasser (1959), "Note on Nielsen transformations", Proceedings of the American Mathematical Society, 10 (2): 228–235, MR 0104724