Presentations and Free Groups

A presentation specifies a group by generators and relations — the most economical way to write down a group, and the natural language for symmetry groups defined by geometric constraints (rotations, reflections, braids). The free group is the universal case with no relations at all. This page rounds out the abstract theory, connecting the reflection/Coxeter groups to the Weyl groups of lie-classification.md and flagging the undecidability of the word problem. It builds on homomorphisms.md.

Free groups

The free group $F_S$ on a set $S$ consists of all reduced words in the symbols $S$ and their formal inverses (strings with no $s{s}^{-1}$ cancellation), under concatenation-then-reduce. It has no relations beyond those forced by the axioms, and is characterised by a universal property:

Any set map $S\to G$ into a group extends uniquely to a homomorphism $F_S\to G$.

So $F_S$ is the "most general" group generated by $S$: every group generated by $|S|$ elements is a quotient of $F_S$. The free group on one generator is $\mathbb{Z}$; on two or more generators it is non-abelian and contains free subgroups of every rank (a Nielsen–Schreier phenomenon: every subgroup of a free group is free).

Presentations

A presentation $G=⟨S\mid R⟩$ expresses $G$ as the quotient of the free group $F_S$ by the normal closure of a set $R$ of relator words: $$⟨S\mid R⟩=F_S/⟨⟨R⟩⟩.$$ $S$ are the generators, $R$ the relations. A group is finitely presented if both $S$ and $R$ can be taken finite. Examples:

• ${\mathbb{Z}}_n=⟨r\mid r^n⟩$.
• ${\mathbb{Z}}^2=⟨a,b\mid ab{a}^{-1}{b}^{-1}⟩$ (one commutator relation makes it abelian).
• Dihedral $D_n=⟨r,s\mid r^n,s^2,sr{s}^{-1}r⟩$ — rotation $r$, reflection $s$, with $srs=r^{-1}$ (the semidirect structure of products.md).
• Symmetric $S_n=⟨s_1,\dots ,s_{n-1}\mid s_i^2,(s_i{s}_{i+1}{)}^3,(s_i{s}_j{)}^2\text{ for }|i-j|\ge 2⟩$ — the Coxeter presentation by adjacent transpositions.

von Dyck's theorem. If $G=⟨S\mid R⟩$ and $H$ is any group whose generators (images of $S$) satisfy all the relations $R$, then there is a unique surjection $G\twoheadrightarrow H$. Relations can only add collapse.

Coxeter and reflection groups

A Coxeter group is presented by generators $s_i$ (thought of as reflections) with relations $$s_i^2=e,(s_i{s}_j{)}^{m_{ij}}=e(m_{ij}\in \{2,3,\dots ,\infty \}),$$ encoded in a Coxeter diagram. These are exactly the groups generated by reflections; the finite ones classify the symmetry groups of regular polytopes and — crucially — the Weyl groups of semisimple Lie algebras, whose Coxeter diagrams are the Dynkin diagrams with edge multiplicities. This is the discrete skeleton controlling the root systems of lie-classification.md, and the reason the finite reflection groups and the simple Lie algebras share the same $ADE$ (and $BCFG$) labelling.

The word problem

Presentations are compact but can hide their group's structure completely:

Word problem. Given a finite presentation and a word $w$, decide whether $w=e$ in the group.

Novikov–Boone theorem: the word problem is undecidable — there is no algorithm solving it for all finitely presented groups (related: the isomorphism problem and the triviality problem are also undecidable). This is one of the earliest and most striking incursions of logic and computability into algebra: a finite amount of data (generators and relations) can determine a group whose most basic questions no algorithm can answer. For specific well-behaved classes (finite, abelian, hyperbolic, automatic groups) the word problem is solvable.

References

• Lyndon & Schupp, Combinatorial Group Theory.
• Magnus, Karrass & Solitar, Combinatorial Group Theory.
• Humphreys, Reflection Groups and Coxeter Groups.