Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 1 / 2

All three generators commute, so the group is the abelian group ${\mathbb{Z}}^3$ modulo the integer relation lattice generated by $(2,6,0)$ and $(1,2,2)$. Thus $x^m{y}^n{z}^k=1$ exactly whenEliminating $a,b$ gives $6m-2n-k=0$, and $n=6a+2b$ is even. Conversely, if $n$ is even and $k=6m-2n$, take $a=n/2-m$ and $b=3m-n$; these are integers and reproduce all three coordinates. ThereforeOne can also see the invariant factors directly. The second relation gives $x=y^{-2}{z}^{-2}$. Substitution into the first gives $y^2{z}^{-4}=1$. Put $t=y{z}^{-2}$; thenThe two presentations are equivalent by the explicit substitutions in both directions, so this is not just a quotient guess. An arbitrary input word is first converted, using commutativity, to its exponent totals $m,n,k$. Its coordinates are $(n\mathrm{mod}2,k+2n-6m)$, giving a terminating word problem for a group algorithm.

The allowed algebraic characterization is the Boone-Higman theorem:The simple group $S$ need not itself be finitely presented. The primary statement is Theorem I of An algebraic characterization of groups with soluble word problem. In particular, a finitely generated group with insoluble word problem for a group cannot embed in any finitely presented simple group: otherwise take that group as both $S$ and $P$ in the characterization.

Use the following effective form of the permitted Messuage lemma for groups. Given a finite group presentation of $K$ and a word $w$, one can algorithmically write a finite presentation $K_w$ such that $w=1$ in $K$ implies $K_w=1$, while $w\ne 1$ implies that $K$ embeds in $K_w$. The construction is performed without first deciding whether $w$ is trivial. A collapse-and-embedding lemma with these properties is also stated as Lemma 5.13 in Combinatorial Group Theory. No proof of that allowed lemma is needed here.

Fix a finitely presented group $U$ with insoluble word problem for a group, whose existence is allowed. For each input word $w$ in its generators, construct $U_w$ by the lemma and then form the finite presentation ofIf $w=1$, then $P_w\cong C_2$, which is a nontrivial simple group. If $w\ne 1$, the lemma embeds $U$ in $U_w$, and the normal form theorem for a free product embeds $U_w$ in $P_w$. If $P_w$ were simple, it would be a finitely presented simple group containing $U$, contradicting the characterization. HenceAn algorithm deciding simplicity from arbitrary finite presentations would therefore solve the insoluble word problem for a group in $U$. This proves simplicity of finitely presented groups is algorithmically undecidable. Using $C_2$ avoids any convention about whether the trivial group is called simple.