Presentation of a 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 a set R of relations among those generators. We then say G has presentation

: <math>\langle S \mid R\rangle.</math>

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 to the quotient of a free group on S by the normal subgroup generated by the relations R.

As a simple example, the cyclic group of order n has the presentation

: <math>\langle a \mid a^n = 1\rangle,</math>

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

: <math>\langle a \mid a^n\rangle,</math>

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 on a set S is a group where each element can be uniquely described as a finite length product of the form:

: <math>s_1^{a_1} s_2^{a_2} \cdots s_n^{a_n}</math>

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 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 rs and fs.

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 let . That is, we let R be the subgroup generated by the strings rfrf, r8, f2, each of which is also equivalent to 1 when considered as products in D8.

If we then let N be the subgroup of F generated by all conjugates x−1Rx of R, then it follows by definition that every element of N is a finite product x1−1r1x1 ... xm−1rm 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 . We then say that D8 has presentation

: <math>\langle r, f \mid r^8 = 1, f^2 = 1, (rf)^2 = 1\rangle.</math>

Here the set of generators is , and the set of relations is . We often see R abbreviated, giving the presentation

: <math>\langle r, f \mid r^8 = f^2 = (rf)^2 = 1\rangle.</math>

An even shorter form drops the equality and identity signs, to list just the set of relators, which is . Doing this gives the presentation

: <math>\langle r, f \mid r^8, f^2, (rf)^2 \rangle.</math>

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 on S. Let R be a set of words on S, so R naturally gives a subset of <math>F_S</math>. To form a group with presentation <math>\langle S \mid R\rangle</math>, take the quotient of <math>F_S</math> by the smallest normal subgroup that contains each element of R. (This subgroup is called the normal closure N of R in <math>F_S</math>.) The group <math>\langle S \mid R\rangle</math> is then defined as the quotient group

:<math>\langle S \mid R \rangle = F_S / N.</math>

The elements of S are called the generators of <math>\langle S \mid R\rangle</math> and the elements of R are called the relators. A group G is said to have the presentation <math>\langle S \mid R\rangle</math> if G is isomorphic to <math>\langle S \mid R\rangle</math>.

It is a common practice to write relators in the form <math>x = y</math> where x and y are words on S. What this means is that <math>y^{-1}x\in R</math>. 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 <math>r^n=1</math>. 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 in 1856, in his icosian calculus – a presentation of the icosahedral group.

The first systematic study was given by Walther von Dyck, student of Felix Klein, 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.

{| border=1 class="wikitable"

! Group || Presentation || Comments

| the free group on S || <math>\langle S \mid \varnothing \rangle</math>

| A free group is "free" in the sense that it is subject to no relations.

|<math>\pi_1(S_g)</math>, the surface group of orientable genus <math>g\ge 0</math>

|<math>\left\langle a_1, b_1,\ldots, a_g, b_g | [a_1, b_1][a_2, b_2]\ldots [a_g, b_g] \right\rangle</math>

|The bracket stands for the commutator: <math>[a, b] = aba^{-1}b^{-1}</math>

| Cn, the cyclic group of order n

| <math>\langle a \mid a^n \rangle</math>

| Dn, the dihedral group of order 2n

| <math>\langle r,f \mid r^n , f^2 , (rf)^2 \rangle</math>

| Here r represents a rotation and f a reflection

| D∞, the infinite dihedral group

| <math>\langle r,f \mid f^2, (rf)^2 \rangle</math>

| Dicn, the dicyclic group of order 4n

| <math>\langle r,f \mid r^{2n}, r^n=f^2, frf^{-1}=r^{-1} \rangle</math>

| The quaternion group Q8 is a special case when

| Z × Z

| <math>\langle x,y \mid xy = yx \rangle</math>

| Z/mZ × Z/nZ

| <math>\langle x,y \mid x^m, y^n, xy=yx \rangle</math>

| the free abelian group on S

| <math>\langle S \mid R \rangle</math> where R is the set of all commutators of elements of S

| Sn, the symmetric group on n symbols

| generators: <math>\sigma_1, \ldots, \sigma_{n-1}</math>relations:

<math>\sigma_i^2 = 1</math>,
<math>\sigma_i\sigma_j = \sigma_j\sigma_i \mbox{ if } j \neq i\pm 1</math>,
<math>\sigma_i\sigma_{i+1}\sigma_i = \sigma_{i+1}\sigma_i\sigma_{i+1} </math>

The last set of relations can be transformed into

<math>{(\sigma_i\sigma_{i+1)^3=1\ </math>

using <math>\sigma_i^2=1 </math>.

| Here σi is the permutation that swaps the ith element with the i+1st one. The product σiσi+1 is a 3-cycle on the set {i, i+1, i+2}.

| Bn, the braid groups

| generators: <math>\sigma_1, \ldots, \sigma_{n-1}</math>

relations:

<math>\sigma_i\sigma_j = \sigma_j\sigma_i \mbox{ if } j \neq i\pm 1</math>,
<math>\sigma_i\sigma_{i+1}\sigma_i = \sigma_{i+1}\sigma_i\sigma_{i+1}\ </math>

| Note the similarity with the symmetric group; the only difference is the removal of the relation <math>\sigma_i^2 = 1</math>.

| , the Klein 4 group

| <math>\langle s,t \mid s^2, t^2, (st)^2 \rangle</math>

| , the tetrahedral group

| <math>\langle s,t \mid s^2, t^3, (st)^3 \rangle</math>

| , the octahedral group

| <math>\langle s,t \mid s^2, t^3, (st)^4 \rangle</math>

| , the icosahedral group

| <math>\langle s,t \mid s^2, t^3, (st)^5 \rangle</math>

| Q8, the quaternion group

| <math>\langle i,j \mid i^4, jij = i, iji = j \rangle\,</math>

| For an alternative presentation see Dicn above with .

| SL(2, Z)

| <math>\langle a,b \mid aba=bab, (aba)^4 \rangle</math>

| topologically a and b can be visualized as Dehn twists on the torus

| GL(2, Z)

| <math>\langle a,b,j \mid aba=bab, (aba)^4,j^2,(ja)^2,(jb)^2 \rangle</math>

| nontrivial Z/2Z – group extension of SL(2, Z)

| PSL(2, Z), the modular group

| <math>\langle a,b \mid a^2, b^3 \rangle</math>

| PSL(2, Z) is the free product of the cyclic groups Z/2Z and Z/3Z

| Heisenberg group

| <math>\langle x,y,z \mid z=xyx^{-1}y^{-1}, xz=zx, yz=zy \rangle</math>

| BS(m, n), the Baumslag–Solitar groups

| <math>\langle a, b \mid a^n = b a^m b^{-1} \rangle</math>

| Tits group

| <math>\langle a, b \mid a^2, b^3, (ab)^{13}, [a, b]^5, [a, bab]^4, ((ab)^4 ab^{-1})^6 \rangle</math>

| [a, b] is the commutator

An example of a finitely generated group that is not finitely presented is the wreath product <math>\mathbf{Z} \wr \mathbf{Z}</math> of the group of integers with itself.

Some theorems

<blockquote>Theorem. Every group has a presentation.</blockquote>

To see this, given a group G, consider the free group FG on G. By the universal property of free groups, there exists a unique group homomorphism 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.

<blockquote>Corollary. Every finite group has a finite presentation.</blockquote>

One may take the elements of the group for generators and the Cayley table for relations.

Novikov–Boone theorem

The negative solution to the word problem for groups 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 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 has presentation ;
the direct product has presentation , where [S, T] means that every element from S commutes with every element from T (cf. commutator); and
the semidirect product has presentation .

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, which has a metric, 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) are intrinsic, meaning independent of choice of generators.

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, etc.
― fundamental algorithms from theoretical computer science, computational number theory, and computational commutative algebra, etc.

External links

Small groups and their presentations on GroupNames