Nielsen transformation

Last updated November 25, 2024

In mathematics, especially in the area of modern algebra known as combinatorial group theory, Nielsen transformations 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 ).

Given a finite basis of a free group $F_{n}$ , the corresponding set of elementary Nielsen transformations forms a finite generating set of $\mathrm {Aut} (F_{n})$ . This system of generators is analogous to elementary matrices for $GL_{n}(\mathbb {Z} )$ and Dehn twists for mapping class groups of closed surfaces.

Nielsen transformations were introduced in ( Nielsen 1921 ) to prove that every subgroup of a free group is free (the Nielsen–Schreier theorem). They are now used in a variety of mathematics, including computational group theory, k-theory, and knot theory.

Definitions

Free groups

Let ${\textstyle F_{n}}$ be a finitely generated free group of rank ${\textstyle n}$ . An elementary Nielsen transformation maps an ordered basis ${\textstyle [x_{1},\ldots ,x_{n}]}$ to a new basis ${\textstyle [y_{1},\ldots ,y_{n}]}$ by one of the following operations:

Permute the ${\textstyle x_{i}}$ s by some permutation ${\textstyle \sigma \in S_{n}}$ , i.e. ${\textstyle [y_{1},\ldots ,y_{n}]=[x_{\sigma (1)},\ldots ,x_{\sigma (n)}]}$
Invert some ${\textstyle x_{i}}$ , i.e. ${\textstyle [y_{1},\ldots ,y_{n}]=[x_{1},\ldots ,x_{i}^{-1},\ldots ,x_{n}]}$
Replace some ${\textstyle x_{i}}$ with $x_{i}x_{j}$ for some ${\textstyle j\neq i}$ , i.e. ${\textstyle [y_{1},\ldots ,y_{n}]=[x_{1},\ldots ,x_{i}x_{j},\ldots ,x_{n}]}$ .

A Nielsen transformation is a finite composition of elementary Nielsen transformations. Since automorphisms of $F_{n}$ are determined by the image of a basis, the elementary Nielsen transformations correspond to a finite subset of the automorphism group ${\textstyle \mathrm {Aut} (F_{n})}$ , which is in fact a generating set (see below). Hence, Nielsen transformation can alternatively be defined simply as the action of an automorphism of ${\textstyle F_{n}}$ on bases.

Elementary Nielsen transformations are the analogues of the elementary row operations. Transformations of the first kind are analogous to row permutations. Transformations of the second kind correspond to scaling a row by an invertible scalar. Transformations of the third kind correspond to row additions (transvections).

Since the finite permutation group $S_{n}$ is generated by transpositions, one sees from the chain of elementary Nielsen transformations of type 2 and 3: $(x_{i},x_{i+1})\mapsto {(x_{i},x_{i+1}^{-1})}\mapsto {{(x_{i}x_{i+1}^{-1}},x_{i+1}^{-1})}\mapsto ({{x_{i+1}x_{i}^{-1}},x_{i+1}^{-1}})\mapsto {({x_{i+1}x_{i}^{-1}},x_{i}^{-1})}\mapsto (x_{i+1}x_{i}^{-1},x_{i})\mapsto (x_{i+1},x_{i})$ that elementary Nielsen transformations of type 2 and 3 are in fact enough to generate all Nielsen transformations.

Using the two generators ${\textstyle (12)}$ and ${\textstyle (1\ldots n)}$ of ${\textstyle S_{n}}$ , one can alternatively restrict attention to only four operations:

switch ${\textstyle x_{1}}$ and ${\textstyle x_{2}}$
cyclically permute the ${\textstyle x_{i}}$ s
invert ${\textstyle x_{1}}$
replace ${\textstyle x_{1}}$ with ${\textstyle x_{1}x_{2}}$ .

General finitely generated groups

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 (beware this is not an equivalence relation). 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

The Nielsen-Schreier theorem states that every subgroup ${\textstyle F'\leq F}$ of a free group ${\textstyle F}$ is also free. The modern proof relies on the fact that a group (finitely generated or not) is free, if and only if it is the fundamental group of a graph (finite or not). This allows one to explicitly find a basis of ${\textstyle F'}$ , since it is geometrically realized as the fundamental group of a covering of a graph whose fundamental group is $F$ .

However, the original proof by Nielsen for the case of finitely generated subgroups, given in ( Nielsen 1921 ), is different and more combinatorial. It relies on the notion of a Nielsen reduced generating set, which roughly means one for which 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 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 standard textbooks such as ( Magnus, Karrass & Solitar 2004 , p. 131, Th 3.2).

For a given generating set of a finitely generated group, it is not necessarily true that every automorphism is a Nielsen transformation, but for every automorphism, there is a generating set where the automorphism is given by a Nielsen transformation, ( Rapaport 1959 ).

The adequate generalization of Nielsen transformations for automorphisms of free products of freely indecomposable groups are Whitehead automorphisms. Together with the automorphisms of the Grushko factors, they form a generating set of the automorphism group of any finitely generated group, known as the Fouxe-Rabinovitch generators.^[2]

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, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after Niels Henrik Abel.

In mathematics, in the area of abstract algebra known as Galois theory, the Galois group of a certain type of field extension is a specific group associated with the field extension. The study of field extensions and their relationship to the polynomials that give rise to them via Galois groups is called Galois theory, so named in honor of Évariste Galois who first discovered them.

<span class="mw-page-title-main">Homeomorphism</span> Mapping which preserves all topological properties of a given space

In mathematics and more specifically in topology, a homeomorphism, also called topological isomorphism, or bicontinuous function, is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are the mappings that preserve all the topological properties of a given space. Two spaces with a homeomorphism between them are called homeomorphic, and from a topological viewpoint they are the same.

<span class="mw-page-title-main">Isomorphism</span> Inversible mapping (mathematics)

In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is derived from Ancient Greek ἴσος (isos) 'equal' and μορφή (morphe) 'form, shape'.

In mathematics, and more specifically in linear algebra, a linear map is a mapping $between two vector spaces that preserves the operations of vector addition and scalar multiplication. The same names and the same definition are also used for the more general case of modules over a ring; see Module homomorphism.$

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group $defined over a finite set of symbols consists of the permutations that can be performed on the symbols. Since there are such permutation operations, the order of the symmetric group is .$

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 Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections. Indeed, the finite Coxeter groups are precisely the finite Euclidean reflection groups; for example, the symmetry group of each regular polyhedron is a finite Coxeter group. However, not all Coxeter groups are finite, and not all can be described in terms of symmetries and Euclidean reflections. Coxeter groups were introduced in 1934 as abstractions of reflection groups, and finite Coxeter groups were classified in 1935.

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 commutative algebra and field theory, the Frobenius endomorphism is a special endomorphism of commutative rings with prime characteristic $p$ , an important class that includes finite fields. The endomorphism maps every element to its $p$ -th power. In certain contexts it is an automorphism, but this is not true in general.

In mathematics, Out(F_n) is the outer automorphism group of a free group on n generators. These groups are at universal stage in geometric group theory, as they act on the set of presentations with $generators of any finitely generated group. Despite geometric analogies with general linear groups and mapping class groups, their complexity is generally regarded as more challenging, which has fueled the development of new techniques in the field.$

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

In the mathematical subject of group theory, a co-Hopfian group is a group that is not isomorphic to any of its proper subgroups. The notion is dual to that of a Hopfian group, named after Heinz Hopf.

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.
↑ Gilbert, N. D. (1987). "Presentations of the Automorphism Group of a Free Product". Proceedings of the London Mathematical Society. s3-54 (1): 115–140. doi:10.1112/plms/s3-54.1.115.

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, JSTOR 24529483
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.

[2] Gilbert, N. D. (1987). "Presentations of the Automorphism Group of a Free Product". Proceedings of the London Mathematical Society. s3-54 (1): 115–140. doi:10.1112/plms/s3-54.1.115.

[1]

[2]