A presentation such as \(\langle a,b\mid aba^{-1}b^{-1}\rangle\) specifies generators and the rules they obey. It determines a group up to isomorphism, but it need not give an algorithm for deciding whether two words name the same element. For some finite presentations, no such algorithm exists.
We build free groups as words modulo cancellation, then use their universal property to define normal closures and presentations. The word problem explains why describing a group and computing in it are different tasks. Three examples show how a natural deletion algorithm fails; the symmetric and Coxeter groups show how additional structure makes computation possible.
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.
1. Words
Definition 1.1. Alphabet with formal inverses
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 1.2. Words
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. The words \(abb^{-1}a^{-1}bba\) and \(bba\) are different sequences, but cancelling \(bb^{-1}\) and then \(aa^{-1}\) shows that they name the same group element.
Definition 1.3. Concatenation and formal inverse
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 1.4. Reduced words
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 1.5. Free equivalence
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 1.6. The word-quotient model
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 1.7. Group structure
\(F(S)\) is a group.
Proof.
The empty chain, reversal, and concatenation of chains make \(\sim\) an equivalence relation. Every elementary move can be performed inside any surrounding words, so \(w\sim w'\) implies \(uwv\sim uw'v\). Thus multiplication of classes is well defined.
Concatenation gives associativity and the identity \([\varepsilon]\). In \(ww^{-1}\), cancelling the middle pair exposes the next pair until the word is empty; likewise for \(w^{-1}w\). Hence \([w]^{-1}=[w^{-1}]\).
□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.
2. The normal form theorem
Theorem 2.1. Unique reduced representatives
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.
Proof.
Existence. Repeated cancellation reduces length by two, so it ends at a reduced word.
An invariant. On the set \(\mathcal W\) of reduced words, each letter \(a\) acts by
\[\sigma_a(w)=\begin{cases}w',&w=a^{-1}w',\\aw,&\text{otherwise}.\end{cases}\]The output is reduced. If the first branch deletes \(a^{-1}\), then \(w'\) cannot begin with \(a\), so \(\sigma_{a^{-1}}\) restores the deleted letter. In the other branch it deletes the added \(a\). Thus \(\sigma_a^{-1}=\sigma_{a^{-1}}\).
Define \(\Phi(a_1\cdots a_r)=\sigma_{a_1}\circ\cdots\circ\sigma_{a_r}\), with the rightmost map acting first. Inserting or deleting \(aa^{-1}\) does not change \(\Phi\), since the two corresponding maps cancel.
Uniqueness. For reduced \(w=a_1\cdots a_r\), applying \(\Phi(w)\) to \(\varepsilon\) builds the word from right to left without cancellation, so \(\Phi(w)(\varepsilon)=w\). If reduced words \(u,v\) are equivalent, their maps \(\Phi\) agree; evaluating at \(\varepsilon\) gives \(u=v\).
□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)}. \]Corollary 2.2. Minimal length
The reduced form \(\red{w}\) is the unique word of minimal length in \([w]\).
Proof.
Every representative \(v\) reduces to \(\red{w}\) by deletions alone, so \(|v|\geq|\red{w}|\). Equality means no deletion occurred, hence \(v=\red{w}\).
□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 2.3. Free reduction decides equality
For a finite alphabet, equality in \(F(S)\) is decidable in \(O(|w|+|w'|)\) time.
Proof.
Scan each word with a stack: pop when the next letter cancels the top; otherwise push. The stack represents the scanned prefix, stays reduced, and therefore ends at the unique reduced form. Each letter is pushed or popped at most once. Compare the two final stacks.
□The same procedure works for an effectively encoded infinite alphabet with decidable equality of letters; the linear bound counts letter comparisons.
Corollary 2.4. Generators embed; nonempty bases give infinite groups
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 needs no external lemma. Both matter later: the overlap calculation is exactly the check that fails for general presentations.
3. 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 3.1. The universal property
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 3.2. The quotient is free on its generators
\(\big(F(S), \iota\big)\) is free with basis \(S\).
Proof.
Given \(f:S\to G\), evaluate a word by replacing \(s^{\pm1}\) with \(f(s)^{\pm1}\). Inserting or deleting \(aa^{-1}\) does not change the value, so evaluation descends to
\[\varphi([x_1^{\epsilon_1}\cdots x_r^{\epsilon_r}])=f(x_1)^{\epsilon_1}\cdots f(x_r)^{\epsilon_r}.\]Concatenation evaluates to multiplication, so \(\varphi\) is a homomorphism extending \(f\). Every class is a product of generator classes and their inverses; any extending homomorphism must therefore have this formula.
□Example 3.3. Detecting unequal words with a small target group
Let \(F(a,b)\) be free on two generators. In \(S_3\), the group of permutations of \(\{1,2,3\}\), choose \(a\mapsto(1\ 2)\) and \(b\mapsto(2\ 3)\), where \((i\ j)\) swaps \(i\) and \(j\). The universal property immediately gives a unique homomorphism
\[\varphi:F(a,b)\longrightarrow S_3,\qquad \varphi(a)=(1\ 2),\quad \varphi(b)=(2\ 3).\]Compose permutations with the rightmost acting first. Then
\[\varphi(ab)(1)=2,\qquad \varphi(ba)(1)=3.\]Indeed, \((2\ 3)\) fixes \(1\), then \((1\ 2)\) sends it to \(2\); in the opposite order, \(1\) goes to \(2\) and then \(3\). The images differ, so \(ab\neq ba\) in \(F(a,b)\). Thus the free group is not abelian.
The useful shortcut is that choosing two target elements constructs a map on the entire free group. We need not check multiplication for infinitely many pairs of words. A calculation in a six-element group now distinguishes two elements of the free group. Equal images would not, by themselves, prove equal words.
The quotient construction makes associativity automatic: it comes from concatenation. The reduced-word model makes the elements concrete, but its multiplication requires reducing a concatenation. The normal form theorem proves that both descriptions give the same group.
Corollary 3.4. Uniqueness of the free group
Two free groups on \(S\) have a unique isomorphism preserving the specified generators.
Proof.
Use the universal properties to map each group to the other. Each composite and the identity extend the same generator map, so uniqueness makes both composites identities.
□This licenses the name “the free group on \(S\),” written \(F(S)\), or \(F_n\) when \(|S|=n\).
Proposition 3.5. Rank is well defined
If \(F\) is free with bases \(S\) and \(T\), then \(|S| = |T|\).
Proof.
For a finite basis \(S\), the universal property gives \(|\operatorname{Hom}(F,\mathbb Z/2\mathbb Z)|=2^{|S|}\). Thus two finite bases have the same size.
If \(S\) is infinite, \(F\) cannot have a finite generating set: all words in finitely many proposed generators involve only finitely many letters of \(S\). A letter outside that set cannot be represented by them, by normal form. Hence any other free basis \(T\) is infinite. The set of finite words on an infinite set has the same cardinality as that set, and the basis embeds in \(F\); therefore \(|S|=|F|=|T|\).
□The cardinality of a free basis is the rank. Further standard results, not proved here, say that free groups are torsion free, that commuting elements are powers of a common element [2, ch. 6], and that every subgroup of a free group is free (the Nielsen–Schreier theorem [2, ch. 6]).
4. 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 4.1. 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 4.2. Products of conjugates
Proof.
Call the displayed set \(K\). The empty product is the identity; concatenation and reversing a product give closure under products and inverses. Conjugating by \(h\) replaces each \(g_i\) by \(g_ih\), so \(K\) is normal. It contains \(R\). Conversely, every normal subgroup containing \(R\) contains all these conjugates and their products. Hence \(K\) is the smallest such subgroup.
□The subtlety. The set of bare conjugates
\[ C = \{\, g^{-1}rg : g \in G,\ r \in R \,\} \]need not be a subgroup: it may fail to contain products of its elements. The normal closure is the subgroup generated by \(C\). Suppose \(w_Lw_R\) and \(x\) are relators. Why does inserting \(x\) between \(w_L\) and \(w_R\) still give a trivial word? It need not be a single conjugate of a relator, 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}}, \]Both factors lie in the normal closure, so their product does too. This is the familiar argument “\(w_Lw_R=1\) and \(x=1\) imply \(w_Lxw_R=1\),” carried out in the free group. Closure under products, as well as conjugation, is essential.
5. 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 5.1. Presentation and equality of words
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}\).
Definition 5.2. Relations and 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 7 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 5.3. Von Dyck's theorem
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\).
□Every group has a presentation
Theorem 5.4. Every group is a quotient of a free group
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\).
□Corollary 5.5. Every group has a presentation
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\).
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 5.6. Finiteness of presentations
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.
Eliminating a generator requires substituting for it in the remaining relators. Deleting its name alone can change the group. The corresponding Tietze transformation is
\[ \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 defining relator used for elimination disappears; the other becomes a relator in the remaining generator and kills it. Trivial abelianization alone would not prove the group trivial, but the explicit calculation does.
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.
Alphabeta Math: Tietze transformations
6. The word problem
In 1911 Dehn isolated three decision questions about presentations [5]. Let \(G = \langle S \mid R\rangle\) be finitely presented.
- The word problem. Given a word \(w\) in \(S\), decide whether \(w =_G 1\).
- The conjugacy problem. Given words \(w, v\), decide whether they represent conjugate elements of \(G\).
- The isomorphism problem. Given two finite presentations, decide whether they present isomorphic groups.
Definition 6.1. 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.
Alphabeta Math: independence of generators
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 6.2. Residual finiteness
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 6.3. Residual finiteness gives a decision procedure
A finitely presented residually finite group has solvable word problem.
Proof.
Run two searches in parallel, alternating their steps.
- Enumerate all finite products \(\prod_i g_i^{-1}r_i^{\epsilon_i}g_i\), with \(r_i\in R\), \(\epsilon_i=\pm1\), and \(g_i\) words in the finite alphabet. Compare each freely reduced product with \(\red{w}\). The normal-closure lemma ensures this search finds a match exactly when \(w=_G1\).
- Enumerate finite multiplication tables and check the group axioms. For each finite group, try all assignments of the finite set \(S\) to its elements. Those satisfying the finitely many relators extend by von Dyck to homomorphisms. Test whether the image of \(w\) is nonidentity.
If \(w\) is trivial, the first search succeeds. If it is nontrivial, residual finiteness makes the second succeed. Exactly one succeeds, so their interleaving decides the word problem.
□Alphabeta Math: enumerating trivial words
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 6.4. Direct and free products
If \(G\) and \(H\) are finitely presented with solvable word problems, then so are \(G\times H\) and \(G*H\).
Proof.
For the direct product, project a word to each factor by deleting the other alphabet. It is trivial exactly when both projections are trivial. For the free product, use each factor's decision procedure to remove trivial syllables and merge adjacent syllables from the same factor. The free-product normal form is trivial exactly when no syllable remains [3, ch. IV].
□And where it fails
Theorem 6.5. Novikov–Boone undecidability
There exists a finitely presented group whose word problem is unsolvable.
The proof is beyond this article [1, chs. 4–7], [9]. Its idea is to encode machine computations in a finitely presented group, with a designated word trivial exactly when the corresponding computation halts. A word-problem decider for that group would decide the halting problem.
Undecidability rules out a procedure that always terminates and correctly handles every finite presentation. The next section examines a particular candidate and shows concretely where it fails.
7. 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 7.1. Deletion is sound
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.
□Proposition 7.2. Deletion terminates
Assuming no relator is the empty word, every step strictly decreases length, so the procedure halts on every input.
Corollary 7.3. No universal delete-only decision procedure
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.
Alphabeta Math: missed conjugate
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.
With only free cancellations and insertions or deletions of these relators, any reduction must begin with an insertion: no shortening move applies to this word. The first step therefore increases its length. Length-preserving replacements, or additional derived rules, can overcome this particular obstruction; the unchanged delete-only rules cannot.
Alphabeta Math: lengthening example
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 overlapping deletions have different irreducible outcomes: the rules are not confluent. Backtracking over all deletion choices repairs this example, but not the preceding example, where no deletion can start. A general repair needs additional rules or moves.
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.
Alphabeta Math: order dependence
What actually works
- Dehn's algorithm. First include cyclic permutations of relators and their inverses. 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. Orient equations and add rules to resolve overlaps. If completion produces a finite terminating confluent system, normal forms decide equality. Completion may run indefinitely; there is no guarantee of such a system for an arbitrary finite presentation.
- Todd–Coxeter coset enumeration. Build a coset table for a subgroup. Suitable exhaustive strategies terminate for finite index; at infinite index the computation cannot produce a finite complete table. This is not a general word-problem decider. The next proof uses the idea by hand.
8. 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 8.1. The symmetric group presentation
\(G_n \cong S_n\), with \(s_i\) corresponding to the adjacent transposition \(\sigma_i = (i,\ i{+}1)\).
Proof.
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\).
Adjacent transpositions generate \(S_n\): repeatedly swapping adjacent out-of-order entries sorts any permutation. Thus \(\varphi\) is surjective and \(|G_n|\geq n!\).
The bound \(|G_n| \le n!\)
Induct on \(n\), starting with \(|G_2|\leq2\). Put \(H=\langle s_1,\dots,s_{n-2}\rangle\). Its generators satisfy the relations of \(G_{n-1}\), so von Dyck gives a surjection \(G_{n-1}\to H\); therefore \(|H|\leq(n-1)!\).
Set
\[q_0=1,\qquad q_k=s_{n-1}\cdots s_{n-k}\quad(1\leq k\leq n-1),\qquad X=\bigcup_{k=0}^{n-1}Hq_k.\]We show that right multiplication by every generator preserves \(X\). For \(k=0\), \(Hs_j=H\) if \(j\leq n-2\), and \(Hs_{n-1}=Hq_1\). For \(k\geq1\), there are four cases:
- If \(j\leq n-k-2\), commute \(s_j\) through \(q_k\): \(q_ks_j=s_jq_k\), with \(s_j\in H\).
- If \(j=n-k-1\), append one link: \(q_ks_j=q_{k+1}\).
- If \(j=n-k\), cancel the last letter: \(q_ks_j=q_{k-1}\).
- If \(j\geq n-k+1\), then \(q_ks_j=s_{j-1}q_k\), with \(s_{j-1}\in H\).
For the last identity, write \(q_k=A s_js_{j-1}B\), where \(A=s_{n-1}\cdots s_{j+1}\) and \(B=s_{j-2}\cdots s_{n-k}\). Commuting the final \(s_j\) past \(B\), applying the braid relation, and commuting \(s_{j-1}\) past \(A\) gives
\[q_ks_j=A(s_js_{j-1}s_j)B=A s_{j-1}s_js_{j-1}B=s_{j-1}q_k.\]Since \(1\in X\) and every generator is its own inverse, closure under right multiplication gives \(X=G_n\). Hence
\[|G_n|=[G_n:H]|H|\leq n(n-1)!=n!.\]The surjection onto \(S_n\) now has source and target of equal finite size, so it is an isomorphism.
□Reading the proof
Under \(\varphi\), the subgroup \(H\) maps onto the stabiliser of \(n\), a copy of \(S_{n-1}\), and the cosets \(Hq_k\) correspond to the fibres of \(g\mapsto g^{-1}(n)\). The proof closes the coset list inside the abstract presentation before establishing injectivity. This is the Todd–Coxeter idea: enumerate cosets until they close, then use their count to bound the group order.
Each relation family has a job: commutation moves separated indices past each other, the braid relation handles the fourth case, and involutions allow the third case to cancel. In the braid-and-commutation version of this presentation, removing only the involution relations gives the braid group \(B_n\). Its generators no longer cancel against themselves, and the group is infinite.
9. Coxeter groups
The presentation of \(S_n\) is one instance of a family defined by the same shape of relation.
Definition 9.1. 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\).
[7]
Definition 9.2. Coxeter group and system
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, \]The pair \((W,S)\), with \(S=\{s_i\}\), is a Coxeter system. The diagonal entries supply \(s_i^2=1\). If \(m_{ij}=\infty\), no relation is imposed on \(s_is_j\); that this product really has infinite order is a theorem, not part of the definition.
[7]
Proposition 9.3. Braid form of the Coxeter relations
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\).
[7]
Definition 9.4. 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.
[7]
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 for \(m\geq3\); for \(m=2\), it is the Klein four group.
- 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.
We have seen that a presentation can collapse unexpectedly. Coxeter presentations have a theorem ruling this out.
Theorem 9.5. Orders in a Coxeter system
The generators are distinct nonidentity involutions, and \(s_is_j\) has order exactly \(m_{ij}\) for distinct indices, including infinite order when \(m_{ij}=\infty\).
[7, §§5.3–5.4]
The geometric representation explains why. Take a real vector space with basis \(\{\alpha_i\}\) and symmetric bilinear form
\[ B(\alpha_i, \alpha_j) = -\cos\!\left(\frac{\pi}{m_{ij}}\right) \]with value \(-1\) when \(m_{ij}=\infty\), and reflections \(\rho_i(v)=v-2B(\alpha_i,v)\alpha_i\). The Coxeter relations hold, giving a representation of \(W\). On the two-dimensional span of \(\alpha_i,\alpha_j\), a finite parameter gives a rotation of order \(m_{ij}\). For an infinite parameter, the form is degenerate and the product has matrix \(U=\begin{bmatrix}3&-2\\2&-1\end{bmatrix}\). Since \((U-I)^2=0\) but \(U\neq I\), its powers \(U^r=I+r(U-I)\) are distinct, so its order is infinite. These image orders, together with the defining relations, prove the asserted orders in \(W\). The geometric representation is developed in [7, §§5.3–5.4].
The word problem, repaired
The extra moves needed for Coxeter groups preserve length rather than increasing it. To describe the result, distinguish reduced Coxeter expressions from freely reduced words.
Definition 9.6. Coxeter length and reduced expressions
The length \(\ell(w)\) is the minimum \(k\) such that \(w=s_{i_1}\cdots s_{i_k}\). An expression attaining this minimum is reduced.
[7]
Theorem 9.7. Braid moves and the deletion criterion
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].
[7, §8.1], [8]
For a finite Coxeter system, this yields an algorithm. Explore every word reachable by braid moves; only finitely many words have the given length. If one contains an adjacent repeated generator, delete that pair and repeat at the shorter length. If none does, the expression is reduced. Two reduced expressions represent the same element exactly when they 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.
Each successful procedure needs a theorem establishing where it works: normal form for free groups, Dehn presentations for hyperbolic groups, or the braid-move and deletion theorems for Coxeter groups. Termination alone is not a proof of correctness.
References
Alphabeta Math item links accompany the corresponding statements. The main chapters are Free Groups and Presentations and Decision Problems for Finitely Presented Groups. The Coxeter results retain their textbook and primary references.
- Will Cravitz. An Introduction to the Word Problem for Groups. University of Chicago REU, 2021. math.uchicago.edu
- Derek J. S. Robinson. A Course in the Theory of Groups. 2nd ed., Springer, 1996.
- Roger C. Lyndon and Paul E. Schupp. Combinatorial Group Theory. Springer, 1977.
- M. H. A. Newman. On theories with a combinatorial definition of equivalence. Annals of Mathematics 43 (1942), 223–243.
- Max Dehn. Über unendliche diskontinuierliche Gruppen. Mathematische Annalen 71 (1911), 116–144.
- Martin R. Bridson and André Haefliger. Metric Spaces of Non-Positive Curvature. Springer, 1999.
- James E. Humphreys. Reflection Groups and Coxeter Groups. Cambridge University Press, 1990.
- Jacques Tits. Le problème des mots dans les groupes de Coxeter. Symposia Mathematica 1 (1969), 175–185.
- 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.
Comments