Presentation to a group

In mathematics , the presentation (or presentation ) of a group is given by a set of elements that create the group and a set of relations that exist between these producers . For example, the cyclic group of the order is created by an element with the relation . Such a presentation is therefore also called representation by producers and relations. In more detail, this means the following: ${\displaystyle n}$ ${\displaystyle g}$ ${\displaystyle g^{n}=1}$

• Each element of the group can be written as the product of the specified producers (and their inverses).
• Any two such spellings of the same element differ only in the specified relations (and their consequences).

Any group can be presented this way, and thus presentations are a universal tool for constructing and exploring groups. Many infinite groups allow a finite presentation and thus an efficient description. The combinatorial group theory studied groups with the help of their presentations and this provides extensive techniques.

Motivation and History

In order to do some practical arithmetic in a group, it is often helpful to rely on a cleverly chosen number of producers. This is especially true if the group is large and complicated (or even infinite), but is generated by a small, clear set (in the best case finite). The corresponding idea for vector spaces over a body leads to the concept of the base , which is essential for linear algebra .

In general, one cannot expect such a simple structure for any groups: In order to determine the calculation rules in the group, one must specify the relations between the producers. These depend on the group under consideration and can be as complicated as desired. In this practical sense, the concept of presentation has been used since the dawn of group theory, albeit initially without a precise definition. Calculations with generators and relations can be found in the second half of the 19th century, for example in the works of Arthur Cayley , Henri Poincaré and Walther von Dyck . It was not until the 20th century that the practice of the groups finally presented was expanded into a theory, the combinatorial group theory, which was largely initiated by Max Dehn .

Introductory examples

The simplest case of a presentation is obtained for the group of whole numbers with their addition. This group can be created from a single element , namely or . In this case there are no relations and this is written as ${\displaystyle C=(\mathbb {Z} ,+)}$ ${\displaystyle s}$ ${\displaystyle s=1}$ ${\displaystyle s=-1}$

${\displaystyle C=\langle s\mid -\rangle }$.

Each element of is clearly written as with . In the absence of any relations one also speaks of the free group over the given generators. ${\displaystyle C}$ ${\displaystyle s^{k}}$ ${\displaystyle k\in \mathbb {Z} }$

If we now insert the relation , where , we get the group ${\displaystyle s^{n}=1}$ ${\displaystyle n\geq 1}$

${\displaystyle C_{n}=\langle s\mid s^{n}=1\rangle }$

Here, too, each element can be written as with . However, it also applies , and as a consequence for everyone . It follows that the group has exactly elements. It is called the cyclic group of order , and it is isomorphic to . ${\displaystyle C_{n}}$ ${\displaystyle s^{k}}$ ${\displaystyle k\in \mathbb {Z} }$ ${\displaystyle s^{n}=1}$ ${\displaystyle s^{k}=s^{k+n}}$ ${\displaystyle k}$ ${\displaystyle C_{n}=\{s,s^{2},s^{3},\dotsc ,s^{n}=1\}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

Universal construction

If you give yourself arbitrary generators and relations , then it is not initially clear whether and how a group can be defined. The following construction solves this problem by defining the group shown as the quotient of a free group: ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle \langle S\mid R\rangle }$

Given a set , the elements of which we want to use as generators in the following. Let the free group over . This consists of all reduced words with factors , where for all , and exponents , where for all . Furthermore, a lot of such words are over . We denote by the set of all conjugate elements where and . Let it be the subgroup of generated by the set . We call the set of all the consequences of the relations . It can also be described as the normal divisor generated by, and the term is used for this . ${\displaystyle S}$ ${\displaystyle F=F(S)}$ ${\displaystyle S}$ ${\displaystyle s_{1}^{e_{1}}s_{2}^{e_{2}}\cdots s_{n}^{e_{n}}}$ ${\displaystyle s_{1},s_{2},\dotsc ,s_{n}\in S}$ ${\displaystyle s_{i}\neq s_{i+1}}$ ${\displaystyle i}$ ${\displaystyle e_{1},e_{2},\dotsc ,e_{n}\in \mathbb {Z} }$ ${\displaystyle e_{i}\neq 0}$ ${\displaystyle i}$ ${\displaystyle R\subset F}$ ${\displaystyle S}$ ${\displaystyle R^{F}}$ ${\displaystyle r^{x}}$ ${\displaystyle r\in R}$ ${\displaystyle x\in F}$ ${\displaystyle K=\langle R^{F}\rangle }$ ${\displaystyle R^{F}}$ ${\displaystyle F}$ ${\displaystyle K}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle K=\langle \langle R\rangle \rangle }$

According to construction, is a normal divisor of the free group . So we get a group as the quotient ${\displaystyle K}$ ${\displaystyle F}$

${\displaystyle \langle S\mid R\rangle :=F/K}$

and call this the group with producers and relations . More precisely, the couple is called the presentation, and the group presented by . ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle (S,R)}$ ${\displaystyle \langle S\mid R\rangle }$ ${\displaystyle (S,R)}$

Way of speaking

In the above construction, the elements of are usually regarded as elements of the group . From a formal point of view they are elements of the free group and not of the quotient . However, it is often more convenient to use the quotient homomorphism to consider them as producers of . If there is no risk of confusion, no distinction is made between the element and its image in . ${\displaystyle S}$ ${\displaystyle \langle S\mid R\rangle }$ ${\displaystyle F=F(S)}$ ${\displaystyle F/K}$ ${\displaystyle \varphi \colon F\to F/K}$ ${\displaystyle F/K}$ ${\displaystyle s\in S}$ ${\displaystyle {\bar {s}}=\varphi (s)}$ ${\displaystyle F/K}$

Spellings

If and are finite sets, the presentation is called finite. In this case the group presented in this way is simply written down . ${\displaystyle S=\{s_{1},s_{2},\dotsc ,s_{m}\}}$ ${\displaystyle R=\{r_{1},r_{2},\dotsc ,r_{n}\}}$ ${\displaystyle (S,R)}$ ${\displaystyle \langle S\mid R\rangle }$ ${\displaystyle \langle s_{1},s_{2},\dotsc ,s_{m}\mid r_{1},r_{2},\dotsc ,r_{n}\rangle }$

Often a relation is also written in the form to emphasize that it is mapped to the neutral element in the quotient . In a somewhat more general way, the more convenient notation is used instead of the relation . ${\displaystyle r\in F}$ ${\displaystyle r=1}$ ${\displaystyle F/K}$ ${\displaystyle 1}$ ${\displaystyle u=v}$ ${\displaystyle uv^{-1}=1}$

Universal property

Be a lot and be a lot of words over . The group thus presented has the following universal property: ${\displaystyle S}$ ${\displaystyle R\subset F(S)}$ ${\displaystyle S}$ ${\displaystyle \langle S\mid R\rangle }$

For each mapping into a group that fulfills the condition , there is exactly one group homomorphism that continues, i.e. fulfills for all . ${\displaystyle f\colon S\to G}$ ${\displaystyle G}$ ${\displaystyle f(R)=\{1\}}$ ${\displaystyle h\colon \langle S\mid R\rangle \to G}$ ${\displaystyle f}$ ${\displaystyle h({\bar {s}})=f(s)}$ ${\displaystyle s\in S}$

In other words, the group is the "freest possible" group created by the given relations . This universal mapping property is equivalent to the definition given at the beginning. Either of the two characterizations can therefore be used as a definition of the group , and both approaches can be found in the literature. The other characterization is then a consequence. ${\displaystyle \langle S\mid R\rangle }$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle \langle S\mid R\rangle }$

Presentation to a given group

Given a group , we can choose a generating system of elements . The free group over then allows a surjective group homomorphism with for all . Second, we can now choose a subset that the kernel creates as a normal subgroup. This gives us a group isomorphism . This presents the given group through the producers and the relations existing between them . Note the trick that the relations are expressed in the free generators , which serve here as variables or placeholders for the actual group elements in . ${\displaystyle G}$ ${\displaystyle (g_{i})_{i\in I}}$ ${\displaystyle g_{i}\in G}$ ${\displaystyle F=F(S)}$ ${\displaystyle S=\{s_{i}\mid i\in I\}}$ ${\displaystyle h\colon F\to G}$ ${\displaystyle h(s_{i})=g_{i}}$ ${\displaystyle i\in I}$ ${\displaystyle R=\{r_{j}\mid j\in J\}}$ ${\displaystyle K=\ker(h)}$ ${\displaystyle \langle S\mid R\rangle =F/K\to G}$ ${\displaystyle G}$ ${\displaystyle (g_{i})_{i\in I}}$ ${\displaystyle (r_{j})_{j\in J}}$ ${\displaystyle r_{j}}$ ${\displaystyle s_{i}}$ ${\displaystyle (g_{i})_{i\in I}}$ ${\displaystyle G}$

If one can choose a finite generating system, then it is called finitely generated. If one can also choose a finite set of relations, then is called finite presented. ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle G}$

Examples

Link table of a finite group

→ Main article : finite group

If a finite group is of order , we can interpret its connection table as a presentation by generators and relations. The producers are the elements of the given group , and each product defines a relation in the free group . In general, however, it also allows much shorter presentations, as the following examples show. ${\displaystyle (G,\cdot )}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n^{2}}$ ${\displaystyle a,b,c,\dotsc }$ ${\displaystyle G}$ ${\displaystyle a\cdot b=c}$ ${\displaystyle abc^{-1}}$ ${\displaystyle G}$ ${\displaystyle G}$

Cyclic groups

→ Main article : cyclic group

The presentations and have already been presented above as introductory examples. Every presentation with only one producer defines an isomorphic group. ${\displaystyle \mathbb {Z} =\langle s\mid -\rangle }$ ${\displaystyle \mathbb {Z} /n=\langle s\mid s^{n}=1\rangle }$

Presentations with two producers, on the other hand, can be surprisingly complicated. Two particularly simple examples are given by the dihedral group and the quaternion group .

Dihedral groups

→ Main article : Diedergruppe

The dihedral group of the order is the isometric group of a regular corner in the plane. It is generated by two adjacent reflections and so the presentation is obtained ${\displaystyle D_{n}}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle s_{0},s_{1}}$

${\displaystyle D_{n}=\langle s_{0},s_{1}\mid s_{0}^{2}=s_{1}^{2}=(s_{0}s_{1})^{n}=1\rangle }$.

Quaternion groups

→ Main article : Quaternion group

The generalized quaternion group of order for is given by the presentation ${\displaystyle Q_{4n}}$ ${\displaystyle 4n}$ ${\displaystyle n\geq 2}$

${\displaystyle Q_{4n}=\langle x,y\mid x^{2n}=1,x^{n}=y^{2},yxy^{-1}=x^{-1}\rangle }$.

For it receives from this the Hamiltonian quaternion with the link ${\displaystyle n=2}$ ${\displaystyle Q_{8}=\{\pm 1,\pm i,\pm j,\pm k\}}$

${\displaystyle i\cdot i=j\cdot j=k\cdot k=i\cdot j\cdot k=-1}$.

In this case the spelling and and as well as is historically common. ${\displaystyle i=x}$ ${\displaystyle j=y}$ ${\displaystyle k=xy}$ ${\displaystyle x^{2}=y^{2}=-1}$

Symmetrical groups

→ Main article : symmetric group

The symmetrical group is created by the transpositions , where . One calculates directly that the following relations apply between these generators: ${\displaystyle S_{n}}$ ${\displaystyle t_{i}=(i,i+1)}$ ${\displaystyle i=1,2,\dotsc ,n-1}$

• ${\displaystyle t_{i}^{2}=1}$ for all ${\displaystyle i}$
• ${\displaystyle t_{i}t_{j}=t_{j}t_{i}}$ if ${\displaystyle |i-j|\geq 2}$
• ${\displaystyle t_{i}t_{j}t_{i}=t_{j}t_{i}t_{j}}$ if ${\displaystyle |i-j|=1}$

The group presented in this way

${\displaystyle G=\left\langle s_{1},s_{2},\dotsc ,s_{n-1}{\Big |}{\begin{matrix}s_{i}^{2}=1{\mbox{ für }}i=1,2,\dotsc ,n-1\\s_{i}s_{j}=s_{j}s_{i}{\text{ falls }}|i-j|\geq 2\\s_{i}s_{j}s_{i}=s_{j}s_{i}s_{j}{\text{ falls }}|i-j|=1\end{matrix}}\right\rangle }$

thus allows a surjective group homomorphism virtue . At first it is not obvious that this is also injective, that the specified relations already generate all relations. However, with the help of the above relations one can show that contains at most elements, and thus holds . ${\displaystyle G\to S_{n}}$ ${\displaystyle s_{i}\mapsto t_{i}}$ ${\displaystyle G}$ ${\displaystyle n!}$ ${\displaystyle G\cong S_{n}}$

Note that because of the above relationships, one can also rewrite it as ${\displaystyle s_{i}^{2}=1}$

• ${\displaystyle (s_{i}s_{j})^{2}=1}$for , ${\displaystyle |i-j|\geq 2}$
• ${\displaystyle (s_{i}s_{j})^{3}=1}$for . ${\displaystyle |i-j|=1}$

This equivalent notation can also be found frequently in the literature.

Coxeter groups

Reflection groups are groups that are created by reflections, i.e. elements of the order . Reflection groups play an important role in classical geometry, for example in the classification of regular polyhedra. They have been studied in depth by the British mathematician Harold Scott MacDonald Coxeter , in whose honor they are also called Coxeter groups . ${\displaystyle 2}$

In order to clearly write down all relations of such a group, we choose a symmetrical matrix whose entries are natural numbers or infinite, i.e. for . We also assume that and for everyone . Such a matrix is ​​then called the Coxeter matrix and defines the following Coxeter group: ${\displaystyle M=(m_{ij})}$ ${\displaystyle m_{ij}\in \mathbb {N} \cup \{\infty \}}$ ${\displaystyle i,j=1,\dotsc ,n}$ ${\displaystyle m_{ii}=1}$ ${\displaystyle m_{ij}\geq 2}$ ${\displaystyle i\neq j}$

${\displaystyle \Gamma _{M}=\langle s_{1},s_{2},\dotsc ,s_{n}\mid (s_{i}s_{j})^{m_{ij}}=1\rangle }$

If so, the corresponding relation is simply left out. ${\displaystyle m_{ij}=\infty }$

For example, the dihedral group is the Coxeter group to the matrix ${\displaystyle D_{n}}$

${\displaystyle {\begin{pmatrix}1&n\\n&1\end{pmatrix}}}$

The symmetrical group is the Coxeter group to the matrix ${\displaystyle S_{n}}$ ${\displaystyle (n-1)\times (n-1)}$

${\displaystyle {\begin{pmatrix}1&3&2&\dots &2\\3&1&3&\ddots &\vdots \\2&3&1&\ddots &2\\\vdots &\ddots &\ddots &\ddots &3\\2&\dots &2&3&1\end{pmatrix}}}$

Such matrices can be clearly displayed and classified as Dynkin diagrams .

Area groups

The fundamental group of the closed , orientable surface of gender has the presentation ${\displaystyle g}$

${\displaystyle \pi _{1}S_{g}=\langle a_{1},b_{1},\dotsc ,a_{g},b_{g}\mid \Pi _{i=1}^{g}\left[a_{i},b_{i}\right]=1\rangle }$.

Tietze transformations

There are always an infinite number of different presentations for a given group . For example, the following transformations change the presentation but not the presented group : ${\displaystyle G}$ ${\displaystyle (S,R)}$ ${\displaystyle \langle S\mid R\rangle }$

Adding or removing a redundant relation

If it is a consequence of the relations , the relations result in a new presentation , but an isomorphic group . ${\displaystyle r\in F(S)}$ ${\displaystyle R}$ ${\displaystyle R^{*}=R\cup \{r\}}$ ${\displaystyle (S,R^{*})}$ ${\displaystyle \langle S\mid R^{*}\rangle \cong \langle S\mid R\rangle }$

Adding or removing a redundant generator

For and you get a new presentation with the generators and the relations , but an isomorphic group . ${\displaystyle s\notin S}$ ${\displaystyle w\in F(S)}$ ${\displaystyle S^{*}=S\cup \{s\}}$ ${\displaystyle R^{*}=R\cup \{sw^{-1}\}}$ ${\displaystyle (S^{*},R^{*})}$ ${\displaystyle \langle S^{*}\mid R^{*}\rangle \cong \langle S\mid R\rangle }$

Tietze's theorem says that these transformations already exhaust all possibilities:

If and are two finite presentations, then they represent isomorphic groups if and only if they can be converted into one another by a finite sequence of the two above transformations. ${\displaystyle (S_{1},R_{1})}$ ${\displaystyle (S_{1},R_{2})}$

The three Dehnian problems

The German mathematician Max Dehn had a decisive influence on combinatorial group theory with his fundamental work at the beginning of the 20th century. In particular, he highlighted three general problems that are fundamental to working with presentations, both in practical and theoretical terms.

The word problem

The first problem is the most obvious: if you want to do concrete calculations in the group , you have to be able to compare elements and determine whether they are the same or different. Since all elements can be written as words above the generating set , this leads directly to the following word problem: ${\displaystyle \langle S\mid R\rangle }$ ${\displaystyle S}$

Given a finite presentation of the group . ${\displaystyle (S,R)}$ ${\displaystyle G=\langle S\mid R\rangle }$

For given words, determine whether they represent the same element in . ${\displaystyle w_{1},w_{2}\in F(S)}$ ${\displaystyle G}$

The following problem is equivalent to this, by means of : ${\displaystyle w=w_{1}w_{2}^{-1}}$

For a given word, determine whether the group represents the neutral element. ${\displaystyle w\in F(S)}$ ${\displaystyle w}$ ${\displaystyle G}$

After constructing , you have to determine whether it is in the normal divider or not. Even with a small set of relations, the normal divisor generated in this way is huge. At least one can enumerate the set systematically and thus the word problem is always semi-decidable : If applies, then one finds this after a finite long time as a consequence of the relations. If, however , applies , then the list of does not end. ${\displaystyle G=F/K}$ ${\displaystyle w}$ ${\displaystyle K=\langle R^{F}\rangle }$ ${\displaystyle R}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle w\in K}$ ${\displaystyle w\notin K}$ ${\displaystyle K}$

Novikov-Boone's theorem says that the word problem is generally algorithmically unsolvable.

The conjugation problem

The conjugation problem is similar to the word problem, but it is generally more difficult:

Given a finite presentation of the group . ${\displaystyle (S,R)}$ ${\displaystyle G=\langle S\mid R\rangle }$

For given words, determine whether they represent conjugate elements in . ${\displaystyle w_{1},w_{2}\in F(S)}$ ${\displaystyle G}$

With one contains the word problem as a special case. ${\displaystyle w_{2}=1}$

Just like the word problem, the conjugation problem is only semi-decidable and generally algorithmically unsolvable.

The isomorphism problem

The third and most difficult of Dehn's problems is the isomorphism problem:

Given are two finite presentations and . ${\displaystyle (S_{1},R_{1})}$ ${\displaystyle (S_{2},R_{2})}$

Determine whether the groups so presented are and are isomorphic. ${\displaystyle G_{1}=\langle S_{1}\mid R_{1}\rangle }$ ${\displaystyle G_{2}=\langle S_{2}\mid R_{2}\rangle }$

The Tietze transformations explained above describe how presentations can be transformed into one another. Based on a given presentation, one can therefore enumerate all equivalent presentations. Just like the word and conjugation problem, the isomorphism problem is only semi-decidable and generally algorithmically unsolvable.

literature

• Roger C. Lyndon , Paul E. Schupp : Combinatorial group theory. Reprint of the 1977 edition. Classics in Mathematics. Springer-Verlag, Berlin, 2001. ISBN 3-540-41158-5 .
• Joseph J. Rotman: An introduction to the theory of groups. Fourth edition. Graduate Texts in Mathematics, 148. Springer-Verlag, New York, 1995. ISBN 0-387-94285-8 .
• Max Dehn : Papers on group theory and topology. Translated from the German and with introductions and an appendix by John Stillwell. With an appendix by Otto Schreier. Springer-Verlag, New York, 1987. ISBN 0-387-96416-9 .
• Wilhelm Magnus , Abraham Karrass, Donald Solitar : Combinatorial Group Theory. Presentations of Groups in Terms of Generators and Relations. Interscience, New York 1966, 2nd edition, Dover 1976.

Web links

• Martin Bridson : Geometric and combinatorial group theory