RECOGNITION OF SUBGROUPS

OF DIRECT PRODUCTS OF HYPERBOLIC GROUPS

MARTIN R. BRIDSON AND CHARLES F. MILLER III

Abstract. We give examples of direct products of three hyperbolic groups in which there cannot exist an algorithm to decide which finitely presented subgroups are isomorphic.

In [1] Baumslag, Short and the present authors constructed an example of a biautomatic group G in which there is no algorithm that decides isomorphism among the finitely presented subgroups of G. The group G was a direct product of a certain (word) hyperbolic group H with an HNN extension B of H which is CAT(0) and biautomatic but not hyperbolic. At the time of writing [1] we were unable to construct, more simply, a direct product of hyperbolic groups in which the isomorphism problem for finitely presented subgroups was unsolvable.

In the course of our project on finiteness properties of subdirect products [7], we uncovered a new criterion for the finite presentability of certain semidirect products (see Section 2). That, combined with improved understanding of subgroups of direct products, has enabled us to prove the following result:

Theorem 1. Let 1 → K → Γ → L → 1 be an exact sequence of groups. Suppose that

1. Γ is torsion-free and (word) hyperbolic,

2. K is infinite and finitely generated, and

3. L is a non-abelian free group. If F is a non-abelian free group, then there is no algorithm to decide which pairs of finitely presented subgroups of Γ×Γ×F are isomorphic.

In more detail, there is a recursive sequence Δ_{i}, where i = 0, 1, …, of finite subsets of Γ×Γ×F together with finite presentations ⟨Δ_{i} | Θ_{i}⟩ of the subgroups they generate such that there is no algorithm to determine whether or not ⟨Δ_{i} | Θ_{i}⟩ ≅ ⟨Δ_{0} | Θ_{0}⟩.

Date: January 31, 2002.

1991 Mathematics Subject Classification. Primary: 20F10, 20F67.

Key words and phrases. hyperbolic groups, finitely presented subgroups, isomorphism problem.

The first author’s research was funded by an Advanced Fellowship from the EPSRC.

An example of such a group Γ is given, for instance, by applying the construction of Rips [14] to a non-abelian free group.

The crucial element of undecidability in Theorem 1 comes from an encoding of the fact that the generation problem for a direct product of non-abelian free groups is undecidable.

It is possible to avoid using the criteria we develop for finite presentability of certain semidirect products by appealing to recent deeper results of Mosher and others as discussed in Section 4.

1. A criterion for finite presentability

Recall that a subgroup H of a direct product A × B is termed a subdirect product if its projection to each of A and B is surjective.

We discovered the following criterion in the course of our project on finiteness properties of subdirect products [7]. It is based on the special case proved in Lemma 2.3 of [5].

Proposition 2. Let K_{1} and K_{2} be finitely generated groups. Let L_{1} and L_{2} be finitely generated free groups and let ϕ_{i} : L_{i} → Aut K_{i} be homomorphisms such that the semidirect products K_{i} ⋊_{ϕ_{i}} L_{i} are finitely presented.

Let p : F → H be a homomorphism from a finitely presented group F to a subdirect product H ⊂ L_{1} × L_{2}. Let Φ = (ϕ_{1}, ϕ_{2}) ∘ p. Then the associated semidirect product (K_{1} × K_{2}) ⋊_{Φ} F is finitely presented.

Proof. For each i = 1, 2, fix a finite set of generators B_{i} for K_{i} and a free basis C_{i} for L_{i}. Now K_{i} has a presentation of the form ⟨B_{i} | T_{i}⟩ where T_{i} consists of words in B_{i}. Let R_{i} be the (finite) set of words c^{−1}bcβ^{−1} with b ∈ B_{i} and c ∈ C_{i}, where β is a word in B_{i} chosen so that β = (ϕ_{i}(c))(b) in K_{i}.

With these choices, ⟨B_{i}, C_{i} | T_{i}, R_{i}⟩ is a presentation of K_{i} ⋊_{ϕ_{i}} L_{i}. Now by assumption K_{i} ⋊_{ϕ_{i}} L_{i} is finitely presented. So for some finite subset S_{i} ⊆ T_{i}, the “subpresentation” ⟨B_{i}, C_{i} | S_{i}, R_{i}⟩ is a presentation for K_{i} ⋊_{ϕ_{i}} L_{i}, and all the remaining relations in T_{i} are consequences of those in S_{i} and R_{i}.

Let Z_{B} consist of the commutators [b_{1}, b_{2}] with b_{i} ∈ B_{i}. Then ⟨B_{1}, B_{2} | T_{1}, T_{2}, Z_{B}⟩ is a presentation for K_{1} × K_{2}.

Choose a finite presentation ⟨X | Y ⟩ for F. For each i = 1, 2, let U_{i} Consist of words x^{−1}bxγ^{−1} where b ∈ B_{i} and x ∈ X and where the γ = (ϕ_{i}(p(x)))(b) are words in B_{i}. It follows that

⟨B_{1}, B_{2}, X | T_{1}, T_{2}, Z_{B}, Y, U_{1}, U_{2}⟩

is a presentation for (K_{1} × K_{2}) ⋊_{Φ} F.

For each c ∈ C_{i}, i = 1, 2 there is a word ρ on X such that ρ ↦ c under the composition F → L_{1} × L_{2} → L_{i}. (This is the point at which we are using the fact that the image of F is a subdirect product of L_{1} × L_{2}.) Let V_{i} be the (finite) set of words cρ^{−1}. Applying a simple Tietze transformation, it follows that

⟨B_{1}, B_{2}, C_{1}, C_{2}, X | T_{1}, T_{2}, Z_{B}, Y, U_{1}, U_{2}, V_{1}, V_{2}⟩

is also a presentation for (K_{1} × K_{2}) ⋊_{Φ} F since the added relations V_{i} say that the added generators c ∈ C_{i} are abbreviations for the corresponding words ρ.

By construction, the finite sets of relations R_{i} are consequences of the relations in the above presentation. Applying a simple Tietze transformation we can therefore add them to obtain a new presentation

⟨B_{1}, B_{2}, C_{1}, C_{2}, X | T_{1}, T_{2}, R_{1}, R_{2}, Z_{B}, Y, U_{1}, U_{2}, V_{1}, V_{2}⟩

for the group (K_{1} × K_{2}) ⋊_{Φ} F.

Recall that the relations T_{i} are consequences of the finite set of relations S_{i} ∪ R_{i}. So again applying a Tietze transformation we obtain the finite presentation

⟨B_{1}, B_{2}, C_{1}, C_{2}, X | S_{1}, S_{2}, R_{1}, R_{2}, Z_{B}, Y, U_{1}, U_{2}, V_{1}, V_{2}⟩

for the group (K_{1} × K_{2}) ⋊_{Φ} F. This completes the proof of the proposition.

2. A Seed of Undecidability

In the published version of his thesis ([10], also [9] page 194 and [11]), the second author proved that the generation problem for the direct product L × L of two non-abelian, finitely generated free groups is unsolvable. Combining that construction with non-finitely presentability results of Grunewald [8] or of Baumslag and Roseblade [2] we have the following:

Theorem 3. Let L be a free group of rank at least 2 and let X be a finite generating set for L × L. For some sufficiently large integer m, there exists a recursive sequence Λ_{n} of finite sets of words on X ∪ X^{−1} such that

1. each Λ_{n} has cardinality m;

2. each of the subgroups ⟨Λ_{n}⟩ ⊂ L × L is a subdirect product;

3. ⟨Λ_{0}⟩ = L × L;

4. there is no algorithm to determine whether or not ⟨Λ_{n}⟩ = L × L;

5. if ⟨Λ_{n}⟩ ≠ L × L then ⟨Λ_{n}⟩ is not finitely presented.

It is convenient (though this could be avoided) to recall a bit more detail about these sets of words Λ_{n}. Suppose that L has a free basis c_{1}, …, c_{k}. The construction of Λ_{n} involves a family of finite presentations of quotients of L of the form Π_{n} = ⟨c_{1}, …, c_{k} | q_{n,1}, …, q_{n,m−k}⟩ all having the same set of generators and the same number m − k of relators which depend on a parameter. Then the m words in Λ_{n} correspond to the elements

{(c_{1}, c_{1}), …, (c_{k}, c_{k}), (q_{n,1}, 1), …, (q_{n,m−k}, 1)} (1)

thought of as pairs in the direct product L × L. The presentations Π_{n} are chosen so that determining whether the group presented is trivial or infinite is an unsolvable problem. The subgroup generated by Λ_{n} is all of L × L if and only if the group presented by Π_{n} is trivial.

Beginning the proof of Theorem 1: Let F be a free group of rank^{1} 2m with basis {x_{1}, …, x_{m}, y_{1}, …, y_{m}}. If we list the elements of the sets Λ_{n} as say Λ_{n} = {λ_{n,1}, …, λ_{n,m}}, ordered in consonance with (1), then we can define a homomorphism p_{n} : F → L × L by p_{n}(x_{i}) = λ_{n,i} and p_{n}(y_{i}) = 1 for i = 1, …, m. Of course the image p_{n}(F) = ⟨Λ_{n}⟩.

We take K = K_{i} and L = L_{i} as in Proposition 2. Thus Γ = Γ_{i} := K_{i} ⋊_{ϕ_{i}} L_{i}. Associated to each Λ_{n} we have a semidirect product

E_{n} = (K × K) ⋊_{Φ_{n}} F. (2)

Suppose b_{1}, …, b_{p} generate K. Then, using the detailed notation above, E_{n} is isomorphic to the subgroup of Γ × Γ × F generated by the following set of elements

Δ_{n} = {(b_{1}, 1, 1), …, (b_{p}, 1, 1), (1, b_{1}, 1), …, (1, b_{p}, 1),
(c_{1}, c_{1}, x_{1}), …, (c_{k}, c_{k}, x_{k}), (q_{n,1}, 1, x_{k+1}), …, (q_{n,m−k}, 1, x_{m}),
(1, 1, y_{1}), …, (1, 1, y_{m})}.

Since each ⟨Λ_{n}⟩ ⊂ L × L is a subdirect product, the groups E_{n} are all finitely presented. Because {x_{1}, …, x_{k}} projects onto a basis for each direct factor L, the finite presentation for E_{n} given in the proof of Proposition 2 easily simplifies to ⟨Δ_{n} | Θ_{n}⟩ = ⟨B_{1}, B_{2}, X | S_{1}, S_{2}, U_{n}⟩ where the S_{i} are fixed and the U_{n} can be written down explicitly using the words q_{i,j}.

Note that E_{n} is a subdirect product of Γ × Γ × F. The structure of E_{n} will obviously depend on Φ_{n} and hence Λ_{n}. If ⟨Λ_{n}⟩ = ⟨Λ_{0}⟩ = L × L then one is tempted to say that E_{n} is “obviously” isomorphic to E_{0}, since the images of Φ_{n} and Φ_{0} are the same. But a little care is needed, since in general a semidirect product G ⋊_{ψ} F is determined by the actual map ψ : F → Aut G but not by the set im ψ. The issue here is one of Nielsen equivalence between different generating sets of im ψ. It is to circumvent this difficulty that we took F above to be a free group of rank 2m rather than simply m. This apparent redundancy has been employed so that we can appeal to the following version of Rapaport’s Theorem [13], which is proved is Section 4 of [6].

1Since a non-abelian free group contains a free group of any given finite rank, this suffices in order to prove Theorem 1

Lemma 4. Let Γ be a group. Let F_{2m} be a free group of rank 2m with basis {x_{1}, …, x_{m}, y_{1}, …, y_{m}}. Let ϕ_{1}, ϕ_{2} : F_{2m} → Γ be homomorphisms such that im ϕ_{1} = im ϕ_{2} and ϕ_{1}(y_{i}) = ϕ_{2}(y_{i}) = 1 for i = 1, …, m. Then there exists an automorphism Ψ : F_{2m} → F_{2m} such that ϕ_{2} ∘ Ψ = ϕ_{1}.

Corollary 5. If Γ ⊂ Aut N, then under the above hypotheses N ⋊_{ϕ_{1}} F_{2m} ≅ N ⋊_{ϕ_{2}} F_{2m}.

Proof. Define N ⋊_{ϕ_{1}} F_{2m} → N ⋊_{ϕ_{1}} F_{2m} to be the identity on N and Ψ on F_{2m}.

Corollary 6. In the above construction, if ⟨Λ_{n}⟩ = L × L, that is, if p_{n} maps F onto L × L, then E_{n} ≅ E_{0}; equivalently, ⟨Δ_{n} | Θ_{n}⟩ ≅ ⟨Δ_{0} | Θ_{0}⟩.

To complete the proof of Theorem 1, we need a method of showing that if ⟨Λ_{n}⟩ ≠ L×L, then ⟨Δ_{n} | Θ_{n}⟩ ≅ ⟨Δ_{0} | Θ_{0}⟩. This is accomplished in the next section by considering centralizers of pairs of elements.

3. Centralizers in Full Subgroups

If Γ is a torsion-free hyperbolic group, then the centralizer of each non-trivial element γ ∈ Γ is the cyclic group ⟨\overline{γ}⟩, where \overline{γ} is the maximal root of γ. It follows that if γ_{1} and γ_{2} are two non-commuting elements of Γ, then the centralizer C_{Γ}(γ_{1}, γ_{2}) of the pair is trivial.

Let D = Γ_{1} × ⋯ × Γ_{n} be a direct product of non-cyclic, torsionfree hyperbolic groups. Consider a non-commuting pair of elements x = (x_{1}, …, x_{n}) and y = (y_{1}, …, y_{n}) of D. Then for some i, their coordinates x_{i} and y_{i} do not commute. If z = (z_{1}, …, z_{n}) commutes with both x and y, then z_{i} = 1 since Γ_{i} is torsion-free hyperbolic. Thus the elements in the centralizer of the pair C_{D}(x, y) all have their i-th coordinates equal to 1, and so

C_{D}(x, y) ≤ Γ_{1} × ⋯ × Γ_{i−1} × 1 × Γ_{i+1} × ⋯ × Γ_{n}.

Definition 1. A subgroup H of a direct product Γ_{1} × ⋯ × Γ_{n} is said to be full if H ∩ Γ_{i} is contains a non-commuting pair of elements x_{i}, y_{i} for each i = 1, …, n.

Suppose that H is a full subgroup of D. Then the collection Σ of centralizers of non-commuting pairs of elements of H has a finite set of maximal elements, namely the centralizers of pairs x_{i} and y_{i} which are non-commuting pairs in H ∩ Γ_{i}. These maximal elements are exactly the subgroups

M_{i} = H ∩ (Γ_{1} × ⋯ × Γ_{i−1} × 1 × Γ_{i+1} × ⋯ × Γ_{n})

for i = 1, …, n. The set of subgroups {M_{1}, …, M_{n}} form an isomorphism invariant of H. For if ϕ : H → K is an isomorphism, then each ϕ(M_{i}) will be a maximal centralizer of a non-commuting pair of elements of K.

A set of subgroups of H is said to be characteristic if any automorphism of H permutes the subgroups in the set. Clearly {M_{1}, …, M_{n}} is also a characteristic set of subgroups of H. Now each of the subgroups H ∩ Γ_{i} is the intersection of the n − 1 distinct M_{j} which contain it. It follows that the H ∩Γ_{i} also form a characteristic set of subgroups of H. From these observations we conclude the following:

Proposition 7. If H is a full subgroup of a direct product D = Γ_{1} × ⋯ × Γ_{n} of non-cyclic, torsion-free hyperbolic groups, then the set of subgroups {H ∩ Γ_{i}} is characteristic, and hence

(H ∩ Γ_{1}) × ⋯ × (H ∩ Γ_{n})

is a characteristic subgroup.

Applying these considerations to the case H is D itself, we obtain the following:

Corollary 8. If D = Γ_{1} × ⋯ × Γ_{n} is the direct product of non-cyclic, torsion-free hyperbolic groups, then the set of subgroups {Γ_{i}} is characteristic. In particular, the decomposition of D as a direct product of hyperbolic subgroups is unique.

Observe that the corollary is no longer true if either cyclic or finite factors are allowed in the definition of D as a direct sum of hyperbolic groups.

Completing the proof of Theorem 1: We resume the notation developed in Section 2. Since K is an infinite normal subgroup of the non-cyclic torsion-free hyperbolic group Γ, K is non-abelian and so contains a pair of non-commuting elements. The intersections of ⟨Δ_{n}⟩ with the first and second factors of Γ_{1} × Γ_{2} × F (where we have added subscripts to distinguish the factors) are just two copies K_{1} and K_{2} of K. In particular they are finitely generated.

The intersection of ⟨Δ_{n}⟩ with the third factor of Γ × Γ × F is the kernel of p_{n} : F → L×L. The image p_{n} is ⟨Λ_{n}⟩ ⊆ L×L. So if p_{n}(F) = ⟨Λ_{n}⟩ = L × L, then ker p_{n} = F ∩ ⟨Δ_{n}⟩ is finitely normally generated, since L × L is finitely presented. In particular, ker p_{0} = F ∩ ⟨Δ_{0}⟩ is finitely normally generated.

On the other hand, if p_{n}(F) = ⟨Λ_{n}⟩ ≠ L × L, then ker p_{n} = F ∩ ⟨Δ_{n}⟩ is not finitely normally generated, since ⟨Λ_{n}⟩ is not finitely presented.

We know from Proposition 7 that {K_{1}, K_{2} , F ∩ ⟨Δ_{n}⟩} is a characteristic set of subgroups of ⟨Δ_{n}⟩. The foregoing discussion tells us that all three of these subgroups will be finitely normally generated if and only if ⟨Δ_{n}⟩ = L × L. Thus ⟨Λ_{n}⟩ ≠ L × L implies ⟨Δ_{n} | Θ_{n}⟩ ≅ ⟨Δ_{0} | Θ_{0}⟩. By Theorem 3 there is no algorithm to determine whether or not ⟨Λ_{n}⟩ = L × L. Therefore, deciding whether or not ⟨Δ_{n} | Θ_{n}⟩ ≅ ⟨Δ_{0} | Θ_{0}⟩ is an unsolvable problem. This completes the proof of Theorem 1.

Remark 1. A slight variation on the above proof shows that there is no algorithm to determine which finitely presented subgroups of Γ × Γ × F are abstractly commensurable.

4. Hyperbolic-by-Hyperbolic Hyperbolic Groups

As mentioned in the introduction, examples of hyperbolic groups Γ as required for Theorem 1 are provided by the well-known construction of Rips [14]. If the subgroup K in the theorem is also finitely presented, then the groups E_{n} are visibly finitely presented without appeal to Section 1. In this section we describe short exact sequences of torsionfree non-elementary hyperbolic groups, thus animating Theorem 1 with additional examples.

First we describe Mosher’s examples [12]. Let S be a closed hyperbolic surface, pick a base point p ∈ S and let Σ = π_{1}(S, p) be the fundamental group. Let MCG(S) denote the mapping class group of S (isotopy classes of self-homeomorphisms) and let MCG(S, p) be the mapping class group of S punctured at p. The kernel of the natural map MCG(S, p) → MCG(S) is generated by homeomorphisms that drag the puncture p around a simple closed loop in Σ and are the identity off a neighborhood of the loop. This description gives an obvious identification of the kernel with Σ. Thus we have a short exact sequence

1 → Σ → MCG(S, p) → MCG(S) → 1.

Thurston shows that the action of any pseudo-Anosov element ϕ ∈ MCG(S) on the boundary of Teichmüller space has two fixed points. One says that a set of pseudo-Anosov mapping classes is independent if the fixed point sets of its elements are disjoint. It is not difficult to construct arbitrarily large independent sets of pseudo-Anosov mapping classes.

Theorem 9. [Mosher] Let S be a closed hyperbolic surface. Suppose that ϕ_{1}, …, ϕ_{m} ∈ MCG(S) is an independent set of pseudo-Anosov mapping classes of S. Let i_{1}, …, i_{m} be positive integers, and consider the subgroup H = ⟨ϕ_{1}^{i_{1}}, …, ϕ_{m}^{i_{m}}⟩ of MCG(S). Let G ≤ MCG(S, p) be the preimage of H. If i_{1}, …, i_{m} are sufficiently large, then the group H is free on the given generators and G is word hyperbolic. Therefore 1 → K → G → H → 1 is a short exact sequence of non-elementary hyperbolic groups.

Hyperbolic groups of the form Γ = F ⋊ F, with F free, have been constructed by Bestvina, Feighn and Handel in analogy with the above construction [3]. Brady and Miller [4] have shown that such groups arise as the fundamental groups of certain compact, negatively curved 2-complexes X. In this case Γ × Γ × F is the fundamental group of Z = X × X × Y, where Y is a compact metric graph. In the product metric Z is non-positively curved in the sense of A.D. Alexandrov, and we can therefore recover Theorem B of [1].

References

[1] G. Baumslag, M. R. Bridson, C. F. Miller III and H. Short, Fibre products, nonpositive curvature, and decision problems, Comment. Math. Helv. 75 (2000), 457–477.

[2] G. Baumslag and J. E. Roseblade, Subgroups of direct products of free groups, J. London Math. Soc. (2) 30 (1984), 44–52.

[3] M. Bestvina, M. Handel and M. Feighn, Laminations, trees, and irreducible automorphisms of free groups, Geom. Funct. Anal. 7 (1997), no. 2, 215–244.

[4] N. Brady and A. Miller, CAT(−1) structures for free-by-free groups, Geom. Dedicata, to appear.

[5] M. R. Bridson, Subgroups of semihyperbolic groups, L’Enseign. Math. Monograph, to appear.

[6] M. R. Bridson, The conjugacy and isomorphism problems for combable groups, preprint December 2001, http://www.maths.ox.ac.uk/∼bridson/papers/IsoC.

[7] M. R. Bridson and C. F. Miller III, Finiteness conditions for subdirect products of groups, in preparation.

[8] F. Grunewald, On some groups which cannot be finitely presented, J.London Math.Soc. (2) 17 (1978), 427–436.

[9] R. C. Lyndon and P. E. Schupp, “Combinatorial group theory”, Springer-Verlag, Berlin Heidelberg New York, 1977.

[10] C. F. Miller III, “On group-theoretic decision problems and their classification”, Annals of Mathematics Studies, No. 68, Princeton University Press [11] C. F. Miller III, Decision problems for groups: survey and reflections, in “Algo-

rithms and Classification in Combinatorial Group Theory” (eds. G Baumslag and C. F. Miller III), MSRI Publications No. 23, Springer-Verlag (1992), 1-59.

[12] L. Mosher, A hyperbolic-by-hyperbolic hyperbolic group, Proc. Amer. Math. Soc. 125 (1997), 3447–3455.

[13] E. S. Rapaport, Note on Nielsen transformations, Proc. Amer. Math. Soc., 10 (1959), 229–235.

[14] E. Rips, Subgroups of small cancellation groups, Bull. London Math. Soc., 14 (1982), 45–47.

Martin R. Bridson, Mathematics Department, 180 Queen’s Gate, London SW7 2BZ, U.K.

  E-mail address: m.bridson@ma.ic.ac.uk

Charles F. Miller III, Department of Mathematics and Statistics, University of Melbourne, Parkville 3052, Australia

  E-mail address: c.miller@ms.unimelb.edu.au