Baumslag, Bridson, Miller and Short (BBMS) provide criteria for what they call the fibre products to be finitely presented. They then leverage these results to show that, amongst other things, there exists a torsion-free hyperbolic group with a fibre product subgroup , such that the membership problem for in is undecidable. To connect this to our pursuit of the distortion functions of finitely generated subgroups, we recall that a finitely generated subgroup of a finitely generated group (with solvable word problem) has a solvable membership problem if and only if the distortion function of in is bounded above by a recursive function.
Theorem 1. There exists a torsion free word hyperbolic group and a finitely presented subgroup such that there is no algorithm to decide membership of and the conjugacy problem of is unsolvable. Additionally, can be chosen to be the fundamental group of a compact negatively curved 2-complex.
The group has a solvable conjugacy problem (Gersten-Short).
1. Fibre products
The central construction of BBMS is similar to the Mihailova construction we’ve covered before. To any short exact sequence
we have the associated fibre product where
If is finitely presented and is finitely generated then is finitely generated. We can think of as the graph of the relation , and so questions about equality in are questions about membership of .
When is free and is finitely presented with undecidable word problem, has many undecidable properties (Miller), but will generally not be finitely presented in this case (see the Mihailova construction). Using a refined version of the Rips construction, encapsulated by the following theorem, allows one to get finitely presented .
1-2-3 Theorem. Suppose
is exact, and let be the associated fibre product. If is finitely generated (type ), is finitely presented ( type ), and is of type , then is finitely presented.
1.1. Type and
The major conceptual underpinning of Theorem 1 is a connection between type and . Let be an Eilenberg-Maclane space for with finite 3-skeleton. We will assume that has a single vertex. This means that its 2-skeleton, , can be identified with to a finite presentation of whose generators are given by the 1-cells and whose relations are given by the attaching maps of 2-cells in . Since is finitely generated as a -module, is finite. This can be seen by taking the attaching maps of the 3-cells as the generators of the module. This identification allows one to find a nice presentation for and thus a nice presentation for .
Obtaining this presentation is rather technical and takes a major portion of BBMS, and we omit the details. However, we will sketch their approach. Let be a presentation for a group . Let be a sequence of words of the form where and is some word over . We call such a sequence an identity sequence if is freely equal to the empty word in . An equivalence relation is given on identity sequences, and we consider the action of on these sequences given by . This action naturally induces a -action on the equivalence classes of identity sequences. We can view the identity sequences equipped with this action as a -module is isomorphic to . Thus being finitely generated as a module means that there is a finite set of identity sequences such that any identity sequence can be reduced under the equivalence relation to finitely many of these sequences in this set. This identification can then be used to determine a presentation for entirely from the presentations of and .
2. Proof of Theorem 1
Theorem 1 relies on an extension of the enhanced Rips construction.
Theorem 3 (Modified Rips Construction). There is an algorithm that associates to any finite group presentation , a compact, negatively curved, piecewise hyperbolic 2-dimensional complex and a short exact sequence
- presents the group ,
- has a single vertex ,
- the 2-cells of are right angled hyperbolic pentagons (each side of which crosses several 1-cells),
- has a finite generating set of cardinality at least 2,
- each of the 1-cells in is the unique closed geodesic in its homotopy class,
- the homotopy class of each is represented by one of the 1-cells of ,
- is torsion-free,
- and each generates its centralizer.
The first seven items follow from a construction in Bridson-Haefliger and Wise. Item (8) comes from the fact that the fundamental group of any compact non-positively curved space is torsion free. Item (9) follows from (7). is hyperbolic and torsion free, so the centralizer of every non-trivial element in is cyclic. Thus, if were a proper power, its homotopy class would not correspond to a simple closed geodesic.
Theorem follows from the next result.
Theorem 4. There exists a compact negatively curved 2-complex and a finitely presented subgroup such that
- the membership problem for is unsolvable, and
- has unsolvable conjugacy problem.
This theorem utilizes the existence of groups of type with unsolvable word problems. Collins and Miller constructed a group with a finite 2-dimensional and unsolvable word problem. The enhanced Rips construction is applied to to for , where is a compact negatively curved 2-complex.
Following the notation of the Rips construction, take where and the are lifts of generators of . We take for a generating set for . The 1-2-3 Theorem implies that the fibre product is finitely presented.
To see that the membership problem for is unsolvable we restrict to specific words. A word on the generators is in if and only if the same word in the is equivalent to the identity in . Thus the unsolvability of the word problem for implies the unsolvability of the membership problem for .
The unsolvability of the conjugacy problem follows from the next lemma.
Lemma 5 Let be finitely generated groups. Suppose and there exists such that . If there is no algorithm to decide membership of , then has an unsolvable conjugacy problem.
The thrust of the lemma is that, given a word in , we consider where is a generator of , and this word being conjugate to in is equivalent to being in . This lemma is applied with , as item (9) of Theorem 3 tells us that the centralizer of is , and thereby gives us unsolvability of the conjugacy problem.
3. Isomorphism problem
BBMS also addressees the isomorphism problem for subgroups of fundamental groups of non-positively curved spaces. These results take us away from subgroup distortion, but are worth noting for their own sake.
Corollary of Modified Rips construction. Let and be as above. Let . Then is the fundamental group of a compact non=-positively curved squared complex, and is thus biautomatic (Niblo-Reeves).
Proof: Re-metrize by subdividing each pentagonal face by introducing a new vertex in the middle of each face and side and using these to break the pentagons into hyperbolic quadrilaterals. These quadrilaterals are replaced by Euclidean squares without changing side length. The resulting space is still non-positively curved and the original 1-cells are still geodesics. We refine these squares until their side lengths are half that of the original 1-cells in . We attach an annulus (union of two Euclidean squares) by gluing the boundary circles to the loop representing by an isometry.
Theorem 7. There exists a non-positively curved 4-dimensional complex with biautomatic fundamental group , and a (countable) recursive class of finitely presented subgroups such that there is no algorithm to determine whether or not is isomorphic to .
The group in this theorem is a direct product where is a torsion free word hyperbolic group and is an HNN-extension of given by where generates a maximal cyclic subgroup.
Corollary 8. There exists a non-positively curved manifold of dimension 9 and a recursive class of finitely presented subgroups of such that there is no algorithm to determine homotopy equivalence between covering spaces corresponding to these subgroups.