Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 2 / 3

Suppose $G=⟨g_1,\dots ,g_n\mid R⟩$ has a finite group presentation. Work in the free product $B=G\ast F(a,b)$ and putThe $u_i$ freely generate a subgroup of $F(a,b)$. Indeed, in a reduced word in these conjugates, combine adjacent powers with the same index. Expanding the remaining word leaves nonzero powers of $a$ separated by nonzero powers of $b$, so the normal form theorem for a free product makes it nonidentity. This proves the free conjugate bases in a rank-two free group fact we need.

The group homomorphism $B\to F(a,b)$ killing $G$ sends $v_i$ to $a^{-i}b{a}^i$, including $v_0=b$. These are a free conjugate basis by the same argument with $a,b$ interchanged. A nonempty reduced word in the $v_i$ therefore has nontrivial image and cannot be trivial in $B$. Thus $u_i\mapsto v_i$ extends to an isomorphism between the two rank-$(n+1)$ free groups embedded in $B$.

Adjoin one stable letter implementing this isomorphism:We assume Britton's lemma, including its assertion that the base embeds in this HNN extension, and the factor-embedding assertion of the normal form theorem for a free product. Hence $G\hookrightarrow E$. The presentation is finite, and its relations express every generator in $a,t$:Eliminating $b,g_i$ by Tietze transformations therefore gives a two-generator finite presentation with $\boxed{G\hookrightarrow E=⟨a,t⟩}$. This explicitly constructs the two-generator HNN embedding; it does not rely on an arbitrary two-generator embedding preserving finite presentability.

The Messuage lemma for groups is the following effective collapse-versus-embedding statement: from a finite group presentation for $K$ and a word $w$, one can algorithmically write a finite presentation $K_w$ such that $w=1$ in $K$ makes $K_w$ trivial, whereas $w\ne 1$ makes the specified copy of $K$ embed in $K_w$. It can also be arranged that the image of $w$ normally generates $K_w$. We use this lemma as an assumed construction, as requested; the construction of its presentation does not require deciding which case applies.

Let $P$ be a finitely presented group with insoluble word problem for a group, whose existence is allowed. Set $K=P\ast ⟨z⟩$, with $z$ of infinite order. It is finitely presented, and the normal form theorem for a free product embeds both $P$ and the infinite cyclic factor. Thus an input word $w$ from $P$ is trivial in $K$ exactly when it is trivial in $P$, while $K$ is certainly infinite.

Apply the Messuage lemma for groups to this $K,w$. If $w=1$ in $P$, the constructed group $K_w$ is trivial and hence finite. If $w\ne 1$, it contains $K$ and is infinite. ConsequentlyA hypothetical algorithm deciding infinitude from arbitrary finite group presentations would therefore decide every input word in $P$, a contradiction. There is no such algorithm. The infinite cyclic free factor ensures the reduction does not need an additional assumption about the size of $P$.