In
mathematics, especially in the area of
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathematics), fields, module (mathe ...
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 nat ...
, Nielsen transformations, named after
Jakob Nielsen Jacob or Jakob Nielsen may refer to:
* Jacob Nielsen, Count of Halland (died c. 1309), great grandson of Valdemar II of Denmark
* , Norway (1768-1822)
* Jakob Nielsen (mathematician) (1890–1959), Danish mathematician known for work on automorphi ...
, are certain
automorphisms
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all 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''−1' ...
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 operations performed on the corresponding matrix (mathematics), matrix of coefficients. This me ...
and one of the main tools used in studying free groups, . They were introduced in to prove that every
subgroup
In group theory, a branch of mathematics, 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 a free group is free (the
Nielsen–Schreier theorem), but are now used in a variety of mathematics, including
computational group theory
In mathematics, computational group theory is the study of
groups by means of computers. It is concerned
with designing and analysing algorithms and
data structures to compute information about groups. The subject
has attracted interest because f ...
,
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. 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
1, ..., ''x''''n'' ">''x''1, ..., ''x''''n'' can be factored into elementary Nielsen transformations of the following sorts:
* Switch ''x''
1 and ''x''
2
* Cyclically permute ''x''
1, ''x''
2, ..., ''x''
''n'', to ''x''
2, ..., ''x''
''n'', ''x''
1.
* Replace ''x''
1 with ''x''
1−1
* Replace ''x''
1 with ''x''
1·''x''
2
These transformations are the analogues of the
elementary row operations In mathematics, an elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group GL''n''(F) when F is a field. Left multiplication (pre-multi ...
. 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
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 refle ...
. 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:
*
−1, ''y'' ">''x''−1, ''y'' type 3
*
−1 ">''y'', ''x''−1 type 1
*
−1, ''x''−1 ">''y''−1, ''x''−1 type 3
*
−1''x''−1, ''x''−1 ">''y''−1''x''−1, ''x''−1 type 4
*
−1 ">''xy'', ''x''−1 type 3
*
−1, ''xy'' ">''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.
[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. There are similar results for ]polycyclic group
In mathematics, a polycyclic group is a solvable group that satisfies the maximal condition on subgroups (that is, every subgroup is finitely generated). Polycyclic groups are finitely presented, which makes them interesting from a computational ...
s, and certain other finitely generated group
In algebra, a finitely generated group is a group ''G'' that has some finite generating set ''S'' so that every element of ''G'' can be written as the combination (under the group operation) of finitely many elements of ''S'' and of inverses o ...
s as well. 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 , 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 group. Nielsen, and later
Bernhard Neumann
Bernhard Hermann Neumann (15 October 1909 – 21 October 2002) was a German-born British-Australian mathematician, who was a leader in the study of group theory.
Early life and education
After gaining a D.Phil. from Friedrich-Wilhelms Universit ...
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 the textbook .
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, .
Word problem
A particularly simple case of the
word 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 el ...
and the
isomorphism problem for groups
In abstract algebra, the group isomorphism problem is the decision problem of determining whether two given finite group presentations refer to isomorphic groups.
The isomorphism problem was formulated by Max Dehn, and together with the word pr ...
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 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 and so it is usuall ...
. This is known to be intractable in general, even though there is a finite sequence of elementary
Tietze transformation In group theory, Tietze transformations are used to transform a given presentation of a group into another, often simpler presentation of the same group. These transformations are named after Heinrich Franz Friedrich Tietze who introduced them in a ...
s 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
In abstract algebra, the group isomorphism problem is the decision problem of determining whether two given finite group presentations refer to isomorphic groups.
The isomorphism problem was formulated by Max Dehn, and together with the word pr ...
concerns the fundamental groups of three-dimensional
knots
A knot is a fastening in rope or interwoven lines.
Knot may also refer to:
Places
* Knot, Nancowry, a village in India
Archaeology
* Knot of Isis (tyet), symbol of welfare/life.
* Minoan snake goddess figurines#Sacral knot
Arts, entertainme ...
, 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
groups by means of computers. It is concerned
with designing and analysing algorithms and
data structures to compute information about groups. The subject
has attracted interest because f ...
, 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
In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space.
An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...
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
Burn-in is the process by which components of a system are exercised before being placed in service (and often, before the system being completely assembled from those components). This testing process will force certain failures to occur under ...
)
** 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 de ...
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 In group theory, Tietze transformations are used to transform a given presentation of a group into another, often simpler presentation of the same group. These transformations are named after Heinrich Franz Friedrich Tietze who introduced them in a ...
*
Automorphism 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 ...
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