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.
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 Nielsen transformations.
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:
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:
![]() | 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).
![]() | This section needs expansion. You can help by adding to it. (July 2008) |
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 Bernhard 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 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 ).
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.
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 J. W. Alexander ( Magnus, Karrass & Solitar 2004 , Ch 3.4).
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:
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 ):
![]() | 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.
In mathematics, the free groupFS over a given set S consists of all words that can be built from members of S, considering two words to be different unless their equality follows from the group axioms. The members of S are called generators of FS, and the number of generators is the rank of the free group. An arbitrary group G is called free if it is isomorphic to FS for some subset S of G, that is, if there is a subset S of G such that every element of G can be written in exactly one way as a product of finitely many elements of S and their inverses.
In mathematics, a presentation is one method of specifying a group. A presentation of a group G comprises a set S of generators—so that every element of the group can be written as a product of powers of some of these generators—and a set R of relations among those generators. We then say G has presentation
In mathematics, a free abelian group is an abelian group with a basis. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a subset such that every element of the group can be uniquely expressed as an integer combination of finitely many basis elements. For instance the two-dimensional integer lattice forms a free abelian group, with coordinatewise addition as its operation, and with the two points (1,0) and (0,1) as its basis. Free abelian groups have properties which make them similar to vector spaces, and may equivalently be called free-modules, the free modules over the integers. Lattice theory studies free abelian subgroups of real vector spaces. In algebraic topology, free abelian groups are used to define chain groups, and in algebraic geometry they are used to define divisors.
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing expander graphs.
In mathematics, specifically group theory, the free product is an operation that takes two groups G and H and constructs a new group G ∗ H. The result contains both G and H as subgroups, is generated by the elements of these subgroups, and is the “universal” group having these properties, in the sense that any two homomorphisms from G and H into a group K factor uniquely through a homomorphism from G ∗ H to K. Unless one of the groups G and H is trivial, the free product is always infinite. The construction of a free product is similar in spirit to the construction of a free group.
In geometric topology, a field within mathematics, the obstruction to a homotopy equivalence of finite CW-complexes being a simple homotopy equivalence is its Whitehead torsion which is an element in the Whitehead group. These concepts are named after the mathematician J. H. C. Whitehead.
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups can act non-trivially.
In mathematics, the Feit–Thompson theorem, or odd order theorem, states that every finite group of odd order is solvable. It was proved by Walter Feit and John Griggs Thompson.
In abstract algebra, the conjugacy problem for a group G with a given presentation is the decision problem of determining, given two words x and y in G, whether or not they represent conjugate elements of G. That is, the problem is to determine whether there exists an element z of G such that
In group theory, a word is any written product of group elements and their inverses. For example, if x, y and z are elements of a group G, then xy, z−1xzz and y−1zxx−1yz−1 are words in the set {x, y, z}. Two different words may evaluate to the same value in G, or even in every group. Words play an important role in the theory of free groups and presentations, and are central objects of study in combinatorial group theory.
In group theory, a branch of mathematics, the Nielsen–Schreier theorem states that every subgroup of a free group is itself free. It is named after Jakob Nielsen and Otto Schreier.
In the mathematical field of group theory, the Kurosh subgroup theorem describes the algebraic structure of subgroups of free products of groups. The theorem was obtained by Alexander Kurosh, a Russian mathematician, in 1934. Informally, the theorem says that every subgroup of a free product is itself a free product of a free group and of its intersections with the conjugates of the factors of the original free product.
In mathematics, the ping-pong lemma, or table-tennis lemma, is any of several mathematical statements that ensure that several elements in a group acting on a set freely generates a free subgroup of that group.
In mathematics, in the area of abstract algebra known as group theory, a verbal subgroup is a subgroup of a group that is generated by all elements that can be formed by substituting group elements for variables in a given set of words.
In the area of mathematics called combinatorial group theory, the Schreier coset graph is a graph associated with a group G, a generating set S={si : i in I} of G, and a subgroup H ≤ G. The Schreier graph encodes the abstract structure of a group modulo an equivalence relation formed by the coset.
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.
In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit–evasion games on the graph, or as topological ends of topological spaces associated with the graph.
Donald Solitar was an American and Canadian mathematician, known for his work in combinatorial group theory. The Baumslag–Solitar groups are named after him and Gilbert Baumslag, after their joint 1962 paper on these groups.
In the mathematical subject of group theory, a one-relator group is a group given by a group presentation with a single defining relation. One-relator groups play an important role in geometric group theory by providing many explicit examples of finitely presented groups.
Whitehead's algorithm is a mathematical algorithm in group theory for solving the automorphic equivalence problem in the finite rank free group Fn. The algorithm is based on a classic 1936 paper of J. H. C. Whitehead. It is still unknown if Whitehead's algorithm has polynomial time complexity.