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).

Advertisements