Decision Problems for Finitely Presented Groups

Because the relator language of the recursive presentation is recursively enumerable, there is a procedure that lists all relator words in $R$ and hence also all pairs $(r,\epsilon )$ with $r\in R$ and $\epsilon \in \{1,-1\}$. By dovetailing over lengths, one can therefore enumerate all finite lists of conjugators and signed relators.

First freely reduce the input word $w$ to a reduced word $\bar{w}$. For each finite list from step 1.1, form the corresponding product of conjugates from [L2] and freely reduce it in the ambient free group. Whenever the result is $\bar{w}$, accept. If $w$ is trivial in the presented group, then [L1] and [L2] supply a relator expression representing the same free-group element as $w$, so its free reduction is $\bar{w}$ and the search eventually halts; if $w$ is nontrivial, the search may run forever.

Hence the trivial words are exactly the words on which this procedure halts, so they form a recursively enumerable language.

By [L1], it is enough to show that each single Tietze transformation preserves solvability of the word problem.

A relator-addition or relator-deletion Tietze move does not change which words are trivial in the presented group, by the equality criterion [L2]. So the same decision procedure works before and after such a move.

A generator-addition move introduces one new generator $y$ together with a defining word $u(X)$. To decide whether a word in the enlarged alphabet is trivial, replace each $y^{\pm 1}$ by $u(X{)}^{\pm 1}$ and run the original algorithm on the resulting word. The inverse generator-deletion move is the same transport in the opposite direction.

Every finite Tietze chain transports a decision procedure step by step, so solvability for $\mathcal{P}$ is equivalent to solvability for $\mathcal{Q}$.

Repeatedly apply the elementary cancellations of [L1] until no adjacent inverse pair remains. Because each cancellation shortens the word by two letters, the process halts after finitely many steps with a reduced word $r$.

The free group element represented by $w$ is the same as that represented by $r$, because step 1.1 used only the free-equivalence moves of [L1]. By [L2], the identity class has exactly one reduced representative, namely the empty word. Therefore $w$ represents the identity if and only if $r$ is empty.

The halting free-reduction procedure of step 1.1 therefore decides the word problem in $F(X)$.

By [L1], identify $A$ with ${\mathbb{Z}}^r\times \mathbb{Z}\mathrm{/}{d}_1\mathbb{Z}\times \cdots \times \mathbb{Z}\mathrm{/}{d}_k\mathbb{Z}$. Any input word on a finite generating set evaluates, using commutativity, to one integer exponent sum in each of these finitely many coordinates.

The word represents the identity exactly when the ${\mathbb{Z}}^r$ coordinates are all $0$ and each torsion coordinate is congruent to $0$ modulo its invariant factor $d_i$. Those are finitely many integer checks, so they give a terminating decision procedure.

Therefore finitely generated abelian groups have solvable word problem.

In each factor, solvability of the word problem lets us compare any two words. Enumerating the words in shortlex order therefore computes a canonical representative for every group element, and in the amalgam case it also computes the least representative of every left coset of $K$: two words represent the same left coset exactly when their quotient lies in the embedded copy of $K$, which is decidable by hypothesis. The extra hypothesis also makes every factor word that represents an element of $K$ effectively translatable into a canonical word in the fixed generators of $K$.

For an input alternating word in the generators of the factors, first replace each factor block by its canonical representative. Whenever two consecutive blocks lie in the same factor, multiply them there and recanonize. In the amalgam case, if a block lies in the amalgamating subgroup, step 1.1 translates it to the canonical $K$-word and then into the generators of the opposite factor, so the amalgam relation pushes it across the next syllable effectively. The computable coset representatives from step 1.1 ensure that each such rewrite strictly shortens the syllable length.

The reduction process of step 2.1 halts with the normal form from [L1]. By uniqueness in [L1], the input represents the identity exactly when the final normal form has length zero and terminal $K$-part equal to the identity. Hence the procedure decides the word problem in $G{\ast }_{K}H$.

Taking $K=\{e\}$ gives the free-product case, so both clauses follow.

Because $w$ is null, the admissible lengths in [L1] form a nonempty subset of $\mathbb{N}$: every relator expression for $w$ contributes one such length, and the empty product contributes the value $0$ in the boundary case.

Every nonempty subset of $\mathbb{N}$ has a least element. Applying this to the set of admissible lengths from step 1.1 gives a least $m$, and [L1] defines that least number to be ${\mathrm{Area}}_{\mathcal{P}}(w)$.

Hence the minimal algebraic relator area exists for every null word.

Let $n=\mathrm{\mid }w\mathrm{\mid }$ and let $M:=\max (\{0\}\cup \{\mathrm{\mid }r\mathrm{\mid }:r\in R\})$, so $M=0$ when $R=\mathrm{\varnothing }$. Because ${\delta }_{\mathcal{P}}$ is recursive, one can compute the bound $B={\delta }_{\mathcal{P}}(n)$. If $w$ is null and $B>0$, [L2] gives a relator expression of area at most $B$; choose one of minimal area and, among those, with minimal total conjugator length. Then each conjugator may be taken of length at most $n+BM$: otherwise an initial segment that never survives the free reduction to $w$ could be shortened, contradicting the chosen minimality.

Step 1.1 reduces the search for a certificate of triviality to finitely many possibilities: at most $B$ relator factors, each chosen from the finite set $R^{\pm 1}$, and, when $B>0$, each conjugator drawn from the finite set of words of length at most $n+BM$. When $B=0$, the only candidate certificate is the empty product. Enumerate these possibilities and use [L3] to test in the free group whether any of them equals $w$.

If the search in step 2.1 succeeds, then [L1] says $w$ is trivial. If it fails, then no relator expression of area at most $B$ exists, so by the definition of the Dehn function $w$ cannot be null. Thus step 2.1 decides whether $w{=}_{\mathcal{P}}1$.

Therefore a recursive Dehn function gives a solution to the word problem.

By [L1], there exists a finitely presented group $G$ whose word problem is unsolvable.

That group $G$ is a counterexample to the statement, so the statement is false.

By [L1], every recursively presented group has a semidecision procedure that halts on trivial words and may run forever on nontrivial words.

By [L3], there exists a finitely presented group with unsolvable word problem; by [L2], that group is recursively presented, so step 1.1 applies to it.

The group from step 2.1 has recursively enumerable trivial words by step 1.1, but its word problem is not solvable. Therefore recursively enumerable positive instances do not force a decision algorithm.

Therefore the statement is false.

An unsolvable word problem means that no single algorithm decides triviality for all input words in that fixed group.

That does not prevent a particular word from being settled by an ad hoc calculation, a special normal form, or a direct proof. So failure of one uniform algorithm is not the claim that every individual instance is forever inaccessible.

Therefore the statement is false.

By [L1], Novikov-Boone already produces one fixed finitely presented group whose word problem is unsolvable.

A theorem about one fixed finitely presented group is stronger than a statement that only the varying-presentation problem fails. So the theorem is not limited to the uniform problem.

Therefore the statement is false.

Tietze-equivalent finite presentations present the same group, so [L1] applies to them.

Hence either both word problems are solvable or neither is. They cannot differ, so the statement is false.