HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 :\langle S \mid R\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, 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 i ...
to the
quotient In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
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' ...
on ''S'' by the normal subgroup generated by the relations ''R''. As a simple example, the
cyclic group In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
of order ''n'' has the presentation :\langle a \mid a^n = 1\rangle, where 1 is the group identity. This may be written equivalently as :\langle a \mid a^n\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 group.


Background

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' ...
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^ \cdots s_n^ 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 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
dihedral group In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ...
D8 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 D8 is a product of ''r''s and ''f''s. However, we have, for example, , , etc., so such products are ''not unique'' in D8. 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 D8. 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 ... ''xm''−1''rm'' ''xm'' of members of such conjugates. It follows that each element of ''N'', when considered as a product in D8, will also evaluate to 1; and thus that ''N'' is a normal subgroup of ''F''. Thus D8 is isomorphic to the
quotient group A quotient group or factor group is a mathematical 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 "factored" out). For exam ...
. We then say that D8 has presentation :\langle r, f \mid r^8 = 1, f^2 = 1, (rf)^2 = 1\rangle. Here the set of generators is , and the set of relations is . We often see ''R'' abbreviated, giving the presentation :\langle r, f \mid r^8 = f^2 = (rf)^2 = 1\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 :\langle r, f \mid r^8, f^2, (rf)^2 \rangle. All three presentations are equivalent.


Notation

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 ''FS'' be the
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' ...
on ''S''. Let ''R'' be a set of
words A word is a basic element of language that carries an objective or practical 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 conse ...
on ''S'', so ''R'' naturally gives a subset of F_S. To form a group with presentation \langle S \mid R\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 \langle S \mid R\rangle is then defined as the
quotient group A quotient group or factor group is a mathematical 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 "factored" out). For exam ...
:\langle S \mid R \rangle = F_S / N. The elements of ''S'' are called the generators of \langle S \mid R\rangle and the elements of ''R'' are called the relators. A group ''G'' is said to have the presentation \langle S \mid R\rangle if ''G'' is isomorphic to \langle S \mid R\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\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, ''rn'' 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.


Alternate definition

The definition of group presentation may alternatively be recast in terms of
equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es of words on the alphabet S \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 theory.


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 (or
Gödel numbering In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of h ...
) 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 ''FS'' recursive (respectively recursively enumerable) 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 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 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 Sir William Rowan Hamilton Doctor of Law, LL.D, Doctor of Civil Law, DCL, Royal Irish Academy, MRIA, Royal Astronomical Society#Fellow, FRAS (3/4 August 1805 – 2 September 1865) was an Irish mathematician, astronomer, and physicist. He was the ...
in 1856, in his icosian calculus – a presentation of the icosahedral group. 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 ennobled, was a German mathematician. He is credited with being the first to define a mathematical group, in the modern sense in . He laid the foundations ...
, 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 grou ...
, in the early 1880s, laying the foundations for combinatorial group theory.


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 a finitely generated group that is not finitely presented is the
wreath product In group theory, the wreath product is a special combination of two groups based on the semidirect product. It is formed by the action of one group on many copies of another group, somewhat analogous to exponentiation. Wreath products are used i ...
\mathbf \wr \mathbf of the group of
integers An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
with itself.


Some theorems

Theorem. Every group has a presentation.
To see this, given a group ''G'', consider the free group ''FG'' on ''G''. By the
universal property In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fr ...
of free groups, there exists a unique
group homomorphism In mathematics, given two groups, (''G'', ∗) and (''H'', ·), a group homomorphism from (''G'', ∗) to (''H'', ·) is a function ''h'' : ''G'' → ''H'' such that for all ''u'' and ''v'' in ''G'' it holds that : h(u*v) = h(u) \cdot h(v) w ...
whose restriction to ''G'' is the identity map. Let ''K'' be the kernel of this homomorphism. Then ''K'' is normal in ''FG'', therefore is equal to its normal closure, so . Since the identity map is surjective, ''φ'' is also surjective, so by the First Isomorphism Theorem, . 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 mathematician Arthur Cayley, a Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements in a square table reminiscent of an addition or multiplic ...
for relations.


Novikov–Boone theorem

The negative solution to 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 ...
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 Pyotr Sergeyevich Novikov (russian: Пётр Серге́евич Но́виков; 15 August 1901, Moscow, Russian Empire – 9 January 1975, Moscow, Soviet Union) was a Soviet mathematician. Novikov is known for his work on combinatorial pr ...
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 * the
free product In mathematics, specifically group theory, the free product is an operation that takes two groups ''G'' and ''H'' and constructs a new The result contains both ''G'' and ''H'' as subgroups, is generated by the elements of these subgroups, and is ...
has presentation and * the
direct product In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one t ...
has presentation , where 'S'', ''T''means that every element from ''S'' commutes with every element from ''T'' (cf.
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 The commutator of two elements, ...
).


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 of geometric group theory: one has the
Cayley graph 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 (named after Arthur Cay ...
, which has a
metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathe ...
, called the word metric. These are also two resulting orders, the ''weak order'' and the '' Bruhat order'', and corresponding Hasse diagrams. An important example is in the Coxeter groups. Further, some properties of this graph (the
coarse geometry In the mathematical fields of geometry and topology, a coarse structure on a set ''X'' is a collection of subsets of the cartesian product ''X'' × ''X'' with certain properties which allow the ''large-scale structure'' of metric spaces and topo ...
) are intrinsic, meaning independent of choice of generators.


See also

*
Nielsen transformation In mathematics, especially in the area of abstract algebra known as combinatorial group theory, Nielsen transformations, named after Jakob Nielsen, are certain automorphisms of a free group which are a non-commutative analogue of row reduction a ...
* Tietze transformation * Presentation of a module *
Presentation of a monoid In algebra, a presentation of a monoid (or a presentation of a semigroup) is a description of a monoid (or a semigroup) in terms of a set of generators and a set of relations on the free monoid (or the free semigroup ) generated by . The monoid ...


Notes


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 In mathematics, the Golod–Shafarevich theorem was proved in 1964 by Evgeny Golod and Igor Shafarevich. It is a result in non-commutative homological algebra which solves the class field tower problem, by showing that class field towers can be ...
, 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, Yves
Small groups and their presentations on GroupNames
Combinatorial group theory Combinatorics on words