Nielsen Transformation
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, especially in the area of modern algebra known as
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. It is much used in geometric topology, the fundamental group of a simplicial complex having in a na ...
, Nielsen transformations are certain automorphisms of a
free group In mathematics, the free group ''F'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 (e.g. ''st'' = ''suu''− ...
which are a non-commutative analogue of
row reduction In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can als ...
and one of the main tools used in studying free groups . Given a finite basis of a free group F_n, the corresponding set of elementary Nielsen transformations forms a finite generating set of \mathrm(F_n). This system of generators is analogous to elementary matrices for GL_n(\Z) and Dehn twists for mapping class groups of closed surfaces. Nielsen transformations were introduced in to prove that every
subgroup In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G. Formally, given a group (mathematics), group under a binary operation  ...
of a free group is free (the
Nielsen–Schreier theorem 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. Statement of the theorem A free group may be defined from a gro ...
). They are now used in a variety of mathematics, including
computational group theory In mathematics, computational group theory is the study of group (mathematics), groups by means of computers. It is concerned with designing and analysing algorithms and data structures to compute information about groups. The subject has attracte ...
,
k-theory In mathematics, K-theory is, roughly speaking, the study of a ring generated by vector bundles over a topological space or scheme. In algebraic topology, it is a cohomology theory known as topological K-theory. In algebra and algebraic geometr ...
, and
knot theory In topology, knot theory is the study of knot (mathematics), mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are joined so it cannot be und ...
.


Definitions


Free groups

Let F_n be a finitely generated free group of rank n. An elementary Nielsen transformation maps an ordered basis _1,\ldots, x_n/math> to a new basis _1,\ldots,y_n/math> by one of the following operations: # Permute the x_is by some
permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...
\sigma\in S_n, i.e. _1,\ldots,y_n= _,\ldots, x_/math> # Invert some x_i, i.e. _1,\ldots,y_n= _1,\ldots, x_i^,\ldots,x_n/math> # Replace some x_i with x_ix_j for some j\ne i, i.e. _1,\ldots,y_n= _1,\ldots, x_ix_j,\ldots,x_n/math>. 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 In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
\mathrm(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 F_n on bases. Elementary Nielsen transformations are the analogues of the
elementary row operations In mathematics, an elementary matrix is a square matrix obtained from the application of a single elementary row operation to the identity matrix. The elementary matrices generate the general linear group when is a field. Left multiplication ...
. 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_) \mapsto \mapsto \mapsto () \mapsto \mapsto (x_x_i^, x_i) \mapsto (x_, x_i)that elementary Nielsen transformations of type 2 and 3 are in fact enough to generate all Nielsen transformations. Using the two generators (1 2) and (1 \ldots n) of S_n, one can alternatively restrict attention to only four operations: * switch x_1 and x_2 * cyclically permute the x_is * invert x_1 * replace x_1 with x_1x_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 In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equ ...
). 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 In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections (or kaleidoscopic mirrors). Indeed, the finite Coxeter groups are precisely the finite Euclidean ref ...
. 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''−1''x''−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


Applications


Nielsen–Schreier theorem

The Nielsen-Schreier theorem states that every subgroup F' \le F of a free group 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 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 , 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 .


Automorphism groups

In , 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 group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
s of free groups. This is also described in standard textbooks such as . 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, . 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.


Word problem

A particularly simple case of the
word problem for groups A word is a basic element of language that carries meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consensus among linguists on its ...
and the isomorphism problem for groups asks if a
finitely presented group 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 ...
is the
trivial group In mathematics, a trivial group or zero group is a group that consists 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 and so it is usu ...
. 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.


Isomorphism problem

A particularly important special case of the isomorphism problem for groups concerns the fundamental groups of three-dimensional
knots A knot is a fastening in rope or interwoven lines. Knot or knots may also refer to: Other common meanings * Knot (unit), of speed * Knot (wood), a timber imperfection Arts, entertainment, and media Films * ''Knots'' (film), a 2004 film * ''Kn ...
, which can be solved using Nielsen transformations and a method of J. W. Alexander .


Product replacement algorithm

In
computational group theory In mathematics, computational group theory is the study of group (mathematics), groups by means of computers. It is concerned with designing and analysing algorithms and data structures to compute information about groups. The subject has attracte ...
, it is important to generate random elements of a
finite group In abstract algebra, a finite group is a group whose underlying set is finite. Finite groups often arise when considering symmetry of mathematical or physical objects, when those objects admit just a finite number of structure-preserving tra ...
. Popular methods of doing this apply
Markov chain In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally ...
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 In mathematics, a random walk, sometimes known as a drunkard's walk, is a stochastic process that describes a path that consists of a succession of random steps on some Space (mathematics), mathematical space. An elementary example of a rand ...
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 in) ** Choose integers ''i'' and ''j'' uniformly at random from 1 to ''n'', and choose ''e'' uniformly at random from ** Replace the ''i''th generator with the product of the ''i''th generator and the ''j''th generator raised to the ''e''th 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 In mathematics, particularly in group theory, the Frattini subgroup \Phi(G) of a group is the intersection of all maximal subgroups of . For the case that has no maximal subgroups, for example the trivial group or a Prüfer group, it is def ...
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 ''k''th generator.


K-theory

To understand Nielsen equivalence of non-minimal generating sets, module theoretic 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.


See also

* Tietze transformation * Automorphism group of a free group


References


Notes


Textbooks and surveys

* * * *


Primary sources

* * * * * * * * * * {{Citation , last1=Rapaport , first1=Elvira Strasser , title=Note on Nielsen transformations , doi=10.2307/2033582 , mr=0104724 , year=1959 , journal=Proceedings of the American Mathematical Society , volume=10 , pages=228–235 , issue=2 , jstor=2033582, doi-access=free Combinatorial group theory Computational group theory Combinatorics on words