Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 5 / 3

An algorithm is a finite effective procedure on finitely encoded inputs; a Turing machine is one precise model. A decision algorithm must halt on every permitted input and answer correctly. An algorithmic problem specifies the input encoding and the required output; enumerating positive answers alone is not a decision algorithm.

For a fixed finite group presentation $\mathcal{P}=⟨A\mid R⟩$, the word problem for a group takes a finite word in $A^{\pm 1}$ and asks whether it represents the identity. Equality of two represented elements is equivalent to testing $u^{-1}v$. Positive answers are recursively enumerable: enumerate finite products of conjugates of relators and their inverses, freely reduce them, and compare with the input. Equivalently enumerate finite labelled disc diagrams. The van Kampen lemma ensures that every null word eventually appears. For a non-null word this search continues forever. Solvability requires a procedure that also terminates with a negative answer.

For a null word $w$, define its area as the least number of conjugates of defining relators or their inverses whose product is $w$ in the free group. By the van Kampen lemma, this is also its minimum number of relator faces in a disc diagram. The Dehn function isThe maximum is finite because there are finitely many words of bounded length. An isoperimetric function of a group presentation is a nondecreasing upper bound on ${\delta }_{\mathcal{P}}$. Here subrecursive means bounded above by a total computable function, not merely recursively enumerable.

Suppose ${\delta }_{\mathcal{P}}(n)\le F(n)$ with $F$ computable. Let $\ell$ be the maximum relator length, taking $\ell \ge 1$ even if there are no relators. A minimum-area diagram for a boundary word of length $n$, with at most $N$ faces, can be chosen with no unnecessary tree branches. Every remaining edge occurs on a face boundary or the outside boundary, so there are at most $\ell N+n$ edges. Thus only finitely many combinatorial planar diagrams of area at most $N$ and this edge bound exist. Their finite edge labels and face labels can be enumerated, and the planar contractible diagram topology (allowing boundary spurs and pinched vertices), relator face boundaries and outside boundary word can be checked by finite combinatorial operations.

For the input $w$, compute $N=F(|w|)$ and inspect all these diagrams. Answer yes if one has boundary $w$, and no otherwise. The diagram bound and van Kampen lemma prove correctness, including the negative answer. This finite search avoids the invalid attempt to bound area while allowing unbounded conjugating words.

Conversely, suppose a word problem decider is available. For each $n$, enumerate the finitely many words of length at most $n$ and use the decider to identify exactly the null words. For each such word search diagrams in increasing area, with the finite edge bound just given at each area. The search terminates, and the first successful area is its minimum area. Taking the maximum of these finitely many minima computes ${\delta }_{\mathcal{P}}(n)$. This proves the recursive area bounds and the word problem equivalence:In fact, for finite group presentations, a word decider computes the minimal Dehn function itself.

The required quasi-isometry is the identity on the group vertices. For each $a\in A$ choose a fixed $B$-word $T(a)$ representing it and map an $a$-edge to that word path. The bounded substitutions in Q2(ii) prove the distortion inequalities.

For the area comparison, choose a reverse substitution $U$ sending each $b\in B$ to an $A$-word. Let $L$ bound the lengths of $T(a)$. Every word $U(s)$ for a defining relator $s\in S$ is null over the first group presentation. Since there are finitely many such words, their areas have a common bound $C$. Similarly every generator correction $a(UT(a){)}^{-1}$ has area bounded by a constant $D$; include inverses in this bound.

Let $w$ be null over $A$ with length at most $n$. Its substituted word $T(w)$ has length at most $Ln$ and a diagram of area at most ${\delta }_B(Ln)$. Replace each $B$-edge by its $U$-path. Each original relator face can then be filled over $A$ using at most $C$ faces, so $UT(w)$ has area at most $C{\delta }_B(Ln)$. Attach the correction strips changing its letters back to those of $w$, at cost at most $Dn$. ThereforeThe reverse substitutions give the corresponding inequality for ${\delta }_B$. Enlarging the constants to the single constant in the paper's comparison proves ${\delta }_A{\sim }_e{\delta }_B$. This is Dehn functions under a change of finite presentation.

Two qualifications are necessary for the printed continuation. The invariant is the optimal isoperimetric function, namely the Dehn function, not arbitrary upper bounds. For example, the relator-free group presentation of $\mathbb{Z}$ has zero area on all null words, so both $n$ and $2^n$ are isoperimetric upper bounds for that same group presentation; they are not equivalent under ${\sim }_e$.

Also, the comparison supplies no recursive bound unless one was available beforehand. Its actual consequence, by part (ii), isThe unconditional assertion that every finitely presented group has a solvable word problem is false. Finitely presented counterexamples are established in the primary paper The Word Problem. Thus the missing solvability premise cannot be inferred from group presentation equivalence alone.