KLEINIAN GROUPS AND THE RANK PROBLEM

ILYA KAPOVICH AND RICHARD WEIDMANN

Abstract. We prove that the rank problem is decidable in the class of torsionfree word-hyperbolic Kleinian groups.

1. Introduction

If G is a finitely generated group, the rank of G, denoted rk(G), is the smallest cardinality of a subset S ⊆ G such that S generates G. The rank problem for a particular class of finitely generated groups asks if there is an algorithm that, given a finite presentation of a group G from the class, computes the rank of G.

The rank problem is one of the more enigmatic and little understood grouptheoretic decision problems. For example, the word problem, the conjugacy problem and even (in the torsion-free case) the isomorphism problem [25] are solvable for the class of word-hyperbolic groups. On the other hand, the rank problem is unsolvable for word-hyperbolic groups [5] because of a remarkable construction due to Rips [24]. Namely, Rips proves that, given an arbitrary finitely presented group Q, there exists a short exact sequence 1 → K → G → Q → 1 where G is torsion-free wordhyperbolic and where K is two-generated. Using the classical undecidability results, it is not hard to create a family of finitely presented groups where it is undecidable whether Q is trivial or not, and where every nontrivial Q has rank at least three. Then the group G based on Q via the Rips construction can be generated by two elements if and only if Q is trivial. Hence it is undecidable whether rk(G) ≤ 2 and therefore rk(G) is not computable.

A crucial feature of Rips’ construction is that, if both K and Q are infinite, then K is not quasiconvex in G. As it turns out, it is the presence of finitely-generated non-quasiconvex subgroups that is often responsible for undecidability of various algorithmic problems in the context of word-hyperbolic groups. Thus Kapovich and Weidmann [20] proved that the rank problem is solvable for torsion-free locally quasiconvex word-hyperbolic groups.

However, some of the most important and interesting examples of word-hyperbolic groups come from the world of Kleinian groups and they are not necessarily locally quasiconvex. For instance, let M be a closed hyperbolic 3-manifold fibering over a circle. In this case the fiber is a closed surface of negative Euler characteristic. Then G = π_{1}(M) splits as a semi-direct product G = H ⋉ ℤ, where H is the fundamental group of a fiber. Thus H is not quasiconvex in G.

The rank problem for 3-manifold groups is particularly interesting because of the connection between the rank and another important invariant, the Heegaard genus. Thus if M is a closed 3-manifold, G = π_{1}(M) and h(M) is the Heegaard genus of M then rk(G) ≤ h(M). Waldhausen conjectured that in fact rk(G) is always equal to h(M). Boileau and Zieschang [6] constructed a counter-example by producing a family of Seifert manifolds of Heegard genus three with 2-generated fundamental groups. To this day the Waldhausen conjecture remains open in the case of hyperbolic manifolds (see, for example, a paper of Dunfield and Thurston [9] where some experimental data is discussed).

2000 Mathematics Subject Classification. 20F67, 57M.

Key words and phrases. word-hyperbolic groups, Nielsen methods, 3-manifolds.

The first author acknowledges the support of the Max Planck Institute of Mathematics in Bonn.

The genus problem for 3-manifolds has been solved by Johannson [16] for sufficiently large 3-manifolds. Moreover he provides a procedure that produces all Heegaard splittings of a given genus. The case of small 3-manifolds has been claimed by Jaco and Rubinstein [15] and relies on the existence and constructability of so-called 1-efficient triangulations of irreducible atoroidal 3-manifolds.

Definition 1.1. Let M be the class of all torsion-free word-hyperbolic groups G such that G admits a properly discontinuous isometric action on ℍ^{3}.

Our main result is:

Theorem 1.2. There exists an algorithm which, given a finite presentation of a group G from the class M, finds the rank of G.

The main technical tool needed for the proof is a machinery developed by Kapovich and Weidmann in [19, 20] that provides a far-reaching generalization of Nielsen methods in the general context of groups acting by isometries on Gromovhyperbolic spaces. Another important ingredient is the ”tameness conjecture” for Kleinian groups that has been recently proved by Agol [1] and, independently, by Calegari and Gabai [7]. Together with the results of Canary [8] this yields a precise characterization of non-quasiconvex subgroups in the Kleinian groups context.

There are very few other classes of groups where the rank problem is known to be solvable. These include, in particular, the class of finitely generated nilpotent groups. For an arbitrary group G it is easy to see that rk(G) = rk(G/F(G)), where F(G) is the Frattini subgroup of G. If G is finitely generated nilpotent, then the Frattini subgroup F(G) contains the commutator [G, G]. This implies that rk(G) = rk(G_{ab}) where G_{ab} = G/[G, G] is the abelianization of G. The rank problem is also decidable for torsion-free word-hyperbolic locally quasiconvex groups (Kapovich-Weidmann [20]), for (sufficiently large) Fuchsian groups [27] and for one-relator groups [22]. The results of Arzhantseva and Ol’shanskii [4] show that, in a sense, the rank problem is ”generically” solvable for finitely presented groups. The work of Weidmann [27] (see also Kapovich-Weidmann [20]) shows that the presence of torsion often creates a substantial difficulty for solving the rank problem. Indeed, there are many natural and seemingly easy to understand classes of finitely generated groups where the rank problem remains open. These include: virtually abelian groups, virtually free groups, virtually nilpotent groups, 3-manifold groups as well as lattices in ℍ^{3}.

We should stress that Theorem 1.2 is an abstract computability result. The nature of the proof is such that it cannot provide any complexity bound on the running time of the algorithm. In particular, the proof involves many ”general enumeration” arguments, where several procedures are run in parallel, and at least one of them is guaranteed to eventually terminate, but where no complexity estimate is possible. We also stress that all the algorithms considered in this paper need to be uniform in all of their arguments, including the group presentation.

The proof of Proposition 3.6 about virtually cyclic groups is based on an argument explained to the first author by Derek Holt and we express special thanks to him. We are also grateful to Brian Bowditch, Misha Kapovich and w Walter Neumann for helpful discussions about 3-manifold groups.

2. Preliminary reductions and auxiliary facts

If G is a group with a finite generating set S, we will denote by X(G, S) the Cayley graph of G with respect to S.

We refer the reader to [2, 10, 11, 13, 14, 18] for the basic background information regarding word-hyperbolic groups, quasiconvexity, Gromov hyperbolic spaces and their boundaries. Recall, however, that a subgroup H of a word-hyperbolic group G is quasiconvex in G if for some (equivalently, for any) finite generating set S of G the subgroup H is a quasiconvex subset of X(G, S), that is, there is ϵ ≥ 0 such that for any h_{1}, h_{2} ∈ H any geodesic [h_{1}, h_{2}] in X(G, S) is contained in the ϵ-neighborhood of H.

Definition 2.1. Let M_{1} be the class of one-ended torsion-free groups G such that G admits a properly discontinuous convex-cocompact isometric action on ℍ^{3}.

It is clear that every group from M_{1} is word-hyperbolic so that M_{1} ⊆ M. Also, each of the classes M and M_{1} is closed under taking subgroups of finite index.

Moreover, it is a straightforward corollary of Thurston’s Hyperbolization Theorem (see, for example, Theorem 1.43 in [21]) that every one-ended group from M actually belongs to M_{1}:

Proposition 2.2. Let G be a group acting isometrically and properly discontinuously on ℍ^{3} and such that G is torsion-free word-hyperbolic and one-ended. Then G is isomorphic to the fundamental group of a compact hyperbolic 3-manifold with (possibly empty) convex boundary. That is, G belongs to M_{1}.

The above fact reduces the rank problem for M to the rank problem for M_{1} because of Grushko’s theorem, since by a result of Gerasimov [12] in the class of word-hyperbolic groups one can algorithmically compute a maximal free product decomposition of a group into freely indecomposable factors.

Definition 2.3. Two subgroups H, K ≤ G of a group G, are said to be commensuarable in G if H ∩ K has finite index in both H and K.

Let G be a group and H ≤ G be a subgroup. The commensurator Comm_{G}(H) of H in G is the set of all g ∈ G such that H and g^{−1}Hg are commensurable in G.

The commensurator Comm_{G}(H) is easily seen to be a subgroup of G containing H.

We need a precise description of non-quasiconvex finitely generated subgroups of groups from M_{1}.

Definition 2.4. Let G be a group from M_{1}.

We will say that a subgroup H ≤ G is a fiber group for G if H is the fundamental group of a closed hyperbolic surface, H is normal in G and the quotient G/H ≅ ℤ is infinite cyclic.

We will say that H ≤ G is a virtual fiber group for G if H is commensurable in G with a subgroup H_{1} where H_{1} is a fiber group for some subgroup G_{1} ≤ G of finite index in G.

It is obvious that virtual fiber groups are not quasiconvex, and, as it turns out, the converse is also true. The following statement is a corollary of the work of Canary [8] on geometrically infinite ends and of Marden’s ”tameness conjecture” for Kleinian groups recently proved by Agol [1] and Calegari-Gabai [7].

Theorem 2.5. Let G be a group from M_{1} and let H ≤ G be a finitely generated subgroup. Then H is quasiconvex in G if and only if H is not a virtual fiber group for G.

We will also be relying on the following statement summarizing some known general algorithmic results regarding hyperbolic groups.

Proposition 2.6. The following statements hold:

(1) There is an algorithm that, given a finite presentation G = ⟨S|R⟩ of a word-hyperbolic group G, computes an integer δ ≥ 0 such that the Cayley graph X = X(G, S) of G with respect to S is δ-hyperbolic. Moreover:

(a) The algorithm then computes a finite state automaton accepting the language L = L(G, S) of all short-lex geodesic words over S for G. The algorithm then decides if G is finite or infinite, and if G is finite, the algorithm computes the order of G and decides whether or not G is virtually cyclic.

(c) Given an arbitrary word w over S, the algorithm decides whether or not w = 1 in G, and computes the order of the element of G represented by w.

(2) There is an algorithm with the following property.

(a) Given a finite presentation G = ⟨S|R⟩ of a word-hyperbolic group G and a finite set Q of words over S generating a subgroup H = ⟨Q⟩ ≤ G, the algorithm computes an integer C ≥ 0 such that H is a C-quasiconvex subset of X(G, S) if H is quasiconvex in G, and runs forever if H is not quasiconvex in G.

(b) If H is quasiconvex in G, the algorithm also computes a finite state automaton L_{H} = L_{H}(G, S) accepting all the Short-Lex geodesic words over S representing elements of H.

(c) If H is quasiconvex in G, the algorithm decides whether H = G, that is to say, whether Q generates G.

(d) If H is quasiconvex in G, the algorithm computes the index of H in G.

(e) If H is quasiconvex in G, the algorithm computes a finite presentation of H on S.

(f) If Q_{1} is another set of words over S generating a quasiconvex subgroup H_{1} ≤ G (so that H_{1} ∩H is also quasiconvex), the algorithm computes a finite generating set for H_{1} ∩ H.

(g) If H ≤ G turns out to be quasiconvex, then, given an arbitrary word w over S, the algorithm decides whether or not w represents an element of H.

Proof. The algorithm detecting hyperbolicity of a finite presentation G = ⟨S|R⟩ and producing a hyperbolicity constant δ is due to Papasoglu [23]. A general result of [10] states that, given a finite group presentation G = ⟨S|R⟩ known to possess a Short-Lex automatic structure with respect to S, one can algorithmically find such a structure. Since a word-hyperbolic group is Short-Lex automatic with respect to every finite generating set, this algorithm will always terminate if G is wordhyperbolic.

The algorithm detecting quasiconvexity of a finitely generated subgroup is due to Kapovich [17]. To decide if a hyperbolic group G is virtually cyclic, we compute an automaton accepting the language L(G, S) off all Short-Lex geodesic words over S and check whether or not L(G, S) has linear growth.

All of the other statements, except (2d), follow from basic well-known facts about word-hyperbolic groups.

To show that (2d) holds, suppose that H is a quasiconvex subgroup of G. We need to compute the index of H in G. Recall that all cyclic subgroups in a wordhyperbolic group are quasiconvex.

For a quasiconvex subgroup H of a word-hyperbolic group G a result of Arzhantseva [3] implies that [G : H] = ∞ if and only if there is an element g ∈ G of infinite order such that ⟨g⟩ ∩ H = 1. Therefore we will run in parallel the following two procedures.

We will start the Todd-Coxeter coset enumeration process [26] for H in G. If [G : H] < ∞, the process will eventually terminate and its output can be used to compute the index of H in G.

In parallel, we will start enumerating all elements g of G (that is all words over S). For each of them we check if g has finite order or not. If g has infinite order, compute the automaton accepting L_{⟨g⟩} and then an automaton accepting L_{⟨g⟩∩H} = L_{⟨g⟩} ∩ L_{H}. We then check whether or not L_{⟨g⟩∩H} consists of only the empty word. If yes, we conclude that ⟨g⟩ ∩ H = 1 and hence [G : H] = ∞. If not, we go on to the next g.

Eventually one of these procedures will terminate and we will have computed the index of H in G. □

Proposition 2.6 will be often used implicitly throughout the paper.

Proposition 2.7. There exists an algorithm with the following properties. Given a finite presentation G = ⟨S|R⟩ of a torsion-free word-hyperbolic group G, the algorithm computes the number r and finite presentations for groups G_{1}, …, G_{k} (with k ≥ 0) such that

G ≅ G_{1} ∗ ⋯ ∗ G_{k} ∗ F_{r}

and such that each G_{i} is one-ended.

Proof. A result of Gerasimov [12] shows that there is an algorithm that, given a finite presentation of a torsion-free word-hyperbolic group G, decides whether the group has 1, 2 or infinitely many ends. If G is two-ended, then G is infinite cyclic. If G is one-ended, then it is freely indecomposable.

Suppose it turns out that G has infinitely many ends, that is, it is freely decomposable. We then start the following process. We enumerate all pairs A, B of tuples of nontrivial elements of G. For each such pair we run the ”detection of quasiconvexity” algorithm to check if the subgroups H = ⟨A⟩ ≤ G and K = ⟨B⟩ ≤ G are quasiconvex in G. For each pair (A, B) where both H and K are detected to be quasiconvex, we compute finite presentations for H = ⟨A|U⟩ and K = ⟨B|V ⟩ on A and B respectively. We also compute hyperbolicity constants for the Cayley graphs X(H, A) and X(K, B). We then start enumerating maps ϕ from S to G_{1} := H ∗K. There is a canonical homomorphism j : G_{1} → G such that j(h) = h and j(k) = k for every h ∈ H, k ∈ K.

For each of such maps ϕ we check if it extends to a homomorphism ϕ : G → G_{1} by checking if the defining relations of G go to the trivial element of G_{1}. If yes, then we check whether the compositions of ϕ ∘ j and j ∘ ϕ are the identity maps on G_{1} and G respectively. (This can be done by looking at the image of the generators S of G and A ∪ B of G_{1}.) If yes, then G = H ∗ K. Since we know that G is freely decomposable and free factors are quasiconvex in G, the above process will eventually terminate and produce a decomposition G = H ∗ K.

We then iterate the entire process (including determining the number of ends) by applying it to each of H, K separately. Eventually we will get a collection of infinite cyclic and one-ended groups that gives a required decomposition of G. □

3. Virtual fibers and virtually cyclic groups

If G is the fundamental group of a closed surface of negative Euler characteristic, then G admits a presentation

G = ⟨a_{1}, b_{1}, …, a_{k}, b_{k}|[a_{1}, b_{1}] … [a_{k}, b_{k}] = 1⟩ where k ≥ 2

if the surface is orientable and

G = ⟨a_{1}, a_{2}, …, a_{m}|a_{1}^{2}a_{2}^{2} … a_{m}^{2} = 1⟩ where m ≥ 3,

if the surface is non-orientable. The rank of G is equal to 2k in the first case and to m in the second case. We will refer to the above presentations as the standard surface group presentations.

Convention 3.1 (Computing a subgroup). From now on to compute a wordhyperbolic subgroup H of a word-hyperbolic group G = ⟨S|R⟩ shall mean to do all of the following:

(a) to find a finite generating set for H, a finite presentation for H on that generating set, a hyperbolicity constant for that presentation and the order of H;

(b) if H is known to be quasiconvex in G, to find a quasiconvexity constant for H in the Cayley graph of the ambient group G, the index of H in G and a finite state automaton acception the language L_{H}(G, S) of all ShortLex represntatives over S of elements of H;

(c) if H is known to have finite index in G, to find a right transveral for H in G;

(d) if H is known to be a surface group, to find a standard surface group presentation of H and to express the standard generators of H as words over S.

Lemma 3.2. Suppose P is a class of finitely presented group with uniformly solvable word problem. There exists a partial algorithm with the following property.

Let G be a group from P given by a finite presentation G = ⟨S|R⟩. Let A ⊂ G be a finite subset of G generating a subgroup H. Given a finite subset Q ⊆ G, the algorithm will eventually terminate if H has finite index in L := ⟨A, Q⟩ and it will run forever otherwise.

Suppose further that H turns out to have finite index in L, that H is given by a finite presentation on A and that the pair (H, G) comes from a class of subgroups of groups from P where the membership problem for H in G is solvable. Then the algorithm will also produce a finite presentation of L on A ∪ Q.

Proof. Denote B = A ∪ Q. Start enumerating all elements of H (that is all words in S) and, in parallel, start enumerating all finite prefix-closed sets W of words in B. For each such set W = {w_{1}, w_{2}, …, w_{n}}, using this enumeration of H and the algorithm solving the word problem in G, start checking if it is true that for every w_{i} and every b ∈ B^{±1} there is some w_{j} such that w_{i}bw_{j}^{−1} belongs to H. If yes, then, clearly, H has finite index in L. Conversely, it is also obvious that if H has finite index in L, the algorithm will eventually discover it and terminate.

Suppose now that H was given by a finite presentation, that G has solvable membership problem with respect to H and that L turns out to contain H as a subgroup of finite index. The above algorithm in fact produces a finite set W such that L = ∪_{w∈W} Hw. Using the algorithm solving the membership problem for H in G, we can decide when Hw = Hw′ and when Hw ≠ Hw′ for all w, w′ ∈ W. Using this information we can construct the Schreier coset graph for H in L with respect to the generating set B of L. Combined with a finite presentation of H this yields a finite presentation for L. □

Proposition 3.3. There is an algorithm with the following properties.

Suppose we are given a finite presentation G = ⟨S|R⟩ of a group from M_{1}. Then the algorithm decides whether the subgroup H = ⟨A⟩ ≤ G is quasiconvex in G or not. If H is quasiconvex, the algorithm also produces a quasiconvexity constant for H in X = X(G, S) and a finite presentation for H on S.

If H is not quasiconvex (and therefore is a virtual fiber group for G), the algorithm finds a standard surface group presentation H = ⟨Q|u = 1⟩ for H as well as explicit expressions of elements of Q in terms of elements of A and vise versa. Additionally, in this case the algorithm computes a subgroup G_{1} of finite index in G such that H is commensurable with a fiber H_{1} of G_{1}. The algorithm also computes a presentation of G_{1} as a cyclic extension of H_{1} and it computes a subgroup H′ ≤ H ∩ H_{1} such that H′ is of finite index in both H and H_{1}.

Proof. We will run the ”detection of quasiconvexity” algorithm from Proposition 2.6 in parallel with the following procedure.

Start enumerating subgroups of finite index in G and computing their presentations. For each such subgroup G_{1} ≤ G start checking if G_{1} splits as a surface-by-cyclic group G_{1} = H_{1} ⋉ ℤ, where H_{1} is a surface group. This can be done by a ”general enumeration” algorithm that lists all surface-by-cyclic presentations. For each such presentation W start enumerating maps from the generating set of W to G_{1} and from the generating set of G_{1} to W. For each pair of such maps, via enumeration of all the relations in W and G_{1}, start checking if they define group homomorphisms and if their compositions define identity maps of W and G_{1} respectively. [We refer to this as the ”general enumeration presentation comparison” argument].

If yes, then indeed G_{1} = H_{1} ⋉ ℤ. Note that there is an algorithm which, for each H_{1} above, solves the membership problem for H_{1} in G. Now for each such H_{1}, using the algorithm from Lemma 3.2, start enumerating subgroups H_{2} of G containing H_{1} as a subgroup of finite index and computing finite presentations for such subgroups H_{2}.

For each of H_{2} then start checking if A ⊆ H_{2} (that is H ≤ H_{2}). If yes, check if H = ⟨A⟩ ≤ H_{2} has finite index in the surface group H_{2}. If yes, then H is a virtual fiber group for G.

Since H is either quasiconvex or is a virtual fiber group in G, eventually we will either detect the quasiconvexity of G or will discover the fact that H is a virtual fiber for G. Moreover, in the latter case we will find an explicit surface subgroup H_{2} of G containing H as a subgroup of finite index. This information can be used to compute a standard surface group presentation of H, as required. □

Definition 3.4 (Relative rank). Let G be a finitely generated group and let Z ⊆ G be a subset. Define the relative rank rk_{Z}(G) of G with respect to Z as the smallest cardinality of a subset S ⊆ G such that G = ⟨S ∪ Z⟩.

The following statement is an elementary exercise.

Lemma 3.5. Let D = ⟨a, b|a^{2} = b^{2} = 1⟩ be an infinite dihedral group.

(1) A tuple (d_{1}, …, d_{k}) generates D if and only if k ≥ 2 and this tuple is Nielsen-equivalent to (a, b, 1, …, 1).

(2) Suppose s has order two in D and d_{1}, …, d_{k} ∈ ⟨ab⟩. Then (s, d_{1}, …, d_{k}) generates D if and only (d_{1}, …, d_{k}) generates ⟨ab⟩, that is, if and only if, (d_{1}, …, d_{k}) is Nielsen-equivalent to (ab, 1, …, 1) in D.

Proposition 3.6. There is an algorithm that, given a finite presentation of a virtually cyclic group G and a finite subset Z ⊆ G, finds rk_{Z}(G).

Proof. We first compute the order of G and the order of L := ⟨Z⟩. If G is finite or L is infinite (that is [G : L] < ∞), the problem easily reduces to the relative rank problem for finite groups.

Therefore we may assume that G is infinite and L is finite. Then, by a wellknown fact about virtually cyclic groups, G possesses a finite normal subgroup N such that \overline{G} := G/N is either infinite cyclic or infinite dihedral. By a general enumeration argument we can find such a subgroup N and determine which of these two possibilities occurs. Case 1. The group \overline{G} is infinite cyclic.

In this case clearly N is the set of all torsion elements of G and hence L ≤ N. Find an element x ∈ G such that \overline{G} = ⟨\overline{x}⟩.

By performing the Euclidean algorithm mod N we see that if a tuple (g_{1}, …, g_{k}, Z) generates G then the tuple (g_{1}, …, g_{k}) is Nielsen-equivalent to a tuple of the form (xn_{1}, n_{2}, …, n_{k}) where n_{i} ∈ N.

To decide if rk_{Z}(G) ≤ k we enumerate all tuples (xn_{1}, n_{2}, …, n_{k}, Z), where n_{i} ∈ N, and check if at least one of them generates G. Case 2. The group \overline{G} is infinite dihedral.

Then \overline{G} = ⟨\overline{s}, \overline{t}|\overline{s}^{2} = \overline{t}^{2} = 1⟩. We compute s, t ∈ G that map to \overline{s}, \overline{t} accordingly. The infinite cyclic subgroup ⟨\overline{st}⟩ has index two in \overline{G}. Let H ≤ G be the full preimage of ⟨\overline{st}⟩ in G, so that H = ⟨st, N⟩ has index two in G.

Note that \overline{L} is either trivial or cyclic of order two. Suppose first that \overline{L} is trivial, that is Z ⊆ N. Then by Lemma 3.5 if (g_{1}, …, g_{k}, Z) generates G then k ≥ 2 and (g_{1}, …, g_{k}) is Nielsen-equivalent to a tuple of the form (sn_{1}, tn_{2}, n_{3}, …, n_{k}) where n_{i} ∈ N. To decide if rk_{Z}(G) ≤ k we enumerate all tuples (sn_{1}, tn_{2}, n_{3} …, n_{k}, Z), where n_{i} ∈ N, and check if at least one of them generates G.

Suppose now that \overline{L} is cyclic of order two, that is there is some element z ∈ Z such that \overline{z} has order two. In this case L ∩ H ≤ N. Also, if z′ ∈ Z is different from z, then either z′ ∈ H (and hence z′ ∈ N) or \overline{z′} = \overline{z}.

Suppose (g_{1}, …, g_{k}, Z) generates G. After multiplying g_{i} by z^{−1} if necessary, we obtain a tuple (g′_{1}, …, g′_{k}, Z) generating G such that all g′_{i} ∈ H. Note that (\overline{g′_{1}}, …, \overline{g′_{k}}, \overline{z}) generates \overline{G} since for each z′ ∈ Z either \overline{z′} = \overline{z} or \overline{z′} = 1. Now Lemma 3.5 implies that (g′_{1}, …, g′_{k}) is Nielsen-equivalent to (stn_{1}, n_{2}, …, n_{k}) where n_{i} ∈ N.

To decide if rk_{Z}(G) ≤ k we enumerate all tuples (stn_{1}, n_{2}, …, n_{k}, Z) where n_{i} ∈ N, and check if at least one of them generates G. □

Lemma 3.7. Let G ∈ M_{1}, let G_{1} be a subgroup of finite index in G and let H ≤ G_{1} be a fiber subgroup for G_{1}. Thus G_{1} = H ⋉ ⟨t⟩. Let P ≤ H be a subgroup of finite index in H that is normal in G_{1}.

Then the following hold:

(1) For each subgroup K of G such that P ≤ K, either K has finite index in G or K contains P as a subgroup of finite index.

(2) The set of subgroups conjugate to P is G is finite.

(3) For each g ∈ G either P has finite index in L := ⟨P, g^{−1}P g⟩ (in which case g ∈ Comm_{G}(P)) or L has finite index in G.

(4) Either there is g ∈ G − G_{1} such that ⟨P, g^{−1}P g⟩ has finite index in G or for every g ∈ G the subgroup P has finite index in ⟨P, g^{−1}P g⟩ (in which case G = Comm_{G}(P)).

Proof. Let g_{1} = 1, …, g_{n} be a right transversal for G_{1} in G. Then every element of G is uniquely expressible in the form g = ht^{j}g_{i} where 1 ≤ i ≤ n, j ∈ ℤ and h ∈ H. Recall that P is normal in G_{1}. Hence g^{−1}P g = g_{i}^{−1}t^{−j}h^{−1}P ht^{j}g_{i} = g_{i}^{−1}P g_{i}. This shows that the set of conjugates of P in G is finite and part (2) of the lemma is established.

Let K ≤ G be a subgroup such that P ≤ K and suppose that P has infinite index in K. Let K_{1} = K ∩ G_{1}. Then P ≤ H ≤ K_{1} ≤ K and K_{1} has finite index in K. Therefore P has infinite index in K_{1}. Since K_{1} ≤ G_{1}, every element of K_{1} can be written in the form t^{j}h where j ∈ ℤ and h ∈ H. Assume first that there is some element a ∈ K_{1} of the form a = t^{j}h, where j ≠ 0. Then it is easy to see that ⟨P, a⟩ has finite index in G_{1} and hence in G, as required.

Suppose now that there is no element a ∈ K_{1} of the form a = t^{j}h with j ≠ 0. This implies that P ≤ K_{1} ≤ H, contradicting our assumption that [K_{1} : P] = ∞. This verifies part (1) of the lemma.

Part (3) follows immediately from part (1). In turn, part (3) immediately implies part (4). □

Lemma 3.8. There is an algorithm with the following properties. Suppose we are given a group G ∈ M_{1}, a subgroup of finite index G_{1} ≤ G and a fiber group H of G_{1} so that G_{1} = H ⋉ ⟨t⟩. Suppose we are also given a subgroup P ≤ H of finite index in H that is normal in G_{1}.

The algorithm decides if there is g ∈ G − G_{1} such that ⟨P, g^{−1}P g⟩ has finite index in G or if for every g ∈ G the subgroup P has finite index in ⟨P, g^{−1}P g⟩.

In the former case the algorithm computes all the (finitely many) subgroups ⟨P, g^{−1}P g⟩, where g ∈ G, that have finite index in G. It then computes their intersection and finds a normal subgroup N ≤ G of finite index in G that is contained in that intersection and such that N ≤ G_{1}.

In the latter case the algorithm computes the intersection N_{1} of all conjugates of P in G. Thus N_{1} is a normal subgroup of G that has finite index in P and in H.

Proof. We first compute a right transversal g_{1} = 1, g_{2}, … g_{n} for G_{1} in G. We have already seen in the proof of Lemma 3.7 that each conjugate of P in G has the form g_{i}^{−1}P g_{i}. Put L_{i} := ⟨P, g_{i}^{−1}P g_{i}⟩ ≤ G. For each i either P has finite index in L_{i} or L_{i} has finite index in G. For each i we run the algorithm provided by Lemma 3.2 in parallel with the Todd-Coxeter coset enumeration algorithm for L_{i} to decide which of these alternatives holds.

In particular, we find all of the L_{i} (if any) that have finite index in G. If there is at least one such L_{i}, we find their intersection L, and the intersection L′ = L ∩ G_{1}. Then L′ still has finite index in G. We then find the intersection of all conjugates of L′ in G and denote it by N. Clearly N is normal of finite index in G, also N is a subgroup of G_{1} and N is contained in all those L_{i} that have finite index in G, as required.

Suppose now that all L_{i} turn out to contain P as a subgroup of finite index. Thus each L_{i} is a virtual fiber for G. For each of L_{i} we compute its finite presentation. Recall that all conjugates of P in G are of the form P_{i} := g_{i}^{−1}P g_{i}. For each i, operating inside L_{i} we compute a generating set for P′_{i} := P_{i} ∩ P and rewrite it as the set of words in the generators of P. This is possible by Proposition 2.6 since L_{i} is a surface group and thus is locally quasiconvex. Finally, operating inside the surface group H, we compute the subgroup

N_{1} := ∩_{i=1}^{n}P′_{i} = ∩_{i=1}^{n}P′_{i} = ∩_{g∈G}g^{−1}P g.

Then N_{1} is a subgroup of finite index in H and N_{1} is normal in G, as required. □

Proposition 3.9. There is an algorithm with the following properties. Suppose we are given a group G ∈ M_{1}, a subgroup of finite index G_{1} ≤ G, a fiber group H of G_{1} so that G_{1} = H ⋉ ⟨t⟩ and a virtual fiber group H_{1} commensurable with H.

The algorithm computes the relative rank rk_{H_{1}}(G) of G with respect to H_{1}.

Proof. First we compute a subgroup P ≤ H of finite index in H such that P ≤ H_{1} and such that P is normal in G_{1}. Such a subgroup obviously exists since H ∩H_{1} has finite index in H and hence contains a subgroup P′ such that P′ is a characteristic subgroup of finite index in H. Since conjugation by t induces an automorphism of H, such a subgroup P′ will be normal in G_{1}.

We can algorithmically find some subgroup P with the required properties as follows. First, compute the automorphism ϕ of H induced by conjugation by t. That is, for each generator x of H express t^{−1}xt as a word in the generators of H. Then start enumerating subgroups of finite index P in H. For each such P start checking if P is normal in H, if P is contained in H_{1} and if ϕ(P) = P. If yes, then P is as required, and we terminate the process. As we observed above, this algorithm will necessarily terminate since some P with required properties does exist.

We then use the algorithm from Lemma 3.8 and decide if there is g ∈ G − G_{1} such that ⟨P, g^{−1}P g⟩ has finite index in G or if for every g ∈ G the subgroup P has finite index in ⟨P, g^{−1}P g⟩.

Suppose first that the former occurs. Then we compute the normal subgroup N of G of finite index in G defined in Lemma 3.8. Denote \overline{G} = G/N.

Claim For any set B ⊆ G we have ⟨H_{1}, B⟩ = G if and only if ⟨\overline{H}_{1}, \overline{B}⟩ = \overline{G}. Indeed, recall that N ≤ G_{1} is normal of finite index in G. Since P is normal in G_{1}, for every g ∈ G and every n ∈ N we have g^{−1}n^{−1}P ng = g^{−1}P g and hence ⟨P, g^{−1}P g⟩ = ⟨P, g^{−1}n^{−1}P ng⟩.

Suppose ⟨\overline{H}_{1}, \overline{B}⟩ = \overline{G}. Choose g ∈ G such that ⟨P, g^{−1}P g⟩ has finite index in G. Then there is n ∈ N such that gn ∈ ⟨H_{1}, B⟩. Hence ⟨P, g^{−1}P g⟩ = ⟨P, g^{−1}n^{−1}P ng⟩ has finite index in G and therefore contains N. But both P and gn are contained in ⟨H_{1}, B⟩. Hence N ≤ ⟨H_{1}, B⟩. Since ⟨\overline{H}_{1}, \overline{B}⟩ = \overline{G}, this implies that ⟨H_{1}, B⟩ = G. This verifies the Claim.

We now compute the image \overline{H}_{1} of H in the finite group \overline{G} and solve the relative rank problem for \overline{G} with respect to \overline{H}_{1}. By the Claim rk_{H_{1}}(G) = rk_{\overline{H}_{1}}(\overline{G}).

Suppose now that the second alternative of Lemma 3.8 occurs. Then, as in Lemma 3.8 we compute the intersection N_{1} of all conjugates of P in G. This is a normal subgroup of G which has finite index in H.

Then the group Ĝ := G/N_{1} is virtually cyclic. Since N_{1} ≤ H_{1}, it is clear that rk_{H_{1}}(G) = rkĤ_{1}(Ĝ). We use then use the algorithm provided by Proposition 3.6 to compute rkĤ_{1}(Ĝ). □

4. Main technical tool

In this section we will state the main technical tool needed to prove our main result. This tool was obtained by Kapovich and Weidmann in [20].

If n ≥ 0 is an integer, for an n-tuple T = (g_{1}, …, g_{n}) of elements of a group G denote n = l(T) and call n the length of T.

Let us recall the notion of Nielsen equivalence:

Definition 4.1 (Nielsen equivalence). Let G be a group and let T = (g_{1}, …, g_{n}) ∈ G^{n} be an n-tuple of elements of G. The following moves are called elementary Nielsen moves on T:

(N1) For some i, 1 ≤ i ≤ n replace g_{i} by g_{i}^{−1} in T.

(N2) For some i ≠ j, 1 ≤ i, j ≤ n replace g_{i} by g_{i}g_{j} in T.

(N3) For some i ≠ j, 1 ≤ i, j ≤ n interchange g_{i} and g_{j} in T.

We say that T = (g_{1}, …, g_{n}) ∈ G^{n} and T′ = (f_{1}, …, f_{n}) ∈ G^{n} are Nielsenequivalent in G, if there is a chain of elementary Nielsen moves which transforms T to T′.

Definition 4.2 (Partitioned tuple). Let G be a group. A partitioned tuple for G is a tuple M = (Y_{1}, …, Y_{s}; T) where s ≥ 0, and where

(a) each of Y_{i}, T is a tuple of elements of G;

(b) either s > 0 or l(T) > 0;

(c) we have ⟨Y_{i}⟩ ≠ 1 for each i > 0.

We call l(Y_{1})+⋯+l(Y_{s})+l(T) the length of M and denote it by l(M). We call the l(M)-tuple of elements of G obtained by concatenating the tuples Y_{1}, …, Y_{s}, T the underlying tuple of M.

Thus (; T) (where l(T) > 0) and (Y_{1}; ) (where ⟨Y_{1}⟩ ≠ 1) are examples of partitioned tuples.

Definition 4.3 (Elementary Moves). Let M = (Y_{1}, …, Y_{s}; T) be a partitioned tuple for a group G. Let T = (t_{1}, …, t_{m}). The elementary moves on M are the following:

(1) Replace some Y_{i} by g^{−1}Y_{i}g where g ∈ ⟨(∪_{j≠i}Y_{j}) ∪ T ⟩.

(2) Replace some entry t_{i} in T by ut_{i}u′ where
u, u′ ∈ ⟨(∪_{j=1}^{s}Y_{j}) ∪ {t_{1}, …, t_{i−1}, t_{i+1}, …, t_{m}}⟩.

Definition 4.4 (Equivalence of partitioned tuples). Two partitioned tuples M = (Y_{1}, …, Y_{s}; T), M′ = (Y′_{1}, …, Y′_{s}; T′) for a group G are equivalent if there exists a chain of elementary moves taking M to M′.

It is easy to see that the above definition gives an equivalence relation on the set of partitioned tuples. Moreover, if M and M′ are equivalent partitioned tuples then l(M) = l(M′) and the underlying tuples of M, M′ are Nielsen-equivalent in G.

Definition 4.5 (Complexity of a partitioned tuple). We define the complexity of a partitioned tuple M = (Y_{1}, …, Y_{n}; T) with T = (t_{1}, …, t_{m}) to be the pair (m, n) ∈ ℕ^{2}. We define an order on ℕ^{2} by setting (m, n) ≤ (m′, n′) if m < m or if m = m′ and n ≤ n′. This clearly gives a well-ordering on ℕ^{2}.

Notation 4.6 (Invariant sets). Let G be a nonelementary torsion-free word-hyperbolic group G with a finite generating set S. Let X be the Cayley graph of G with respect to S. Let δ ≥ 1 be an integer such that X is δ-hyperbolic.

Let U ≤ G be a nontrivial subgroup (which is therefore infinite). Let ΛU ⊆ ∂X be the limit set of U in X.

Let E(U) be the set of all x ∈ X such that for some g ∈ U, g ≠ 1 we have d(x, gx) ≤ 100δ. Let Z(U) be the weak convex hull of E(U) ∪ ΛU, that is Z(U) is the union of all geodesics in X with both endpoints in E(U) ∪ ΛU. Finally, let X(U) denote the closure of Z(U) in X.

Note that the definitions of the above U-invariant subsets of X depend on the choice of δ.

The following is a corollary of Theorem 2.4 of [20]. This is the main technical tool required for our proofs in this paper.

Theorem 4.7. For every integer k ≥ 1 there exists a computable constant L = L(k) ≥ 0 with the following property.

Let G be a nonelementary torsion-free word-hyperbolic group with a finite generating set S. Let X be the Cayley graph of G with respect to S. Let δ ≥ 1 be an integer such that X is δ-hyperbolic.

Let M = (Y_{1}, …, Y_{s}; T) by a partitioned tuple for G with l(M) = k. Let U be the subgroup generated by the underlying tuple of M. Then either

U = ⟨Y_{1}⟩ ∗ … ⟨Y_{s}⟩ ∗ F (T)

or M is equivalent to a partitioned tuple M′ = (Y′_{1}, …, Y′_{s}; T′) such that, denoting U′_{i} = ⟨Y′_{i}⟩, one of the following occurs:

(1) There are some i ≠ j such that d(X(U′_{i}), X(U′_{j})) ≤ δL(k).

(2) There is some i, 1 ≤ i ≤ s and some element g of T′ such that

d(X(U′_{i}), gX(U′_{i})) ≤ δL(k).

(3) There is some element g of T′ such that g is conjugate in G to an element of length at most δL(k).

5. Generator Transfer Process

If G is a group with a finite generating set S and if g ∈ G, we will denote by |g|_{S} the S-geodesic length of g. Thus |g|_{S} = d(g, 1) in X(G, S). All the constants in this section are assumed to be monotone non-decreasing in each of their integer arguments.

We recall here some results of Kapovich-Weidmann [20].

Lemma 5.1. There exists a computable constant c_{1} = c_{1}(G, S, δ, ϵ) > 0 such that the following holds:

Suppose G = ⟨S|R⟩ is a finite presentation of a torsion-free word-hyperbolic group G and that δ ≥ 0 is an integer such that the Cayley graph X(G, S) is δhyperbolic. Let ϵ ≥ 0 be an integer and let U ≤ G be an infinite subgroup such that U is ϵ-quasiconvex in X = X(G, S). Then U and X(U) are c_{1}-Hausdorff close (where X(U) is defined relative δ).

Lemma 5.1 follows from Lemma 10.3 and Remark 10.9 of [20].

Lemma 5.2. For any integers K ≥ 0 and n ≥ 1 there is a computable constant c_{2} = c_{2}(G, S, δ, n, K) with the following property. Suppose G = ⟨S|R⟩ is a finite presentation of a group G from class M_{1}. Suppose δ ≥ 1 is an integer such that the Cayley graph X = X(G, S) is δ-hyperbolic. Suppose U ≤ G is a non-trivial quasiconvex subgroup U ≤ G generated by a set Y with at most n elements such that Y is contained in the K-ball around 1 in Γ(G, S). Then the sets U and X(U) are c_{2}-Hausdorff close (where X(U) is defined relative to δ).

Proof. Let E be the maximum of quasiconvexity constants of infinite quasiconvex subgroups generated by subsets with at most n-elements from the K-ball around 1 in Γ(G, S). Put c_{2} := c_{1}(G, S, δ, E). Then c_{2} clearly satisfies the requirements of the lemma. In order to see that c_{2} is computable it suffices to see that E is computable. For each n-tuple Y of words of length at most K over S apply the algorithm of Proposition 3.3 to decide whether or not H = ⟨Y ⟩ is quasiconvex in G, and if yes, to compute a quasiconvexity constant for H. Then E is the maximum of all the quasiconvexity constants obtained in this way and hence E is computable. □

Proposition 5.3. There exist a computable constant c = c(G, S, δ, n_{1}, n_{2}, K) with the following properties.

Suppose G = ⟨S|R⟩ is a finite presentation of a group G from class M_{1}. Suppose δ ≥ 1 is an integer such that the Cayley graph X = X(G, S) is δ-hyperbolic. Suppose that K, n_{1}, n_{2} ≥ 1 are integers.

Suppose U_{1} = ⟨Y_{1}⟩ and U_{2} = ⟨gY_{2}g^{−1}⟩ are two quasiconvex subgroups of G, where g ∈ G, Y_{1} = (y_{1}, …, y_{n_{1}}) ∈ G^{n_{1}}, Y_{2} = (y′_{1}, …, y′_{n_{2}}) ∈ G^{n_{2}}, |y_{i}|_{S} ≤ K for 1 ≤ i ≤ n_{1} and |y′_{i}|_{S} ≤ K for 1 ≤ i ≤ n_{2}. Suppose also that d(X(U_{1}), X(U_{2})) ≤ K.

Then the (n_{1} + n_{2})-tuple (y_{1}, …, y_{n_{1}}, gy′_{1}g^{−1}, …, gy′_{n_{2}}g^{−1}) is Nielsen-equivalent to a tuple conjugate in G to (y_{1}, …, y_{n_{1}+n_{2}}) where |y_{i}|_{S} ≤ c for 1 ≤ i ≤ n_{1} + n_{2}.

Proof. It is proved in [20] that c = 4c_{2}(G, S, δ, n, K)+3K satisfies the requirements of the proposition. The computability of c_{4} now follows from the computability of c_{2} established in Lemma 5.2. □

Proposition 5.4. There exist a computable constant c′ = c′(G, S, δ, n_{1}, n_{2}, K) with the following properties.

Suppose G = ⟨S|R⟩ is a finite presentation of a group G from class M_{1}. Suppose δ ≥ 1 is an integer such that the Cayley graph X = X(G, S) is δ-hyperbolic. Suppose that K, n ≥ 1 are integers.

Let U = ⟨Y ⟩ where Y = (y_{1}, …, y_{n}) ∈ G^{n} and |y_{i}| ≤ K for 1 ≤ i ≤ n. Suppose that U is quasiconvex in G and that d(X(U), gX(U)) ≤ K.

Then the tuple (y_{1}, …, y_{n}, g) is Nielsen-equivalent to a tuple (y_{1}, …, y_{n}, y_{n+1}) such that |y_{i}|_{S} ≤ c′ for 1 ≤ i ≤ n + 1.

Proof. It is proved in [20] that c′ = 2c_{2}(G, S, δ, n, K) + 3K satisfies the requirements of the proposition. By Lemma 5.2 c_{2} is computable and therefore c′ is also computable. □

Theorem 5.5. There exists a computable integer constant C = C(G, S, δ, k) > 0 with the following properties.

Suppose G = ⟨S|R⟩ be a finite presentation of a group G from the class M_{1}. Suppose δ ≥ 1 is an integer such that the Cayley graph X = X(G, S) of G with respect to S is δ-hyperbolic. Suppose k ≥ 1 is an integer.

Then for any k-tuple T = (g_{1}, g_{2}, …, g_{k}) generating G one of the following holds:

(1) There exists a k-tuple T′ = (g′_{1}, g′_{2}, …, g′_{k}) Nielsen-equivalent to T such that |g′_{i}|_{S} ≤ C for i = 1, …, k.

(2) There exists a k-tuple T′ = (g′_{1}, g′_{2}, …, g′_{k}) Nielsen-equivalent to T such that for some j < k the set (g′_{1}, …, g′_{j}) generates a virtual fiber of G and |g′_{i}|_{S} ≤ C for i = 1, …, j.

Proof. Let G = ⟨S|R⟩ be a finite presentation of a group from M_{1} and let δ ≥ 1 be an integer such that X = X(G, S) is δ-hyperbolic.

We will prove the result by induction on k. For k = 1 there is nothing to prove, since G is not cyclic. Suppose now that k ≥ 2 and that the statement has been proved for all 1 ≤ k′ < k.

We define the constants R(i) = R(k, i) for i = 1, …, k inductively as follows. Put R(1) := δL(k), where L(k) is the constant provided by Theorem 4.7. For 1 < i ≤ k put

R(i) = max (R(i − 1), c′ (G, S, δ, i − 1, R(i − 1)) , max_{p,j≥1_{p+j=i}} c (G, S, δ, p, j, R(i − 1))) .

Note that the constants R(k, i) are algorithmically computable.

Let M = (Y_{1}, …, Y_{s}; H) be a partitioned tuple of length k. Let n_{i} be the length of Y_{i}. We will say that M is good if one of the following holds:

(a) each Y_{j} generates a nontrivial quasiconvex subgroup of G and each Y_{j} is conjugate in G to a tuple contained in the ball of radius R(n_{i}) in X.

(b) there is some Y_{j} which generates a virtual fiber of G and such that Y_{i} is conjugate to a tuple contained in the ball of radius R(n_{i}) in X.

Put

C(G, S, δ, k) := max{C(G, S, δ, k − 1), R(k)}.

Suppose now that G is generated by a k-tuple T_{0} = (g_{1}, …, g_{k}). If T_{0} is Nielsenequivalent in G to some tuple containing 1 ∈ G, the statement follows from the inductive hypothesis. Therefore we will assume that every k-tuple Nielsen-equivalent to T_{0} consists of nontrivial elements of G.

Consider a partitioned tuple M_{0} := (; T_{0}). Note that M_{0} is good and that the underlying tuple of M_{0} is T_{0}. Among all the good partitioned tuples with the underlying tuple Nielsen-equivalent to T_{0} choose a partitioned tuple M of minimal complexity.

Claim. We claim that either M has the form M = (Y_{1}; ) or part (b) of the definition of a good partitioned tuple applies to M.

Indeed, suppose not. Then M = (Y_{1}, …, Y_{s}; T) where either s ≥ 2 or l(T) > 0 and where each Y_{j} generates a quasiconvex subgroup of G. Denote n_{i} = l(Y_{i}) and n = l(T). Recall that the underlying tuple of M is Nielsen-equivalent to T_{0} and hence n_{1} + ⋯ + n_{s} + n = k.

Since M generates a freely indecomposable group G, there exists a partitioned tuple M′ = (Y′_{1}, … Y′_{s}; T′) equivalent to M and such that one of the three cases of Theorem 4.7 applies to M′. Recall that by definition of equivalence of partitioned tuples each Y′_{i} is conjugate to Y_{i} and the underlying tuple of M′ is Nielsen-equivalent to the underlying tuple of M. In particular M′ is good, since M was good. Put U_{i} = ⟨Y′_{i}⟩.

Suppose that Case (1) of Theorem 4.7 applies to M′. Without loss of generality we may assume that d(X(U_{1}), X(U_{2})) ≤ L(k)δ. Recall that since M and M′ are good, each Y′_{i} is conjugate to a tuple contained in the ball of radius R(n_{i}) in X. Then by Proposition 5.3 the tuple (Y′_{1}, Y′_{2}) is Nielsen-equivalent to an (n_{1} + n_{2})- tuple Y′′_{1} such that Y′′_{1} is conjugate to a set contained in the ball of radius c = c(G, S, δ, n_{1}, n_{2}, max{L(k)δ, R(n_{1}), R(n_{2})}) in X. Recall that by definition of R(i) we have R(1) = L(k)δ ≤ R(n_{1}), R(n_{2}) ≤ R(n_{1} +n_{2} −1). Therefore Y′′_{1} is conjugate to a set contained in the ball of radius R(n_{1} + n_{2}). Consider now a partitioned tuple M′′ := (Y′′_{1}, Y′_{3}, …, Y′_{s}; T′). Then M′′ is good and the underlying tuple of M′′ is Nielsen-equivalent to T_{0}. On the other hand the complexity of M′′ is smaller than the complexity of M, which contradicts the minimal choice of M.

Suppose now that Case (2) of Theorem 4.7 applies to M′. Without loss of generality we may assume that for some entry g of T′ we have d(X(U_{1}), gX(U_{1})) ≤ L(k)δ. Then by Proposition 5.4 the (n_{1} + 1)-tuple (Y′_{1}, h) is Nielsen-equivalent to an (n_{1} + 1)-tuple Y′′_{1} which is conjugate to a subset contained in the ball of radius c′ = c′(G, S, δ, n_{1}, max{R(n_{1}), L(k)δ}) ≤ R(n_{1} + 1) in X. Put M′′ := (Y′′_{1}, Y′_{2}, …, Y′_{s}; T′′) where T′′ is obtained from T′ by deleting the entry g. Then M′′ is good and the underlying tuple of M′′ is Nielsen-equivalent to T_{0}. On the other hand the complexity of M′′ is smaller than that of M, which contradicts the minimal choice of M.

Suppose that Case (3) of Theorem 4.7 applies to M′. Then T′ contains an element g that is conjugate in G to an element of length at most L(k)δ. Put M′′ := (Y′_{1}, … Y′_{s}, Y_{s+1}; T′′) where Y_{s+1} = (g) and where T′′ is obtained from T′ by deleting the entry g. Then M′′ is good and the underlying tuples of M′ and M′′ coincide. In particular, the underlying tuple of M′′ is Nielsen-equivalent to T_{0}. On the other hand the complexity of M′′ is smaller than that of M, which contradicts the minimal choice of M.

Thus we have verified the Claim. This immediately implies the statement of the theorem. □

Theorem 5.6. There is an algorithm that, given a finite presentation G = ⟨S|R⟩ of a group G from the class M_{1}, computes the rank of G.

Proof. Let G = ⟨S|R⟩ be a finite presentation of G ∈ M_{1}. Denote X = X(G, S), the Cayley graph of G with respect to S. First we compute an integer δ ≥ 1 such that X is δ-hyperbolic. Let k = #S. We next compute the constant C = C(G, S, δ, k) > 0 provided by Theorem 5.5. We then enumerate all p-tuples T of words over S with 1 ≤ p ≤ k, where every word has length at most C. Let T be the set of all such tuples.

For each tuple T ∈ T we use Proposition 3.3 to decide if H_{T} := ⟨T ⟩ is quasiconvex in G or if H_{T} is a virtual fiber of G. If H_{T} is a virtual fiber of G we compute the rank of H_{T} and, using Proposition 3.9, the relative rank rk_{H_{T}} (G) of G with respect to H_{T}. If H_{T} is quasiconvex in G, we check whether or not H_{T} = G, that is ⟨T ⟩ = G.

Let p ≤ k. Theorem 5.5 implies that rk(G) ≤ p if and only if either there exists a p-tuple T ∈ T such that G = ⟨T ⟩ or there exists a tuple T ∈ T generating a virtual fiber H_{T} such that rk(H_{T}) + rk_{H_{T}} (G) ≤ p.

Therefore for each 0 ≤ p ≤ k we can decide whether or not rk(G) ≤ p. The smallest 0 ≤ p ≤ k such that rk(G) ≤ p is the rank of G. □

Theorem 5.7. There is an algorithm that, given a finite presentation G = ⟨S|R⟩ of a group G from the class M, computes the rank of G.

Proof. We first apply the algorithm from Proposition 2.7 and compute a decomposition

G = G_{1} ∗ ⋯ ∗ G_{s} ∗ F_{r}

where each G_{i} is one-ended and is given to us by an explicit finite presentation.

By Proposition 2.2 each G_{i} ∈ M_{1}. We use the algorithm from Theorem 5.6 and compute rk(G_{i}) for each i.

Then by Grushko’s Theorem

rk(G) = rk(G_{1}) + ⋯ + rk(G_{s}) + r.
□

References

[1] I. Agol, Tameness of hyperbolic 3-manifolds, preprint, 2004, http://front.math.ucdavis.edu/math.GT/0405568.

[2] J. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro and H. Short. Notes on hyperbolic groups. in “Group

[3] G. Arzhantseva, On quasiconvex subgroups of word hyperbolic groups. Geom. Dedicata 87 (2001), no. 1-3, 191–208

[4] G. Arzhantseva, and A. Yu. Ol’shanskii, Generality of the class of groups in which subgroups with a lesser number of generators are free. Mat. Zametki 59 (1996), no. 4, 489–496, 638

[5] G. Baumslag, C. F. Miller, III; H. Short, Unsolvable problems about small cancellation and word hyperbolic groups. Bull. London Math. Soc. 26 (1994), no. 1, 97–101

[6] M. Boileau and H. Zieschang, Heegaard genus of closed orientable Seifert 3-manifolds. Invent. Math. 76 (1984), no. 3, 455–468

[7] D. Calegari and D. Gabai, Shrinkwrapping and the taming of hyperbolic 3-manifolds, preprint, 2004, http://front.math.ucdavis.edu/math.GT/0407161.

[8] R. Canary, A covering theorem for hyperbolic 3-manifolds and its applications, Topology 35 (1996), no. 3, 751–778

[9] N. Dunfield and W. P. Thurston, The virtual Haken conjecture: Experiments and examples, Geom. and Topol. 7 (2003), 399–441

[10] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992

[11] É. Ghys and P. de la Harpe (eds.), Sur les groupes hyperboliques d’après Mikhael Gromov, Birkhäuser Boston Inc., Boston, MA, 1990, Papers from the Swiss Seminar on Hyperbolic Groups held in Bern, 1988.

[12] V. Gerasimov, Detecting connectedness of the boundary of a hyperbolic group, 1999, Preprint

[13] S. M. Gersten, and H. Short, Rational subgroups of biautomatic groups. Ann. of Math. (2) 134 (1991), no. 1, 125–158.

[14] M. Gromov, Hyperbolic groups, Essays in group theory, editor S.M. Gersten, Springer-Verlag, MSRI Publications 8, 1985, 75–263.

[15] W. Jaco and H. Rubinstein, 0-efficient triangulations of 3-manifolds to appear in J. Amerc. Math. Soc.

[16] K. Johannson, Topology and combinatorics of 3-manifolds, Lecture Notes in Mathematics 1599, Springer, 1995.

[17] I. Kapovich, Detecting quasiconvexity: algorithmic aspects, in “Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994)”, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25, Amer. Math. Soc., Providence, RI, 1996, 91–99

[18] I. Kapovich and H. Short, Greenberg’s theorem for quasiconvex subgroups of word hyperbolic groups, Canad. J. Math. 48 (1996), no. 6, 1224–1244.

[19] I. Kapovich and R. Weidmann, Nielsen Methods for groups acting on hyperbolic spaces, Geometriae Dedicata 98 (2003), no. 1, 95–121

[20] I. Kapovich and R. Weidmann, Freely indecomposable groups acting on hyperbolic spaces, Internat. J. Algebra Comput. 14 (2004), no. 2, 115–171.

[21] M. Kapovich, Hyperbolic manifolds and discrete groups, Progress in Mathematics, 183, Birkhäuser, Boston, 2001

[22] A. Karrass, W. Magnus, D. Solitar, Combinatorial Group Theory: Presentations of groups in terms of generators and relations. Interscience Publishers [John Wiley and Sons, Inc.], New York-London-Sydney 1966

[23] P. Papasoglu, An algorithm detecting hyperbolicity Baumslag, Gilbert (ed.) et al., Geometric and computational perspectives on infinite groups. Proceedings of a joint DI-MACS/Geometry Center workshop, 1994, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 25, 193-200 (1996).

[24] E. Rips, Subgroups of small cancellation groups, Bull. Lond. Math. Soc. 14, 45-47, 1982.

[25] Z. Sela, The isomorphism problem for hyperbolic groups. I. Ann. of Math. (2) 141 (1995), no. 2, 217–283

[26] C. Sims, Computation with finitely presented groups. Encyclopedia of Mathematics and its Applications, 48. Cambridge University Press, Cambridge, 1994.

[27] R. Weidmann, The rank problem for Fuchsian groups I: The sufficiently large case., preprint

Dept. of Mathematics, University of Illinois at Urbana-Champaign, 1409 West Green Street, Urbana, IL 61801, USA

E-mail address: kapovich@math.uiuc.edu

Fachbereich Mathematik, Johann Wolfgang Goethe Universität, Robert Mayer-Straße 6-8, 60325 Frankfurt, Germany

E-mail address: rweidman@math.uni-frankfurt.de