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 be a property of finitely presented groups. We say that is a Markov property if is preserved by isomorphism, if there exists a finitely presented group satisfying and if there exists a finitely presented group which cannot be embedded into a finitely presented group satisfying .
Theorem: (Adyan) Let be a Markov property. There is no algorithm to decide whether or not a finitely presented group satisfies .
Proof. Let be a finitely presented group satisfying and be a finitely presented group which cannot be embedded into a finitely presented group satisfying . Let be a finitely generated group with insoluble word problem.
First, we give a finite presentation to the free product
Notice that has an insoluble word problem, because does. If is any word, we want to construct a finitely presented group , such that satisfies if and only if . It will be sufficient to deduce our theorem.
Let be a infinite cyclic group and define . In particular, with when , we have
Because the ‘s have an infinite order, we may take successively HNN extensions from in order to obtain the group
From Britton’s lemma, we know that the subgroups and of are freely generated. Therefore, the map defines an isomorphism , and we have the following associated HNN extension
Let be an infinite cyclic group, a HNN extension of (in fact is isomorphic to the Baumslag-Solitar group ), and the following HNN extension of :
The successive HNN extensions are well-defined because and have an infinite order in and respectively.
Finally, if is any word, we define as the group quotiented by the relations and .
Notice that, if in (or equivalently, in ), then has an infinite order in , and a fortiori in ; in particular, the subgroup of is freely generated. Therefore, because the subgroup of is also freely generated, is an amalgamated product of and identifying the two previous subgroups. In particular, we have the embeddings
By definition of , we deduce that does not satisfy .
If in (or equivalently, in ), we deduce successively
Therefore, is trivial since it is generated by the elements just mentionned.
To conclude, let . If in , satisfies . Otherwise, embedds into and a fortiori into , so does not satisfies .
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.
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.
We conclude our note with some consequences on decision problems in topology:
Theorem: Let and be a finitely-presented group. Then is isomorphic to the fundamental group of a closed -manifold.
Sketch of proof. Let be a finite presentation of our group and let be the connected sum
Then is a free group of rank . In particular, the relation may viewed as an element of , and so as an embedding ; it can be extended to a tubular neighborhood . Let . According to van Kampen theorem,
Because the image of in coincides with , we deduce that
Then, notice that the boundary is homeomorphic to ; therefore, via we may glue along . Let denote the manifold constructed by this way. By van Kampen theorem,
But implies that is simply connected, we saw that is isomorphic to , and is a cyclic sugbroup generated by the loop . Therefore,
The same construction can be done successively with , and the final manifold is of course closed and -dimensional, and satisfies .
Corollary: Let . There is no algorithm to decide whether or not two closed -manifolds are homeomorphic (or even simply connected).