Nielsen transformation
Encyclopedia
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, . They were introduced in 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 devotes all of chapter 3 to Nielsen transformations.
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.
. 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. A transforming sequence using more convenient elementary transformations (all swaps, all inverses, all products) is:
. 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 .
For a given generating set of a finite group, 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, .
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 , 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.
, which can be solved using Nielsen transformations and a method of Alexander .
, 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 . 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", :
investigations have been useful, as in . Continuing in these lines, a K-theoretic formulation of the obstruction to Nielsen equivalence was described in and . These show an important connection between the Whitehead group of the group ring and the Nielsen equivalence classes of generators.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, especially in the area of abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
known as combinatorial group theory
Combinatorial group theory
In mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group by generators and relations...
, Nielsen transformations, named after Jakob Nielsen
Jakob Nielsen (mathematician)
Jakob Nielsen was a Danish mathematician known for his work on automorphisms of surfaces. He was born in the village Mjels on the island of Als in North Schleswig, in modern day Denmark. His mother died when he was 3, and in 1900 he went to live with his aunt and was enrolled in the Realgymnasium...
, are certain automorphisms of a free group
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...
which are a non-commutative analogue of row reduction and one of the main tools used in studying free groups, . They were introduced in to prove that every subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
of a free group is free (the Nielsen–Schreier theorem
Nielsen–Schreier theorem
In group theory, a branch of mathematics, the Nielsen–Schreier theorem is the statement that every subgroup of a free group is itself free. It is named after Jakob Nielsen and Otto Schreier.-Statement of the theorem:...
), but are now used in a variety of mathematics, including computational group theory
Computational group theory
In mathematics, computational group theory is the study ofgroups by means of computers. It is concernedwith designing and analysing algorithms anddata structures to compute information about groups...
, k-theory
K-theory
In mathematics, K-theory originated as the study of a ring generated by vector bundles over a topological space or scheme. In algebraic topology, it is an extraordinary cohomology theory known as topological K-theory. In algebra and algebraic geometry, it is referred to as algebraic K-theory. It...
, and knot theory
Knot theory
In topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life in shoelaces and rope, a mathematician's knot differs in that the ends are joined together so that it cannot be undone. In precise mathematical language, a knot is an embedding of a...
. The textbook 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:
- 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 elementary row operations
Elementary row operations
In mathematics, an elementary matrix is a simple matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group of invertible matrices...
. 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 groupCoxeter group
In mathematics, a Coxeter group, named after H.S.M. Coxeter, is an abstract group that admits a formal description in terms of mirror symmetries. Indeed, the finite Coxeter groups are precisely the finite Euclidean reflection groups; the symmetry groups of regular polyhedra are an example...
. 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:
- [ 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. 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
Nielsen–Schreier theorem
In , 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 .Automorphism groups
In , it is shown that the automorphism defined by the elementary Nielsen transformations generate the full automorphism group of a finitely generated free groupAutomorphism group of a free group
In mathematical group theory, the automorphism group of a free group is a discrete group of automorphisms of a free group. The quotient by the inner automorphisms is the outer automorphism group of a free group, which is similar in some ways to the mapping class group of a surface.-Presentation:...
. Nielsen, and later Neumann
Bernhard Neumann
Bernhard Hermann Neumann AC FRS was a German-born British mathematician who was one of the leading figures in group theory, greatly influencing the direction of the subject....
used these ideas to give finite presentations of the automorphism groups of free groups. This is also described in the textbook .
For a given generating set of a finite group, 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, .
Word problem
A particularly simple case of the word problem for groupsWord problem for groups
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element...
and the isomorphism problem for groups asks if a finitely presented group is the trivial group
Trivial group
In mathematics, a trivial group is a group consisting of a single element. All such groups are isomorphic so one often speaks of the trivial group. The single element of the trivial group is the identity element so it usually denoted as such, 0, 1 or e depending on the context...
. 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
Andrews–Curtis conjecture
In mathematics, the Andrews–Curtis conjecture states that every balanced presentation of the trivial group can be transformed into a trivial presentation by a sequence of Nielsen transformations on the relators together with conjugations of relators, named after James J. Andrews and Morton L....
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 , 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 isomorphism problem for groups concerns the fundamental groups of three dimensional knotsKnot (mathematics)
In mathematics, a knot is an embedding of a circle in 3-dimensional Euclidean space, R3, considered up to continuous deformations . A crucial difference between the standard mathematical and conventional notions of a knot is that mathematical knots are closed—there are no ends to tie or untie on a...
, which can be solved using Nielsen transformations and a method of Alexander .
Product replacement algorithm
In computational group theoryComputational group theory
In mathematics, computational group theory is the study ofgroups by means of computers. It is concernedwith designing and analysing algorithms anddata structures to compute information about groups...
, it is important to generate random elements of a finite group
Finite group
In mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...
. Popular methods of doing this apply markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
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
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
on the graph of generating sets of the group. The algorithm is well studied, and survey is given in . 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 inBurn inBurn-in is the process by which components of a system are exercised prior to being placed in service ....
)- Choose integers i and j uniformly at random from 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
- 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
Frattini subgroup
In mathematics, the Frattini subgroup Φ of a group G is the intersection of all maximal subgroups of G. For the case that G is the trivial group e, which has no maximal subgroups, it is defined by Φ = e...
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", :
- 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
To understand Nielsen equivalence of non-minimal generating sets, module theoreticModule (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
investigations have been useful, as in . Continuing in these lines, a K-theoretic formulation of the obstruction to Nielsen equivalence was described in and . These show an important connection between the Whitehead group of the group ring and the Nielsen equivalence classes of generators.