In

_{i}'' are elements of S, adjacent ''s_{i}'' are distinct, and ''a_{i}'' 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 an adjacent occurrence of 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 _{8} 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_{8} is a product of ''r''s and ''f''s.
However, we have, for example, , , etc., so such products are ''not unique'' in D_{8}. Each such product equivalence can be expressed as an equality to the identity, such as
:,
:, or
:.
Informally, we can consider these products on the left hand side as being elements of the free group , 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_{8}.
If we then let ''N'' be the subgroup of ''F'' generated by all conjugates ''x''^{−1}''Rx'' of ''R'', then it follows by definition that every element of ''N'' is a finite product ''x''_{1}^{−1}''r''_{1}''x''_{1} ... ''x_{m}''^{−1}''r_{m}'' ''x_{m}'' of members of such conjugates. It follows that each element of ''N'', when considered as a product in D_{8}, will also evaluate to 1; and thus that ''N'' is a normal subgroup of ''F''. Thus D_{8} is isomorphic to the _{8} has presentation
:$\backslash langle\; r,\; f\; \backslash mid\; r^8\; =\; 1,\; f^2\; =\; 1,\; (rf)^2\; =\; 1\backslash rangle.$
Here the set of generators is , and the set of relations is . We often see ''R'' abbreviated, giving the presentation
:$\backslash langle\; r,\; f\; \backslash mid\; r^8\; =\; f^2\; =\; (rf)^2\; =\; 1\backslash rangle.$
An even shorter form drops the equality and identity signs, to list just the set of relators, which is . Doing this gives the presentation
:$\backslash langle\; r,\; f\; \backslash mid\; r^8,\; f^2,\; (rf)^2\; \backslash rangle.$
All three presentations are equivalent.

_{S}'' be the ^{n}'' in the list of relators is equivalent with $r^n=1$.
For a finite group ''G'', it is possible to build a presentation of ''G'' from the group multiplication table, as follows. Take ''S'' to be the set elements $g\_i$ of ''G'' and ''R'' to be all words of the form $g\_ig\_jg\_k^$, where $g\_ig\_j=g\_k$ is an entry in the multiplication table.

_{S}''

_{G}'' on ''G''. By the _{G}'', therefore is equal to its normal closure, so . Since the identity map is surjective, ''φ'' is also surjective, so by the

Small groups and their presentations on GroupNames

Combinatorial group theory Combinatorics on words

mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...

, a presentation is one method of specifying a group
A group is a number
A number is a mathematical object used to counting, count, measurement, measure, and nominal number, label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with ...

. 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
:$\backslash langle\; S\; \backslash mid\; R\backslash rangle.$
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
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

to the quotient
In arithmetic
Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne' ...

of a free group
for the free group on two generators would look like. Each vertex represents an element of the free group, and each edge represents multiplication by ''a'' or ''b''.
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the stud ...

on ''S'' by the normal subgroup generated by the relations ''R''.
As a simple example, the cyclic group
In group theory
The popular puzzle Rubik's cube invented in 1974 by Ernő Rubik has been used as an illustration of permutation group">Ernő_Rubik.html" ;"title="Rubik's cube invented in 1974 by Ernő Rubik">Rubik's cube invented in 1974 by Er ...

of order ''n'' has the presentation
:$\backslash langle\; a\; \backslash mid\; a^n\; =\; 1\backslash rangle,$
where 1 is the group identity. This may be written equivalently as
:$\backslash langle\; a\; \backslash mid\; a^n\backslash rangle,$
thanks to the convention that terms that do not include an equals sign are taken to be equal to the group identity. Such terms are called relators, distinguishing them from the relations that do 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 of a groupIn mathematics, an absolute presentation is one method of defining a group (mathematics), group.B. Neumann, ''The isomorphism problem for algebraically closed groups,'' in: Word Problems, Decision Problems, and the Burnside Problem in Group Theory, A ...

.
Background

Afree group
for the free group on two generators would look like. Each vertex represents an element of the free group, and each edge represents multiplication by ''a'' or ''b''.
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the stud ...

on a set ''S'' is a group where each element can be ''uniquely'' described as a finite length product of the form:
:$s\_1^\; s\_2^\; \backslash cdots\; s\_n^$
where the ''sdihedral group
In mathematics, a dihedral group is the group (mathematics), group of symmetry, symmetries of a regular polygon, which includes rotational symmetry, rotations and reflection symmetry, reflections. Dihedral groups are among the simplest example ...

Dquotient group
A quotient group or factor group is a mathematical group (mathematics), group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is "factore ...

. We then say that DNotation

Although the notation used in this article for a presentation is now the most common, earlier writers used different variations on the same format. Such notations include the following: * * * *Definition

Let ''S'' be a set and let ''Ffree group
for the free group on two generators would look like. Each vertex represents an element of the free group, and each edge represents multiplication by ''a'' or ''b''.
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the stud ...

on ''S''. Let ''R'' be a set of words
In linguistics
Linguistics is the scientific study of language
A language is a structured system of communication used by humans, including speech (spoken language), gestures (Signed language, sign language) and writing. Most lang ...

on ''S'', so ''R'' naturally gives a subset of $F\_S$. To form a group with presentation $\backslash langle\; S\; \backslash mid\; R\backslash rangle$, take the quotient of $F\_S$ by the smallest normal subgroup that contains each element of ''R''. (This subgroup is called the normal closure ''N'' of ''R'' in $F\_S$.) The group $\backslash langle\; S\; \backslash mid\; R\backslash rangle$ is then defined as the quotient group
A quotient group or factor group is a mathematical group (mathematics), group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is "factore ...

:$\backslash langle\; S\; \backslash mid\; R\; \backslash rangle\; =\; F\_S\; /\; N.$
The elements of ''S'' are called the generators of $\backslash langle\; S\; \backslash mid\; R\backslash rangle$ and the elements of ''R'' are called the relators. A group ''G'' is said to have the presentation $\backslash langle\; S\; \backslash mid\; R\backslash rangle$ if ''G'' is isomorphic to $\backslash langle\; S\; \backslash mid\; R\backslash rangle$.
It is a common practice to write relators in the form $x\; =\; y$ where ''x'' and ''y'' are words on ''S''. What this means is that $y^x\backslash in\; R$. This has the intuitive meaning that the images of ''x'' and ''y'' are supposed to be equal in the quotient group. Thus, for example, ''rAlternate definition

The definition of group presentation may alternatively be recast in terms ofequivalence class
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

es of words on the alphabet $S\; \backslash cup\; S^$. In this perspective, we declare two words to be equivalent if it is possible to get from one to the other by a sequence of moves, where each move consists of adding or removing a consecutive pair $x\; x^$ or $x^\; x$ for some in , or by adding or removing a consecutive copy of a relator. The group elements are the equivalence classes, and the group operation is concatenation.
This point of view is particularly common in the field of combinatorial group theoryIn mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group by generator (mathematics), generators and relation (mathematics), relations. It is much used in geometric topology, the fundamental ...

.
Finitely presented groups

A presentation is said to be finitely generated if ''S'' is finite and finitely related if ''R'' is finite. If both are finite it is said to be a finite presentation. A group is finitely generated (respectively finitely related, ) if it has a presentation that is finitely generated (respectively finitely related, a finite presentation). A group which has a finite presentation with a single relation is called a one-relator group.Recursively presented groups

If ''S'' is indexed by a set ''I'' consisting of all the natural numbers N or a finite subset of them, then it is easy to set up a simple one to one coding (orGödel numbering
In mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical ...

) from the free group on ''S'' to the natural numbers, such that we can find algorithms that, given ''f''(''w''), calculate ''w'', and vice versa. We can then call a subset ''U'' of ''Frecursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics
Linguistics is the science, scientific study of language. It e ...

(respectively recursively enumerable
In computability theory, traditionally called recursion theory, a set ''S'' of natural numbers is called recursively enumerable, computably enumerable, semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is a ...

) if ''f''(''U'') is recursive (respectively recursively enumerable). If ''S'' is indexed as above and ''R'' 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 ''R'' recursively enumerable then it has another one with ''R'' recursive.
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 Fellow of the Royal Society, FRS (19 January 1917 – 8 April 2008) was a prominent English mathematician known for his contributions to group theory.
Biography
Higman was born in Louth, Lincolnshire and attended Sutton High Sc ...

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
In mathematics, a countable set is a Set (mathematics), set with the same cardinality (cardinal number, number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set. Whether f ...

many finitely generated recursively presented groups. Bernhard Neumann
Bernhard Hermann Neumann Companion of the Order of Australia, AC Fellow of the Royal Society, FRS (15 October 1909 – 21 October 2002) was a Germany, German-born United Kingdom, British-Australian mathematician who was a leader in the study of grou ...

has shown that there are uncountably
In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many Element (mathematics), elements to be countable set, countable. The uncountability of a set is closely related to its cardinal number: a set ...

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 mathematicianWilliam Rowan Hamilton
Sir William Rowan Hamilton LL.D, DCL, MRIA (4 August 1805 – 2 September 1865) was an Irish mathematician, Andrews Professor of Astronomy at Trinity College Dublin, Trinity College Dublin, and Dunsink Observatory#Directors, Royal Astronomer ...

in 1856, in his icosian calculus – a presentation of the icosahedral group
A regular icosahedron has 60 rotational (or orientation-preserving) symmetries, and a symmetry order of 120 including transformations that combine a reflection and a rotation. A regular dodecahedron has the same set of symmetries, since it is th ...

.
The first systematic study was given by Walther von Dyck
Walther Franz Anton von Dyck (6 December 1856 – 5 November 1934), born Dyck and later von, ennobled, was a Germany, German mathematician. He is credited with being the first to define a mathematical group (mathematics), group, in the modern sen ...

, student of Felix Klein
Christian Felix Klein (; 25 April 1849 – 22 June 1925) was a German mathematician and mathematics educator, known for his work with group theory, complex analysis, non-Euclidean geometry, and on the associations between geometry and group ...

, in the early 1880s, laying the foundations for combinatorial group theoryIn mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group by generator (mathematics), generators and relation (mathematics), relations. It is much used in geometric topology, the fundamental ...

.
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. An example of afinitely generated group
In algebra
Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In ...

that is not finitely presented is the wreath product
In group theory
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( ...

$\backslash mathbf\; \backslash wr\; \backslash mathbf$ of the group of integers
An integer (from the Latin
Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of t ...

with itself.
Some theorems

Theorem. Every group has a presentation.To see this, given a group ''G'', consider the free group ''F

universal property
In category theory
Category theory formalizes mathematical structure
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), ...

of free groups, there exists a unique group homomorphism
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...

whose restriction to ''G'' is the identity map. Let ''K'' be the kernel
Kernel may refer to:
Computing
* Kernel (operating system), the central component of most operating systems
* Kernel (image processing), a matrix used for image convolution
* Compute kernel, in GPGPU programming
* Kernel method, in machine learnin ...

of this homomorphism. Then ''K'' is normal in ''FFirst Isomorphism Theorem
In mathematics, specifically abstract algebra, the isomorphism theorems (also known as Noether's isomorphism theorems) are theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for ...

, . This presentation may be highly inefficient if both ''G'' and ''K'' are much larger than necessary.
Corollary. Every finite group has a finite presentation.One may take the elements of the group for generators and the

Cayley table Named after the 19th century British
British may refer to:
Peoples, culture, and language
* British people, nationals or natives of the United Kingdom, British Overseas Territories, and Crown Dependencies.
** Britishness, the British identity a ...

for relations.
Novikov–Boone theorem

The negative solution to theword 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 elem ...

states that there is a finite presentation for which there is no algorithm which, given two words ''u'', ''v'', decides whether ''u'' and ''v'' describe the same element in the group. This was shown by Pyotr Novikov 200px, ''P. S. Novikov''.
Pyotr Sergeyevich Novikov (russian: Пётр Серге́евич Но́виков; 15 August 1901, Moscow, Russian Empire – 9 January 1975, Moscow, Soviet Union) was a USSR, Soviet mathematician.
Novikov is known for hi ...

in 1955 and a different proof was obtained by William Boone in 1958.
Constructions

Suppose ''G'' has presentation and ''H'' has presentation with ''S'' and ''T'' being disjoint. Then * thefree product
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...

has presentation and
* the direct productIn mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...

has presentation , where 'S'', ''T''means that every element from ''S'' commutes with every element from ''T'' (cf. commutator
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gene ...

).
Deficiency

The deficiency of a finite presentation is just and the ''deficiency'' of a finitely presented group ''G'', denoted def(''G''), is the maximum of the deficiency over all presentations of ''G''. The deficiency of a finite group is non-positive. The Schur multiplicator of a finite group ''G'' can be generated by −def(''G'') generators, and ''G'' is efficient if this number is required.Geometric group theory

A presentation of a group determines a geometry, in the sense ofgeometric group theory
Geometric group theory is an area in mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mat ...

: one has the Cayley graph on two generators ''a'' and ''b''
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathemati ...

, which has a metric
METRIC (Mapping EvapoTranspiration at high Resolution with Internalized Calibration) is a computer model
Computer simulation is the process of mathematical modelling, performed on a computer, which is designed to predict the behaviour of or th ...

, called the word metricIn group theory
The popular puzzle Rubik's cube invented in 1974 by Ernő Rubik has been used as an illustration of permutation group">Ernő_Rubik.html" ;"title="Rubik's cube invented in 1974 by Ernő Rubik">Rubik's cube invented in 1974 by Ern ...

. These are also two resulting orders, the ''weak order'' and the ''Bruhat orderIn mathematics, the Bruhat order (also called strong order or strong Bruhat order or Chevalley order or Bruhat–Chevalley order or Chevalley–Bruhat order) is a partial order on the elements of a Coxeter group, that corresponds to the inclusion o ...

'', and corresponding Hasse diagram
In order theory
Order theory is a branch of mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they ...

s. An important example is in the Coxeter group
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...

s.
Further, some properties of this graph (the coarse geometry) are intrinsic, meaning independent of choice of generators.
See also

* Nielsen transformation * Tietze transformation * Presentation of a module * Presentation of a monoidNotes

References

* ― This useful reference has tables of presentations of all small finite groups, the reflection groups, and so forth. * ― Schreier's method, Nielsen's method, free presentations, subgroups and HNN extensions, Golod–Shafarevich theorem, etc. * ― fundamental algorithms from theoretical computer science, computational number theory, and computational commutative algebra, etc.External links

*{{MathWorld, title=Group Presentation, id=GroupPresentation, author= de Cornulier, YvesSmall groups and their presentations on GroupNames

Combinatorial group theory Combinatorics on words