Free groups, presentations, and the word problem

A group presentation like \(\langle a, b \mid aba^{-1}b^{-1}\rangle\) looks like a complete description of a group: here are the generators, here are the rules they obey, everything else follows. It is a complete description, in the precise sense that the presentation determines the group up to isomorphism. What it does not give you is a way to read anything off. Given two words in the generators, deciding whether they name the same element turns out to be impossible by any algorithm, for some presentations. That result, the Novikov–Boone theorem, is the reason this subject exists as a subject rather than as an exercise.

This article builds the machinery from the ground up. Free groups first, defined as words modulo cancellation, with the normal form theorem proved in full because everything downstream leans on it. Then the universal property, normal closures, presentations, and von Dyck's theorem. Then the word problem: what it asks, when it is solvable, and a detailed autopsy of a natural algorithm that looks like it should work and does not. The last two sections put the theory to work on the symmetric group and introduce Coxeter groups, where the failed algorithm gets repaired.

Sections one through three follow the opening chapters of Cravitz's REU paper on the word problem [1], with proofs restructured to use the quotient construction of the free group throughout.

Words

Definition (alphabet). Let \(S\) be a set. Let \(S^{-1}\) be a set disjoint from \(S\) together with a fixed bijection \(S \to S^{-1}\), written \(s \mapsto s^{-1}\). Put \(A = S \sqcup S^{-1}\) and extend the bijection to an involution on all of \(A\) by declaring \((s^{-1})^{-1} = s\). Elements of \(A\) are called letters. At this stage \(s^{-1}\) is a symbol, not yet an inverse of anything.

Definition (word). A word in \(S\) is a finite sequence of letters, written

\[ w = x_1^{\epsilon_1} x_2^{\epsilon_2}\cdots x_r^{\epsilon_r}, \qquad x_i \in S,\ \epsilon_i = \pm 1,\ r \ge 0. \]

The integer \(r\) is the length \(|w|\). When \(r = 0\) the word is the empty word, written \(\varepsilon\). Two words are equal when they are the same sequence: same letters, same order. Write \(W(S)\) for the set of all words in \(S\).

Example. \(abb^{-1}a^{-1}bba\) is a word in \(\{a, b\}\) of length \(7\). It is a different word from \(a^{-1}bba\), even though the two will turn out to name the same group element.

Definition (product and inverse of words). The product of \(w = x_1^{\epsilon_1}\cdots x_r^{\epsilon_r}\) and \(v = y_1^{\eta_1}\cdots y_t^{\eta_t}\) is the concatenation

\[ wv = x_1^{\epsilon_1}\cdots x_r^{\epsilon_r}\, y_1^{\eta_1}\cdots y_t^{\eta_t}, \]

and the formal inverse of \(w\) is \(w^{-1} = x_r^{-\epsilon_r}\cdots x_1^{-\epsilon_1}\), obtained by reversing the order and inverting each letter. Concatenation is associative and \(\varepsilon w = w \varepsilon = w\), so \(W(S)\) is a monoid, the free monoid on \(A\). It is not a group: no amount of concatenation ever shortens a word, so nothing except \(\varepsilon\) has an inverse.

Definition (reduced word). A word is reduced if no letter is immediately followed by its involution, that is, if the pattern \(x_i x_i^{-1}\) or \(x_i^{-1} x_i\) never occurs. The empty word is reduced. Write \(\mathcal{W} \subseteq W(S)\) for the set of reduced words.

Definition (elementary moves and the relation \(\sim\)). An elementary deletion replaces a word \(u\,aa^{-1}\,v\) by \(uv\), where \(a \in A\) and \(u, v\) are arbitrary words. An elementary insertion is the reverse operation. Two words \(w\) and \(w'\) are equivalent, written \(w \sim w'\), if some finite chain of elementary moves carries one to the other.

Definition (free group). The free group on \(S\) is the set of equivalence classes

\[ F(S) := W(S)/\!\sim, \]

with multiplication \([w][v] := [wv]\), together with the map \(\iota : S \to F(S)\), \(s \mapsto [s]\).

Proposition. \(F(S)\) is a group.

Proof. First, \(\sim\) is an equivalence relation: the empty chain gives reflexivity, reversing a chain (each insertion becoming a deletion and vice versa) gives symmetry, and concatenating chains gives transitivity.

Second, \(\sim\) is compatible with concatenation. If a single elementary move carries \(w\) to \(w'\), the same move performed inside the larger word carries \(uwv\) to \(uw'v\); chaining, \(w \sim w'\) implies \(uwv \sim uw'v\). Hence if \(w \sim w'\) and \(v \sim v'\) then \(wv \sim w'v \sim w'v'\), so the product \([w][v] := [wv]\) does not depend on the representatives chosen.

Associativity is inherited from concatenation of sequences, and \([\varepsilon]\) is a two-sided identity. For inverses, take \(w = x_1^{\epsilon_1}\cdots x_r^{\epsilon_r}\). Then

\[ w\,w^{-1} = x_1^{\epsilon_1}\cdots x_r^{\epsilon_r}\, x_r^{-\epsilon_r}\cdots x_1^{-\epsilon_1} \]

contains the cancelling pair \(x_r^{\epsilon_r}x_r^{-\epsilon_r}\) at its centre. Deleting it exposes the next pair, and after \(r\) deletions nothing is left, so \(ww^{-1} \sim \varepsilon\) and similarly \(w^{-1}w \sim \varepsilon\). Thus \([w]^{-1} = [w^{-1}]\). \(\blacksquare\)

So far \(F(S)\) is a group, but a possibly very small one: nothing yet rules out that every word is equivalent to \(\varepsilon\). That is what the next theorem settles.

The normal form theorem

Theorem (normal form). Every \(\sim\)-class contains exactly one reduced word.

Before the proof, note where the difficulty lies. A chain witnessing \(w \sim w'\) is allowed to insert as well as delete, so it need not shorten monotonically, and induction on length along such a chain is unavailable. The theorem says insertions are never needed, but that is exactly what has to be proved rather than assumed.

Step 1 (existence). Every word is equivalent to a reduced word. Induct on \(|w|\). If \(w\) is reduced there is nothing to do. Otherwise \(w = u\,aa^{-1}\,v\) for some \(a \in A\), and \(w \sim uv\) with \(|uv| = |w| - 2\); by induction \(uv\) is equivalent to a reduced word, and transitivity finishes. Note the chain produced uses deletions only, a fact needed in Step 6.

Step 2 (a permutation for each letter). For \(a \in A\) define \(\sigma_a : \mathcal{W} \to \mathcal{W}\) on reduced words by

\[ \sigma_a(w) = \begin{cases} a\,w, & \text{if } w = \varepsilon \text{ or } w = b\,w' \text{ with } b \neq a^{-1},\\[2pt] w', & \text{if } w = a^{-1}w'. \end{cases} \]

The output really is reduced: in the first case \(aw\) is reduced because \(w\) is and its first letter is not \(a^{-1}\); in the second, \(w'\) is a suffix of a reduced word. We claim \(\sigma_{a^{-1}} \circ \sigma_a = \mathrm{id}\). If \(w\) does not begin with \(a^{-1}\), then \(\sigma_a(w) = aw\) begins with \(a = (a^{-1})^{-1}\), so \(\sigma_{a^{-1}}\) takes its second branch and strips the \(a\), returning \(w\). If \(w = a^{-1}w'\), then \(\sigma_a(w) = w'\); since \(w\) is reduced its second letter is not \((a^{-1})^{-1} = a\), so \(w'\) does not begin with \(a\) and \(\sigma_{a^{-1}}\) takes its first branch, returning \(a^{-1}w' = w\). Applying this with \(a^{-1}\) in place of \(a\) gives the other composite, so each \(\sigma_a\) is a bijection of \(\mathcal{W}\) with \(\sigma_a^{-1} = \sigma_{a^{-1}}\).

Step 3 (an invariant). Since \(W(S)\) is the free monoid on \(A\), there is a unique monoid homomorphism

\[ \Phi : W(S) \to \operatorname{Sym}(\mathcal{W}), \qquad \Phi(a_1a_2\cdots a_n) = \sigma_{a_1}\circ \sigma_{a_2}\circ \cdots \circ \sigma_{a_n}, \qquad \Phi(\varepsilon) = \mathrm{id}. \]

If \(w \sim w'\) then \(\Phi(w) = \Phi(w')\). It is enough to check one elementary move: for \(w = u\,aa^{-1}\,v\) and \(w' = uv\),

\[ \Phi(w) = \Phi(u)\circ\sigma_a\circ\sigma_{a^{-1}}\circ\Phi(v) = \Phi(u)\circ\Phi(v) = \Phi(w'), \]

by Step 2, and an insertion is the same equation read backwards. This is the point that defeats the difficulty flagged above: \(\Phi\) is blind to the direction of the moves, so it survives chains that grow the word.

Step 4 (evaluation recovers reduced words). If \(w \in \mathcal{W}\) then \(\Phi(w)(\varepsilon) = w\). Induct on \(|w|\); the case \(w = \varepsilon\) is immediate. For \(w = a_1a_2\cdots a_n\), the suffix \(w'' = a_2\cdots a_n\) is reduced, so \(\Phi(w'')(\varepsilon) = w''\) by induction, and

\[ \Phi(w)(\varepsilon) = \sigma_{a_1}\big(\Phi(w'')(\varepsilon)\big) = \sigma_{a_1}(a_2\cdots a_n) = a_1a_2\cdots a_n = w, \]

the last step because \(w\) reduced forces \(a_2 \neq a_1^{-1}\), so \(\sigma_{a_1}\) takes its first branch.

Step 5 (uniqueness). Let \(u, v\) be reduced with \(u \sim v\). Then \(\Phi(u) = \Phi(v)\) by Step 3, and evaluating both at \(\varepsilon\) with Step 4 gives \(u = v\). Combined with Step 1, each class contains exactly one reduced word. \(\blacksquare\)

Write \(\red{w}\) for the unique reduced word in \([w]\), the reduced form of \(w\). The theorem says precisely

\[ w \sim w' \iff \red{w} = \red{w'} \quad\text{(as words)}. \]

Step 6 (minimality). \(\red{w}\) is the unique word of minimal length in \([w]\). Let \(r = \red{w}\) and let \(v \in [w]\). By Step 1 there is a deletion-only chain from \(v\) to some reduced word, and by Step 5 that word must be \(r\). If the chain has \(k \ge 0\) steps then \(|r| = |v| - 2k\), so \(|v| \ge |r|\), with equality only when \(k = 0\), that is, when \(v\) is already reduced, in which case \(v = r\). \(\blacksquare\)

A byproduct: all words in a class have the same length parity, so length modulo \(2\) is a well defined invariant of a group element.

Corollary (the word problem in \(F(S)\)). The relation \(w \sim w'\) is decidable, in time linear in \(|w| + |w'|\). Scan \(w\) once, maintaining a stack: push each letter unless it cancels against the top of the stack, in which case pop instead. The stack contents at the end are \(\red{w}\). By the theorem the answer is independent of the order in which cancellations are performed, so this greedy scan is correct. Compare \(\red{w}\) with \(\red{w'}\) letter by letter.

Corollary (\(\iota\) is injective and \(F(S)\) is large). Distinct \(s, t \in S\) give distinct reduced words of length one, so \([s] \neq [t]\), and \([s] \neq [\varepsilon]\). Every distinct reduced word gives a distinct element, so \(F(S)\) is infinite whenever \(S \neq \emptyset\). We henceforth identify \(s\) with \(\iota(s)\) and write words for their classes.

The same theorem by rewriting theory

There is a second standard proof. Orient the moves as rewriting rules \(aa^{-1} \to \varepsilon\). The system terminates, since each rule application drops the length by \(2\). It is locally confluent: two applicable cancellations either occupy disjoint positions, in which case they commute, or they overlap. Two cancelling pairs can overlap in at most one letter, so an overlap means the word contains a factor \(x\,y\,z\) with \(xy\) and \(yz\) both cancelling, forcing \(y = x^{-1}\) and \(z = y^{-1} = x\); the factor is \(x\,x^{-1}x\), and deleting either pair leaves \(x\). Terminating plus locally confluent implies confluent by Newman's lemma [4], so normal forms are unique.

That proof generalizes to arbitrary rewriting systems, which is why it is worth knowing. The permutation proof above is shorter and needs no external lemma. Both matter later: the overlap calculation is exactly the check that fails for general presentations.

The universal property

Free groups are the groups with no relations beyond those forced by the group axioms. That informal statement is made precise by a mapping property.

Definition (free group with basis \(S\)). Let \(F\) be a group and \(\iota : S \to F\) a map. The pair \((F, \iota)\) is free with basis \(S\) if for every group \(G\) and every map \(f : S \to G\) there is a unique homomorphism \(\varphi : F \to G\) with \(\varphi \circ \iota = f\).

Theorem. \(\big(F(S), \iota\big)\) is free with basis \(S\).

Proof. Let \(f : S \to G\) be any map. Extend it to the alphabet by \(\hat f(s) = f(s)\) and \(\hat f(s^{-1}) = f(s)^{-1}\). This satisfies \(\hat f(a^{-1}) = \hat f(a)^{-1}\) for every \(a \in A\): for \(a = s\) it is the definition, and for \(a = s^{-1}\) it reads \(\hat f(s) = (f(s)^{-1})^{-1}\), which is true.

Since \(W(S)\) is the free monoid on \(A\), there is a unique monoid homomorphism

\[ \Psi : W(S) \to G, \qquad \Psi(a_1a_2\cdots a_n) = \hat f(a_1)\hat f(a_2)\cdots \hat f(a_n), \qquad \Psi(\varepsilon) = e. \]

\(\Psi\) is constant on \(\sim\)-classes. For an elementary move,

\[ \Psi(u\,aa^{-1}\,v) = \Psi(u)\,\hat f(a)\hat f(a)^{-1}\,\Psi(v) = \Psi(u)\Psi(v) = \Psi(uv), \]

and chains follow. So \(\Psi\) descends to a well defined map \(\varphi : F(S) \to G\), \(\varphi([w]) = \Psi(w)\). It is a homomorphism because \(\varphi([w][v]) = \varphi([wv]) = \Psi(wv) = \Psi(w)\Psi(v) = \varphi([w])\varphi([v])\), and \(\varphi(\iota(s)) = \Psi(s) = f(s)\).

For uniqueness, note \(\iota(S)\) generates \(F(S)\): the class \([x_1^{\epsilon_1}\cdots x_r^{\epsilon_r}]\) equals \(\iota(x_1)^{\epsilon_1}\cdots \iota(x_r)^{\epsilon_r}\). Two homomorphisms agreeing on a generating set are equal, so any \(\varphi'\) with \(\varphi' \circ \iota = f\) equals \(\varphi\). \(\blacksquare\)

The quotient construction pays for itself here. Had we defined the free group as the set of reduced words under "concatenate then reduce", the map \(\varphi\) would be defined immediately but proving it multiplicative would require splitting into cases according to how much cancellation occurs between \(w\) and \(v\) (this is how [1] proceeds). Defining \(\Psi\) on all words, where multiplicativity is free, and then checking invariance under a single elementary move, removes the case analysis entirely. The cost is that associativity and the size of the group are not obvious, and that cost is paid once by the normal form theorem.

Corollary (uniqueness of the free group). If \((F, \iota)\) and \((F', \iota')\) are both free with basis \(S\), there is a unique isomorphism \(\theta : F \to F'\) with \(\theta \circ \iota = \iota'\). Apply the property of \(F\) to \(\iota'\) and of \(F'\) to \(\iota\), getting \(\theta\) and \(\theta'\); then \(\theta'\theta\) and \(\mathrm{id}_F\) are both homomorphisms \(F\to F\) extending \(\iota\), so they agree by uniqueness, and symmetrically. This licenses the article "the" free group on \(S\), written \(F(S)\) or \(F_n\) when \(|S| = n\).

Proposition (rank is well defined). If \(F\) is free with bases \(S\) and \(T\), then \(|S| = |T|\).

Proof. The universal property gives a bijection between homomorphisms \(F \to \mathbb{Z}/2\) and maps \(S \to \mathbb{Z}/2\), so \(|\operatorname{Hom}(F, \mathbb{Z}/2)| = 2^{|S|}\), and likewise \(2^{|T|}\). For finite bases this forces \(|S| = |T|\). If \(S\) is infinite then the set of words over \(S \sqcup S^{-1}\) has cardinality \(|S|\), so \(|F| = |S| = |T|\). \(\blacksquare\)

The common name for this invariant is the rank of \(F\). Three further facts are recorded without proof, all standard [2, ch. 6]: a free group is torsion free; two elements commute only if both are powers of a common element; and every subgroup of a free group is free (the Nielsen–Schreier theorem).

Normal closures

Presentations are quotients of free groups, and the subgroup we quotient by is a normal closure. Getting its definition exactly right resolves a subtlety that trips people up immediately afterwards.

Definition (normal closure). Let \(G\) be a group and \(R \subseteq G\). The normal closure of \(R\) is

\[ \nc{R} \;=\; \bigcap_{\substack{R \subseteq N \trianglelefteq G}} N, \]

the smallest normal subgroup of \(G\) containing \(R\). The intersection is over a nonempty family since \(G\) itself qualifies, and an intersection of normal subgroups is normal, so \(\nc{R}\) is well defined.

Lemma (explicit description).

\[ \nc{R} = \left\{\, \prod_{i=1}^{n} g_i^{-1} r_i^{\epsilon_i} g_i \;:\; n \ge 0,\ g_i \in G,\ r_i \in R,\ \epsilon_i = \pm 1 \,\right\}. \]

Proof. Call the right-hand side \(K\). It contains the identity (take \(n = 0\)) and is closed under multiplication (concatenate the two products). It is closed under inversion, since

\[ \Big(\prod_{i=1}^{n} g_i^{-1}r_i^{\epsilon_i}g_i\Big)^{-1} = \big(g_n^{-1}r_n^{-\epsilon_n}g_n\big)\cdots \big(g_1^{-1}r_1^{-\epsilon_1}g_1\big), \]

which is again of the required shape. It is normal, because conjugating termwise gives \(h^{-1}\big(\prod g_i^{-1} r_i^{\epsilon_i}g_i\big)h = \prod (g_ih)^{-1}r_i^{\epsilon_i}(g_ih)\). It contains \(R\), taking \(n = 1\), \(g_1 = e\), \(\epsilon_1 = 1\). Finally, any normal \(N\) containing \(R\) contains every conjugate \(g^{-1}r^{\epsilon}g\) and, being a subgroup, every product of such, so \(N \supseteq K\). Hence \(K\) is the smallest such subgroup. \(\blacksquare\)

The subtlety. The set of bare conjugates

\[ C = \{\, g^{-1}rg : g \in G,\ r \in R \,\} \]

is not a subgroup: it is not closed under multiplication. The normal closure is the subgroup generated by \(C\), and the products in the lemma are not decoration. Here is the case where this matters most often. Suppose \(R\) contains two relators, one of which we split as \(w_L w_R\), and the other of which is \(x\). Why is the word \(w_L\,x\,w_R\) in \(\nc{R}\)? It is generally not a conjugate of anything in \(R\). But

\[ w_L\,x\,w_R \;=\; \underbrace{\big(w_L\,x\,w_L^{-1}\big)}_{\text{a conjugate of } x} \cdot \underbrace{\big(w_L w_R\big)}_{\text{a relator}}, \]

as one checks by cancelling \(w_L^{-1}w_L\) in the middle. Both factors lie in \(C\) (the first with \(g = w_L^{-1}\), the second with \(g = e\)), so their product lies in \(\nc{R}\). Closure under products is doing all the work. The group-theoretic content is the obvious one: if \(w_Lw_R = 1\) then \(w_R = w_L^{-1}\), and if \(x = 1\) then \(w_L x w_R = w_L w_L^{-1} = 1\). The identity above is that argument carried out upstairs in the free group, which is where a membership proof has to live.

Presentations

Start from the question of how to specify a group compactly. Listing a multiplication table works for small finite groups and nothing else. Listing a generating set is compact but underdetermines the group: \(\mathbb{Z}\) and the cyclic group \(C_n\) are both generated by one element and are not isomorphic. What distinguishes them is a constraint on the generator, \(a^n = 1\), which \(\mathbb{Z}\) does not satisfy. Generators plus constraints is the idea; the free group is what makes it precise.

Definition (presentation). Let \(S\) be a set and \(R \subseteq F(S)\) a set of elements of the free group, called relators. The group presented by \(S\) and \(R\) is

\[ \langle S \mid R\rangle \;:=\; F(S)\big/\nc{R}. \]

A group \(G\) has presentation \(\langle S \mid R\rangle\) if \(G \cong F(S)/\nc{R}\). Given a word \(w\) in \(S\) we write \(w =_G g\) to mean that the image of \([w]\) in \(G\) is \(g\); in particular \(w =_G 1\) means \([w] \in \nc{R}\).

Relations versus relators. An equation \(u = v\) between words is a relation; it is equivalent to the relator \(uv^{-1}\), since \(u =_G v\) exactly when \(uv^{-1} =_G 1\). The two styles are interchangeable and both are used. For instance \(S_3\) can be written

\[ \langle a, b \mid a^3 = 1,\; b^2 = 1,\; ba = a^2b \rangle \quad \text{or} \quad \langle a, b \mid a^3,\, b^2,\, bab^{-1}a^{-2}\rangle. \]

Reading the quotient concretely: \(\nc{R}\) consists of exactly the words that the relators force to be trivial, by the explicit description above, so two words are equal in \(G\) precisely when one can be turned into the other by inserting and deleting conjugates of relators (and free cancellation). This is the right mental picture, and section six is about how badly it fails as an algorithm.

Von Dyck's theorem

The universal property of \(F(S)\) descends to presentations. This is the tool that lets you build homomorphisms out of a presented group by checking finitely many identities.

Theorem (von Dyck). Let \(G = \langle S \mid R\rangle\) and let \(K\) be a group with chosen elements \(\{k_s\}_{s \in S}\). If every relator \(r \in R\) becomes the identity of \(K\) when each \(s\) is replaced by \(k_s\), then there is a unique homomorphism \(\theta : G \to K\) with \(\theta(s) = k_s\) for all \(s \in S\).

Proof. The universal property gives a unique homomorphism \(\psi : F(S) \to K\) with \(\psi(s) = k_s\). The hypothesis says \(R \subseteq \ker\psi\). Kernels are normal, and \(\nc{R}\) is the smallest normal subgroup containing \(R\), so \(\nc{R} \subseteq \ker\psi\). Therefore \(\psi\) factors through the quotient, giving \(\theta : F(S)/\nc{R} \to K\) with \(\theta(s) = k_s\). Uniqueness holds because the images of \(S\) generate \(G\). \(\blacksquare\)

Every group has a presentation

Theorem. Every group is a quotient of a free group.

Proof. Let \(S\) be any generating set of \(G\), for example \(S = G\). The inclusion \(f : S \hookrightarrow G\) extends to a homomorphism \(\varphi : F(S) \to G\) by the universal property. The image \(\varphi(F(S))\) is a subgroup containing the generating set \(S\), hence equals \(G\), so \(\varphi\) is surjective and the first isomorphism theorem gives \(G \cong F(S)/\ker\varphi\). \(\blacksquare\)

Corollary. Every group admits a presentation. With \(\varphi\) as above set \(R = \ker\varphi\). Being already normal, \(R = \nc{R}\), so \(G \cong F(S)/\nc{R} = \langle S \mid R\rangle\). \(\blacksquare\)

This existence result is cheap and correspondingly weak: the presentation it produces has \(|G|\) generators and a relator set as large as the kernel. The interesting presentations are the small ones.

Definition (finiteness conditions). A group \(G\) is finitely generated if it admits a presentation with \(S\) finite, finitely related if it admits one with \(R\) finite, and finitely presented if it admits one with both finite.

Examples.

• Free group. \(F_n = \langle a_1, \dots, a_n \mid\ \rangle\), the case \(R = \emptyset\), where \(\nc{\emptyset} = 1\).
• Free abelian. \(\mathbb{Z}^2 = \langle a, b \mid aba^{-1}b^{-1}\rangle\). The single relator is the commutator, and killing it is exactly imposing commutativity.
• Klein four group. \(C_2 \times C_2 = \langle a, b \mid a^2,\, b^2,\, aba^{-1}b^{-1}\rangle\).
• Dihedral. \(D_{2n} = \langle a, b \mid a^n,\, b^2,\, abab^{-1}\rangle\), of order \(2n\) (the subscript here counts elements). The last relator says \(bab^{-1} = a^{-1}\), the reflection inverting the rotation.
• Quaternions. \(Q_8 = \langle i, j \mid i^4,\, j^2i^{-2},\, ijij^{-1}\rangle\). The second relator says \(j^2 = i^2\), the third says \(jij^{-1} = i^{-1}\).

A presentation that collapses

Presentations conceal their groups effectively enough that even tiny ones can surprise you. Consider

\[ G = \langle a, b \mid ab,\; aba \rangle. \]

Is \(a\) trivial? Yes: in \(F(a,b)\),

\[ (ab)^{-1}(aba) = b^{-1}a^{-1}\cdot aba = b^{-1}ba = a, \]

exhibiting \(a\) as a product of a relator and the inverse of a relator, hence \(a \in \nc{R}\). Does that make \(G \cong \mathbb{Z}\), generated by the surviving \(b\)? No. Once \(a \in \nc{R}\), we also get

\[ b = a^{-1}(ab) \in \nc{R}, \]

because \(\nc{R}\) is a subgroup containing both \(a^{-1}\) and \(ab\). So \(\nc{R} = F(a,b)\) and \(G\) is the trivial group.

The tempting error is to delete a dead generator and leave the relator set alone. You cannot: eliminating a generator requires substituting for it in the remaining relators. This is a Tietze transformation, and done correctly it reads

\[ \langle a, b \mid ab,\, aba\rangle \;\xrightarrow{\;b = a^{-1}\;}\; \langle a \mid a\,a^{-1}a\rangle = \langle a \mid a\rangle = 1. \]

The relator used to eliminate a generator is consumed; the other one survives and becomes a relator in what is left, and here it kills the last generator. A check: the abelianization is \(\mathbb{Z}^2\) modulo the subgroup generated by \((1,1)\) and \((2,1)\), and the matrix \(\left(\begin{smallmatrix}1&1\\2&1\end{smallmatrix}\right)\) has determinant \(-1\), a unit, so those vectors span \(\mathbb{Z}^2\) and the abelianization is trivial, consistent with \(G = 1\).

Tietze proved that any two finite presentations of the same group are connected by a finite sequence of four moves: adding or removing a relator that is a consequence of the others, and adding or removing a generator together with a defining relator for it [2, sec. 2.2]. That theorem is what makes "the presentation determines the group" and "the group does not determine the presentation" coexist peacefully.

The word problem

In 1911 Dehn isolated three decision questions about presentations [5]. Let \(G = \langle S \mid R\rangle\) be finitely presented.

1. The word problem. Given a word \(w\) in \(S\), decide whether \(w =_G 1\).
2. The conjugacy problem. Given words \(w, v\), decide whether they represent conjugate elements of \(G\).
3. The isomorphism problem. Given two finite presentations, decide whether they present isomorphic groups.

Definition (solvable word problem). \(G = \langle S \mid R\rangle\) finitely presented has solvable word problem if the set \(\{w \in W(S) : w =_G 1\}\) is decidable, that is, if some algorithm halts on every input word and correctly answers whether it is trivial in \(G\).

Remark (two formulations agree). Asking whether \(w =_G v\) is the same as asking whether \(wv^{-1} =_G 1\), so the equality problem and the triviality problem are interchangeable.

Remark (independence of presentation). Solvability is a property of the group, not of the chosen finite presentation. Suppose \(\langle S \mid R\rangle\) and \(\langle S' \mid R'\rangle\) present the same \(G\) with \(S, S'\) finite. Each \(s \in S\) equals some word \(V_s\) in \(S'\); fix such a choice once, a finite table. The substitution \(w \mapsto w'\) replacing each letter of \(w\) by the corresponding \(V_s^{\pm 1}\) is computable, and \(w =_G 1\) if and only if \(w' =_G 1\). So a decision procedure for one presentation yields one for the other.

Cases where it is solvable

Free groups. \(F(S) = \langle S \mid \emptyset \rangle\), and by the normal form theorem \(w =_{F(S)} 1\) if and only if \(\red{w} = \varepsilon\). Free reduction terminates because each step shortens the word, and the corollary above computes \(\red{w}\) in linear time. Note the logical dependence: the procedure is correct because the reduced form is unique, not merely because it exists.

Definition (residually finite). A group \(G\) is residually finite if for every \(g \in G\) with \(g \neq 1\) there is a normal subgroup \(N \trianglelefteq G\) with \(g \notin N\) and \(G/N\) finite. Equivalently, for every \(g \neq 1\) there is a finite group \(F\) and a homomorphism \(\theta : G \to F\) with \(\theta(g) \neq 1\). Finite groups, finitely generated abelian groups, and free groups are all residually finite [2, sec. 6.1].

Theorem. A finitely presented residually finite group has solvable word problem.

Proof. Let \(G = \langle S \mid R\rangle\) with \(S, R\) finite, and let \(w\) be an input word. Run two enumerations in parallel, alternating steps between them.

The first enumerates all products of conjugates of relators,

\[ (g_1^{-1}r_{i_1}^{\epsilon_1}g_1)(g_2^{-1}r_{i_2}^{\epsilon_2}g_2) \cdots (g_n^{-1}r_{i_n}^{\epsilon_n}g_n), \]

over all \(n\), all \(r_{i_j} \in R\), all \(\epsilon_j = \pm 1\), and all words \(g_j\) in \(S\), comparing the reduced form of each against \(\red{w}\). By the explicit description of \(\nc{R}\), this list is exactly the set of words that are trivial in \(G\), so if \(w =_G 1\) this enumeration finds a match in finite time. The list is effectively enumerable precisely because the normal closure has that explicit product form.

The second enumerates all finite groups \(F\) by writing out multiplication tables, and for each, all maps \(S \to F\); a map extends to a homomorphism \(G \to F\) exactly when every relator maps to the identity, which is a finite check. For each homomorphism \(\theta\) so obtained, test whether \(\theta(w) \neq 1\). If \(w \neq_G 1\) then residual finiteness guarantees such a \(\theta\) exists, so this enumeration finds one in finite time.

Exactly one of the two events occurs, and whichever it is occurs after finitely many steps, so the alternating search halts with the correct answer. \(\blacksquare\)

The structure is worth naming. Each enumeration alone is a semi-decision procedure: the first confirms triviality but may run forever on nontrivial input, the second the reverse. A set is decidable exactly when it and its complement are both semi-decidable, and the first enumeration is available for every finitely presented group. So the entire difficulty of the word problem sits in the second half: certifying that a word is not trivial.

Proposition. If \(G\) and \(H\) are finitely presented with solvable word problems, so are \(G \times H\) and \(G * H\). For the direct product, a word in \(S_G \sqcup S_H\) is trivial exactly when both of its projections are (delete the letters of the other alphabet), and each projection is decidable by hypothesis. The free product case follows from the normal form theorem for free products [3, ch. IV].

And where it fails

Theorem (Novikov 1955, Boone 1958). There exists a finitely presented group whose word problem is unsolvable.

The proof is beyond this article. The version in [1, ch. 4–7], due to Aanderaa and Cohen, encodes a Turing machine as a modular machine, an automaton whose configurations are pairs of integers, then builds a finitely presented group by a sequence of HNN extensions in which the element \(t(\alpha,\beta)^{-1}k^{-1}t(\alpha,\beta)k\) is trivial exactly when the machine halts on the configuration \((\alpha, \beta)\). A solution to the word problem would solve the halting problem.

Every negative result in the next section is downstream of this one. No procedure that is effective and always terminates can be correct for all finite presentations, so any candidate algorithm must fail, and the only question is where.

Why scan-and-delete does not solve the word problem

Here is a natural first algorithm, and a good one to understand because its failure modes are exactly the phenomena the real theory is built to handle.

The procedure. Given a word \(w\) over \(S \sqcup S^{-1}\), read left to right one letter at a time. Whenever the letters read so far end in a subword belonging to \(R\), delete that subword and restart the scan from the leftmost letter. Also perform free cancellation of \(aa^{-1}\) whenever possible. Report trivial if the word becomes empty, nontrivial otherwise.

Proposition (soundness). If the procedure empties the word, then \(w =_G 1\).

Proof. Each step replaces a word \(w_L\,x\,w_R\) by \(w_Lw_R\), where either \(x \in R\) or \(x = aa^{-1}\). In \(F(S)\),

\[ w_L\,x\,w_R \,=\, \big(w_L x w_L^{-1}\big)\big(w_Lw_R\big), \]

and \(w_Lxw_L^{-1}\) is a conjugate of a relator (or is trivial, in the free-cancellation case), hence lies in \(\nc{R}\). Since \(\nc{R}\) is a subgroup, \(w_Lxw_R \in \nc{R}\) if and only if \(w_Lw_R \in \nc{R}\). So every step preserves the class of the word in \(G\) exactly, and reaching \(\varepsilon\) is a genuine proof of triviality. \(\blacksquare\)

Proposition (termination). Assuming no relator is the empty word, every step strictly decreases length, so the procedure halts on every input.

Corollary (it cannot be correct). The procedure is effective and total. If it were also complete, it would decide the word problem for every finite presentation uniformly, contradicting Novikov–Boone. So it must be incomplete: it will halt on words that are trivial and report otherwise.

That is an impossibility argument, and it says nothing about how the failure shows up. There are three separate mechanisms, and each has a small counterexample.

Failure 1: conjugates and cyclic permutations

Take \(G = \langle a, b \mid ab\rangle\). The single relation says \(b = a^{-1}\), so \(G \cong \mathbb{Z}\). Feed the procedure \(w = ba\). It is trivial in \(G\), and one can see this at the level of the free group:

\[ ba = a^{-1}(ab)a \in \nc{R}. \]

But \(ba\) is freely reduced and its subwords are \(b\), \(a\), and \(ba\); none of them is \(ab\). The procedure halts immediately and reports nontrivial.

The relator occurs, but conjugated. A natural patch is to close \(R\) under inversion and cyclic permutation before starting, which makes this example work. It does not save the procedure.

Failure 2: sometimes the word must get longer first

Take \(G = \langle a, b \mid aba^{-1}b^{-1}\rangle \cong \mathbb{Z}^2\), and

\[ w = a\,a\,b\,b\,a^{-1}a^{-1}b^{-1}b^{-1}. \]

This word is freely reduced, and it is trivial in \(G\): the group is abelian and both exponent sums are zero. Now close \(R\) under inversion and cyclic permutation, giving eight relators:

\[ aba^{-1}b^{-1},\; ba^{-1}b^{-1}a,\; a^{-1}b^{-1}ab,\; b^{-1}aba^{-1}, \; bab^{-1}a^{-1},\; ab^{-1}a^{-1}b,\; b^{-1}a^{-1}ba,\; a^{-1}bab^{-1}. \]

Every one of them strictly alternates between an \(a\)-letter and a \(b\)-letter. The length-four subwords of \(w\) are

\[ aabb,\quad abba^{-1},\quad bba^{-1}a^{-1},\quad ba^{-1}a^{-1}b^{-1}, \quad a^{-1}a^{-1}b^{-1}b^{-1}, \]

and each contains two consecutive letters built from the same generator, so none of them alternates. No deletion applies, no free cancellation applies, and the procedure halts on a trivial word.

To reduce \(w\) you must insert a commutator to create cancellation, temporarily pushing the length above eight. A monotonically shortening procedure structurally cannot do that, and no patch to the relator list changes it. This is the same obstruction that made the normal form theorem nontrivial, now appearing where it genuinely bites.

Failure 3: the order of deletions matters

Take \(G = \langle a, b \mid ab,\; aba\rangle\), the trivial group from earlier, and \(w = aba\). Reading left to right, after two letters the procedure has the subword \(ab \in R\) and deletes it, leaving \(a\). No subword of \(a\) is in \(R\), so it halts and reports nontrivial. But \(aba \in R\) as well, and deleting that empties the word in one step.

The two available deletions overlap and lead to different outcomes, so the rewriting system is not confluent, and committing to the first match found is a choice that can be wrong. Repairing this requires backtracking over all match sequences, which is exponential, or engineering the rule set so that the choice does not matter.

Compare with free reduction, where the analogous check succeeds. Two cancelling pairs overlap only in the pattern \(x\,x^{-1}x\), and both choices leave \(x\). That single calculation is the whole reason the greedy stack scan is a correct algorithm for \(F(S)\) and the greedy scan here is not.

What actually works

• Dehn's algorithm. Replace rather than delete: if a subword \(u\) occurs with \(r = uv \in R\) and \(|u| \gt |v|\), substitute \(v^{-1}\) for \(u\). This still shortens, but it can act on words where no relator occurs whole. A finite presentation for which this decides the word problem is called a Dehn presentation, and a finitely presented group admits one exactly when it is word-hyperbolic in the sense of Gromov [6, ch. III.\(\Gamma\)]. Note that \(\mathbb{Z}^2\) is not hyperbolic, so Failure 2 defeats Dehn's algorithm as well; that example is not an accident.
• Knuth–Bendix completion. Systematically add derived rules until every overlap resolves, producing a confluent terminating rewriting system with unique normal forms. This is the principled fix for Failure 3, and for Failure 1 by orienting and closing the rule set. It is a semi-algorithm: it may not terminate, which it cannot in general, by Novikov–Boone.
• Todd–Coxeter coset enumeration. Enumerate cosets of a subgroup rather than reduce words. It terminates when the index is finite and semi-decides otherwise. The proof in the next section is this algorithm carried out by hand.

The symmetric group

Now a presentation proved correct end to end. For \(n \ge 2\) define

\[ G_n \;=\; \big\langle\, s_1, \dots, s_{n-1} \;\big|\; s_i^2,\; (s_is_{i+1})^3,\; (s_is_j)^2 \ \text{for } |i-j| \ge 2 \,\big\rangle, \]

where \(i\) ranges over \(1 \le i \le n-1\) in the first family and \(1 \le i \le n-2\) in the second. Rewritten as relations, the three families say: each generator is an involution; adjacent generators satisfy the braid relation

\[ s_is_{i+1}s_i = s_{i+1}s_is_{i+1}, \]

and non-adjacent generators commute, \(s_is_j = s_js_i\). The third family is empty for \(n \le 3\), so it only starts carrying weight at \(n \ge 4\).

Theorem. \(G_n \cong S_n\), with \(s_i\) corresponding to the adjacent transposition \(\sigma_i = (i,\ i{+}1)\).

The proof has two halves: build a surjection \(G_n \to S_n\), then bound \(|G_n|\) above by \(n!\).

A surjection onto \(S_n\)

First check the relations hold for the \(\sigma_i\) in \(S_n\). Transpositions are involutions, so \(\sigma_i^2 = e\). For adjacent indices, \(\sigma_i\) and \(\sigma_{i+1}\) are transpositions meeting in exactly one point, so \(\sigma_i\sigma_{i+1}\) is a \(3\)-cycle on \(\{i, i{+}1, i{+}2\}\) and \((\sigma_i\sigma_{i+1})^3 = e\). For \(|i-j| \ge 2\) the supports \(\{i, i{+}1\}\) and \(\{j, j{+}1\}\) are disjoint, so \(\sigma_i\) and \(\sigma_j\) commute and \((\sigma_i\sigma_j)^2 = \sigma_i^2\sigma_j^2 = e\). By von Dyck there is a homomorphism \(\varphi : G_n \to S_n\) with \(\varphi(s_i) = \sigma_i\).

Next, \(\varphi\) is surjective, that is, adjacent transpositions generate \(S_n\). Induct on \(n\), the case \(n = 1\) being trivial. Given \(\pi \in S_n\), let \(j = \pi(n)\) and put \(\rho = \sigma_{n-1}\sigma_{n-2}\cdots\sigma_j\) (composition applied right to left). Applying \(\rho\) to \(j\) sends it to \(j+1\), then \(j+2\), and so on up to \(n\), so \(\rho(\pi(n)) = n\) and \(\rho\pi\) fixes \(n\). Hence \(\rho\pi\) lies in the copy of \(S_{n-1}\) acting on \(\{1, \dots, n-1\}\), which by induction is generated by \(\sigma_1, \dots, \sigma_{n-2}\). Then \(\pi = \rho^{-1}(\rho\pi)\) is a product of adjacent transpositions. In particular \(|G_n| \ge n!\).

The bound \(|G_n| \le n!\)

Induct on \(n\). For \(n = 2\), \(G_2 = \langle s_1 \mid s_1^2\rangle\) has order at most \(2 = 2!\). Assume \(|G_{n-1}| \le (n-1)!\) and set

\[ H := \langle s_1, \dots, s_{n-2}\rangle \le G_n. \]

Claim 1: \(|H| \le (n-1)!\). The elements \(s_1, \dots, s_{n-2}\) of \(G_n\) satisfy every defining relation of \(G_{n-1}\), since those relations form a subset of the relations of \(G_n\). By von Dyck there is a homomorphism \(G_{n-1} \to G_n\) sending the \(i\)-th generator to \(s_i\), and its image is exactly \(H\). So \(|H| \le |G_{n-1}| \le (n-1)!\).

Claim 2: \([G_n : H] \le n\). Define \(n\) coset representatives

\[ q_0 = e, \qquad q_k = s_{n-1}s_{n-2}\cdots s_{n-k} \quad (1 \le k \le n-1), \]

and let \(X = Hq_0 \cup Hq_1 \cup \cdots \cup Hq_{n-1}\). We show \(Xs_j \subseteq X\) for every generator \(s_j\). Since \(e \in H \subseteq X\), this forces \(X \supseteq e\cdot G_n = G_n\), so \(G_n\) is covered by at most \(n\) right cosets of \(H\).

Fix \(k\) and \(j\). The indices appearing in \(q_k\) are exactly \(\{n-k, \dots, n-1\}\). The case \(k = 0\) is immediate: \(Hs_j = H\) for \(j \le n-2\), and \(Hs_{n-1} = Hq_1\). For \(k \ge 1\) there are four cases.

(i) \(j \le n-k-2\). Every index \(i\) in \(q_k\) satisfies \(i \ge n-k \ge j+2\), so \(s_j\) commutes with all of them, and \(j \le n-3\) puts \(s_j\) in \(H\). Hence \(Hq_ks_j = Hs_jq_k = Hq_k\).

(ii) \(j = n-k-1\). Then \(k \le n-2\), and appending \(s_j\) extends the chain: \(q_ks_j = s_{n-1}\cdots s_{n-k}s_{n-k-1} = q_{k+1}\), so \(Hq_ks_j = Hq_{k+1} \subseteq X\).

(iii) \(j = n-k\). The last letter of \(q_k\) is \(s_{n-k} = s_j\), and \(s_j^2 = 1\), so \(q_ks_j = s_{n-1}\cdots s_{n-k+1} = q_{k-1}\), giving \(Hq_ks_j = Hq_{k-1} \subseteq X\).

(iv) \(n-k+1 \le j \le n-1\). Here \(j \ge 2\). Split \(q_k = A\,s_j\,B\) with \(A = s_{n-1}\cdots s_{j+1}\) and \(B = s_{j-1}s_{j-2}\cdots s_{n-k}\), where \(A\) and part of \(B\) may be empty. Every index in \(s_{j-2}\cdots s_{n-k}\) is at most \(j-2\), so \(s_j\) commutes past that block:

\[ q_ks_j = A\,s_js_{j-1}\big(s_{j-2}\cdots s_{n-k}\big)s_j = A\, \big(s_js_{j-1}s_j\big)\,s_{j-2}\cdots s_{n-k}. \]

Apply the braid relation \(s_js_{j-1}s_j = s_{j-1}s_js_{j-1}\), then move the leading \(s_{j-1}\) leftward past \(A\), whose indices are all at least \(j+1 = (j-1)+2\):

\[ q_ks_j = A\,s_{j-1}s_js_{j-1}\,s_{j-2}\cdots s_{n-k} = s_{j-1}\, A\,s_js_{j-1}s_{j-2}\cdots s_{n-k} = s_{j-1}\,q_k. \]

Since \(1 \le j-1 \le n-2\) we have \(s_{j-1} \in H\), so \(Hq_ks_j = Hs_{j-1}q_k = Hq_k\).

All four cases land back in \(X\), proving Claim 2. Combining,

\[ |G_n| = [G_n : H]\cdot|H| \le n\cdot(n-1)! = n!. \]

Conclusion. \(\varphi\) is surjective, so \(|G_n| \ge |S_n| = n!\), and the bound gives \(|G_n| \le n!\). Hence \(|G_n| = n!\) and \(\varphi\) is a surjection between finite sets of equal cardinality, therefore a bijection. So \(\varphi\) is an isomorphism. \(\blacksquare\)

Reading the proof

Under \(\varphi\), the subgroup \(H\) maps onto the stabiliser of the point \(n\), a copy of \(S_{n-1}\), and the \(n\) cosets \(Hq_k\) are the fibres of \(g \mapsto g^{-1}(n)\). Claim 2 is orbit-stabiliser, executed inside the abstract group before we know what that group is, which is exactly the Todd–Coxeter idea: enumerate cosets until they close up, and the count bounds the order.

Each relation family earns its place. The braid relation is the entire content of case (iv); without it the cosets do not close and the index bound fails. The commuting relations do the bookkeeping in cases (i) and (iv). The involutions give case (iii). Dropping only the involutions \(s_i^2\) and keeping the braid relations yields the braid group \(B_n\), which is infinite, so finiteness here is carried specifically by \(s_i^2 = 1\).

Coxeter groups

The presentation of \(S_n\) is one instance of a family defined by the same shape of relation.

Definition (Coxeter matrix). Let \(I\) be a set. A Coxeter matrix on \(I\) is a symmetric matrix \(M = (m_{ij})_{i,j \in I}\) with entries in \(\{1, 2, 3, \dots\} \cup \{\infty\}\) such that \(m_{ii} = 1\) and \(m_{ij} \ge 2\) for \(i \neq j\).

Definition (Coxeter group). The Coxeter group associated with \(M\) is

\[ W \;=\; \big\langle\, s_i\ (i \in I) \;\big|\; (s_is_j)^{m_{ij}} \ \text{ for all } i, j \text{ with } m_{ij} \lt \infty \,\big\rangle, \]

and the pair \((W, S)\) with \(S = \{s_i\}\) is a Coxeter system. The diagonal entries \(m_{ii} = 1\) contribute the relators \(s_i^2\), so every generator is an involution. Entries \(m_{ij} = \infty\) contribute no relator, leaving the product \(s_is_j\) of infinite order.

Braid form. Given \(s_i^2 = s_j^2 = 1\), the relation \((s_is_j)^{m} = 1\) is equivalent to the braid relation

\[ \underbrace{s_is_js_i\cdots}_{m \text{ letters}} \;=\; \underbrace{s_js_is_j\cdots}_{m \text{ letters}}, \]

since multiplying the left side by the inverse of the right side and using \(s^2 = 1\) recovers \((s_is_j)^{\pm m}\). For \(m = 2\) this is commutation, for \(m = 3\) it is \(s_is_js_i = s_js_is_j\). So the symmetric group presentation is precisely the Coxeter group with \(m_{i,i+1} = 3\), \(m_{ij} = 2\) for \(|i-j| \ge 2\), and \(m_{ii} = 1\).

Coxeter diagram. A Coxeter system is drawn as a graph with one node per generator, an edge joining \(i\) and \(j\) whenever \(m_{ij} \ge 3\), labelled by \(m_{ij}\) when \(m_{ij} \ge 4\). Absence of an edge means the two generators commute.

Examples.

• Type \(A_{n-1}\). A path of \(n-1\) nodes, all \(m_{ij} = 3\) along the path. \(W = S_n\), by the theorem above.
• Type \(I_2(m)\). Two generators with \(m_{12} = m\). \(W = \langle s, t \mid s^2, t^2, (st)^m\rangle\) is the dihedral group of order \(2m\), the symmetries of a regular \(m\)-gon.
• Infinite dihedral. Two generators with \(m_{12} = \infty\), giving \(\langle s, t \mid s^2, t^2\rangle \cong \mathbb{Z}/2 * \mathbb{Z}/2\), which acts on the line by reflections in two points.
• Type \(B_n\). A path with one label \(4\) at the end. \(W\) is the group of signed permutations of \(n\) coordinates, of order \(2^nn!\), the symmetry group of the \(n\)-cube.

The presentations do not collapse. Nothing in the definition prevents a Coxeter presentation from being smaller than intended; that is precisely the pathology of \(\langle a, b \mid ab, aba\rangle\). It is a theorem, not an observation, that in \((W, S)\) the generators \(s_i\) are pairwise distinct involutions and the order of \(s_is_j\) is exactly \(m_{ij}\). The standard proof constructs the geometric representation: a real vector space with basis \(\{\alpha_i\}_{i \in I}\), the symmetric bilinear form

\[ B(\alpha_i, \alpha_j) = -\cos\!\left(\frac{\pi}{m_{ij}}\right) \]

(interpreted as \(-1\) when \(m_{ij} = \infty\)), and the reflections \(\rho_i(v) = v - 2B(\alpha_i, v)\alpha_i\). These satisfy the Coxeter relations, so von Dyck gives \(W \to GL(V)\), and restricting to the plane spanned by \(\alpha_i, \alpha_j\) shows \(\rho_i\rho_j\) is a rotation by \(2\pi/m_{ij}\), of order exactly \(m_{ij}\). Since the order in the image is a lower bound for the order in \(W\), and the relator provides the upper bound, the two agree. Details are in [7, sec. 5.3–5.4].

The word problem, repaired

Coxeter groups close the loop with section six. Define the length \(\ell(w)\) of \(w \in W\) as the smallest \(k\) with \(w = s_{i_1}\cdots s_{i_k}\); such an expression of minimal length is reduced.

Theorem (Matsumoto, Tits). Any two reduced expressions for the same element of \(W\) are related by braid moves alone, without ever using \(s_i^2 = 1\). Moreover a word is non-reduced exactly when some sequence of braid moves produces a word containing \(s_is_i\) [7, sec. 8.1], [8].

This yields an algorithm. Given a word, apply braid moves; there are finitely many words of any given length, so the set of words reachable by braid moves is finite and computable. If any of them contains a repeated adjacent letter, delete that pair, shortening the word, and repeat. Otherwise the word is reduced. Two words represent the same element exactly when their reduced forms lie in the same braid-move orbit.

Compare that with the three failures. Braid moves are length-preserving, so the procedure is still monotonically non-increasing in length and still terminates; Failure 2 is avoided not by allowing the word to grow but by allowing it to be rearranged at constant length. Braid moves also generate all the ambiguity there is, by Matsumoto's theorem, so exploring the orbit before deleting removes the wrong-choice problem of Failure 3. And the moves are symmetric in the two generators involved, which handles Failure 1. The correct algorithm is the naive one plus exactly the extra moves the group theory says are needed, and identifying those moves is the theorem.

The general lesson runs the other way as well. Every effective, always-terminating rewriting procedure of this kind is correct only for a restricted class of groups: free reduction for free groups, Dehn's algorithm for hyperbolic groups, braid moves for Coxeter groups. Novikov–Boone says no single such procedure can cover everything, so the design question is never "what is the algorithm" but "for which groups does this algorithm work, and why".

References

1. Will Cravitz. An Introduction to the Word Problem for Groups. University of Chicago REU, 2021. math.uchicago.edu
2. Derek J. S. Robinson. A Course in the Theory of Groups. 2nd ed., Springer, 1996.
3. Roger C. Lyndon and Paul E. Schupp. Combinatorial Group Theory. Springer, 1977.
4. M. H. A. Newman. On theories with a combinatorial definition of equivalence. Annals of Mathematics 43 (1942), 223–243.
5. Max Dehn. Über unendliche diskontinuierliche Gruppen. Mathematische Annalen 71 (1911), 116–144.
6. Martin R. Bridson and André Haefliger. Metric Spaces of Non-Positive Curvature. Springer, 1999.
7. James E. Humphreys. Reflection Groups and Coxeter Groups. Cambridge University Press, 1990.
8. Jacques Tits. Le problème des mots dans les groupes de Coxeter. Symposia Mathematica 1 (1969), 175–185.
9. P. S. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov 44 (1955); William W. Boone, The word problem, Annals of Mathematics 70 (1959), 207–265.