This is the fourth and last note of our series dedicated to constructions using amalgamated products and HNN extensions. Our main goal is to exhibit several insoluble decision problems in group theory, assuming that there exists a finitely-presented group with an insoluble word problem.

Definition: Let $\mathcal{M}$ be a property of finitely presented groups. We say that $\mathcal{M}$ is a Markov property if $\mathcal{M}$ is preserved by isomorphism, if there exists a finitely presented group satisfying $\mathcal{M}$ and if there exists a finitely presented group which cannot be embedded into a finitely presented group satisfying $\mathcal{M}$.

Theorem: (Adyan) Let $\mathcal{M}$ be a Markov property. There is no algorithm to decide whether or not a finitely presented group satisfies $\mathcal{M}$.

Proof. Let $G_1$ be a finitely presented group satisfying $\mathcal{M}$ and $G_2$ be a finitely presented group which cannot be embedded into a finitely presented group satisfying $\mathcal{M}$. Let $U$ be a finitely generated group with insoluble word problem.

First, we give a finite presentation to the free product

$U_0:= U \ast G_2 = \langle x_1, \dots, x_m \mid R(x_1,\dots, x_m) \rangle$.

Notice that $U_0$ has an insoluble word problem, because $U$ does. If $w=w(x_1,\dots,x_m)$ is any word, we want to construct a finitely presented group $G_w$, such that $G_w$ satisfies $\mathcal{M}$ if and only if $w=1$. It will be sufficient to deduce our theorem.

Let $\langle y_0 \rangle$ be a infinite cyclic group and define $U_1 := U_0 \ast \langle y_0 \rangle$. In particular, with $y_i:= y_0x_i$ when $1 \leq i \leq m$, we have

$U_1 = \langle y_0,y_1, \dots, y_m \mid R(y_0^{-1}y_1, \dots, y_0^{-1}y_m) \rangle$.

Because the $y_i$‘s have an infinite order, we may take successively $(m+1)$ HNN extensions from $U_1$ in order to obtain the group

$U_2 := \langle y_0,y_1, \dots, y_m,t_0,\dots, t_m \mid R, t_iy_it_i^{-1} = y_i^2, 0 \leq i \leq m \rangle$.

From Britton’s lemma, we know that the subgroups $H := \langle t_0, \dots, t_m \rangle$ and $K := \langle t_0^2, \dots, t_m^2 \rangle$ of $U_2$ are freely generated. Therefore, the map $t_i \mapsto t_i^2$ defines an isomorphism $H \to K$, and we have the following associated HNN extension

$U_3 := \langle y_0,y_1, \dots, y_m , t_0, \dots, t_m,z \mid R, t_iy_it_i^{-1}= y_i^2, zt_iz^{-1}= t_i^2, 0 \leq i \leq m \rangle$.

Let $V_1 := \langle r \rangle$ be an infinite cyclic group, $V_2:= \langle r,s \mid srs^{-1}=r^2 \rangle$ a HNN extension of $V_1$ (in fact $V_2$ is isomorphic to the Baumslag-Solitar group $BS(1,2)$), and the following HNN extension of $V_2$:

$V_3 := \langle r,s,t \mid srs^{-1}=r^2, tst^{-1}=s^2 \rangle$.

The successive HNN extensions are well-defined because $r$ and $s$ have an infinite order in $V_1$ and $V_2$ respectively.

Finally, if $w=w(x_1,\dots, x_n)$ is any word, we define $W$ as the group $U_3 \ast V_3$ quotiented by the relations $r=z$ and $t= [y,y_0]$.

Notice that, if $w \neq 1$ in $U_0$ (or equivalently, in $W$), then $[w,y_0]$ has an infinite order in $U_1$, and a fortiori in $U_3$; in particular, the subgroup $\langle z, [w,y_0] \rangle$ of $U_3$ is freely generated. Therefore, because the subgroup $\langle r,t \rangle$ of $V_3$ is also freely generated, $W$ is an amalgamated product of $U_3$ and $V_3$ identifying the two previous subgroups. In particular, we have the embeddings

$G_2 \hookrightarrow U_0 \hookrightarrow U_1 \hookrightarrow U_2 \hookrightarrow U_3 \hookrightarrow W$.

By definition of $G_2$, we deduce that $W$ does not satisfy $\mathcal{M}$.

If $w=1$ in $U_0$ (or equivalently, in $W$), we deduce successively

$w=1 \Rightarrow t=1 \Rightarrow s=1 \Rightarrow r=1 \Rightarrow z=1 \Rightarrow t_i=1 \Rightarrow y_i=1$.

Therefore, $W$ is trivial since it is generated by the elements just mentionned.

To conclude, let $G_w := W \ast G_1$. If $w=1$ in $U_0$, $G_w= G_1$ satisfies $\mathcal{M}$. Otherwise, $G_2$ embedds into $W$ and a fortiori into $G_w$, so $G_w$ does not satisfies $\mathcal{M}$. $\square$

Corollary: There is no algorithm to decide whether or not a finitely presented group is abelian, finite, trivial, free, torsion-free or cyclic.

Proof. It is elementary to prove that all these properties, or their negations, are Markov properties. $\square$

Corollary: There is no algorithm to decide whether or not two presentations represent the same group.

Proof. If there were such an algorithm, it would be possible to decide whether or not a finitely-presented group is trivial. We know that it is impossible according to the previous corollary. $\square$

We conclude our note with some consequences on decision problems in topology:

Theorem: Let $n \geq 4$ and $G$ be a finitely-presented group. Then $G$ is isomorphic to the fundamental group of a closed $n$-manifold.

Sketch of proof. Let $\langle x_1,\dots, x_r \mid r_1, \dots, r_s \rangle$ be a finite presentation of our group $G$ and let $M_0$ be the connected sum

$(\mathbb{S}^1 \times \mathbb{S}^{n-1} ) \sharp \cdots \sharp (\mathbb{S}^1 \times \mathbb{S}^{n-1})$   ($r$ times).

Then $\pi_1(M_0)$ is a free group of rank $r$. In particular, the relation $r_1$ may viewed as an element of $\pi_1(M_0)$, and so as an embedding $f : \mathbb{S}^1 \to M_0$; it can be extended to a tubular neighborhood $f : \mathbb{S}^1 \times D^{n-1} \to M_0$. Let $M_1:=M_0 \backslash f( \mathbb{S}^1 \times D^{n-1})$. According to van Kampen theorem,

$\pi_1(M_0) \simeq \pi_1(M_0 \backslash f( \mathbb{S}^1 \times \{0 \})) \underset{\pi_1(\mathbb{S}^1 \times \partial D^{n-1}) }{\ast} \pi_1( \mathbb{S}^1 \times D^{n-1})$.

Because the image of $\pi_1(\mathbb{S}^1 \times \partial D^{n-1})$ in $\pi_1(M_0)$ coincides with $\pi_1( \mathbb{S}^1 \times D^{n-1})$, we deduce that

$\pi_1(M_1) \simeq \pi_1(M_0)$.

Then, notice that the boundary $\partial (\mathbb{S}^1 \times D^{n-1}) = \mathbb{S}^1 \times \partial D^{n-1}$ is homeomorphic to $\partial D^2 \times \mathbb{S}^{n-2}= \partial (D^2 \times \mathbb{S}^{n-2})$; therefore, via $f$ we may glue $D^2 \times \mathbb{S}^{n-2}$ along $\partial f (\mathbb{S}^1 \times \partial D^{n-1})$. Let $M_2$ denote the manifold constructed by this way. By van Kampen theorem,

$\pi_1(M_2) \simeq \pi_1(M_1) \underset{ \pi_1( \partial D^2 \times \mathbb{S}^{n-2}) }{ \ast} \pi_1( D^2 \times \mathbb{S}^{n-2})$.

But $n \geq 4$ implies that $D^2 \times \mathbb{S}^{n-2}$ is simply connected, we saw that $\pi_1(M_1)$ is isomorphic to $\pi_1(M_0)= \langle x_1, \dots, x_r \mid \ \rangle$, and $\pi_1( \partial D^2 \times \mathbb{S}^{n-2} )$ is a cyclic sugbroup generated by the loop $f$. Therefore,

$\pi_1(M_2) \simeq \langle x_1, \dots, x_r \mid r_1 \rangle$.

The same construction can be done successively with $r_2, \dots, r_s$, and the final manifold $M$ is of course closed and $n$-dimensional, and satisfies $\pi_1(M) \simeq G$. $\square$

Corollary: Let $n \geq 4$. There is no algorithm to decide whether or not two closed $n$-manifolds are homeomorphic (or even simply connected).