Presentation of a group
Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, one method of defining a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

 is by a presentation. One specifies a set S of generators
Generating set of a group
In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...

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


Informally, G has the above presentation if it is the "freest group" generated by S subject only to the relations R. Formally, the group G is said to have the above presentation if it is isomorphic
Group isomorphism
In abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations. If there exists an isomorphism between two groups, then the groups are called isomorphic...

 to the quotient
Quotient group
In mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...

 of a free group
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

 on S by the normal subgroup generated by
Conjugate closure
In group theory, the conjugate closure of a subset S of a group G is the subgroup of G generated by SG, i.e. the closure of SG under the group operation, where SG is the conjugates of the elements of S:The conjugate closure of S is denoted or G.The conjugate closure of any subset S of a group G...

 the relations R.

As a simple example, the cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

 of order n has the presentation


where 1 is the group identity. This may be written equivalently as


since terms that don't include an equals sign are taken to be equal to the group identity. Such terms are called relators, distinguishing them from the relations that include an equals sign.

Every group has a presentation, and in fact many different presentations; a presentation is often the most compact way of describing the structure of the group.

A closely related but different concept is that of an absolute presentation
Absolute presentation of a group
In mathematics, one method of defining a group is by an absolute presentation.Recall that to define a group G\ by means of a presentation, one specifies a set S\ of generators so that every element of the group can be written as a product of some of these generators, and a set R\ of relations...

 of a group.

Background

A free group
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

 on a set S is a group where each element can be uniquely described as a finite length product of the form:


where the si are elements of S, adjacent si are distinct, and ai are non-zero integers (but n may be zero). In less formal terms, the group consists of words in the generators and their inverses, subject only to canceling a generator with its inverse.

If G is any group, and S is a generating subset of G, then every element of G is also of the above form; but in general, these products will not uniquely describe an element of G.

For example, the dihedral group
Dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...

 D of order sixteen can be generated by a rotation, r, of order 8; and a flip, f, of order 2; and certainly any element of D is a product of r 's and f 's.

However, we have, for example, r f r = f, r 7 = r −1, etc.; so such products are not unique in D. Each such product equivalence can be expressed as an equality to the identity; such as
r f r f = 1
r 8 = 1
f 2 = 1.


Informally, we can consider these products on the left hand side as being elements of the free group F = <r,f>, and can consider the subgroup R of F which is generated by these strings; each of which would also be equivalent to 1 when considered as products in D.

If we then let N be the subgroup of F generated by all conjugates x −1 R x of R, then it is straightforward to show that every element of N is a finite product x1 −1 r1 x1 . . . xm −1 rm xm of members of such conjugates. It follows that
N is a normal subgroup of F; and that each element of N, when considered as a product in D, will also evaluate to 1. Thus D is isomorphic to the quotient group
Quotient group
In mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...

 F /N. We then say that D has presentation

Formal definition

Let S be a set and let FS be the free group
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

 on S. Let R be a set of words on S, so R naturally gives a subset of FS. To form a group with presentation <S|R> the idea is take the smallest quotient of FS (that is, the largest subgroup of FS) so that each element of R gets identified with the identity element. Note that R may not be a subgroup
Subgroup
In group theory, 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 G if the restriction of * to H x H is a group operation on H...

, let alone a normal subgroup
Normal subgroup
In abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....

 of FS, so we cannot take a naive quotient by R. The solution is to take the normal closure
Normal closure
The term normal closure is used in two senses in mathematics:* In group theory, the normal closure of a subset of a group is the smallest normal subgroup that contains the subset; see conjugate closure....

 N of R in FS, which is defined as the smallest normal subgroup in FS which contains R. The group <S|R> is then defined as the quotient group
Quotient group
In mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...


The elements of S are called the generators of <S|R> and the elements of R are called the relators. A group G is said to have the presentation <S|R> if G is isomorphic to <S|R>.

It is a common practice to write relators in the form = where and are words on . What this means is that . This has the intuitive meaning that the images of x and y are supposed to be equal in the quotient group. Thus e.g. in the list of relators is equivalent with .
Another common shorthand is to write for a commutator
Commutator
In mathematics, the commutator gives an indication of the extent to which a certain binary operation fails to be commutative. There are different definitions used in group theory and ring theory.-Group theory:...

 .

A presentation is said to be finitely generated if is finite and finitely related if is finite. If both are finite it is said to be a finite presentation. A group is finitely generated (respectively finitely related, finitely presented) if it has a presentation that is finitely generated (respectively finitely related, a finite presentation).

If is indexed by a set consisting of all the natural numbers or a finite subset of them, then it is easy to set up a simple one to one coding (or Gödel numbering) from the free group on to the natural numbers, such that we can find algorithms that, given , calculate , and vice versa. We can then call a subset of recursive
Recursive set
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....

 (respectively recursively enumerable) if is recursive (respectively recursively enumerable). If is indexed as above and recursively enumerable, then the presentation is a recursive presentation and the corresponding group is recursively presented. This usage may seem odd, but it is possible to prove that if a group has a presentation with recursively enumerable then it has another one with recursive.

For a finite group , the multiplication table provides a presentation. We take to be the elements of and to be all words of the form , where is an entry in the multiplication table. A presentation can then be thought of as a generalization of a multiplication table.

Every finitely presented group is recursively presented, but there are recursively presented groups that cannot be finitely presented. However a theorem of Graham Higman
Graham Higman
Graham Higman FRS was a leading British mathematician. He is known for his contributions to group theory....

 states that a finitely generated group has a recursive presentation if and only if it can be embedded in a finitely presented group. From this we can deduce that there are (up to isomorphism) only countably many finitely generated recursively presented groups. Bernhard Neumann
Bernhard Neumann
Bernhard Hermann Neumann AC FRS was a German-born British mathematician who was one of the leading figures in group theory, greatly influencing the direction of the subject....

 has shown that there are uncountably many non-isomorphic two generator groups. Therefore there are finitely generated groups that cannot be recursively presented.

History

One of the earliest presentations of a group by generators and relations was given by the Irish mathematician William Rowan Hamilton
William Rowan Hamilton
Sir William Rowan Hamilton was an Irish physicist, astronomer, and mathematician, who made important contributions to classical mechanics, optics, and algebra. His studies of mechanical and optical systems led him to discover new mathematical concepts and techniques...

 in 1856, in his Icosian Calculus
Icosian Calculus
The Icosian Calculus is a non-commutative algebraic structure discovered by the Irish mathematician William Rowan Hamilton in 1856.In modern terms, he gave a group presentation of the icosahedral rotation group by generators and relations....

 – a presentation of the icosahedral group.

The first systematic study was given by Walther von Dyck
Walther von Dyck
Walther Franz Anton von Dyck , born Dyck and later ennobled, was a German mathematician...

, student of Felix Klein
Felix Klein
Christian Felix Klein was a German mathematician, known for his work in group theory, function theory, non-Euclidean geometry, and on the connections between geometry and group theory...

, in the early 1880s, laying the foundations for combinatorial group theory
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...

.

Common examples

The following table lists some examples of presentations for commonly studied groups. Note that in each case there are many other presentations that are possible. The presentation listed is not necessarily the most efficient one possible.
Group Presentation Comments
the free group
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

 on S
A free group is "free" in the sense that it is subject to no relations.
Cn, the cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

 of order n
D2n, the dihedral group
Dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...

 of order 2n
Here r represents a rotation and f a reflection
D, the infinite dihedral group
Infinite dihedral group
In mathematics, the infinite dihedral group Dih∞ is an infinite group with properties analogous to those of the finite dihedral groups.-Definition:...

Dicn, the dicyclic group The quaternion group
Quaternion group
In group theory, the quaternion group is a non-abelian group of order eight, isomorphic to a certain eight-element subset of the quaternions under multiplication...

 is a special case when n = 2
Z × Z
Zm × Zn
the free abelian group
Free abelian group
In abstract algebra, a free abelian group is an abelian group that has a "basis" in the sense that every element of the group can be written in one and only one way as a finite linear combination of elements of the basis, with integer coefficients. Hence, free abelian groups over a basis B are...

 on S
where R is the set of all commutator
Commutator
In mathematics, the commutator gives an indication of the extent to which a certain binary operation fails to be commutative. There are different definitions used in group theory and ring theory.-Group theory:...

s of elements of S
the symmetric group
Symmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...

, Sn
generators:
relations:
  • ,
  • ,


The last set of relations can be transformed into

using .
Here is the permutation that swaps the ith element with the i+1 one. The product is a 3-cycle on the set .
the braid group
Braid group
In mathematics, the braid group on n strands, denoted by Bn, is a group which has an intuitive geometrical representation, and in a sense generalizes the symmetric group Sn. Here, n is a natural number; if n > 1, then Bn is an infinite group...

, Bn
generators:

relations:
  • ,
Note the similarity with the symmetric group; the only difference is the removal of the relation .
the tetrahedral group, TA4
the octahedral group, OS4
the icosahedral group
Icosahedral symmetry
A regular icosahedron has 60 rotational symmetries, and a symmetry order of 120 including transformations that combine a reflection and a rotation...

, IA5
the quaternion group
Quaternion group
In group theory, the quaternion group is a non-abelian group of order eight, isomorphic to a certain eight-element subset of the quaternions under multiplication...

, Q8
For an alternative presentation see Dicn above.
topologically you can visualize a and b as Dehn twist
Dehn twist
In geometric topology, a branch of mathematics, a Dehn twist is a certain type of self-homeomorphism of a surface .-Definition:...

s on the torus
Torus
In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...

non trivial - group extension
Group extension
In mathematics, a group extension is a general means of describing a group in terms of a particular normal subgroup and quotient group. If Q and N are two groups, then G is an extension of Q by N if there is a short exact sequence...

 of
PSL2(Z) is the free product
Free product
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 “most general” group having these properties...

 of the cyclic groups Z2 and Z3
Heisenberg group
Baumslag-Solitar group, B(m,n)
Tits group
Tits group
In mathematics, the Tits group 2F4′ is a finite simple group of order 17971200 = 211 · 33 · 52 · 13 found by ....

[a, b] is the commutator
Commutator
In mathematics, the commutator gives an indication of the extent to which a certain binary operation fails to be commutative. There are different definitions used in group theory and ring theory.-Group theory:...


Some theorems

Every group G has a presentation. To see this, consider the free group FG on G. By the universal property
Universal property
In various branches of mathematics, a useful construction is often viewed as the “most efficient solution” to a certain problem. The definition of a universal property uses the language of category theory to make this notion precise and to study it abstractly.This article gives a general treatment...

 of free groups, there exists a unique group homomorphism
Group homomorphism
In mathematics, given two groups and , a group homomorphism from to is a function h : G → H such that for all u and v in G it holds that h = h \cdot h...

 φ : FGG whose restriction to G is the identity map. Let K be the kernel
Kernel (algebra)
In the various branches of mathematics that fall under the heading of abstract algebra, the kernel of a homomorphism measures the degree to which the homomorphism fails to be injective. An important special case is the kernel of a matrix, also called the null space.The definition of kernel takes...

 of this homomorphism. Then K is normal in FG, therefore is equal to its normal closure, so <G|K> = FG/K. Since the identity map is surjective, φ is also surjective, so by the First Isomorphism Theorem, <G|K> = G. Note that this presentation may be highly inefficient if both G and K are much larger than necessary.

Every finite group has a finite presentation.

The negative solution to the word problem for groups
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 element...

 states that there is a finite presentation <S|R> for which there is no algorithm which, given two words u, v, decides whether u and v describe the same element in the group.

Constructions

Suppose G has presentation <S|R> and H has presentation <T|Q> with S and T being disjoint. Then
  • the free product
    Free product
    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 “most general” group having these properties...

    GH has presentation <S,T|R,Q> and
  • the direct product
    Direct product of groups
    In the mathematical field of group theory, the direct product is an operation that takes two groups and and constructs a new group, usually denoted...

    G × H has presentation <S,T|R,Q, [S,T]>, where [S,T] means that every element from S commutes with every element from T (cf. commutator
    Commutator
    In mathematics, the commutator gives an indication of the extent to which a certain binary operation fails to be commutative. There are different definitions used in group theory and ring theory.-Group theory:...

    ).

Geometric group theory

A presentation of a group determines a geometry, in the sense of geometric group theory
Geometric group theory
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 act .Another important...

: one has the Cayley graph
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...

, which has a metric
Metric (mathematics)
In mathematics, a metric or distance function is a function which defines a distance between elements of a set. A set with a metric is called a metric space. A metric induces a topology on a set but not all topologies can be generated by a metric...

, called the word metric. These are also two resulting orders, the weak order and the Bruhat order
Bruhat order
In mathematics, the Bruhat order is a partial order on the elements of a Coxeter group, that corresponds to the inclusion order on Schubert varieties.-History:The Bruhat order on the Schubert varieties of a flag manifold or Grassmannian...

,
and corresponding Hasse diagram
Hasse diagram
In order theory, a branch of mathematics, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction...

s. An important example is in the Coxeter group
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 mirror symmetries. Indeed, the finite Coxeter groups are precisely the finite Euclidean reflection groups; the symmetry groups of regular polyhedra are an example...

s.

Further, some properties of this graph (the coarse geometry) are intrinsic, meaning independent of choice of generators.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK