Nielsen transformation

Last updated April 16, 2024

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 [ x₁, ..., x_n ] can be factored into elementary Nielsen transformations of the following sorts:

Switch x₁ and x₂
Cyclically permute x₁, x₂, ..., x_n, to x₂, ..., x_n, x₁.
Replace x₁ with x₁⁻¹
Replace x₁ with x₁·x₂

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.

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⁻¹, y ], type 3
[ y, x⁻¹ ], type 1
[ y⁻¹, x⁻¹ ], type 3
[ y⁻¹x⁻¹, x⁻¹ ], type 4
[ xy, x⁻¹ ], type 3
[ x⁻¹, 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

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 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 ).

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

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).

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 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 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

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.

Related Research Articles

In mathematics, the free groupF_S 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 F_S, and the number of generators is the rank of the free group. An arbitrary group G is called free if it is isomorphic to F_S 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⁻¹xzz and y⁻¹zxx⁻¹yz⁻¹ 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={s_i : 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 F_n. 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.

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, Cambridge University Press, doi:10.1017/CBO9780511565878, ISBN 978-0-521-34133-2, 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, ISBN 978-3-11-014793-3, MR 1476950
Schupp, Paul E.; Lyndon, Roger C. (2001), Combinatorial group theory, Springer-Verlag, ISBN 978-3-540-41158-1, MR 0577064
Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald (2004), Combinatorial Group Theory, Dover Publications, ISBN 978-0-486-43830-6, MR 0207802

Primary sources

Alexander, J. W. (1928), "Topological invariants of knots and links", Transactions of the American Mathematical Society , 30 (2): 275–306, doi: 10.2307/1989123 , JFM 54.0603.03, JSTOR 1989123
Evans, Martin J. (1989), "Primitive elements in free groups", Proceedings of the American Mathematical Society, 106 (2): 313–6, doi: 10.2307/2048805 , JSTOR 2048805, 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.
Leedham-Green, C. R.; Murray, Scott H. (2002), "Variants of product replacement", Computational and statistical group theory (Las Vegas, NV/Hoboken, NJ, 2001), Contemp. Math., vol. 298, Providence, R.I.: American Mathematical Society, pp. 97–104, doi:10.1090/conm/298/05116, MR 1929718
Lustig, Martin (1991), "Nielsen equivalence and simple-homotopy type", Proceedings of the London Mathematical Society, 3rd Series, 62 (3): 537–562, doi:10.1112/plms/s3-62.3.537, MR 1095232
Lustig, Martin; Moriah, Yoav (1993), "Generating systems of groups and Reidemeister-Whitehead torsion", Journal of Algebra, 157 (1): 170–198, doi: 10.1006/jabr.1993.1096 , MR 1219664
Nielsen, Jakob (1921), "Om regning med ikke-kommutative faktorer og dens anvendelse i gruppeteorien", Math. Tidsskrift B (in Danish), 1921: 78–94, JFM 48.0123.03
Nielsen, Jakob (1924), "Die Isomorphismengruppe der freien Gruppen", Mathematische Annalen (in German), 91 (3–4): 169–209, doi:10.1007/BF01556078, JFM 50.0078.04
Pak, Igor (2001), "What do we know about the product replacement algorithm?", Groups and computation, III (Columbus, OH, 1999), Ohio State Univ. Math. Res. Inst. Publ., vol. 8, Walter de Gruyter, pp. 301–347, MR 1829489
Rapaport, Elvira Strasser (1959), "Note on Nielsen transformations", Proceedings of the American Mathematical Society, 10 (2): 228–235, doi: 10.2307/2033582 , JSTOR 2033582, MR 0104724

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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. ^{[ citation needed ]} There are similar results for polycyclic groups, and certain other finitely generated groups as well.

[1]