DIOPHANTINE GEOMETRY OVER GROUPS VIII:

THE ELEMENTARY THEORY OF A HYPERBOLIC GROUP

Z. Sela^{1,2}

Preliminary Version posted March 18, 2002

This paper generalizes our work on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group, to a general torsion-free (Gromov) hyperbolic group. In particular, we show that every definable set over such a group is in the Boolean algebra of AE sets, prove that hyperbolicity is a first order invariant of a finitely generated group, and obtain a classification of the elementary equivalence classes of torsion-free hyperbolic groups. Finally, we present an effective procedure to decide if two given torsion-free hyperbolic groups are elementary equivalent.

In [Se1]-[Se7] we studied sets of solutions to systems of equations in a free group, and developed basic techniques and objects required for the analysis of sentences and elementary sets defined over a free group. The techniques we developed, enabled us to present an iterative procedure for quantifier elimination for predicates defined over a free group, and answer some of A. Tarski’s problems on the elementary theory of a free group. We were also able to classify those finitely generated groups that are elementary equivalent to a free group.

In this paper we generalize our entire work from free groups to torsion-free hyperbolic groups. In the first section we study limit groups over hyperbolic groups, generalize Guba’s theorem on the equivalence of an infinite system of equations to some finite subsystem [Gu], and associate a canonical Makanin-Razborov diagram with a given system of equations defined over a torsion-free hyperbolic group. As over free groups, this Makanin-Razborov diagram encodes the entire set of solutions to the system. In the second section we generalize Merzlyakov theorem on the existence of a formal solution associated with a positive sentence [Me], and the construction of a formal solution to a general AE sentence which is known to be true over some variety defined over a free group, presented in [Se2], to AE sentences that are known to be true over some variety defined over a torsion-free hyperbolic group. In the third section, we generalize our study of exceptional solutions of parametric systems of equations defined over a free group [Se3], to hyperbolic groups. The main result of this section is the existence of a global bound (independent of the parameters specialization) on the number of families of exceptional solutions to parametric systems of equations defined over a torsion-free hyperbolic group.

1Hebrew University, Jerusalem 91904, Israel, and Institute for Advanced Study, Princeton, NJ 08540, USA.

2Partially supported by an Israel academy of sciences fellowship and NSF grant no. DMS9729992 through the IAS.

In the fourth section, we generalize the iterative procedure for validation of an AE sentence defined over a free group, to AE sentences defined over a torsion-free hyperbolic group. As over free groups, this terminating iterative procedure is the basis for our analysis of elementary sets defined over a hyperbolic group. In the fifth section we generalize the construction of a core resolution, presented in [Se5], to resolutions defined over a torsion-free hyperbolic group. In the sixth section, we generalize the analysis of the Boolean algebra of AE sets defined over a free group ([Se5],[Se6]), to study the Boolean algebra of AE sets defined over a torsion-free hyperbolic group, and finally prove that every definable set over a torsion-free hyperbolic group is in the Boolean algebra of AE sets.

In the seventh section we use the quantifier elimination obtained in the sixth section, to study some basic properties of the elementary theory of a torsion-free hyperbolic group. We prove that hyperbolicity is a first order invariant of a f.g. group, i.e., we show that a f.g. group that is elementary equivalent to a torsionfree hyperbolic group must be hyperbolic as well. We continue by classifying all the f.g. groups that are elementary equivalent to a given torsion-free hyperbolic group. We obtain this classification, by associating an elementary core with a given torsion-free hyperbolic group, and prove that two torsion-free hyperbolic groups are elementary equivalent if and only if their elementary cores are isomorphic. We conclude this section by proving that the universal theory of a torsion-free hyperbolic group is decidable, and use it to construct an effective procedure to decide if two given torsion-free hyperbolic groups are elementary equivalent.

§1. Γ-Limit Groups and their Makanin-Razborov Diagrams

Let Γ =< γ_{1}, …, γ_{k} > be a torsion-free (Gromov) hyperbolic group, and let X be its Cayley graph. Let G =< g_{1}, …, g_{m} > be a f.g. group. Let {h_{j}} ⊂ Hom(G, Γ) be a set of homomorphisms from G to Γ, and suppose that the homomorphisms {h_{j}} belong to distinct conjugacy classes (i.e., for every j_{1}, j_{2}, 1 ≤ j_{1} < j_{2}, and every γ ∈ Γ, γh_{j_{1}}γ^{−1} ≠ h_{j_{2}}). For each index j we fix an element γ_{j} ∈ Γ having ”minimal displacement” under the action λ_{h_{j}} and set μ_{j} to be:

μ_{j} = max_{1≤u≤m} d_{X}(id., γ_{j}h_{j}(g_{u})γ_{j}^{−1}) = min_{γ∈Γ} max_{1≤u≤m} d_{X}(id., γh_{j}(g_{u})γ^{−1})

Since the homomorphisms in the sequence {h_{j}} ⊂ Hom(G, Γ) are non-conjugate, the sequence of stretching factors {μ_{j}} does not contain a bounded subsequence. We set {(X_{j}, x_{j})}_{j=1}^{∞} to be the pointed metric spaces obtained by rescaling the metric on the Cayley graph of Γ, (X, id.), by μ_{j}. (X_{j}, x_{j}) is endowed with a left isometric action of our f.g. group G via the homomorphisms τ_{γ_{j}} ∘ h_{j} where τ_{γ_{j}} is the inner automorphism of Γ defined by γ_{j}. This sequence of actions of G on the metric spaces {(X_{j}, x_{j})}_{j=1}^{∞} allows us to obtain an action of G on a real tree by passing to a Gromov-Hausdorff limit.

Proposition 1.1 ([Pa], 2.3). Let {X_{j}}_{j=1}^{∞} be a sequence of δ_{j}-hyperbolic spaces with δ_{∞} = \underline{lim} δ_{j} = 0. Let H be a countable group isometrically acting on X_{j}. Suppose there exists a base point x_{j} in X_{j} such that for every finite subset P of H, the sets of geodesics between the images of x_{j} under P form a sequence of totally bounded metric spaces. Then there is a subsequence converging in the Gromov topology to a δ_{∞}-hyperbolic space X_{∞} endowed with a left isometric action of H.

Our spaces {(X_{j}, x_{j})}_{j=1}^{∞} endowed with the left isometric action of G, satisfy the assumptions of the proposition and they are all trees, so they are 0-hyperbolic, hence, X_{∞} is a real tree endowed with an isometric action of G. By construction, the action of G on the real tree X_{∞} is non-trivial. Let {j_{n}}_{n=1}^{∞} be the subsequence for which {(X_{j_{n}}, x_{j_{n}})}_{n=1}^{∞} converge to the limit real tree X_{∞}, and let (Y, y_{0}) denote this (pointed) limit real tree. For convenience, for the rest of this section we denote the homomorphism γ_{j_{n}}h_{j_{n}}γ_{j_{n}}^{−1} : G → Γ, by h_{n}.

As we did in section 1 of [Se1], with the limit tree we obtained by using the Gromov-Hausdorff topology we associate natural algebraic objects, the kernel of the action of G on this (limit) real tree and the quotient of G by this kernel which we call the (strict) Γ-limit group.

Definition 1.2. The kernel of the action of the group G on the limit tree Y is defined to be:

K_{∞} = {g ∈ G | ∀y ∈ Y g(y) = y}

Having the kernel of the action, we define the (strict) Γ-limit group to be: L_{∞} = G/K_{∞} and set η : G → L_{∞} to be the natural quotient map.

The following simple facts on the kernel of the action and the (strict) limit group are important observations, and their proof is identical to the proof of lemma 1.3 of [Se1].

Lemma 1.3. With notation of definition 1.2:

(i) L_{∞} is a f.g. group.

(ii) If Y is isometric to a real line then the (strict) limit group L_{∞} is f.g. free

abelian. (iii) If g ∈ G stabilizes a tripod in Y then for all but at most finitely many

n’s g ∈ ker(h_{n}) (recall that a tripod is a finite tree with 3 endpoints). In particular, if g ∈ G stabilizes a tripod then g ∈ K_{∞}.

(iv) Let g ∈ G be an element which does not belong to K_{∞}. Then for all but at

most finitely many n’s g ∉ ker(h_{n}).

(v) L_{∞} is torsion-free.

(vi) Let [y_{1}, y_{2}] ⊂ [y_{3}, y_{4}] be a pair of non-degenerate segments of Y and assume the stabilizer of [y_{3}, y_{4}] in L_{∞}, stab([y_{3}, y_{4}]), is non-trivial. Then stab([y_{3}, y_{4}]) is an abelian subgroup of L_{∞} and:

stab([y_{1}, y_{2}]) = stab([y_{3}, y_{4}])

Hence, the action of L_{∞} on the real tree Y is stable.

In a torsion-free hyperbolic group every solvable subgroup is infinite cyclic and every maximal cyclic subgroup is malnormal. These properties are naturally inherited by the Γ-limit group L_{∞}. The proof is identical to the proof of lemma 1.4 of [Se1].

Lemma 1.4. With the notation of definition 1.2:

(i) Let u_{1}, u_{2}, u_{3} be non-trivial elements of L_{∞}, and suppose that [u_{1}, u_{2}] = 1 and [u_{1}, u_{3}] = 1. Then [u_{2}, u_{3}] = 1. It follows that every abelian subgroup in L_{∞} is contained in a unique maximal abelian subgroup.

(ii) Every maximal abelian subgroup of L_{∞} is malnormal.

(iii) Every solvable subgroup of the (strict) Γ-limit group L_{∞} is abelian.

Proposition 1.3 shows that the action of L_{∞} on the real tree Y is stable. The original analysis of stable actions of groups on real trees applies to f.p. groups ([Be-Fe1]), and the limit group L_{∞} is only known to be f.g. at this point, by part (i) of lemma 1.3. Still, given the basic properties of the action of L_{∞} on the real tree Y that we already know, we are able to apply a generalization of Rips’ work to f.g. groups obtained in [Se8]. In [Se8], the real tree Y is divided into distinct components, where on each component a subgroup of L_{∞} acts according to one of several canonical types of actions. The theorem from [Se8] we present is going to be used extensively in the next sections and its statement uses the notions and basic definitions appear in the appendix of [Ri-Se1]. Hence, we refer a reader who is not yet familiar with these notions to that appendix and to [Be-Fe1] and [Be].

Theorem 1.5 ([Se8],3.1). Let G be a freely indecomposable f.g. group which admits a stable isometric action on a real tree Y. Assume the stabilizer of each tripod in Y is trivial.

1) There exist canonical orbits of subtrees of Y: Y_{1}, … Y_{k} with the following properties:

(i) gY_{i} intersects Y_{j} at most in one point if i ≠ j.

(ii) gY_{i} is either identical with Y_{i} or it intersects it at most in one point. (iii) The action of stab (Y_{i}) on Y_{i} is either discrete or it is of axial type or

IET type.

2) G is the fundamental group of a graph of groups with:

(i) Vertices corresponding to orbits of branching points with non-trivial stabilizer in Y.

(ii) Vertices corresponding to the orbits of the canonical subtrees Y_{1}, …, Y_{k} which are of axial or IET type. The groups associated with these vertices are conjugates of the stabilizers of these components. To a stabilizer of an IET component there exists an associate 2-orbifold. All boundary components and branching points in this associated 2orbifold stabilize points in Y. For each such stabilizer we add edges that connect the vertex stabilized by it and the vertices stabilized by its boundary components and branching points.

(iii) Edges corresponding to orbits of edges between branching points with non-trivial stabilizer in the discrete part of Y with edge groups which are conjugates of the stabilizers of these edges.

(iv) Edges corresponding to orbits of points of intersection between the orbits of Y_{1}, …, Y_{k}.

Before concluding our preliminary study of (strict) Γ-limit groups and their action on the limit real tree, we present the following basic fact which is necessary in the sequel. It’s proof is identical to the proof of lemma 1.6 of [Se1].

Lemma 1.6. If L_{∞} is a (strict) Γ-limit group acting on a limit tree Y obtained from a converging sequence of homomorphisms from a f.g. group G into a hyperbolic group Γ, and L_{∞} is freely-indecomposable, then stabilizers of non-degenerate segments which lie in the complement of the discrete parts of Y are trivial in L_{∞}. Stabilizers of segments in the discrete components of Y are abelian subgroups of L_{∞}.

To further study the algebraic structure of a (strict) Γ-limit group we need to construct its canonical abelian JSJ decomposition, in a similar way to the construction of the abelian JSJ decomposition of a (F_{k}) limit group ([Se1],2). To construct the JSJ decomposition of a Γ-limit group we need to study some basic properties of abelian splittings. We start with the following lemma, which is identical to lemma 2.1 of [Se1].

Lemma 1.7. Let L_{∞} be a (strict) Γ-limit group, let M be a maximal abelian subgroup in L_{∞}, and let A be an abelian subgroup of L_{∞}. Then:

(i) If L_{∞} = U ∗_{A} V and M is not cyclic then M can be conjugated into either U or V.

(ii) If L_{∞} = U∗_{A} and M is not cyclic then either M can be conjugated into U, or M can be conjugated to M′, so that L_{∞} = U ∗_{A} M′.

By lemma 1.7 if we replace each abelian splitting of L_{∞} of the form L_{∞} = U∗_{A} in which A is a subgroup of a non-elliptic maximal abelian subgroup M by the amalgamated product L_{∞} = U ∗_{A}M′, we get that every non-cyclic abelian subgroup of L_{∞} is elliptic in all the abelian splittings under consideration. This will allow us to use acylindrical accessibility in analyzing all the abelian splittings of L_{∞}.

Definition 1.8 [Se8]. A splitting of a group H is called k-acylindrical if for every element h ∈ H which is not the identity, the fixed set of h when acting on the Bass-Serre tree corresponding to the splitting has diameter at most k.

If a (strict) Γ-limit group L_{∞} = V_{1} ∗_{A_{1}} V_{2} ∗_{A_{2}} V_{3} ∗_{A_{3}} V_{4}, where A_{1}, A_{2}, A_{3} are subgroups of a maximal abelian subgroup M that is a subgroup of V_{1}, then one can modify the corresponding graph of groups to a tripod of groups with V_{1} in the center, and V_{2}, V_{3}, V_{4} at the 3 roots. Since by lemma 1.4 every maximal abelian subgroup of L_{∞} is malnormal, the Bass-Serre tree corresponding to this tripod of groups is 2-acylindrical. This sliding operation generalizes to an arbitrary (finite) abelian splitting of a limit group.

Lemma 1.9. A splitting of L_{∞} in which all edge groups are abelian and all noncyclic abelian groups are elliptic can always be modified (by modifying boundary monomorphisms by conjugations and sliding operations) to be 2-acylindrical.

Lemma 1.9 shows that if in all abelian splittings of L_{∞} under consideration, all non-cyclic abelian subgroups are elliptic, these abelian splittings are 2-acylindrical. By lemma 1.7 if we replace abelian splittings of L_{∞} having the form L_{∞} = U∗_{A} in which A is a subgroup of a non-elliptic maximal abelian subgroup by the amalgamated product L_{∞} = U ∗_{A} M, we get that every non-cyclic abelian subgroup of L_{∞} is elliptic in all the abelian splittings under consideration. Hence, we may assume that all abelian splittings of L_{∞} under consideration are 2-acylindrical. As in our study of (F_{k}) limit groups, this acylindricity finally enables one to construct the canonical abelian JSJ decomposition of a (strict) Γ-limit group (see section 2 of [Se1]).

Theorem 1.10 (cf. ([Se1],2.7)). Suppose that L_{∞} is a freely indecomposable (strict) Γ-limit group. There exists a reduced unfolded splitting of L_{∞} with abelian edge groups, which we call an abelian JSJ (Jaco-Shalen-Johannson) decomposition of L_{∞} with the following properties:

(i) Every canonical maximal QH subgroup (CMQ) of L_{∞} is conjugate to a vertex group in the JSJ decomposition. Every QH subgroup of L_{∞} can be conjugated into one of the CMQ subgroups of L_{∞}. Every vertex group in the JSJ decomposition which is not a CMQ subgroup of L_{∞} is elliptic in any abelian splitting of L_{∞} under consideration.

(ii) A one edge abelian splitting L_{∞} = D ∗_{A} E or H_{∞} = D∗_{A} under consideration which is hyperbolic in another elementary abelian splitting is obtained from the abelian JSJ decomposition of L_{∞} by cutting a 2-orbifold corresponding to a CMQ subgroup of L_{∞} along a weakly essential s.c.c..

(iii) Let Θ be a one edge splitting along an abelian subgroup L_{∞} = D ∗_{A} E or L_{∞} = D∗_{A} under consideration, which is elliptic with respect to any other one edge abelian splitting of L_{∞} under consideration. Then Θ is obtained from the JSJ decomposition of L_{∞} by a sequence of collapsings, foldings, and conjugations.

(iv) If JSJ_{1} is another JSJ decomposition of L_{∞}, then JSJ_{1} is obtained from the JSJ decomposition by a sequence of slidings, conjugations and modifying boundary monomorphisms by conjugations (see section 1 of [Ri-Se2] for these notions)

In section 4 of [Se1] we were able to use the cyclic JSJ decomposition of a (F_{k}) limit group, in order to show that (F_{k}) limit groups are f.p. and that a f.g. group is a limit group if and only if it is ω-residually free. When Γ is a general torsionfree hyperbolic group, Γ may contain f.g. subgroups that are not f.p. in which case there are clearly (strict) Γ-limit groups that are not f.p. Still, the ascending chain conditions that enable us to construct the Makanin-Razborov diagram of a (F_{k}) limit group remain valid, and enable us to construct the (canonical) Makanin-Razborov diagram of a general Γ-limit group.

Definition 1.11. Let Γ be a torsion-free hyperbolic group, and G a f.g. group. We say that G is a Γ-limit group if G is isomorphic to a subgroup of Γ or if G is a (strict) Γ-limit group.

We start the construction of the Makanin-Razborov diagram of a Γ-limit group as in the construction of a Makanin-Razborov diagram of a (F_{k}) limit group. Let Γ be a torsion-free hyperbolic group, and G a f.g. group. On the set of Γ-limit groups we define a relation. Given two Γ-limit groups, R_{1}, R_{2}, that are quotients of G, with prescribed maps η_{i} : G → R_{i}, i = 1, 2 we say that R_{1} > R_{2}, if there exists an epimorphism with non-trivial kernel: τ : R_{1} → R_{2}, so that η_{2} = τ ∘ η_{1}.

Theorem 1.12. Let Γ be a torsion-free hyperbolic group, and G a f.g. group. Every decreasing sequence of Γ-limit groups that are quotients of G:

R_{1} > R_{2} > R_{3} > …

terminates after finitely many steps.

Proof: Suppose that there exists a f.g. group G and a torsion-free hyperbolic group Γ, for which there exists an infinite decreasing sequence of Γ-limit groups: R_{1} > R_{2} > R_{3} > . . .. W.l.o.g. we may assume that the f.g. group is a free group F_{d}, for some integer d. We fix such Γ, fix F_{d}, and fix a free basis for F_{d}, F_{d} =< f_{1}, …, f_{d} >, set C to be the Cayley graph of F_{d} with respect to the given generating set, and look at an infinite decreasing sequence constructed in the following way. We set R_{1} to be a Γ-limit group with the following properties:

(1) R_{1} is a proper quotient of F_{d}.

(2) R_{1} can be extended to an infinite decreasing sequence of Γ-limit groups: R_{1} > L_{2} > L_{3} > . . ..

(3) The map η_{1} : F_{d} → R_{1} maps to the identity the maximal number of elements in the ball of radius 1 in the Cayley graph C, among all possible maps from G to a Γ-limit group L that satisfies properties (1) and (2).

We continue iteratively. At step n, given the finite decreasing sequence R_{1} > R_{2} > … > R_{n−1}, we choose the Γ-limit group R_{n} to satisfy:

(1) R_{n} is a proper quotient of R_{n−1}.

(2) The finite decreasing sequence of Γ-limit groups: R_{1} > R_{2} > … > R_{n} can be extended to an infinite decreasing sequence.

(3) The map η_{n} : F_{d} → R_{n} maps to the identity the maximal number of elements in the ball of radius n in the Cayley graph C, among all possible maps from G to a Γ-limit group L_{n} that satisfies properties (1) and (2).

With the decreasing sequence R_{1} > R_{2} > … we associate a sequence of homomorphisms {h_{n} : F_{d} → Γ}. For each index n, R_{n} is a quotient of F_{d}, hence, R_{n} is generated by d elements that are the image of the fixed generators of F_{d} under the quotient map η_{n}. R_{n} is a Γ-limit group, hence, either R_{n} can be embedded into Γ, or R_{n} is obtained from a converging sequence of homomorphisms {u_{s} : G_{n} → Γ}, where G_{n} is a f.g. group. In the second case, in which R_{n} is a (strict) Γ-limit group, since R_{n} is generated by the image of the elements f_{1}, …, f_{d} under the quotient map η_{n}, for large enough s, the images u_{s}(G_{n}) are d-generated subgroups of Γ, and furthermore, they are generated by the images of d elements in the f.g. group G_{n}, that are mapped by the quotient map ν_{n} : G_{n} → R_{n} onto the elements η_{n}(f_{1}), …, η_{n}(f_{d}). Hence, we may assume that in both cases, the Γ-limit groups R_{n} are obtained as Γ-limit groups from a sequence of homomorphisms {v_{s} : F_{d} → Γ}, and the image of the fixed generating set of the free group F_{d}, is the set of elements η_{n}(f_{1}), …, η_{n}(f_{d}).

For each index n, we pick h_{n} to be a homomorphism h_{n} : F_{d} → Γ, so that h_{n} is obtained from a homomorphism u_{s} : G_{n} → Γ for some large index s, so that h_{n} satisfies the following two conditions:

(i) every element in the ball of radius n of C, the Cayley graph of F_{d}, that is mapped by the quotient map η_{n} : F_{d} → R_{n} to the trivial element, is mapped by h_{n} to the trivial element in Γ. Every such element that is mapped to a non-trivial element by η_{n}, is mapped by h_{n} to a non-trivial element in Γ.

(ii) there exists an element f ∈ F_{d}, that is mapped to the trivial element by η_{n+1} : F_{d} → R_{n+1}, for which h_{n}(f) ≠ 1.

To prove theorem 1.12, we will show that the last descending sequence we constructed terminates after finitely many steps.

By construction, the set of homomorphisms {h_{n} : F_{d} → Γ} does not belong to a finite set of conjugacy classes. Hence, from the sequence {h_{n}} we can extract a subsequence that converges into a (strict) Γ-limit group, that we denote R_{∞}. By construction, the Γ-limit group R_{∞} is the direct limit of the sequence of (proper) epimorphisms:

F_{d} → R_{1} → R_{2} → …

Let η_{∞} : F_{d} → R_{∞} be the canonical quotient map. Our approach towards proving the termination of descending chains of Γ-limit groups is based on studying the structure of the (strict) Γ-limit group R_{∞}, and its associated quotient map η_{∞}. We start this study by listing some basic properties of them.

Lemma 1.13.

(i) the set of homomorphisms {h_{n} : F_{d} → Γ} do not belong to finitely many conjugacy classes, hence, R_{∞} is a (strict) Γ-limit group.

(ii) R_{∞} is not finitely presented.

(iii) R_{∞} can not be presented as the free product of a f.p. group and freely inde-

composable Γ-limit groups that do not admit a cyclic splitting. (iv) Let R_{∞} = U_{1} ∗ … ∗ U_{t} ∗ F be the most refined (Grushko) free decomposition

of R_{∞}, where F is a f.g. free group. Then there exists an index j, 1 ≤ j ≤ t, for which:

(1) U_{j} is not finitely presented.

(2) If B is a f.g. subgroup of F_{d} for which η_{∞}(B) = U_{j}, then the restrictions h_{n}|_{B} do not belong to finitely many conjugacy classes. Furthermore, if b_{1}, …, b_{p} is a generating set for B, then for every index n, h_{n}(B) is not isomorphic to η_{∞}(B) by an isomorphism that sends h_{n}(b_{j}) to η_{∞}(b_{j}) for j = 1, …, p.

Proof: Part (i) follows from the construction of the sequence {h_{n} : F_{d} → Γ}, since for every index n_{0}, there exists some element f ∈ F_{d}, so that h_{n_{0}}(f) ≠ 1 and for some index n_{1} > n_{0} and every index n > n_{1}, h_{n}(f) = 1. To prove part (ii), suppose that R_{∞} is f.p. i.e.:

R_{∞} = < g_{1}, …, g_{d} | r_{1}, …, r_{s} > .

Then for some index n_{0}, and every index n > n_{0}, h_{n}(r_{j}) = 1 for j = 1, …, s. This implies that for some index n_{1} > n_{0}, and every index n > n_{1}, each of the groups R_{n} is a quotient of R_{∞}, by a quotient map that send the generating set g_{1}, …, g_{d} of R_{∞} to the elements η_{n}(f_{1}), …, η_{n}(f_{d}), a contradiction.

Suppose that R_{∞} = V_{1} ∗ … ∗ V_{t} ∗ M where M is f.p. and each of the factors V_{j} is freely indecomposable and does not admit a cyclic splitting. Let B_{1}, …, B_{t} and D be f.g. subgroups of F_{d}, for which η_{∞}(B_{j}) = V_{j} for j = 1, …, t, and η_{∞}(D) = M. W.l.o.g. we may assume that the free group F_{d} is generated by the collection of the subgroups B_{1}, …, B_{t}, D. Since the freely-indecomposable subgroups V_{j} do not admit a cyclic splitting, they are not strict Γ-limit groups. Hence, for every index j, j = 1, …, t, there exists an index n_{j}, so that for every index n > n_{j}, the image h_{n}(B_{j}) is isomorphic to the factor V_{j}, via the isomorphism η_{∞} ∘ h_{n}^{−1}.

The factor M is assumed f.p., hence, if D =< d_{1}, …, d_{s} >, then M =< d_{1}, …, d_{s} | r_{1}, …, r_{u} >. There exists an index n_{0}, for which for every index n > n_{0}, h_{n}(r_{i}) = 1, for i = 1, …, u.

Let m_{0} > n_{j} for j = 0, …, t. By construction, there exists an element f ∈ F_{d}, for which h_{m_{0}}(f) ≠ 1 and η_{m}(f) = 1 for every m > m_{0}. Since h_{m_{0}}(f) ≠ 1, η_{∞}(f) ≠ 1, which clearly contradicts the fact that η_{m}(f) = 1 for every m > m_{0}, Since R_{∞} is a proper quotient of all the Γ-limit groups R_{m}, and proves part (iii) of the lemma. Part (iv) follows by exactly the same argument.

□

R_{∞} is a Γ-limit group that is a (proper) quotient of all the Γ-limit groups, R_{n}. For each index n, the limit group R_{n} was chosen to maximize the number of elements that are mapped to the identity in the ball of radius n of F_{k} by the quotient map η_{n} : F_{k} → R_{n}, among all the proper Γ-limit quotients of R_{n−1} that admit an infinite descending chain of Γ-limit groups. If R_{∞} admits an infinite descending chain of Γ-limit groups:

R_{∞} → L_{1} → L_{2} → …

then the Γ-limit group L_{1} admits an infinite descending chain sequence of Γ-limit groups, and since it is a proper quotient of R_{∞}, for large enough index n, the quotient map ν_{n} : F_{k} → L_{1} maps to the identity strictly more elements of the ball of radius n in the Cayley graph of F_{k}, than the map η_{n} : F_{k} → R_{n}, a contradiction. Hence, R_{∞} does not admit an infinite descending chain of Γ-limit groups.

To continue the proof of theorem 1.12, i.e., to contradict the existence of the infinite descending chain of Γ-limit groups that we constructed, we need a modification of the shortening procedure that was used in [Se1] for (F_{k}) limit groups. The shortening procedure is presented in section 3 of [Se1], and is used there to prove that a freely indecomposable, non-abelian (F_{k}) limit group admits a cyclic splitting. Since the description of the shortening procedure is rather long and involved, we prefer not to repeat it, and refer the interested reader to section 3 of [Se1]. The same construction that appears in [Se1] applies to Γ-limit groups (where Γ is torsion-free hyperbolic). Given a f.g. group G, a torsion-free hyperbolic group Γ, and a sequence of homomorphisms {u_{s} : G → Γ}, that converges into a Γ-limit group L_{∞}, the shortening procedure constructs another (sub) sequence of homomorphisms from a free group F_{d} (where the f.g. group G is generated by d elements), {v_{s_{n}} : F_{d} → Γ}, so that the sequence of homomorphisms v_{s_{n}} converges to a Γ-limit group Q_{∞}, and there exists a natural epimorphism L_{∞} → SQ_{∞}.

Definition 1.14. We call the Γ-limit group SQ_{∞}, obtained by the shortening procedure, a shortening quotient of the Γ-limit group L_{∞}.

By construction, a shortening quotient of a Γ-limit group is, in particular, a quotient of that Γ-limit group. In the case of F_{k}-limit groups, a shortening quotient is always a proper quotient ([Se1],5.3). If the Γ-limit group we start with, L_{∞}, is non-cyclic and freely-indecomposable, and the sequence of homomorphisms do not ”stabilize in a finite time”, a shortening quotient of L_{∞} is a proper quotient of it.

Proposition 1.15. Let G be a f.g. group, let Γ be a torsion-free hyperbolic group, and let {u_{s} : G → Γ} be a sequence of homomorphisms that converges into an action of a non-cyclic, freely-indecomposable (strict) Γ-limit group L on some real tree Y. If for every index s, u_{s}(G) is not isomorphic to L by the natural map that sends the images of the generators of G in u_{s}(G) to the images of these generators in L, then every shortening quotient of L, obtained from the sequence {u_{s}}, is a proper quotient of L.

Proof: Suppose that the f.g. group G is generated by d elements. A shortening quotient SQ of L is obtained from a sequence of homomorphisms {v_{s_{n}} : F_{d} → Γ} that converges into SQ. By construction, the shortening quotient SQ is a quotient of the Γ-limit group L. If the sequence of homomorphisms {v_{s_{n}}} do not belong to finitely many conjugacy classes, then the shortening quotient SQ is a proper quotient of L by the shortening argument that is used in the proof of theorem 5.3 in [Se1]. Hence, by possibly passing to a subsequence, we may assume that the homomorphisms {v_{s_{n}}} are pairwise conjugate. In this case, if SQ is isomorphic to the Γ-limit group L, then v_{s_{n}}(F_{d}) is isomorphic to L for every index n, so for large enough n, the image u_{s_{n}}(G) is isomorphic to L by an isomorphism that that sends the images of the generators of G in u_{s_{n}}(G) to the images of these generators in L, a contradiction.

□

The shortening procedure, and proposition 1.15, enable us to show that from the sequence of homomorphisms {h_{n} : F_{d} → Γ} it is possible to extract a subsequence that factors through a finite resolution of the Γ-limit group R_{∞}.

Proposition 1.16. Let {h_{n} : F_{d} → Γ} be the sequence of homomorphisms constructed above. Then there exists a finite sequence of Γ-limit groups:

R_{∞} → L_{1} → L_{2} → … → L_{s}

for which:

(i) The epimorphisms along the sequence are proper epimorphisms.

(ii) Let L_{s} = H_{1} ∗ … ∗ H_{r} ∗ F_{t} be the (possibly trivial) Grushko’s free decomposition of the terminal Γ-limit group L_{s}. Then there exists a subsequence, {h_{n_{t}}}, of the homomorphisms {h_{n} : G → Γ} so that each of the homomorphisms h_{n_{t}} can be written in the form:

h_{n_{t}} = ν_{t} ∘ η_{s−1} ∘ φ_{s−1}^{t} ∘ η_{s−2} ∘ … ∘ φ_{1}^{t} ∘ η_{0}

where φ_{i}^{t} is a modular automorphism of the Γ-limit group L_{i} for 1 ≤ i ≤ s−1, and ν_{t} is a homomorphism ν_{t} : L_{s} → Γ, that embeds each of the freely indecomposable factors H_{j} of L_{s} into Γ.

(iii) the sequence of homomorphisms h_{n_{t}} : F_{d} → Γ converges into a faithful action of the Γ-limit group R_{∞} on a real tree Y. Furthermore, the entire sequence of homomorphisms h_{n_{t}} factors through the epimorphism η_{∞} : F_{d} → R_{∞}, i.e., for every index t, h_{n_{t}} = ĥ_{t} ∘ η_{∞}, where h_{t} is a homomorphism h_{t} : R_{∞} → Γ.

Proof: By lemma 1.13 and proposition 1.15 a shortening quotient of R_{∞} is a proper quotient of it. Hence, we set L_{1} to be a shortening quotient of R_{∞}. If from the sequence of (shortened) homomorphisms that was used to construct L_{1}, it’s possible to extract a subsequence that satisfy the properties of lemma 1.13, we continue with this subsequence, and use it to get a shortening quotient L_{2} of L_{1}, which by proposition 1.15, is a proper quotient of L_{1}. Continuing this process iteratively, and recalling that every sequence of proper Γ-quotients terminates after finitely many steps, we finally get the sequence of proper epimorphisms:

R_{∞} →→ L_{1} → L_{2} → … → L_{s}.

Let {ν_{n} : F_{d} → Γ} be the sequence of homomorphisms that was used to construct the terminal shortening quotient L_{s}. Let L_{s} = H_{1} ∗ … ∗ H_{r} ∗ F_{t} be the (possibly trivial) Grushko’s decomposition of L_{s}. Since L_{s} is a terminal shortening quotient, from the sequence of homomorphisms {ν_{n}} that was used to construct L_{s}, it is not possible to extract a subsequence that satisfies the properties of lemma 1.13. Hence, if B_{j} is a subgroup of F_{d} that is mapped onto a factor H_{j} by the associated quotient map λ_{s} : F_{d} → L_{s}, then there exists some index n_{j}, so that for every index n > n_{j}, h_{n}(B_{j}) is isomorphic to H_{j} by the map η ∘ h_{n}|_{B_{j}}^{−1}.

We prove part (ii) of the proposition by induction on the number of levels in the sequence: R_{∞} → L_{1} → … → L_{s}. If the sequence has length 1, i.e., if R_{∞} = L_{s}, the claim of part (ii) follows from the argument given above, i.e., follows since R_{∞} = L_{s} does not admit a proper shortening quotient. Suppose the claim of part (ii) holds for the partial sequence: L_{j+1} → … → L_{s}. Then the claim holds for every non-abelian, non-QH vertex group in the abelian JSJ decomposition of L_{j}, hence, every abelian subgroup in L_{j} is f.g. and so are the edge groups and abelian vertex groups in the abelian JSJ decomposition of L_{j}. Since the claim holds for every non-abelian, non-QH vertex group and all the other vertex groups in the abelian JSJ decomposition of L_{j} are f.p. the claim of the proposition is valid for L_{j}. Therefore, by induction it holds for a subsequence of the original sequence of homomorphisms from R_{∞} to Γ. Finally, part (iii) of the proposition is a direct consequence of part (ii).

□

The homomorphisms {h_{n} : F_{d} → Γ} were chosen so that for every index n, there exists some element f ∈ F_{d}, for which η_{n+1}(f) = 1 and h_{n}(f) ≠ 1. Since R_{∞} is a (proper) quotient of all the γ-limit groups R_{n}, for every index n and every element f ∈ F_{d}, if η_{n+1}(f) = 1 then η_{∞}(f) = 1. By part (iii) of proposition 1.16, from the sequence {h_{n}} it is possible to extract a subsequence {h_{n_{t}} : F_{d} → Γ}, that factors through the Γ-limit group R_{∞}, i.e., h_{n_{t}} = h_{t} ∘ η_{∞}, where h_{t} : R_{∞} → Γ. Hence, for every index t, and every element f ∈ F_{d}, if η_{n_{t}+1}(f) = 1 then η_{∞}(f) = 1, so h_{n_{t}}(f) = 1, a contradiction to the construction of the homomorphisms {h_{n}}, which finally concludes the proof of theorem 1.12.

□

Theorem 1.12 clearly implies that a Γ-limit group is Hopf, i.e., that every epimorphism from a Γ-limit group onto itself is an automorphism. Therefore, the relation defined on Γ-limit groups, is indeed a partial order.

Let Γ =< γ_{1}, …, γ_{k} > be a torsion-free hyperbolic group with a Cayley graph X, and let G =< g_{1}, …, g_{m} > be a f.g. group. To analyze the entire set of homomorphisms from the f.g. group G into the hyperbolic group Γ, we start with the following theorem that generalizes proposition 1.16, and associates a resolution with a subsequence of a given sequence of homomorphisms from G to Γ.

Theorem 1.17. Let G be a f.g. group, let Γ be a torsion-free hyperbolic group, and let {h_{n} | h_{n} : G → Γ} be a sequence of homomorphisms from G into Γ. Then there exists a finite sequence of Γ-limit groups:

G → L_{1} → L_{2} → … → L_{s}

for which:

(i) η_{0} : G → L_{1} is an epimorphism and η_{i} : L_{i} → L_{⊂+1} is a proper epimorphism for 1 ≤ i ≤ s − 1.

(ii) Let L_{s} = H_{1} ∗…∗H_{r} ∗F_{t} be the (possibly trivial) Grushko’s free decomposition of the terminal Γ-limit group L_{s}. Then there exists a subsequence {h_{n_{t}}} of the homomorphisms {h_{n} : G → Γ} so that each of the homomorphisms h_{n_{t}} can be written in the form:

h_{n_{t}} = ν_{t} ∘ η_{s−1} ∘ φ_{s−1}^{t} ∘ η_{s−2} ∘ … ∘ φ_{1}^{t} ∘ η_{0}

where φ_{i}^{t} is a modular automorphism of the Γ-limit group L_{i} for 1 ≤ i ≤ s−1, and ν_{t} is a homomorphism ν_{t} : L_{s} → Γ, that embeds each of the freely indecomposable factors H_{j} of L_{s} into Γ.

(iii) the sequence of homomorphisms h_{n_{t}} : G → Γ converges into a faithful action of the Γ-limit group L_{1} on a real tree Y_{1}. Furthermore, the entire sequence of homomorphisms h_{n_{t}} factor through the epimorphism η_{0} : G → L_{1}, i.e., for every index t, h_{n_{t}} = ĥ_{t} ∘ η_{0}, where h_{t} is a homomorphism h_{t}L_{1} → Γ.

Proof: A subsequence of the homomorphisms {h_{n}} converges into an action of a Γ-limit group L_{1} on some real tree. If there exists a subsequence of that sequence that satisfies the properties listed in lemma 1.13, we use it to get a shortening quotient L_{2}, which by proposition 1.15 is a proper quotient of L_{1}. We continue iteratively obtaining proper shortening quotients that are proper quotients, and by theorem 1.12 the process terminates after finitely many steps. This give us the sequence:

G → L_{1} → L_{2} → … L_{s}.

Part (ii) and (iii) of the theorem follow by the argument that was used to prove proposition 1.16.

□

Theorems 1.12 and 1.17 enable us to obtain the ascending chain conditions that are needed in order to construct the (canonical) Makanin-Razborov diagram associated with a system of equations over a torsion-free hyperbolic group. We start with two immediate implications. Let Γ be a non-elementary torsion-free hyperbolic group. A f.g. group G is called ω-residually Γ if for any finite set of elements g_{1}, …, g_{n} ∈ G, there exists a homomorphism h : G → Γ that maps these elements into distinct elements in Γ.

Proposition 1.18. Let Γ be a non-elementary torsion-free hyperbolic group. A f.g. group G is ω-residually Γ if and only if it is a Γ-limit group.

Proof: From the definition of an ω-residually Γ group, an ω-residually Γ group is a Γ-limit group. Suppose G is a Γ-limit group. Then G is obtained as a limit of a sequence of homomorphisms {h_{n} : U → Γ}. By theorem 1.17, by further passing to a subsequence (still denoted {h_{n}}) we may assume that all these homomorphisms factor through the Γ-limit group G. Since the sequence converges into G, for every finite set of elements of G, there exists some n_{0}, so that for every n > n_{0}, the homomorphism h_{n} maps the finite set into distinct elements. Hence, G is ω-residually Γ.

□

Proposition 1.19. Let Γ be a non-elementary torsion-free hyperbolic group. Then there are countably many Γ-limit groups.

Proof: A f.g. group has only countable f.g. subgroups. Since by theorem 1.16 every Γ-limit group is obtained from finitely many f.g. subgroups of Γ using finitely many iterations of free products and amalgamated free products and HNN extensions along (f.g.) abelian subgroups, and free products and amalgamated products with surface groups and f.g. abelian groups, there are only countably many Γ-limit groups.

□

We continue by proving that there are maximal elements in the set of all Γ-limit groups that are all quotients of a (fixed) f.g. group G, and that there are only finitely many equivalence classes of such maximal elements.

Proposition 1.20. Let G be a f.g. group and Γ a torsion-free hyperbolic group. Let R_{1}, R_{2}, … be a sequence of Γ-limit groups that are all quotients of the f.g. group G, and for which:

R_{1} < R_{2} < …

Then there exists a Γ-limit group R that is a quotient of G, so that for every index m, R > R_{m}.

Proof: For each Γ-limit group R_{m}, we choose a homomorphism h_{m} : G → Γ, that factors through the quotient map η_{m} : G → R_{m}, i.e., h_{m} = h′_{m} ∘ η_{m}, so that h′_{m} maps the elements in a ball of radius m in R_{m} into distinct elements in γ. A subsequence of the homomorphisms {h_{m}} converges into a Γ-limit group R, which is a Γ-limit quotient of G, and by theorem 1.17 we may assume that they all factor through the quotient map η : G → Γ. Hence, by construction, R > R_{m} for every index m.

□

The combination of propositions 1.19 and 1.20 implies that there are maximal elements in the set of Γ-limit groups obtained from sequences of homomorphisms from a fixed f.g. group G into Γ. Recall that we say that two Γ-limit quotients of G, η_{1} : G → R_{1}, η_{2} : G → R_{2}, are equivalent, if there exists an isomorphism τ : R_{1} → R_{2}, so that η_{2} = τ ∘ η_{1}.

Proposition 1.21. Let G be a f.g. group, and Γ a torsion-free hyperbolic group. Then there are only finitely many equivalence classes of maximal elements in the set of Γ-limit groups that are quotients of G.

Proof: Identical to the proof of lemma 5.5 in [Se1].

□

As a corollary of proposition 1.21 and theorem 1.12, we get a generalization of Guba’s theorem [Gu] for systems of equations over a free group, to an arbitrary torsion-free hyperbolic group.

Theorem 1.22. Let Γ be a torsion-free hyperbolic group. Then every infinite system of equations in finitely many variables Σ over Γ, is equivalent to a finite subsystem of Σ.

Proof: Going over the equations in the system Σ, we iteratively construct a directed locally finite tree. We start with the first equation, and with it we associate a one relator group G_{1}, generated by the variables of the system, with one relator that correspond to the first equation of the system Σ. By proposition 1.21, with G_{1} we associate its finite collection of maximal Γ-limit quotients R_{1}, …, R_{m}. With this collection, we associate a directed finite rooted tree, where in the root we place the group G_{1} and in each of the other nodes we place its maximal Γ-limit quotients, each connected to the root by an edge directed from the root to the node. We continue with the second equation w_{2} in the system Σ, and with each of the maximal Γ-limit quotients R_{1}, …, R_{m}, in parallel. If w_{2} represents the trivial word in the group R_{i}, we leave it unchanged. If w_{2} is non-trivial in R_{i}, we set R̂_{i} to be the (proper) quotient group R̂_{i} = R_{i}/ < w_{2} >. With R̂_{i} we associate its finite collection of maximal Γ-limit quotients L_{1}, …, L_{t}, which are all proper quotients of the γ-limit group R_{i}. We further extend the locally finite tree, by adding new vertices labeled by L_{1}, …, L_{t}, and connecting each of them by an edge directed from vertex labeled by R_{i} to the vertex labeled by L_{i}.

Continuing iteratively by adding the equations in Σ, we finally construct a locally finite tree. By theorem 1.12 every (directed) path in this locally finite tree is finite, hence, by Konig’s lemma, the locally finite tree is finite. Therefore, the construction of the locally finite tree terminates after finitely many steps, so the infinite system Σ is equivalent to some finite subsystem.

□

To study the entire collection of homomorphisms from a given f.g. group into a hyperbolic group, we need to find a way to ”encode” this collection. To get such ”encoding” we will construct a canonical diagram associated with a Γ-limit group, in a similar way to the construction of the Makanin-Razborov diagram for an (F_{k}) limit group ([Se1],5).

Let R be a freely-indecomposable Γ-limit group and let r_{1}, …, r_{m} ∈ R be a generating set of R. To analyze the entire set of homomorphisms from R to Γ, we will need to look at the set of shortening quotients of R. However, we won’t need to look at all the shortening quotients of R, but only those shortening quotients obtained from sequences of homomorphisms {h_{n} : R → Γ}, for which for every index n, h_{n}(R) is a proper quotient of R, i.e., those homomorphisms that do not embed R in Γ. Note that by theorem 1.15 every such shortening quotient is a proper quotient of R. For the rest of this section we will restrict our attention to those (proper) shortening quotients.

Following [Se1], we say that two (proper) shortening quotients S_{1}, S_{2} of the Γlimit group R are equivalent, if there exists an isomorphism τ : S_{1} → S_{2}, and the canonical map η_{2} : R → S_{2} can be expressed as η_{2} = τ ∘ η_{1} ∘ φ where φ ∈ Mod(R) and η_{1} : R → S_{1} is the canonical map associated with the (maximal) shortening quotient S_{1}. The notion of equivalent shortening quotients is clearly an equivalence relation on the set of couples of shortening quotients and their associated canonical maps: {(S_{i}, η_{i} : R → S_{i})} of the limit group R.

Let SQ(R, r_{1}, …, r_{m}) be the set of (proper) shortening quotients of R. On the set SQ(R, r_{1}, …, r_{m}) we define a partial order similar to the one defined on Γ-limit groups. Given two shortening quotients S_{1}, S_{2} ∈ SQ(R, r_{1}, …, r_{m}), we say that S_{1} > S_{2} if S_{2} is a proper quotient of S_{1} and the canonical map η_{2} : R → S_{2} splits as η_{2} = ν ∘ η_{1} where η_{1} : R → S_{1} is the canonical map associated with S_{1} and ν : S_{1} → S_{2} is a homomorphism.

Lemma 1.23. Let R be a freely-indecomposable Γ-limit group. Let S_{1} < S_{2} < S_{3} < … (where S_{j} ∈ SQ(R, r_{1}, …, r_{m})) be a properly increasing sequence of (proper) shortening quotients of R. Then there exists a shortening quotient S ∈ SQ(R, r_{1}, …, r_{m}) so that S > S_{j} for every shortening quotient S_{j} in the increasing sequence.

Proof: Identical to the proof of proposition 1.20.

□

Lemma 1.23 proves the existence of maximal elements with respect to the partial order on the set of (proper) shortening quotients SQ(R, r_{1}, …, r_{m}). The next lemma shows that there are only finitely many equivalence classes of maximal elements in the set of (proper) shortening quotients.

Lemma 1.24. Let R be a freely-indecomposable Γ-limit group. The set of (proper) shortening quotients of R, SQ(R, r_{1}, …, r_{m}), contains only finitely many equivalence classes of maximal elements with respect to its partial order.

Proof: Identical to the proof of proposition 1.21.

□

The main significance of maximal shortening quotients is the way they ”encode” and simplify all homomorphisms from a freely-indecomposable Γ-limit group into a (torsion-free) hyperbolic group.

Proposition 1.25. Let R be a freely-indecomposable Γ-limit group. Let r_{1}, …, r_{m} ∈ R be a generating set of R, let M_{1}, …, M_{k} be a collection of representatives of the (finite) set of equivalence classes of maximal (proper) shortening quotients in SQ(R, r_{1}, …, r_{m}), and for i = 1, …, k let η_{i} : R → M_{i} be the canonical quotient maps. Let h : R → Γ be a homomorphism which is not an embedding. Then there exists some index 1 ≤ i ≤ k (not necessarily unique!) and a modular automorphism φ_{h} ∈ Mod(R) so that h ∘ φ_{h} splits through the maximal shortening quotient M_{i}. i.e., h ∘ φ_{h} = h_{M_{i}} ∘ η_{i} where h_{M_{i}} : M_{i} → Γ is a homomorphism.

Proof: Identical to the proof of proposition 5.6 in [Se1].

□

The shortening procedure and the lemmas and propositions proved so far in this section finally allow us to present the main goal of this section, the (canonical) Makanin-Razborov diagram associated with a f.g. group G and a torsion-free hyperbolic group Γ. The Makanin-Razborov diagram ”encodes” all possible homomorphisms from G into Γ, and as we will see later, some of its properties can be stated as a criteria for a general f.g. group to be a Γ-limit group.

Let G be a f.g. limit group and Γ a torsion-free hyperbolic group. By proposition 1.21 G has finitely many (equivalence classes of) maximal Γ-limit quotients, R_{1}, …, R_{s}. We continue with each of the maximal Γ-limit quotients in parallel, so we omit their index, and denote the maximal Γ-limit quotient of G we continue with by R. Suppose that R = H_{1} ∗ … H_{ℓ} ∗ F_{g_{1}} be a factorization of R, where each of the H_{i}’s is a freely-indecomposable non-cyclic subgroup of R and F_{g_{1}} is a free group. Let r_{1}^{1}, …, r_{m_{1}}^{1} ∈ R be a generating set of H_{1}, r_{1}^{2}, …, r_{m_{2}}^{2} be a generating set of H_{2} etc. . By lemma 1.23 the sets of (proper) shortening quotients of the freely-indecomposable generalized Γ-limit groups H_{1}, …, H_{ℓ} contain maximal elements (with respect to the partial order defined above) and by lemma 1.24 there are only finitely many equivalence classes of maximal (proper) shortening quotients of each of the Γ-limit groups H_{1}, …, H_{ℓ}. For i = 1, …, ℓ let M_{1}^{i}, …, M_{k_{i}}^{i} be a collection of representatives of equivalence classes of maximal (proper) shortening quotients in SQ(H_{i}, r_{1}^{i}, …, r_{m_{i}}^{i}), and let η_{j}^{i} : H_{i} → M_{j}^{i} be the canonical projection maps.

We define the Makanin-Razborov diagram of G iteratively. We start by mapping G into its finite collection of maximal Γ-limit quotients, and continue with each of the maximal Γ-limit quotients (which we denote R) in parallel. We continue by factoring R into its freely-indecomposable factors H_{1}, …, H_{ℓ} and the free factor F_{g}. From each of the factors H_{i} we associate k_{i} directed edges, starting at H_{i} and terminating at the maximal (proper) shortening quotient M_{j}^{i}. To each such directed edge we associate the canonical quotient η_{j}^{i}. Note that we do not proceed from the free factor F_{g_{1}}.

We proceed iteratively. We factor each of the M_{j}^{i}’s into freely-indecomposable factors and associate with each such factor representatives for its equivalence classes of maximal (proper) shortening quotients. Since each (proper) shortening quotient of a Γ-limit group is a proper quotient of that Γ-limit group, and each sequence of properly decreasing sequence of Γ-limit groups terminates by theorem 1.12, the construction of the Makanin-Razborov diagram terminates after finitely many steps. Finally, the Makanin-Razborov diagram of a f.g. group encodes all the homomorphisms from it into a given torsion-free hyperbolic group.

Theorem 1.26. Let G be a f.g. group. All the homomorphisms h : G → Γ are given by compositions of modular automorphisms of the Γ-limit groups in the diagram with the canonical maps from the Γ-limit groups into their maximal (proper) shortening quotients and finally with either embeddings of a Γ-limit group in the diagram into Γ, or general homomorphisms (”substitutions”) of the terminal free groups that appear in the diagram into Γ.

The (canonical) Makanin-Razborov diagram associated with a f.g. group, encodes all the homomorphsims from that f.g. group into the torsion-free hyperbolic group Γ. Some specific subdiagrams of it can be viewed as a criteria for a general f.g. group to be a Γ-limit group.

Definition 1.27. A subdiagram of the Makanin-Razborov diagram in which we choose a unique maximal shortening quotient R of G, and for each free factor H_{i} of the limit group R we choose a unique edge connecting H_{i} to one of its maximal (proper) shortening quotients, and proceed iteratively choosing only one maximal (proper) shortening quotient at each stage, is called a Makanin-Razborov resolution.

To present a criteria for a f.g. group to be a Γ-limit group we need to show the existence of special type of Makanin-Razborov resolutions which we call strict Makanin-Razborov resolutions.

Definition 1.28. Let R be a freely-indecomposable Γ-limit group. We say that a (proper) shortening quotient S of R is a strict shortening quotient if:

(i) The subgroups generated by each non-CMQ, non-abelian vertex group together with centralizers of edge groups connected to it in the graph of groups obtained from the abelian JSJ of R by replacing each abelian vertex group by the direct summand containing the edge groups connected to it, and the abelian edge groups in the abelian JSJ decomposition of R are mapped monomorphically into the (proper) shortening quotient S by the canonical map η : R → S.

(ii) each CMQ subgroup of R is mapped to a non-abelian subgroup of S by the canonical map η, and each boundary element of a CMQ subgroup of R is mapped to a non-trivial element in S by η.

(iii) Let A be an abelian vertex group in the JSJ decomposition of R, and let A_{1} < A be the subgroup generated by all edge groups connected to the vertex stabilized by A. Then A_{1} is mapped monomorphically into S by the canonical map η.

A Makanin-Razborov resolution is called strict if all the maximal shortening quotients appear in it are strict shortening quotients, and the terminal freely indecomposable non-cyclic groups in the resolution can be embedded into the torsion-free hyperbolic group Γ.

Finally, the existence of strict Makanin-Razborov resolutions is a criteria for a f.g. group to be a Γ-limit group. We first show that a Γ-limit group admits a strict Makanin-Razborov resolution.

Proposition 1.29. Let R be a Γ-limit group. Then the (canonical) Makanin-Razborov diagram of R contains a strict Makanin-Razborov resolution.

Proof: Identical to the proof of proposition 5.10 in [Se1].

□

Proposition 1.29 shows that a Γ-limit group admits a strict Makanin-Razborov resolution. To state a criteria for a f.g. group to be a Γ-limit group we need to define an analogue of a strict Makanin-Razborov resolution in the general context of f.g. groups.

Definition 1.30. Let G be a f.g. group, and let:

G = G_{0}⟶^{ν_{0}}G_{1}⟶^{ν_{1}}G_{2}⟶^{ν_{2}} … ⟶^{ν_{m−2}}G_{m−1}⟶^{ν_{m−1}}G_{m}

be a resolution of G, where each factor in a free decomposition of the terminal group G_{m} can be embedded in Γ. We say that the given resolution of G is a strict MR resolution if the epimorphisms ν_{i} have the following properties.

First, we start with a (possible) free factorization of G, G = G^{1} ∗ … ∗ G^{n} ∗ F^{s}, where F^{s} is a free subgroup of G. Each of the factors G^{j} of G = G_{0} is mapped by the epimorphism ν_{0} : G → G_{1} onto the factor Q^{j} in a free factorization G_{1} = Q^{1} ∗ … ∗ Q^{n} of G_{1}. We further assume that each G^{j} can either be embedded in Γ and G^{j} is mapped isomorphically onto the factor Q^{j}, or it admits a non-trivial abelian splitting Λ_{G^{j}} with the following properties:

(i) each abelian edge group in Λ_{G^{j}} is a maximal abelian subgroup in at least one of the vertex groups it is connected to.

(ii) ν_{0} maps each of the subgroups generated by a non-QH (quadratically hanging), non-abelian vertex groups and the centralizers of the edges connected to it in the graph of groups obtained from the given abelian splitting by replacing each abelian vertex group with the direct summand containing the edge groups connected to it, and each of the abelian edge groups in Λ_{G^{j}} monomorphically into Q^{j}.

iii) ν_{0} maps each QH vertex group in Λ_{G^{j}} into a non-abelian subgroup of Q^{j}. (iv) every abelian vertex group in Λ_{G^{j}} is non-cyclic free abelian, and if A is

an abelian vertex group in Λ_{G^{j}}, and A_{1} < A is the subgroup generated by all edge groups connected to the vertex stabilized by A in Λ_{G^{j}}, then A_{1} is mapped monomorphically into Q^{j} by the map ν_{0}.

Finally, we assume that the epimorphisms ν_{i} associated with the next levels of the resolution of G satisfy similar conditions to the ones listed for ν_{0}, and the resolution terminates when the target group admits a free decomposition in which each of the factors can be embedded into the hyperbolic group Γ.

Note that a strict Makanin-Razborov resolution of a Γ-limit group R is a strict MR resolution of R, so by proposition 1.29 a Γ-limit group admits a strict MR resolution. Theorem 1.31 shows that this is also a sufficient condition for a f.g. group to be a Γ-limit group.

Theorem 1.31 (cf. ([Se1],5.12)). A f.g. group G is a Γ-limit group if and only if it admits a strict MR resolution.

Proof: The argument we use is a modification of the argument used over free groups ([Se1],5.12).

Let:

G = G_{0}⟶^{ν_{0}}G_{1}⟶^{ν_{1}}G_{2}⟶^{ν_{2}} … ⟶^{ν_{m−2}}G_{m−1}⟶^{ν_{m−1}}G_{m}

be a strict MR-resolution of a f.g. group G over the torsion-free hyperbolic group Γ, and let {Λ_{G_{i}}} be the cyclic splittings associated with each of the subgroups G_{i}. We need to show the existence of sequences of modular automorphsims {φ_{i}(n) ∈ Mod(G_{i})} for i = 0, …, m − 1, and embeddings of each of the non-cyclic freelyindecomposable factors of the terminal group G_{m} into Γ, and maps of the terminal free factor in G_{m} into Γ, that we denote τ(n), so that the limit group corresponding to the sequence of homomorphisms:

{h_{n} : G → Γ | h_{n} = τ(n)ν_{m−1}φ_{m−1}(n)ν_{m−2}φ_{m−2}(n) … ν_{1}φ_{1}(n)ν_{0}φ_{0}(n)}

is the group G itself.

To construct the homomorphisms τ(n) of the terminal group G_{m}, we fix embeddings of each of the non-cyclic, freely-indecomposable factors of G_{m}, and pick a couple of elements a, b ∈ Γ, that generate a free quasi-convex subgroup in Γ. We define τ(n), by conjugating each of the fixed embeddings of the non-cyclic, freelyindecomposable factors of G_{m} by elements w_{i}(a, b), and map a free basis of the free factor of G_{m} into elements w_{j}(a, b), so that the length of the elements w_{i}, w_{j} grows fast with n, and the elements w_{i}, w_{j} satisfy a (small cancellation) C′(\frac{1}{n}) condition. If none of the cyclic splittings Λ_{G_{i}} contains a QH vertex groups, we may pick the automorphisms {φ_{i}(n)} to be an increasing sequence of Dehn twists corresponding to the edges in the cyclic splittings Λ_{G_{i}}. In the presence of QH vertex groups we need the following technical lemma.

Lemma 1.32. Let Q be the fundamental group of a (possibly punctured) surface S_{Q} of Euler characteristic at most −2. Let μ : Q → Γ be a homomorphism and suppose Q is mapped into a non-abelian subgroup of Γ and the image of every boundary component of Q is non-trivial. Then either:

(i) there exists a separating s.c.c. γ ⊂ S_{Q} such that γ is mapped non-trivially into Γ, and the image in Γ of the fundamental groups of each of the connected components obtained by cutting S_{Q} along γ is non-abelian.

(ii) there exists a non-separating s.c.c. γ ⊂ S_{Q} such that γ is mapped nontrivially into Γ, and the image of the fundamental group of the connected component obtained by cutting S_{Q} along γ is non-abelian.

Proof: Identical to the free group case ([Se1],5.13).

□

By recursively applying lemma 1.32, for each surface S_{Q_{j}} corresponding to a QH-vertex group in the cyclic splitting Λ_{G_{m−1}}, we can find a finite set of s.c.c. on S_{Q_{j}}, so that each connected component of the surface obtained by cutting S_{Q_{j}} along this family of s.c.c. has Euler characteristic -1, and the fundamental group of each of these connected components is mapped onto a two generated non-abelian subgroup of Γ, i.e., it is either mapped monomorphically into a free subgroup of Γ, or it is mapped onto a freely indecomposable subgroup of Γ. Since the fundamental group of each of the connected components is mapped either monomorphically into Γ, or into a freely indecomposable subgroup of Γ, given any finite collection of s.c.c. on the various surfaces associated with the QH vertex groups in Λ_{G_{m−1}}, if we extend each the cyclic splittings Λ_{G_{m−1}} by further splitting the QH-vertex groups along the families of s.c.c. chosen according to lemma 1.32, and perform high powers of Dehn twists along the edges of the obtained cyclic decomposition, the given s.c.c. from our (fixed) finite collection will be mapped to non-trivial elements in Γ. Hence, after performing a high power of Dehn twists, it is possible to find a new collection of disjoint, non-homotopic, non-boundary-parallel s.c.c. on each of the surfaces associated with QH vertex groups in Λ_{G_{m−1}}, so that each of the connected components obtained by cutting the surfaces along these s.c.c. has Euler characteristic -1, and the fundamental group of each such connected component is mapped onto a free quasi-convex subgroup of rank 2 in Γ. Therefore, the argument used to prove theorem 5.12 in the absence of QH-subgroups generalizes to prove that G_{m−1} is a Γ-limit group. Continuing iteratively to the upper levels of the strict MR resolution, we conclude that G_{0} = G is a Γ-limit group.

□

As in section 8 in [Se1], given a f.g. group G =< x_{1}, …, x_{n}, a_{1}, …, a_{k} >, and a torsion-free hyperbolic group Γ =< γ_{1}, …, γ_{k} >, we say that a homomorphism h : G → Γ is a restricted homomorphism, if h(a_{i}) = γ_{i}, for 1 ≤ i ≤ k. So far, given a f.g. group G and a torsion-free hyperbolic group Γ, we have constructed a Makanin-Razborov diagram that encodes all the homomorphisms from G to Γ. The study of the collection of all homomorphisms from G to Γ, can be easily generalized to study the collection of restricted homomorphisms from G to Γ in the same way it was generalized in section 8 of [Se1]. Similarly, to encode the collection of all the restricted homomorphisms from G to Γ, we associate with G a restricted Makanin-Razborov diagram, constructed in a similar way to our construction of the (non-restricted) Makanin-Razborov diagram.

The understanding of the structure of (F_{k}) limit groups, enable us to show that every residually-free group is the sub-direct product of finitely many limit groups ([Se1],7.5). Given a torsion-free hyperbolic group Γ, we say that a f.g. group G is residually-Γ, if for each non-trivial element g ∈ G, there exists a homomorphism h : G → Γ, for which h(g) ≠ 1.

Theorem 1.33. A f.g. group G is residually-Γ, if and only if it is a sub-direct product of finitely many Γ-limit groups.

Proof: Identical to the proof of claim 7.5 in [Se1].

□

Studying sets of solutions to systems of equations over a torsion-free hyperbolic group Γ, and their associated (restricted) Γ-limit groups, we continue as in [Se1] to study parametric system of equations. Equivalently, given a f.g. group G(x, p) and a torsion-free hyperbolic group Γ, we need to encode the collections of restricted homomorphisms {h : G(x, p, a) → Γ | h(p) = p_{0}}. In parallel with what we did in sections 9-11 of [Se1], with a f.g. group G(x, p, a) and the torsionfree hyperbolic group Γ we associate a finite collection of graded Γ-limit groups, L_{1}(x, p, a), …, L_{s}(x, p, a), and with each graded Γ-limit group L_{i}(x, p, a) we associate a graded Makanin-Razborov diagram, precisely as we did in the case of an (F_{k}) limit groups. Given the graded Makanin-Razborov associated with a Γ-limit group, we can further associate with it a singular locus, as we did in section 11 of [Se1], and as in section 12 in [Se1], the entire analysis of graded Γ-limit groups can be generalized to the multi-graded case.

§2. Formal Solutions

In the first section we generalized the structure theory developed in [Se1] for analyzing sets of solutions to systems of equations defined over a free group, in order to study sets of solutions to systems of equations defined over a torsion-free hyperbolic group.

In [Se2], in order to analyze general sentences and predicates defined over a free group, we used completions, closures, formal solutions and formal limit groups. In this section we generalize these notions and constructions in the context of a general torsion-free hyperbolic group, to finally obtain a generalization of Merzlyakov’s theorem for sentences and predicates defined over a hyperbolic group.

We start this section with a special case of our generalization of Merzlyakov’s theorem, which is very similar to the original Merzlyakov’s theorem (cf. theorem 1.2 in [Se2]). The proof is essentially identical to the free group case.

Proposition 2.1. Let Γ =< a_{1}, …, a_{k} > be a non-elementary torsion-free hyperbolic group, let w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 be a system of equations over Γ, and let v_{1}(x, y, a), …, v_{r}(x, y, a) be a collection of words in the alphabet {x, y, a}. Suppose that the sentence:

∀y ∃x w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 ∧ v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1

is a truth sentence over Γ. Then there exists a formal solution x = x(y, a) so that each of the words w_{j}(x(y, a), y, a) is the trivial word in the free product Γ ∗ F_{y}, where F_{y} is the free group generated by the universal variables y, and the sentence:

∃y v_{1}(x(y, a), y, a) ≠ 1, …, v_{r}(x(y, a), y, a) ≠ 1

is a truth sentence in Γ. Furthermore, if the words w_{1}, …, w_{s} and v_{1}, …, v_{r} are coefficient-free (i.e., they are words only in the variables x and y and not in the coefficients a), then the formal solution x = x(y, a) can be taken to be coefficient-free, i.e., x = x(y).

Theorem 2.1 generalizes Merzlyakov’s theorem in case the universal variables y, belong to the entire affine set Γ^{ℓ}, and are not restricted to some variety. As in analyzing sentences over a free group, to get a generalization of Merzlyakov’s theorem to the case in which the universal variables are restricted to some variety, we need to use completions and closures.

Let Γ be a torsion-free hyperbolic group, and Rlim(y, a) a restricted Γ-limit group. As in [Se2] (proposition 1.10), we may replace the Makanin-Razborov diagram associated with Rlim(y, a) with its (canonical) strict Makanin-Razborov diagram, i.e., in a diagram in which every resolution is a strict resolution. Given a restricted Γ-limit group, the notion of a well-structured resolution of it ([Se2], definition 1.11), directly generalizes to the context of torsion-free hyperbolic groups, and so is the completion of a well-structured resolution ([Se2], definition 1.12) and its basic properties (see [Se2], lemma 1.14).

Definition 2.2 (cf. ([Se2],1.16-1.17)). Let Γ =< a_{1}, …, a_{k} > be a torsion-free hyperbolic group, Rlim(y, a) a (restricted) Γ-limit group, Res(y, a) a well-structured resolution of Rlim(y, a), and Comp(Res)(z, y, a) the completion of the resolution Res(y, a). Let Γ ∗ H_{1} ∗ … ∗ H_{m} ∗ F_{s} be the terminal Γ-limit group of the resolution Res(y, a), where Γ is the coefficient group, F_{s} is a free group of rank s, and H_{1}, …, H_{m} are freely indecomposable groups that are isomorphic to subgroups of Γ.

A closure of the resolution Res(y, a), denoted Cl(Res)(s, z, y, a), is a wellstructured resolution defined over Γ, that is obtained from the completion, Comp(Res)(z, y, a), by the following modifications.

(i) As in the case of F_{k}-limit groups ([Se2],1.16), replacing each of the (free) abelian vertex groups that appear in the various abelian decompositions associated with the completion, Comp(Res)(z, y, a), by (free) abelian supergroups that contain the original ones as subgroups of finite index.

(ii) replacing each of the factors H_{j} by a freely-indecomposable group V_{j} with an associated embedding ν_{j} : H_{j} → V_{j}, and V_{j} is isomorphic to a subgroup of Γ.

We say that a finite set of closures of the well-structured resolution Res(y, a), Cl_{1}(Res)(s, z, y, a), …, Cl_{r}(Res)(s, z, y, a) is a covering closure, if every specialization (y_{0}, a) that factors through the resolution Res(y, a), can be completed to a specialization (s_{0}, z_{0}, y_{0}, a) that factors through at least one of the closures Cl_{i}(Res)(s, z, y, a)

Given the notions of a closure and a covering closure of a well-structured resolution over the torsion-free hyperbolic group Γ, we are finally able to obtain the existence of formal solutions associated with a general true AE-sentence defined over Γ.

Theorem 2.3 (cf. ([Se2],1.18)). Let Γ =< a_{1}, …, a_{k} > be a non-elementary torsion-free hyperbolic group, let Rlim(y, a) be a restricted Γ-limit group, and let V_{y} be its associated variety. Let Res(y, a) be a well-structured resolution of the restricted Γ-limit group Rlim(y, a), and let Comp(Res)(z, y, a) be the completion of the resolution Res(y, a) with a corresponding completed Γ-limit group Comp(Rlim)(z, y, a).

Let w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 be a system of equations over Γ, and let v_{1}(x, y, a), …, v_{r}(x, y, a) be a collection of words in the alphabet {x, y, a}. Suppose that the sentence:

∀y ∈ V_{y} ∃x w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1∧
∧ v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1

is a truth sentence over Γ.

Then there exists a covering closure: Cl_{1}(Res)(s, z, y, a), …, Cl_{q}(Res)(s, z, y, a), and for each index i, 1 ≤ i ≤ q there exists a formal solution x_{i}(s, z, y, a), so that each of the words w_{j}(x_{i}(s, z, y, a), y, a) is the trivial word in the restricted limit group corresponding to the i-th closure Cl_{i}(Rlim)(s, z, y, a). In addition, for each index i there exists a specialization (s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, a) that factors through the i-th closure Cl_{i}(Res)(s, z, y, a), so that for every index j:

v_{j}(x_{i}(s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, a), y_{0}^{i}, a) ≠ 1

(in Γ).

Furthermore, if the Γ-limit group Rlim(y, a) can be written as Rlim(y, a) = Rlim(y) ∗ Γ, Rlim(y) is not abelian, and the words:

w_{1}(x, y, a), …, w_{s}(x, y, a), v_{1}(x, y, a), …, v_{r}(x, y, a)

are coefficient-free, then the formal solutions can be taken to be coefficient-free, i.e., x = x_{i}(u, s, z, y), defined over a group of the form Cl_{i}(Res)(s, z, y, a) ∗ U_{1} ∗ … ∗ U_{r}, where the subgroups U_{j} are non-cyclic, freely indecomposable, and isomorphic to subgroups of Γ.

Having constructed formal solutions associated with a truth AE sentence and a well-structured resolution defined over a torsion-free hyperbolic group Γ, we associate with a general AE sentence and a well-structured resolution defined over Γ, a canonical collection of formal Γ-limit groups and their associated formal Makanin-Razborov diagrams, precisely as we did in section 2 of [Se2], so that the collection of formal resolutions in the formal Makanin-Razborov diagrams encodes the entire collection of formal solutions associated with the well-structured resolution and the given AE sentence. Given an AE predicate and a graded well-structured resolution defined over Γ, we construct finitely many graded formal Γ-limit groups, and their associated graded formal Makanin-Razborov diagrams, precisely as we did in section 3 of [Se2].

§3. A Bound on the Number of Rigid and Solid Solutions

In the first section we have generalized the structure theory developed in [Se1] for F_{k}-limit groups, to Γ-limit groups, for a general torsion-free hyperbolic group Γ. In the second section, we have generalized the results of [Se2], to prove the existence of formal solutions associated with a true AE sentence defined over a general torsionfree hyperbolic group, and further collected all such formal solutions in (graded) formal Γ-limit groups.

In this section we generalize the results of [Se3] to general torsion-free hyperbolic groups. We show that given a torsion-free hyperbolic group Γ, and a rigid (solid) Γ-limit group, Rgd(x, p, a)(Sld(x, p, a)), there exists a global bound (independent of the value of the defining parameters) on the number of rigid (strictly solid families of) solutions associated with an arbitrary value of the defining parameters. As in [Se3] we prove the existence of such a global bound in two steps. Following section 1 of [Se3], we first study the combinatorial types of rigid and solid solutions, and prove the existence of a global constant R, for which every rigid or shortest strictly solid solution is R-AP covered. Then we use this combinatorial bound, to get a global bound on the number of rigid or strictly solid families of solutions.

Let S be the Cayley graph of a rigid graded Γ-limit group Rgd(x, p, a) with respect to the generating system Rgd(x, p, a) =< x, p, a >, and let X be the Cayley graph (tree) of the torsion-free hyperbolic group Γ with respect to some fixed generating set Γ =< a_{1}, …, a_{k} >. Clearly, a homomorphism h : Rgd(x, p, a) → Γ corresponds to a natural equivariant map τ : S → X, where each edge in S is mapped to a (possibly degenerate) geodesic path in X.

Definition 3.1 (cf. ([Se3],1.1)). Let B_{R} be the ball of radius R in the Cayley graph S of Rgd(x, p, a). We say that a homomorphism h : Rgd(x, p, a) → Γ is R-AP -covered, if the union of the R-neighborhoods of the images in X of the edges labeled by either an element of {a} or an element of {p} in B_{R} covers the entire image in X of the ball B_{1}.

As in [Se3], to define and control the combinatorial types of rigid solutions we need the following basic theorem.

Theorem 3.2. Let Rgd(x, p, a) be a rigid Γ-limit group. There exists a constant R_{0} so that every rigid homomorphism h : Rgd(x, p, a) → Γ is R_{0}-AP -covered.

Proof: Suppose that there is no such constant R_{0}. Let {h_{n} | h_{n} : Rgd(x, p, a) → Γ} be a sequence of rigid homomorphisms, so that for every integer n, the n-th homomorphism in the sequence, h_{n}, is not n-AP -covered. By ([Pa],2.3), from the sequence of rigid homomorphisms {h_{n}} one can extract a subsequence converging in the Gromov-Hausdorff topology into an action of Rgd(x, p, a) on a (pointed) real tree (Y, y_{0}). The action of Rgd(x, p, a) on the real tree Y satisfies the conclusions of lemma 1.3, hence, it is in particular a stable action. If K_{∞} denotes the kernel of the action, then L_{∞} = Rgd(x, p, a)/K_{∞} is a Γ-limit group.

Let Y_{AP} ⊂ Y be the convex hull of the images of the base point y_{0} under the action of the subgroup AP =< a, p > of our rigid Γ-limit group Rgd(x, p, a). Clearly, either there exists a non-degenerate segment J ⊂ Y which is not in the orbit of Y_{AP} in Y, or the orbit of every non-degenerate segment in Y contains a non-degenerate subsegment which is in the subtree Y_{AP}.

If there exists a non-degenerate segment J ⊂ Y which does not contain a nondegenerate subsegment that is in the orbit of Y_{AP}, then (by the argument that was used in proving theorem 1.2 in [Se3]) there exists a graph of groups Λ_{L_{∞}}, with fundamental group L_{∞}, for which the subgroup AP < L_{∞} is contained in a proper connected subgraph of groups Λ′ ⊂ Λ_{L_{∞}}.

Now, since AP is contained in a proper connected subgraph of groups Λ′ of a graph of groups Λ_{L_{∞}} with fundamental group L_{∞}, and since the real tree Y was constructed from the homomorphisms {h_{n} : Rgd(x, p, a) → Γ}, for large enough n, the homomorphisms {h_{n}} are flexible homomorphisms, a contradiction to our assumption of the homomorphisms {h_{n} : Rgd(x, p, a) → Γ} being rigid.

By the argument given above, for the rest of the argument we may assume that the orbit of Y_{AP} in Y intersects any non-degenerate segment in the real tree (Y, y_{0}) in a non-degenerate segment. Furthermore, given any non-degenerate segment J in the real tree Y, the segment is covered in a finite time (depending only on the segment J) by the images of the edges (y_{0}, a_{i}(y_{0})) and (y_{0}, p_{j}(y_{0}), where the elements a_{i} are the generators of the coefficient group Γ, and the elements p_{j} are the given generators of the parameter subgroup P.

In case every non-degenerate segment in the real tree Y intersects the orbit of the tree Y_{AP} in a non-degenerate subsegment, we continue inductively by analyzing the actions of each of the point and edge stabilizers on corresponding real trees as in the proof of theorem 1.2 in [Se3], to finally conclude that there exists a graph of groups Θ with fundamental group L_{∞}, for which the subgroup AP is contained in the fundamental group of a proper subgraph Θ′ of Θ, a contradiction to the assumption on the rigidity of the sequence of homomorphisms {h_{n}}. However, to obtain such contradiction, it is necessary to show that an induction process, similar to the one used in the proof of theorem 1.2 in [Se3], terminates after finitely many steps.

Let Λ be the graph of groups associated with the action of the limit group L_{∞} on the real tree Y. If the graph of groups Λ gives rise to a non-trivial free decomposition of L_{∞}, we continue the induction process with each of the free factors in parallel, noting that a free factor in a non-trivial free decomposition of of L_{∞} is a proper quotient of L_{∞}.

Suppose that all the edge stabilizers in the graph of groups Λ are non-trivial. With the graph of groups Λ we naturally associate a modular group, that we denote Mod(Λ), that is generated by Dehn twists along edge groups in Λ, mapping class groups associated the QH vertex groups in Λ, and the subgroups of automorphisms of abelian vertex groups in Λ that fix (elementwise) the edge groups connected to those vertices. We continue by applying the shortening procedure Using the modular group, Mod(Λ). With the given sequence of homomorphisms {h_{n}}, and the modular group Mod(Λ), we associate a finite collection of maximal shortening quotients that are all quotients of L_{∞}. Let L_{1} be one of the maximal shortening quotients, so that infinitely many of the homomorphisms {h_{n}}, can be written in the form: h_{n} = h_{n}^{1} ∘ϕ_{n}, where ϕ_{n} ∈ Mod(Λ) and h_{n}^{1} is the shortest in its class under the action of the modular group Mod(Λ). The maximal shortening quotient L_{1} is a quotient of the limit group L_{∞}. If L_{1} is a proper quotient of L_{∞} we continue to the next step of our inductive process with the limit group L_{1}. Hence, in the sequel, we may assume that L_{1} is isomorphic to L_{∞}.

From the sequence of homomorphisms {h_{n}^{1}} that factor through L_{1} and are the shortest in their modular class, we can extract a subsequence that convergence into a faithful action of L_{1} = L_{∞} on some real tree Y_{1}. With this action, there is an associated graph of groups Λ − 1 with fundamental group L_{1}. If Λ_{1} gives rise to a non-trivial free product of L_{1}, we continue with each of the factors in this free decomposition, which is a proper quotient of L_{1} = L_{∞}. Hence, we may assume that all the edge groups in Λ_{1}, and in the graph of groups λ associated with the action of L_{∞} on the real tree Y, are non-trivial.

First, we modify the graphs of groups Λ and Λ_{1}, according to lemma 1.7, to get graphs of groups in which all non-cyclic abelian groups are elliptic (we still denote the obtained graphs of groups Λ and Λ_{1}). If all the edge groups in Λ are elliptic in Λ_{1} and vice versa, then from the graphs of groups Λ and Λ_{1}, we obtain a common refinement graph of groups with fundamental group L_{1}, that we denote Δ_{1}. If Δ_{1} gives rise to a non-trivial free product, we continue with each of the factors in parallel, and each factor is clearly a proper quotient of the Γ-limit group L_{1}. If Δ_{1} does not give rise to a non-trivial free product of L_{1}, then Δ_{1} is a proper refinement of both graphs of groups Λ and Λ_{1}. With Δ_{1} we associate a modular group of automorphisms of L_{1}, that we denote Mod(Δ_{1}). We continue by further shortening the homomorphisms {h_{n}^{1}}, using the modular group Mod(Δ_{1}), and obtain an (infinite) subsequence that converge into an action of a Γ-limit group L_{2} on a real tree Y_{2}. If L_{2}, which is a quotient of L_{∞}, is isomorphic to it, and the graph of groups Λ_{2}, associated with the action of L_{2} on Y_{2}, is compatible with Δ_{1} (i.e., every edge group in Δ_{1} is elliptic in Λ_{2} and vice versa), we construct a common refinement of Λ_{2} and Δ_{1}, that we denote Δ_{2}, and repeat the process. Since the complexity of the obtained refinements is increasing, and by acylindrical accessibility the complexity of an abelian splitting of L_{∞} is globally bounded, this process of properly refining the abelian decomposition of L_{∞}, terminates after finitely many steps.

Let E_{1} be an edge in Λ, and E_{2} be an edge in Λ_{1}. If the edge stabilizer of E_{1} is elliptic in Λ_{1} and the edge stabilizer of E_{2} is hyperbolic in Λ (or vice versa), then by theorem 2.1 in [Ri-Se2], then from the combination of the graphs of groups Λ and Λ_{1} it is possible to extract a non-trivial free decomposition of L_{1} = L_{∞}. Hence, in case such two edges E_{1} and E_{2} do exist, we continue to the next step of the inductive process with each of the factors in the non-trivial free decomposition extracted from Λ and Λ_{1}.

Finally, we may assume that if E_{1} is an edge in Λ and E_{2} is an edge in Λ_{1}, then their stabilizers are either elliptic-elliptic or hyperbolic-hyperbolic. We start analyzing this case, by first applying the JSJ machine presented in section 4 of [Ri-Se2] to analyze the hyperbolic-hyperbolic edge stabilizers. The outcome of the JSJ machine, is either a non-trivial free decomposition of L_{1} = L_{∞}, in which case we continue to the next step of the inductive process with each of the free factors in parallel. Otherwise, the JSJ machine produces a quadratic decomposition similar to the one described in theorem 4.21 in [Ri-Se2]. In this last case, we continue by refining the quadratic decomposition, obtained by the JSJ machine, using the elliptic-elliptic splittings in the graphs of groups Λ and Λ_{1}, to finally obtain an abelian decomposition of L_{1}, that we denote Δ_{1}. If Δ_{1} gives rise to a non-trivial free decomposition of L_{1} = L − ∞, we continue to the next step of the inductive process with each of the factors. Otherwise, we associate with Δ_{1} a modular group, that is necessarily bigger than the modular group associated with the original graph of groups Λ, and apply the shortening procedure to obtain an (infinite) subsequence that converge into an action of a Γ-limit group L_{2} on a real tree Y_{2}. If L_{2}, which is a quotient of L_{∞}, is isomorphic to it, we continue according to the various cases described above. Since each time in which a non-trivial free decomposition is not obtained, the complexity of the refined graph of groups Δ_{n} is strictly bigger than the complexity of the previous graph of groups, and by acylindrical accessibility the complexity of an abelian splitting of L_{∞} is globally bounded, this process of properly refining the abelian decomposition of L_{∞}, terminates after finitely many steps. Hence, after finitely many steps, we the inductive process replaces the Γ-limit group L_{∞} by a proper quotient of it. Since by theorem 1.12 every decreasing sequence of Γ-limit groups terminates after finitely many steps, the inductive process we’ve constructed terminates after finitely many steps.

□

In a similar way to rigid homomorphisms of rigid Γ-limit groups we analyze solid homomorphisms of solid Γ-limit groups. To state the analogues theorem for solid homomorphisms we will need the notions of solid family of specializations of a solid Γ-limit group, and strictly solid family of a solid Γ-limit group. Those are defined in ([Se3],1.3-1.5) for solid F_{k}-limit groups. The definition for solid Γ-limit groups is identical, so we don’t repeat the definition of these notions.

Definition 3.3. Let Sld(x, p, a) be a solid Γ-limit group, let S be the Cayley graph of the solid Γ-limit group Sld(x, p, a) with respect to the generating set Sld(x, p, a) =< x, p, a >, and let X be the Cayley graph of Γ with respect to the generating set Γ =< a >. With each abelian vertex group A_{i} in the graded abelian JSJ decomposition of the solid limit group Sld(x, p, a), we associate a fixed retract r_{i} : A_{i} → A_{i}^{1}, where A_{i}^{1} is the direct summand of of A_{i} that contains the subgroup generated by the edge groups connected to the vertex stabilized by A_{i} as a subgroup of finite index. Clearly, the collection of retracts {r_{i}} extends to a retract r : Sld(x, p, a) → Sld(x, p, a) which restricts to the identity on all the non-abelian vertex groups, and to the retract r_{i} on the abelian vertex group A_{i}.

We say that a solid homomorphism h : Sld(x, p, a) → Γ is among the shortest in its solid family, if h = ĥ ∘ r for some homomorphism ĥ : Sld(x, p, a) → Γ, and the image of the generating set of Sld(x, p, a) in the free Γ, is the shortest among all homomorphisms h_{1} : Sld(x, p, a) → Γ that are in the same solid family of the homomorphism h, and for which there exists some homomorphism ĥ_{1} for which h_{1} = ĥ_{1} ∘ r.

In the case of a solid limit group we are able to bound the combinatorial types of strictly solid solutions which are among the shortest in their corresponding solid families.

Theorem 3.4. Let Sld(x, p, a) be a solid Γ-limit group. There exists a constant R_{0} so that every strictly solid homomorphism h : Sld(x, p, a) → Γ which is among the shortest in its solid family, is R_{0}-AP -covered.

Proof: Given the argument used to prove the existence of a global bound in the rigid case (theorem 3.2), the modification to the solid case is identical to the modification used over a free group, presented in the proof of theorem 1.7 in [Se3].

□

So far we have shown that for a rigid (solid) Γ-limit group Rgd(x, p, a) (Sld(x, p, a)) there exists a constant R_{0}, so that all the rigid homomorphisms h : Rgd(x, p, a) → Γ (strictly solid homomorphisms h : Sld(x, p, a) → Γ which are the shortest in their solid family) are R_{0}-AP -covered. As in section 2 of [Se3], the existence of this bound on the combinatorial types of states of rigid and shortest strictly solid homomorphisms enable us to get a global bound on the number of possible distinct rigid homomorphisms h : Rgd(x, p, a) → Γ (strictly solid families of homomorphisms, h : Sld(x, p, a) → Γ) for any specialization of the defining parameters h(p) = p_{0}.

Theorem 3.5 (cf. ([Se3],2.3)). Let Rgd(x, p, a) be a rigid Γ-limit group. There exists a global bound b_{R}(Rgd(x, p, a)) for which for any particular value of the defining parameters p_{0}, there are at most b_{R} distinct rigid homomorphisms h : Rgd(x, p, a) → Γ satisfying h(p) = p_{0}.

Proof: Theorem 3.5 generalizes theorem 2.3 in [Se3], to rigid Γ-limit groups. The proof of theorem 2.3 in [Se3], uses the existence of a global constant R, for which every rigid homomorphism of a rigid limit group Rgd(x, p, a) is R-AP -covered, and the finite presentability of an F_{k}-limit group. The existence of a global constant R, for which every rigid homomorphism of a Γ-limit group is R-AP -covered, is proved in theorem 3.2. A Γ-limit group is not f.p. in general, but by the generalization of Guba’s theorem presented in theorem 1.22, a Γ-limit group is f.p. in the class of Γ-limit groups. Hence, the proof of theorem 3.5 follows by an identical argument to the one used to prove theorem 2.3 in [Se3].

□

In a similar way one can globally bound the number of strictly solid families of homomorphisms of a solid Γ-limit group. The proof is identical to the one presented for theorem 2.7 in [Se3].

Theorem 3.6 (cf. ([Se3],2.7)). Let Sld(x, p, a) be a solid Γ-limit group. For any particular value p_{0} of the defining parameters p, there are at most b_{S} distinct strictly solid families of homomorphisms h : Sld(x, p, a) → Γ satisfying h(p) = p_{0}.

Strictly solid families of specializations of a solid Γ-limit group Sld(x, p, a) were defined as those families of specializations that do not factor through completions of the resolutions in the graded Makanin-Razborov diagram of the Γ-limit group Sld(x, p, a) (definition 3.3). Theorem 3.6 bounds the number of strictly solid families of specializations of a solid Γ-limit group Sld(x, p, a) for any possible value p_{0}, of the defining parameters p. As in the free group case, we will need a similar global bound on the number of families of specializations of a solid Γ-limit group Sld(x, p, a), that do not factor through a covering closure (definition 2.2) of the resolutions that appear in the graded Makanin-Razborov diagram of the solid Γ-limit group Sld(x, p, a), for any possible value of the defining parameters p.

Definition 3.7 (cf. ([Se3],2.10)). Let Sld(x, p, a) be a solid Γ-limit group, and let:

GRes_{1}(x, p, a), …, GRes_{r}(x, p, a)

be the resolutions in its graded Makanin-Razborov diagram. Let:

Cl_{1}^{1}(s, x, p, a), …, Cl_{m_{1}}^{1}(s, x, p, a), …, Cl_{1}^{r}(s, x, p, a), …, Cl_{m_{r}}^{r}(s, x, p, a)

be a finite collection of graded closures of the graded resolutions: GRes_{1}(x, p, a), …, GRes_{r}(x, p, a). A specialization (x_{0}, p_{0}, a) of the solid Γ-limit group Sld(x, p, a) is called a strictly solid specialization with respect to the given closure if:

(i) for p = p_{0} the given closures form a covering closure of the (ungraded) resolutions associated with the specialization p_{0} (see definition 2.2).

(ii) the specialization (x_{0}, p_{0}, a) does not factor through any of the the given

closures. Note that a strictly solid solution with respect to the given closures is not necessarily strictly solid with respect to the completions of the resolutions GRes_{1}(x, p, a), …, GRes_{r}(x, p, a) (definition 1.5). An orbit of specializations of the solid Γ-limit group Sld(x, p, a) under the action of the graded modular group GMod(x, p, a) is called strictly solid family with respect to the given closures, if it contains a strictly solid specialization.

As in [Se3], in parallel with theorem 3.6, given a solid Γ-limit group Sld(x, p, a) and a closure of the resolutions that appear in its graded Makanin-Razborov diagram,, one can globally bound the number of strictly solid families of the solid Γ-limit group Sld(x, p, a) with respect to the given closure.

Theorem 3.8 (cf. ([Se3],2.11)). Let Sld(x, p, a) be a solid Γ-limit group, and let:

GRes_{1}(x, p, a), …, GRes_{r}(x, p, a)

be the resolutions in its graded Makanin-Razborov diagram. Let:

Cl_{1}^{1}(s, x, p, a), …, Cl_{m_{1}}^{1}(s, x, p, a), …, Cl_{1}^{r}(s, x, p, a), …, Cl_{m_{r}}^{r}(s, x, p, a)

be a finite collection of graded closures of the graded resolutions: GRes_{1}(x, p, a), …, GRes_{r}(x, p, a). There exists a constant b_{S}, so that for any particular value p_{0} of the defining parameters p, there are at most b_{S} distinct families of homomorphisms h : Sld(x, p, a) → F_{k} that are strictly solid with respect to the given closure, and satisfy h(p) = p_{0}.

Given the global bounds on the numbers of rigid and solid solutions, and theorem 1.22 from which one can deduce that a given Γ-limit group is f.p. in the class of Γ-limit groups, we can generalize the properties of the stratification of the set of the defining parameters associated with a given graded resolution presented in section 3 of [Se3]. In particular, the stratification associated with a graded limit group, or a graded resolution, contains finitely many strata, and each stratum is in the Boolean algebra of AE sets.

§4. An Iterative Procedure for Validation of a Sentence

In the first 3 sections we have generalized the results and notions presented in [Se1], [Se2] and [Se3], for studying varieties, sentences and predicates defined over a free group, to general torsion-free hyperbolic groups. In this paper we use these notions to generalize the iterative procedure for validation of an AE sentence defined over a free group, presented in [Se4], to AE sentences defined over a general torsion-free hyperbolic groups.

The definition of a well-separated resolution over a free group, presented in definition 2.2 of [Se4], generalized in a direct way to well-separated resolutions over a torsion-free hyperbolic group Γ. We further generalize the notion of a geometric subresolution presented in definition 3.1 of [Se4].

Definition 4.1. Let Res(t, y, a) be a a well-separated resolution over a torsion-free hyperbolic group Γ, and let Comp(Res)(u, t, y, a) be its completion. Let GSRes(g, y, a) be a resolution with the following properties:

(i) the resolution GSRes(g, y, a) is a well-separated resolution.

(ii) the resolution GSRes(g, y, a) is a completed resolution, i.e., the completion

of GSRes(g, y, a) is the resolution GSRes(g, y, a) itself. (iii) there exists a (geometric) embedding ν : GSRes(g, y, a) → Comp(Res)(u, t, y, a)

that maps the subgroup < y, a > of the resolution GSRes(g, y, a) onto the subgroup < y, a > of the completed resolution Comp(Res)(u, t, y, a) elementwise. In addition, the embedding ν has the following properties:

1) every QH subgroup in an abelian decomposition associated with one of the various levels of the resolution GSRes(g, y, a) is embedded geometrically into (a finite index subgroup of) a QH subgroup of Comp(Res)(u, t, y, a).

2) every abelian vertex group in an abelian decomposition associated with one of the levels of the resolution GSRes(g, y, a) is embedded into an abelian vertex group in one of the abelian decompositions associated with Comp(Res)(u, t, y, a).

3) every terminal non-cyclic, freely indecomposable factor of the geometric subresolution is embedded by ν into a terminal non-cyclic freely indecomposable of the ambient completion, Comp(Res)(u, t, y, a).

4) except for the terminal free groups and terminal freely-indecomposable factors dropped along the various levels of the geometric subresolution, the free and abelian decompositions associated with each level of the resolution GSRes(g, y, a) are the decompositions induced (using Bass-Serre theory) from the embedding ν and the free and abelian decompositions of Comp(Res)(u, t, y, a). Furthermore, the canonical maps between successive levels in the resolution GSRes(g, y, a) are the ones induced from the canonical maps between successive levels in the completion Comp(Res)(u, t, y, a).

We call the resolution GSRes(g, y, a) together with the embedding ν : GSRes(g, y, a) → Comp(Res)(u, t, y, a), a geometric subresolution of the (completion of the) resolution Res(t, y, a). The modular groups associated with a geometric subresolution are set to be the modular groups induced from those of the completed resolution Comp(Res)(u, t, y, a). In particular, the modular groups associated with each of the QH vertex groups in the abelian decompositions of GSRes(g, y, a), are set to be the modular groups of the corresponding QH vertex groups of Comp(Res)(u, t, y, a) into which they are embedded. Note that the completion, Comp(Res)(u, t, y, a), itself is a geometric subresolution of the (completion of the) resolution Res(t, y, a).

In section 3 of [Se4], while constructing the induced resolution, we have associated a complexity with any geometric subresolution of a well-separated resolution defined over a free group, a complexity that was later used in guaranteeing the termination of the iterative procedure for validation of an AE sentence. The notion of a geometric subresolution generalizes directly to well-separated resolutions defined over a torsion-free hyperbolic group. However, the complexity of such resolutions needs to be slightly modified (cf. definition 3.2 in [Se3]).

Definition 4.2. Let Res(t, a) be a well-separated completed resolution over a torsionfree hyperbolic group Γ, with (possibly) reduced modular groups associated with each of its various QH subgroups. Let Q_{1}, …, Q_{m} be the QH subgroups that appear in the completion Comp(Res)(t, y, a) and let S_{1}, …, S_{m} be the (punctured) surfaces associated with the reduced modular group associated with each of the QH vertex group. To each (punctured) surface S_{j} we may associate an ordered couple (genus(S_{j}), |χ(S_{j})|). We will assume that the QH subgroups Q_{1}, …, Q_{m} are ordered according to the lexicographical (decreasing) order of the ordered couples associated with their corresponding surfaces. Let rk(Res(t, a)) be the rank of the free group that is dropped along the resolution Res(t, a) (see definition 2.1 in [Se4]), let fact(Res(t, a)) be the number of freely-indecomposable, non-cyclic terminal (embedded) factors of the resolution Res(t, a), and let Abrk(Res(t, a)) be the sum of the ranks of the kernels of the mappings of (free) abelian groups that appear as vertex groups along the resolution Res(t, a) (see definition 1.15 in [Se4]).

We set the complexity of the resolution Res(t, a), denoted Cmplx(Res(t, a)), to be:

Cmplx(Res(t, a)) = (fact(Res(t, a)) + rk(Res(t, a)), (genus(S_{1}), |χ(S_{1})|), …

…, (genus(S_{m}), |χ(S_{m})|), Abrk(Res(t, a))).

On the set of complexities of completed resolutions with (possibly) reduced modular groups we can define a linear order. Let Res_{1}(t_{1}, a) and Res_{2}(t_{2}, a) be two completed resolutions with (possibly) reduced modular groups. We say that Cmplx(Res_{1}(t_{1}, a)) = Cmplx(Res_{2}(t_{2}, a)) if the tuples defining the two complexities are identical. We say that Cmplx(Res_{1})(t_{1}, a)) < Cmplx(Res_{2}(t_{2}, a)) if:

(1) the ”kurosh” rank, fact(Res_{1}(t_{1}, a)) + rk(Res_{1}(t_{1}, a)) is smaller than the kurosh rank fact(Res_{2}(t_{2}, a)) + rk(Res_{2}(t_{2}, a)).

(2) the above ranks are equal and the tuple:

((genus(S_{1}^{1}), |χ(S_{1}^{1})|), …, (genus(S_{m_{1}}^{1}), |χ(S_{m_{1}}^{1}|))

is smaller in the lexicographical order than the tuple:

((genus(S_{1}^{2}), |χ(S_{1}^{2})|), …, (genus(S_{m_{2}}^{2}), |χ(S_{m_{2}}^{2}|)).

(3) the above ranks and tuples are equal and Abrk(Res_{1}(t_{1}, a)) < Abrk(Res_{2}(t_{2}, a)).

Given a well-separated resolution Res(t, y, a) over a free group, and a subgroup < y, a > of its associated limit group, we have constructed in section 3 of [Se4], the induced resolution Ind(Res(t, y, a))(u, y, a). The construction of the induced resolution generalizes directly to well-separated resolutions defined over a torsionfree hyperbolic group Γ, hence, we omit its detailed description.

In section 1 of [Se4] we presented an iterative procedure for the validation of an AE sentence over a free group, assuming all the (F_{k}) limit groups that are needed to be treated along the procedure are of minimal rank. This procedure generalizes directly to validate AE sentences over a torsion-free hyperbolic group, in the minimal rank case. The general procedure for validation of a sentence over a free group, presented in section 4 of [Se4], needs to be slightly modified in order to be adopted for general torsion-free hyperbolic groups. In the previous sections we have already modified all the tools needed in order to be able to modify the general procedure presented in [Se4], and in the rest of this section we present the modified procedure.

Let:

∀y ∃x Σ(x, y, a) = 1 ∧ Ψ(x, y, a) ≠ 1

be a truth sentence over a torsion-free hyperbolic group Γ. Let F_{y} =< y_{1}, …, y_{ℓ} > be a the free group with a free basis y_{1}, …, y_{ℓ}. By proposition 2.1 there exists a formal solution x = x(y, a), and a finite set of restricted Γ-limit groups: Rlim_{1}(y, a), …, Rlim_{m}(y, a) for which:

(i) the words corresponding to the equations in the system Σ(x(y, a), y, a) represent the trivial word in the free group Γ ∗ F_{y}.

(ii) for every index i, Rlim_{i}(y, a) is a proper quotient of the free group Γ ∗ F_{y}. (iii) let B_{1}(y), …, B_{m}(y) be the basic sets corresponding to the restricted Γ-

limit groups Rlim_{1}(y, a), …, Rlim_{m}(y, a). If y ∉ B_{1}(y) ∪ … ∪ B_{m}(y), and ψ_{j}(x, y, a) is a word corresponding to one of the equations in the system Ψ(x, y, a), then: ψ_{j}(x(y, a), y, a) ≠ 1.

Proposition 2.1 gives a formal solution that proves the validity of the given sentence on a co-basic set (F_{k})^{ℓ} \ (B_{1}(y) ∪ … ∪ B_{m}(y)), hence, the rest of the procedure needs to construct formal solutions that prove the validity of the sentence on the remaining basic sets B_{1}(y), …, B_{m}(y). We will continue with the Γ-limit groups Rlim_{i}(y, a) in parallel, hence, for brevity we denote the Γ-limit group we continue with, Rlim(y, a). Note that Rlim(y, a) is a proper quotient of the Γ-limit group Γ ∗ F_{y}, hence, the Kurosh rank of every resolution in the (taut) Makanin-Razborov diagram of Rlim(y, a) is strictly less than ℓ, the rank of the free group F_{y}.

With the Γ-limit group Rlim(y, a) we associate its (canonical) taut Makanin-Razborov diagram. Let Res_{1}(y, a), …, Res_{r}(y, a) be the resolutions in this taut diagram. With each resolution Res_{i}(y, a) we can associate its completed resolution Comp(Res_{i})(z, y, a). We continue with each of the resolutions in parallel, hence, we will omit the index in the sequel. By theorem 2.3 from the validity of our given sentence, we get the existence of a covering closure Cl_{1}(Res)(s, z, y, a), …, Cl_{q}(Res)(s, z, y, a) of the resolution Res(y, a), and for each index 1 ≤ n ≤ q there exists a formal solution x_{n}(s, z, y, a) for which:

(i) the words corresponding to the equations in the system Σ(x_{n}(s, z, y, a), y, a) represent the trivial word in the closure Cl_{n}(Res)(s, z, y, a).

(ii) there exists some specialization (s_{0}^{n}, z_{0}^{n}, y_{0}^{n}) for which Ψ(x_{n}(s_{0}^{n}, z_{0}^{n}, y_{0}^{n}, a), y_{0}^{n}, a) ≠ 1.

With each of the closures, Cl_{n}(Res)(s, z, y, a), we associate finitely many auxiliary resolutions and auxiliary Γ-limit groups, precisely as we did in the free group case (definition 4.1 in [Se4]). Given a closure Cl_{n}(s, z, y, a), a formal solution x_{n}(s, z, y, a) defined over it, an auxiliary resolution, and its associated auxiliary limit group AuxCl(Res)(s, z, y, a), we can clearly use the modular groups associated with the various levels of the auxiliary resolution to construct a family of formal solution x_{α}^{n}(s, z, y, a) defined over the auxiliary limit group AuxCl(Res)(s, z, y, a). In the steps of the iterative procedure for validation of a sentence we present, we always start with this setup, which includes a closure, one of its auxiliary resolutions, its associated auxiliary limit group, and a family of formal solutions associated with the auxiliary resolution.

Given a resolution Res(y, a), one of the closures from its given covering closure and the formal solution defined over this closure, an auxiliary resolution associated with the given closure, and its associated auxiliary Γ-limit group AuxCl(Res)(s, z, y, a), we analyze all the specializations (s_{0}, z_{0}, y_{0}, a) that are taut with respect to the closure Cl_{n}(Res)(s, z, y, a) (hence, in particular, factor through Cl_{n}(Res)(s, z, y, a)), for which the tuple (s_{0}, z_{0}, y_{0}, a) factors through the auxiliary Γ-limit group AuxCl(Res)(s, z, y, a) and satisfies the system of equations:

Σ(x_{α}^{n}(s_{0}, z_{0}, y_{0}, a), y_{0}, a) = 1 ∧ ψ_{j}(x_{α}^{n}(s_{0}, z_{0}, y_{0}, a), y_{0}, a) = 1

for some index j and every index α. Note that since the equation: ψ_{j}(x_{n}(s_{0}, z_{0}, y_{0}, a), y_{0}, a) = 1, defined over the set of specializations that factor through the closure Cl_{n}(Res)(s, z, y, a) is a non-trivial equation by construction, the system of equations: ψ_{j}(x_{α}^{n}(s_{0}, z_{0}, y_{0}, a), y_{0}, a) = 1 (for all possible values of the parameter α), is a non-trivial system of equations defined on the set of specializations that factor through the auxiliary limit group AuxCl(Res)(s, z, y, a), in case the Γ-limit group associated with the corresponding auxiliary resolution and the associated modular groups is the closure itself (i.e., not a proper quotient of the closure). The entire collection of specializations (s_{0}, z_{0}, y_{0}, a) that factor through the closure Cl(Res)(s, z, y, a), and through the auxiliary Γ-limit group AuxCl(Res)(s, z, y, a), and satisfy the corresponding system of equations, is contained in a finite set of maximal Γ-limit groups QRlim_{1}(s, z, y, a), …, QRlim_{u}(s, z, y, a). Our analysis of these quotient Γ-limit groups is conducted in parallel, hence, in the sequel we will omit its index.

Let Zlim_{2} =< s_{2}, z_{2}, …, s_{ℓ}, z_{ℓ} > be the subgroup associated with all the levels of the closure, Cl(Res)(s, z, y, a), except the top level. Zlim_{2} is naturally mapped into the auxiliary Γ-limit group Aux(Cl)(s, z, y, a), hence, into the quotient Γlimit group QRlim(s, z, y, a). With the image of Zlim_{2} in the auxiliary Γ-limit group AuxCl(Res)(s, z, y, a) there is an associated (multi) graded abelian decomposition. Let Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1} be the non-abelian, non-QH vertex groups and edge groups in this abelian decomposition. With the quotient Γ-limit group QRlim(s, z, y, a) we associate canonically the multi-graded taut Makanin-Razborov diagram with respect to the subgroups Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1}. In constructing this diagram, we take into consideration only those homomorphisms of the quotient Γlimit group, QRlim(s, z, y, a), that embed the (images of the) terminal non-cyclic, freely-indecomposable factors of the closure, Cl(Res)(s, z, y, a), into the hyperbolic group Γ. Let:

MGQRes_{1}(s, z, y, Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1}, a), …, MGQRes_{q}(s, z, y, Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1}, a)

be the quotient multi-graded resolutions in this taut Makanin-Razborov diagram.

We continue with a subset of the resolutions that appear in the multi-graded taut Makanin-Razborov diagram of the quotient limit group QRlim(s, z, y, a), a subset through which all the specializations (y_{0}, a) that are taut with respect to Res(y, a), and for which there exists a specialization (s_{0}, z_{0}, y_{0}, a) that factor through QRlim(s, z, y, a) do factor, and not with all the quotient multi-graded resolutions in this taut multi-graded diagram. If the subgroup of generated by < y, a > of the limit group (generated by) < s, z, y, a > associated with a quotient multigraded resolution: MGQRes_{i} is a proper quotient of the Γ-limit group Rlim(y, a) associated with the resolution Res(y, a) we have started this branch of the first step of the procedure, we include the quotient multi-graded resolution MGQRes_{i} in the subset we continue with. Otherwise, for each QH vertex group Q in the abelian decomposition associated with the top level of the closure Cl(Res)(s, z, y, a), the boundary elements of Q can be conjugated (in the limit group associated with the closure Cl(Res)(s, z, y, a)) into one of subgroups Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1}. Since the closure Cl(Res)(s, z, y, a) is canonically mapped onto the quotient Γ-limit group QRlim(s, z, y, a), each of the QH subgroups Q in the abelian decomposition associated with the top level of Cl(Res)(s, z, y, a) is naturally mapped into the quotient Γ-limit group QRlim(s, z, y, a). Hence, the QH subgroup Q and its corresponding quotients naturally inherits a sequence of abelian decompositions from the multi-graded abelian decompositions associated with the various levels of a multi-graded resolution MGQRes_{i} abelian decompositions in which the boundary elements of Q are all elliptic. The resolution Res(y, a) was assumed to be well-separated, hence, on each of the QH vertex groups Q associated with its various levels, there exists an additional indication for a collection of s.c.c. on its associated surface S that is mapped to a trivial element in the Γ-limit group associated with the next level of the resolution Res(y, a). Given a multi-graded resolution MGQRes_{i}, if for some QH vertex group Q in the abelian decomposition associated with the top level of the closure Cl_{n}(Res)(s, z, y, a), the sequence of abelian decompositions Q and its corresponding quotients inherit from the multi-graded resolution MGQRes_{i}, is not compatible with the specific indication of the collection of s.c.c. on the surface S associated with the QH vertex group Q that are mapped to the trivial element in the resolution Res(y, a), we omit the quotient multi-graded resolution MGQRes_{i} from our list of quotient multi-graded resolutions. Otherwise, we include the quotient multi-graded resolution in the subset of multi-graded resolutions we continue with. By construction, every specialization (y_{0}, a) that factors and is taut with respect to the resolution Res(y, a) and for which there is a specialization (s_{0}, z_{0}, y_{0}, a) that factors through the closure Cl(Res)(s, z, y, a), there exists a quotient multigraded resolution MGQRes_{i} that is included in the subset of quotient multi-graded resolutions we continue with, and for which the specialization (s_{0}, z_{0}, y_{0}, a) factors through and is taut with respect to that quotient multi-graded resolution.

Let Q_{1}, …, Q_{r} be the QH vertex groups in the abelian decomposition associated with the top level of the resolution Res(y, a) we have started with, i.e., the QH vertex groups in the abelian JSJ decomposition of Rlim(y, a). As in theorems 1.8 and 2.9 in [Se4], we can assume that each multi-graded quotient resolution MGQRes_{i} terminates in a multi-graded abelian Γ-limit group with a multigraded abelian decomposition containing the entire collection of surviving QH vertex groups Q_{i_{1}}, …, Q_{i_{r′}}, and these surviving QH subgroups are either closed surface subgroups or (in case they correspond to punctured surfaces) they are mapped to their images in the subgroup < z_{2}, a > in either a rigid or solid multi-graded limit group with respect to the subgroups Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1}. Furthermore, the surviving QH vertex groups Q_{i_{1}}, …, Q_{i_{r′}} are subgroups of the non-abelian, non-QH vertex groups, the ones stabilized by the subgroups Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1}, in all levels above the two terminating ones (see theorem 1.8 in [Se4]). A basic property of a multi-graded quotient resolution, is the following property (cf. proposition 4.2 in [Se4]).

Proposition 4.3. Suppose that the subgroup generated by < y, a > in the Γ-limit group associated with a multi-graded resolution MGQRes(s, z, y, Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1}, a), is isomorphic to the Γ-limit group Rlim(y, a) associated with the resolution Res(y, a) we have started the iterative process with. Then the complexity of each of the multigraded abelian decompositions associated with the various levels of the multi-graded resolution: MGQRes is bounded by the complexity of the abelian decomposition associated with the top level of the completion Comp(Res)(z, y, a). In case of equality, the multi-graded resolution: MGQRes has only one level and its structure is identical to the structure of the abelian decomposition associated with the top level of the completion Comp(Res)(z, y, a).

Proof: Identical to the proof of proposition 4.2 in [Se4].

□

The other properties of the multi-graded resolutions, MGQRes, that were proved in the free group case can be modified to hold over a general torsion-free hyperbolic group Γ.

Proposition 4.4. Let MGQRes be one of the multi-graded quotient resolutions, for which the subgroup generated by < y, a > in the Γ-limit group associated with that multi-graded resolution is isomorphic to the Γ-limit group Rlim(y, a) associated with the resolution Res(y, a). By construction, the original Γ-limit group Rlim(y, a) is mapped into the Γ-limit groups associated with each of the levels of the multigraded quotient resolution MGQRes. Let Q_{j}(y, a) be the image of Rlim(y, a) in the limit group associated with the j-th level of MGQRes. Then:

(i) Let Q_{term}(y, a) be the image of Rlim(y, a) in the terminal (rigid or solid) multi-graded Γ-limit group of MGQRes. Then the terminal Γ-limit group of the multi-graded resolution: MGQRes can be replaced by a finite collection of finitely many terminal multi-graded Γ-limit groups, in which either Q_{term}(y, a) is a proper quotient of Rlim(y, a), or one can assume that each of the homomorphisms that factors through the given terminal Γ-limit group embeds each of its non-cyclic, freely-indecomposable factors into the coefficient group Γ.

(ii) Suppose that for some level j, Q_{j}(y, a) is isomorphic to Rlim(y, a). Let MGQlim_{j}(s, z, y, a) be the quotient limit group associated with the j-th level of the multi-graded resolution MGQRes. Then either the (ungraded) abelian JSJ decomposition of MGQlim_{j}(s, z, y, a) is obtained from the multi-graded abelian decomposition associated with the j-th level of the multi-graded resolution MGQRes together with the auxiliary decomposition associated with the auxiliary resolution we have started with, or each of the specializations (s_{0}, z_{0}, y_{0}, a) that factor through and are taut with respect to the closure Cl(Res)(s, z, y, a) and the multi-graded resolution MGQRes factor through an auxiliary resolution of higher complexity.

Proof: Identical to the proof of proposition 4.3 in [Se4].

□

The procedure we present for the validation of an AE sentence over a torsion-free hyperbolic group, is similar to the one used over a free group in section 4 of [Se4]. The necessary required modifications are similar to the modifications applied in constructing the tree of stratified sets, presented in section 2 of [Se5].

I: The first step

(1) Let Rlim(y, a) be the Γ-limit group we have started with. Let Q(y, a) be the Γ-limit group generated by < y, a > in the Γ-limit group associated with the multi-graded quotient resolution MGQRes. If Q(y, a) is a proper quotient of Rlim(y, a), we continue this branch of the iterative procedure, by replacing the Γ-limit group Rlim(y, a) by Q(y, a), and continue with the finite collection of resolutions that appear in the taut Makanin-Razborov diagram of the Γ-limit group Q(y, a) in the same way we handled the resolutions in the taut Makanin-Razborov diagram of Rlim(y, a).

(2) At this stage we may assume that Q(y, a) is isomorphic to Rlim(y, a). At this part we will also assume that the multi-graded quotient resolution MGQRes is not of maximal complexity, i.e., that the complexities of the abelian decompositions associated with its various levels are strictly smaller than the complexity of the abelian decomposition associated with the top level of the resolution Res(y, a).

In this case, either the image of Rlim(y, a) in the Γ-limit group associated with the second level of: MGQRes(s, z, y, Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1}, a), Q_{2}(y, a), is a proper quotient of Rlim(y, a), or the image of QRlim(s, z, y, a) in the limit group associated with the second level of:

MGQRes(s, z, y, Base_{2,1}^{1}, …, Base_{2,v_{1}}^{1}, a)

Q_{2}(s, z, y, a), is a proper quotient of QRlim(s, z, y, a), or the homomorphisms that factor through the given multi-graded resolution, MGQRes, embed each of the non-cyclic, freely indecomposable factors of the quotient Γ-limit group, QRlim, into the coefficient group Γ.

If the subgroup Q_{2}(y, a) is a proper quotient of Rlim(y, a), we associate with it its taut Makanin-Razborov diagram, and with each of the resolutions QRes_{j}(y, a) in the diagram we associate a developing resolution, an auxiliary resolution, and an anvil, precisely as we did in part (2) of the initial step in the free group case. If Q_{2}(y, a) is isomorphic to Rlim(y, a) we continue to the next levels of the multi-graded quotient resolution MGQRes If at some level j of MGQRes, the image of Rlim(y, a) in the limit group associated with the j-th level of MGQRes, Q_{j}(y, a), is a proper quotient of Rlim(y, a), we continue in a similar way to what we did in case Q_{2}(y, a) is a proper quotient of Rlim(y, a).

By part (i) of proposition 4.4, if for every level j, Q_{j}(y, a) is isomorphic to the Γ-limit group Rlim(y, a) we have started with, we can assume that each of the homomorphisms that factor through the given terminal Γ-limit group of MGQRes embeds each of its non-cyclic, freely-indecomposable factors into the coefficient group Γ. In this case we associate a developing resolution and an anvil with MGQRes, precisely as we did in case (2) of the initial step of the procedure for the construction of stratified sets (section 2 in [Se5]), in case the map of the original F_{k}-limit group into the terminal limit group of the multi-graded quotient resolution is an isomorphism, and hence, this terminal limit group is rigid or solid with respect to the defining parameters p..

(3) By part (1) we may assume that Q(y, a) is isomorphic to Rlim(y, a). Part (2) treats the case in which the multi-graded quotient resolution MGQRes is not of maximal complexity. The only case left, that of a maximal complexity quotient resolution, MGQRes, is treated in precisely the same way it was treated in the initial step of the procedure over a free group (case (3) of the initial step).

II: The general step

The general step of the iterative procedure is similar to the one over free groups, presented in section 4 of [Se4]. The ultimate goal of the general step of the iterative procedure is to obtain a strict reduction in either the complexity of certain decompositions and resolutions or a strict reduction in the Zariski closures of certain limit groups associated with the anvils constructed in the previous steps of the procedure. The strict reduction in complexity and Zariski closures will finally guarantee the termination of the iterative procedure after finitely many steps, precisely as in the case of free groups.

The description of the general step of the procedure in the case of free groups appears in section 4 of [Se4]. The only modifications needed in the case of a torsionfree hyperbolic group are those presented in lemma 4.4, and as a consequence, in case (2) of the initial step, and its parallels in the general case. The argument for the termination of the procedure is essentially identical to the free group case. hence, we prefered not to repeat the details of the general step of the procedure, and refer the interested reader to the detailed description in section 4 of [Se4].

§5. Core Resolutions

In the first 3 sections of this paper, we have generalized the structure theory developed in [Se1], [Se2] and [Se3] from free groups to torsion-free hyperbolic groups. Section 4 generalizes the iterative procedure for validating an AE sentence to hyperbolic groups, that finally allows us to generalize the quantifier elimination procedure presented in [Se5] and [Se6]. In this section we prepare the main tool needed for generalizing the q.e. procedure, the construction of the core resolution for resolutions defined over torsion-free hyperbolic groups.

Definition 5.1 (cf. ([Se5],4.1). Let Res(t, v, a) be a a well-separated resolution over a torsion-free hyperbolic group Γ, and let Comp(Res)(u, t, v, a) be its completion. Let CRes(r, v, a) be a geometric subresolution of the completed resolution Res(u, t, v, a). We say that the resolution CRes(r, v, a) is a core resolution of the subgroup < v, a > in the completion Comp(Res)(u, t, v, a), if the resolution CRes(r, v, a) is a firm subresolution of the subgroup < r, v, a > ([Se4], definition 3.9). i.e., it has the following properties:

(i) the Kurosh rank of the resolution CRes(r, v, a), i.e., the sum of the number of non-cyclic, freely indecomposable factors and the ranks of the free groups dropped along its levels, is equal to the Kurosh rank of the subgroup < r, v, a > with respect to the completed resolution Comp(Res)(u, t, v, a).

(ii) there exists a firm test sequence for the subgroup < r, v, a >, i.e., a test sequence of the ambient completion, Comp(Res)(u, t, v, a), in which the Kurosh rank of the subgroup < r, v, a > is precisely the Kurosh rank of the core, CRes(r, v, a).

(iii) Let A_{1}, …, A_{m} be all the non-cyclic pegged abelian groups that appear along the completed resolution Comp(Res)(t, v, a), let peg_{1}, …, peg_{m} be the pegs of the abelian groups A_{1}, …, A_{m}, and let {peg_{i}, q_{1}^{i}, …, q_{j_{i}}^{i}}_{i=1}^{m} be an arbitrary basis for the collection of the subgroups A_{1}, …, A_{m}. Then for any set of integers {(s_{j}^{i}, n_{j}^{i})}, where n_{j}^{i} ≥ 2 and 0 ≤ s_{j}^{i} ≤ n_{j}^{i}, there exist a firm test sequence {t_{n}, v_{n}, a} of the subgroup < v, a >, so that for every index n, the specialization of each of the pegs peg_{i} is an element h_{i} with no non-trivial

roots, and the specialization of each of the basis elements q_{j}^{i} is h_{i}^{r_{j}^{i}} where r_{j}^{i} = u_{j}^{i} · n_{j}^{i} + s_{j}^{i} for some positive integer u_{j}^{i}.

We denote a core resolution, Core(< v, a >, Res(t, v, a))(r, v, a). In exactly the same way we define a graded core resolution, and a multi-graded core resolution. Since a core resolution is in particular a geometric subresolution, we set the complexity of a core resolution to be its complexity as a geometric subresolution.

The procedure for the construction of a core resolution over hyperbolic groups, is essentially similar to the one presented in section 4 of [Se5] over a free group.

It is composed from 2 iterative procedures. The procedure used for the first part is essentially identical to the iterative procedure used to construct the induced resolution. In the second part, in a similar way to the procedure over a free group, we use an iterative procedure that either reduces the Kurosh rank of the resolution constructed in the first part, or alternatively, shows that the resolution constructed in the first part is a firm subresolution, hence, it is a core resolution.

Since the first part is identical to the construction of the induced resolution, we do not present it in detail. Let Res(t, v, a) be a complete well-separated resolution. We denote the resolution induced by the subgroup < v, a > from Res(t, v, a), IRes_{f}(u, v, a). To the induced resolution IRes_{f}(u, v, a) we iteratively add pegs of its abelian groups using the procedure presented in section 4 of [Se5]. Using the same procedure, we iteratively add roots to QH vertex groups along our constructed resolution that are finite index subgroups in conjugates of QH vertex groups along the ambient resolution Res(t, v, a), so that the outcome of this iterative procedure is a geometric subresolution of the ambient resolution, Res(t, v, a), in which every QH vertex group is conjugate to a QH vertex group along Res(t, v, a). We denote the resolution obtained by adding pegs and ”completing” QH vertex groups, IRes_{p}(u, v, a). Note that the procedure that iteratively add pegs, and ”complete” QH vertex groups, is conducted by iteratively adding finite order roots to the terminal group, hence, it does not increase the Kurosh rank. Furthermore, if it preserves the Kurosh rank, and the obtained resolution is firm, so is the induced resolution IRes_{f}(u, v, a).

As in the free group case, to modify the resolution IRes_{p}(u, v, a) in order to obtain a firm subresolution, we use an iterative procedure, that is aimed towards sequentially reducing the Kurosh rank of the obtained resolutions. The iterative procedure we present either reduces the Kurosh rank after finitely many steps, or guarantees (after finitely many steps) that the resolution IRes_{p}(u, v, a) is indeed a firm subresolution. The procedure we present, which is a slight modification of the procedure used in the free group case, starts from the bottom level of the resolution Res(t, v, a) and iteratively climbs towards its top level.

(1) The terminal level (which we denote by ℓ) of the resolution Res(t, v, a) is a free product of freely-indecomposable groups that can be embedded in the torsion-free hyperbolic group Γ, and a free group. The terminal level of the resolution IRes_{p}(u, v, a), admits a (possibly trivial) free decomposition to a (possibly trivial) free group and a (possibly trivial) factor M, so that M embeds into the terminal level of the ambient resolution, Res(t, v, a). The factor M inherits a (possibly trivial) free decomposition from the given free decomposition of the terminal group of Res(t, v, a), M = M_{1} ∗ … ∗ M_{s} ∗ F, where F is a (possibly trivial) free group, and the factors M_{i} are embedded into conjugates of the non-cyclic, freely-indecomposable factors in the free decomposition of the terminal group of the ambient resolution, Res(t, v, a). We modify the resolution IRes_{p}(u, v, a) by replacing each of the terminal factors M_{i}, with the non-cyclic, freely-indecomposable factor in the terminal group of Res(t, v, a) that contains it. With the subgroup corresponding to this modified resolution, we associate the induced resolution, and iteratively add pegs and complete QH vertex groups. If the terminal group of the resolution has changed, and there exist new factors that embed into noncyclic, freely-indecomposable factors in the terminal group of Res(t, v, a), we repeat part (1) of the construction. Note that this modification does not increase the Kurosh rank, and if it preserves the Kurosh rank, and the obtained resolution is firm, so is the resolution IRes_{p}(u, v, a). We denote the resolution obtained after this modification IRes_{c}(u, v, a).

(2) We continue from the level above the terminal one (level ℓ − 1). According to the construction of an induced resolution, the subgroup associated with the resolution IRes_{c}(u, v, a) inherits a (possibly trivial) free decomposition from each of the levels of the resolution IRes_{c}(u, v, a), and it is mapped to a subgroup associated with each of the levels. In particular, in accordance with the free decomposition inherited by the subgroup associated with the resolution IRes_{c}(u, v, a) from the levels that lie above the ℓ − 1 level, the image of the subgroup associated with IRes_{c}(u, v, a), G^{ℓ−1}, admits a free decomposition when mapped into the ℓ−1 level, G^{ℓ−1} = H_{1}^{ℓ−1}∗…∗H_{s(ℓ−1)}^{ℓ−1}. We treat the factors H_{i}^{ℓ−1} in parallel.

We fix a system of generators of H_{i}^{ℓ−1}, H_{i}^{ℓ−1} =< h_{1}^{ℓ−1}, …, h_{r(ℓ−1,i)}^{ℓ−1} >. If no (non-trivial) subgroup of the factor H_{i}^{ℓ−1} fixes a vertex in the Bass-Serre tree associated with the ℓ − 1 level of the resolution Res(t, v, a), we have started with, we leave the factor H_{i}^{ℓ−1} unchanged. Suppose that a (non-trivial) subgroup of H_{i}^{ℓ−1} fixes a vertex in the abelian decomposition associated with the ℓ − 1 level of the resolution Res(t, v, a).

Let T_{ℓ−1} be the Bass-Serre tree corresponding to the abelian decomposition associated with the ℓ − 1 level of the ambient resolution Res(t, v, a), and let Λ_{H_{i}^{ℓ−1}} be the graph of groups inherited by H_{i}^{ℓ−1} from its action on the Bass-Serre tree T_{ℓ−1}. Suppose that the abelian decomposition Λ_{H_{i}^{ℓ−1}},

inherited by H_{i}^{ℓ−1} from its action on the Bass-Serre tree T_{ℓ−1}, contains a couple of QH vertex groups, Q_{1}, Q_{2}, that satisfy the following conditions:

(i) Q_{1} is a conjugate of a QH vertex group in the abelian decomposition associated with the ℓ − 1 level of the ambient resolution Res(t, v, a), and Q_{2} is conjugate to the same QH vertex group in the abelian decomposition associated with the ℓ − 1 level of the ambient resolution Res(t, v, a).

(ii) the QH vertex group Q_{1} (hence, also Q_{2}) is not of minimal rank, i.e., there exists a s.c.c. on S_{1} (the surface associated with Q_{1}) that is mapped to the trivial element in the next level of the resolution Res(t, v, a). In this case we say that the abelian decomposition Λ_{H_{i}^{ℓ−1}} contains a reducing QH couple.

If the abelian decomposition Λ_{H_{i}^{ℓ−1}} contains a reducing QH couple, Q_{1}

and Q_{2}, we set the subgroup Ĥ_{i} to be the subgroup generated by H_{i}^{ℓ−1}, and an element in the Γ-limit group associated with the ℓ − 1 level of the ambient resolution Res(t, v, a) that conjugates Q_{1} to Q_{2}. We set H′_{i} to be the Γ-limit group associated with the resolution induced by the subgroup Ĥ_{i} from the ambient resolution Res(t, v, a). Since the QH vertex groups Q_{1} and Q_{2} are not of minimal rank, and since Q_{1} and Q_{2} are not conjugate in the subgroup H_{i}^{ℓ−1} we have started with, and Q_{1} and Q_{2} are conjugate in H′_{i}, the Kurosh rank of H′_{i} is strictly smaller than the Kurosh rank of H_{i}^{ℓ−1}. In this case we replace the factor H_{i}^{ℓ−1} by H′_{i}, and repeat the construction the whole construction of the core resolution starting with the obtained group.

Suppose that the abelian decomposition Λ_{H_{i}^{ℓ−1}} does not contain a reducing QH couple. Let η_{ℓ−1} be the map from the Γ-limit group associated with the ℓ−1 level of Res(t, v, a) to the Γ-limit group associated with the (terminal) ℓ level of Res(t, v, a). Let t_{0} ∈ T_{ℓ−1} be its base point, and let T′_{ℓ−1} be the finite subtree of T_{ℓ−1} spanned by the points t_{0}, h_{1}^{ℓ−1}(t_{0}), …, h_{r(ℓ−1,i)}^{ℓ−1}(t_{0}). To continue our treatment of the factor H_{i}^{ℓ−1} we need the notions of floating and absorbed surfaces.

Definition 5.2 (cf. definition 4.6 in [Se5]). Let Q be a QH vertex group in the finite tree T′_{ℓ−1}, and let S be its associated surface. Since the ambient resolution Res(t, v, a) is well-separated, the image of the QH vertex group Q in the next level of the resolution Res(t, v, a) is non-abelian. Recall (definition 4.6 in [Se5]) that we say that Q is a floating QH vertex group (S is a floating surface) with respect to the geometric subresolution IRes(u, v, a), if Q does not intersect the subgroup H_{i}^{ℓ−1} in a subgroup of finite index, and one of the three conditions hold:

(i) the QH vertex group Q is not of minimal rank, i.e., there exists a s.c.c. on the surface Ŝ that is mapped to the trivial element in the limit group associated with the next level of the ambient resolution Res(t, v, a).

(ii) none of the vertex groups that are adjacent to Q in T′_{ℓ−1} intersect non-

trivially the subgroup H_{i}^{ℓ−1}. (iii) the QH vertex group Q is of minimal rank, and for every vertex group V

in T′_{ℓ−1} that is adjacent to Q in T′_{ℓ−1} and intersects H_{i}^{ℓ−1} non-trivially, the Kurosh rank of the subgroup: η_{ℓ−1}(< H_{i}^{ℓ−1} ∩ V, Q >) is strictly bigger than the Kurosh rank of the subgroup: η_{ℓ−1}(H_{i}^{ℓ−1} ∩ V).

We say that Q is an absorbed vertex group (S is an absorbed surface) if it is not floating.

In the case in which there is no reducing QH couple, we set Ĥ_{i} to be the subgroup generated by the factor H_{i}^{ℓ−1} and one of the following if it exists:

(i) an abelian vertex group in the finite tree T′_{ℓ−1} that is intersected nontrivially by the factor H_{i}^{ℓ−1}, but is not contained in it.

(ii) an absorbed QH vertex group in the finite tree T′_{ℓ−1} (with respect to the

subgroup H_{i}^{ℓ−1}), that is not contained in H_{i}^{ℓ−1}. (iii) an (abelian) edge group E in the finite tree T′_{ℓ−1}, that is not contained in

H_{i}^{ℓ−1}, and is adjacent to a non-abelian, non-QH vertex group V in T′_{ℓ−1} that is intersected non-trivially by H_{i}^{ℓ−1}, for which the Kurosh rank of the subgroup: η_{ℓ−1}(< H_{i}^{ℓ−1} ∩ V, E >) is bounded from above by the Kurosh rank of the subgroup: η_{ℓ−1}(H_{i}^{ℓ−1} ∩ V).

(iv) an element v_{0} ∈ V, v_{0} ∉ H_{i}^{ℓ−1}, where V is a non-abelian, non-QH vertex group in the finite tree T′_{ℓ−1} that is intersected non-trivially by the subgroup H_{i}^{ℓ−1}, for which there exist two edge groups E_{1}, E_{2} that are adjacent to V in the finite tree T′_{ℓ−1} and are not conjugate in the subgroup H_{i}^{ℓ−1}, so that v conjugates E_{1} to E_{2} in the Γ-limit group associated with the ℓ − 1 level of the ambient resolution Res(t, v, a), and the Kurosh rank of the subgroup: η_{ℓ−1}(< H_{i}^{ℓ−1} ∩ V, v_{0} >) is bounded above by the Kurosh rank of the subgroup: η_{ℓ−1}(H_{i}^{ℓ−1} ∩ V).

We further set H′_{i} to be the subgroup associated with the resolution induced by the subgroup Ĥ_{i}. Since Ĥ_{i} is generated by H_{i}^{ℓ−1}, the absorbed QH vertex groups in T′_{ℓ−1} with respect to H_{i}^{ℓ−1}, abelian vertex groups that are intersected non-trivially by H_{i}^{ℓ−1}, and additional elements that do not increase the Kurosh ranks of the corresponding vertex groups, the Kurosh rank of H′_{i} is bounded by the Kurosh rank of H_{i}^{ℓ−1}, rk(H′_{i}) ≤ rk(H_{i}^{ℓ−1}). Furthermore, both groups H′_{i} and H_{i}^{ℓ−1} inherit free decompositions from the abelian decompositions associated with their corresponding actions on the Bass-Serre tree T_{ℓ−1}, and both the number of factors as well as the rank of the additional free group in the abelian decomposition associated with H′_{i} (the Kurosh rank) are bounded by the number of factors and the corresponding rank in the abelian decomposition associated with H_{i}^{ℓ−1}. If H′_{i} is identical to H_{i}^{ℓ−1} we have concluded our treatment of the factor H_{i}^{ℓ−1}. Otherwise, we replace the factor H_{i}^{ℓ−1} by H′_{i}, and repeat the construction of a subgroup Ĥ_{i} associated with the newly obtained subgroup H_{i}^{ℓ−1} (without changing the finite tree T′_{ℓ−1}), and the construction of the subgroup H′_{i} associated with the resolution induced by Ĥ_{i} from the ambient resolution Res(t, v, a), and repeat our treatment of the subgroup H′_{i}. Since in each step we either reduce the Kurosh rank of the obtained subgroup, or we add a new edge group, an abelian vertex group or absorbed QH vertex group from the finite tree T′_{ℓ−1} to the subgroup associated with H_{i}^{ℓ−1}, or we add an element that conjugates two edge groups in T′_{ℓ−1} that were not conjugated previously, we conclude our treatment of the factor H_{i}^{ℓ−1} after finitely many steps. If the Kurosh rank of at least one of the factors H_{i}^{ℓ−1} strictly decreased by the iterative procedure, we replace the resolution IRes_{c}(u, v, a) with the resolution induced by the subgroup generated by the subgroup associated with IRes_{c}(u, v, a) and the newly obtained factors H_{1}^{ℓ−1}, …, H_{s(ℓ−1)}^{ℓ−1}, and denote the obtained resolution IRes_{ℓ−1}(u, v, a). In this case, the Kurosh rank of the resolution IRes_{ℓ−1}(u, v, a) is strictly smaller than the Kurosh rank of the resolution IRes_{c}(u, v, a)), and we continue by starting the second step of the construction of the core resolution with the resolution IRes_{ℓ−1}(u, v, a) (instead of IRes_{f}(u, v, a)). If none of the Kurosh ranks of the various factors H_{i}^{ℓ−1} decreases, we continue by analyzing the next (ℓ − 2) level of the resolution IRes_{c}(u, v, a).

The iterative procedure presented in part (2) terminates after finitely many steps, and concludes our treatment of the various factors H_{i}^{ℓ−1} of the subgroup G^{ℓ−1} = H_{1}^{ℓ−1} ∗ … ∗ H_{s(ℓ−1)}^{ℓ−1}, which is the image of the subgroup associated with the resolution IRes_{c}(u, v, a) in the subgroup associated with the ℓ − 1 level of the ambient resolution Res(t, v, a). We continue by iteratively increasing the index m, and analyzing the various factors of the image of the subgroup G^{ℓ−m} = H_{1}^{ℓ−m}∗…∗H_{s(ℓ−m)}^{ℓ−m}, which is the image of the subgroup associated with the resolution IRes_{c}(u, v, a) in the subgroup associated with the ℓ − m level of the ambient resolution Res(t, v, a), according to the procedure presented in part (2). Since given part (2), this iterative construction is identical to the one presented in [Se5] over free groups, we omit its detail, and refer the interested reader to part (3) of the construction of the core resolution over a free group in section 4 of [Se5].

The iterative procedure used for the second part of the construction of the core resolution terminates after finitely many steps. Using it we obtain a geometric subresolution of the ambient resolution Res(t, v, a), which we denote IRes_{s}(u, v, a), which is set to be either the resolution IRes_{f}(u, v, a) obtained by the first part of the construction, in case the procedure used for the second part of the construction of the core resolution has not reduced the Kurosh rank of the resolution it has constructed, or it is the resolution constructed by the procedure used in the second part of the construction of the core resolution, in case this resolution is of strictly smaller Kurosh rank than the resolution IRes_{f}(u, v, a), constructed by the procedure used in the first part of the construction. The obtained resolution IRes_{s}(u, v, a) is a geometric subresolution of Res(t, v, a) by construction, in addition it is guaranteed to be a firm subresolution by the following theorem, hence, it may serve as a core resolution, Core(< v, a >, Res(t, v, a)).

Theorem 5.3 (cf. ([Se5],4.7). The resolution IRes_{s}(u, v, a), obtained by the procedure for the construction of a core resolution, is a firm subresolution of the resolution Res(t, v, a).

Proof: The proof is essentially identical to the proof of theorem 4.7 in [Se5], replacing rank by Kurosh rank.

□

Once the construction of the core resolution is generalized to torsion-free hyperbolic groups, all the basic properties of the core over a free group, presented in propositions 4.11-4.20 in [Se5], generalize to torsion-free hyperbolic groups as well. The arguments are essentially identical, hence, we refer the interested reader to section 4 in [Se5] for the basic properties of the core and their proofs.

§6. Quantifier Elimination

As in the case of a free group, to obtain quantifier elimination of elementary predicates over a torsion-free hyperbolic group, our goal is showing that the Boolean algebra of AE sets is invariant under projections. Our approach to proving this invariance is similar to the quantifier elimination procedure in the free group case, presented in [Se5] and [Se6].

Given a predicate defined over a torsion-free hyperbolic group Γ, we start by constructing the tree of stratified sets, in the same way it is constructed in section 2 of [Se5] over a free group. The procedure for constructing the tree of stratified sets is based on the iterative procedure for validating an AE sentence, and the modifications required for generalizing it to torsion-free hyperbolic groups, are precisely the modifications presented in section 4. Hence, we omit its detailed description and refer the interested reader to section 2 of [Se5].

The outcome of the tree of stratified sets is an encoding of all the (finitely many) possible sequences of forms of families of formal solutions that are needed in order to validate that a certain specialization p_{0} of the defining parameters p is indeed in the set EAE(p). As in the free group case, this stratification is the basis for our analysis of the structure of the set EAE(p).

Let Γ =< a_{1}, …, a_{k} > be a torsion-free hyperbolic group, and let EAE(p) be the set defined by the predicate:

EAE(p) = ∃w ∀y ∃x Σ(x, y, w, p, a) = 1 ∧ Ψ(x, y, w, p, a) ≠ 1.

Recall (definition 1.19 in [Se5]) that a specialization w_{0} of the variables w, is said to be a witness for a specialization p_{0} of the defining parameters p, if the following sentence:

∀y ∃x Σ(x, y, w_{0}, p_{0}, a) = 1 ∧ Ψ(x, y, w_{0}, p_{0}, a) ≠ 1

is a truth sentence. Clearly, if there exists a witness for a specialization p_{0} then p_{0} ∈ EAE(p), and every p_{0} ∈ EAE(p) has a witness.

By the construction of the tree of stratified sets, a witness w_{0} for a specialization p_{0}, proves that p_{0} ∈ EAE(p) using a certain ”proof system” which is built from a finite sequence of (families of) formal solutions, which correspond to boundedly many paths along the tree of stratified sets. Given p_{0} ∈ EAE(p), we are not able to say much about a possible witness for p_{0} using the information we have collected so far. However, with each ”proof system”, i.e., with each path of (families of) formal solutions that goes along the tree of stratified sets, one can associate a certain Diophantine set. The bound on the form and number of all possible ”proof systems” associated with all possible witnesses suggested by the tree of stratified sets, forces every possible witness for p_{0} to belong to one of the finitely many Diophantine sets associated with the (finite) collection of all proof systems. Furthermore, as in the free group case, we will show that if a specialization p_{0} ∈ EAE(p), and it can be shown that p_{0} ∈ EAE(p) using a witness w_{0} with a corresponding proof system, then every ”generic” specialization of w that belongs to (a closure of) some modular block associated with the Diophantine set which is associated with the specific proof system is a witness for p_{0} using the same proof system as w_{0}. This will reduce the analysis of the set EAE(p) to the analysis of the Diophantine sets and the modular blocks associated with each ”proof system”, and eventually will enable us to show that the set EAE(p) is in the Boolean algebra of AE sets.

Definition 6.1. Let p_{0} ∈ EAE(p) be a specialization of the defining parameters p, and let w_{0} be a witness for p_{0}. By the construction of the tree of stratified sets, one can associate a proof system with the couple (w_{0}, p_{0}), which corresponds to a (finite) collection of paths in the tree of stratified sets. Note that there may be several proof systems associated with a given couple (w_{0}, p_{0}), but the construction of the tree of stratified sets guarantees that the number of proof systems associated with the couple (w_{0}, p_{0}) is globally bounded. We will say that a given proof system associated with the couple (w_{0}, p_{0}) is of depth d, if all the paths associated with the proof system terminate after d steps (levels) of the tree of stratified sets.

As in the free group case, we start by analyzing those specializations of the defining parameters p that have witnesses with proof systems of depth 1, continue by analyzing the specializations of the defining parameters p for which there are witnesses with proof systems of depth at most 2, and then present the analysis of the entire set EAE(p).

Lemma 6.2. Let T_{1}(p) ⊂ EAE(p) be the subset of all specializations p_{0} ∈ EAE(p) of the defining parameters p, that have witnesses with proof system of depth 1. Then T_{1}(p) is an EA set.

Proof: Identical to lemma 1.21 in [Se5].

□

Lemma 6.2 proves that the set of specializations of the defining parameters p that have witnesses with proof statement of depth 1 is an EA set. As in the case of a free group, we continue by showing that the set of p’s that have witnesses with proof statement of depth 2 is in the Boolean algebra of AE sets, and then generalize it to the existence of a witness with an arbitrary depth proof statement.

Theorem 6.3. Let T_{2}(p) ⊂ EAE(p) be the subset of all specializations p_{0} ∈ EAE(p) of the defining parameters p, that have witnesses with proof system of depth 2. Then T_{2}(p) is in the Boolean algebra of AE sets.

Before we start with the proof of theorem 6.3, we need the notion of a valid P S statement.

Definition 6.4. Suppose that a specialization p_{0} ∈ EAE(p) has a witness w_{0} with a proof system of depth 2 (i.e., p_{0} ∈ T_{2}(p)). The structure of the tree of stratified sets guarantees the existence of a rigid or strictly solid families of specializations (h_{0}^{1}, w_{0}, p_{0}) of one of the rigid or solid limit groups W P H(h, w, p, a) with the following properties:

(i) For every Γ-limit group W P HG(g_{1}, h_{1}, w, p, a), which is a terminal Γ-limit group of its associated graded resolution, hence, it is a (possibly trivial) free product of a rigid or solid Γ-limit group with several freely indecomposable groups that are embedded into Γ, there are at most (globally) boundedly many rigid or strictly solid families of specializations of the form (g_{0}^{1}, h_{0}^{1}, w_{0}, p_{0}) of W P HG(g_{1}, h_{1}, w, p, a), where the strictly solid families are with respect to the given set of closures associated with (some of the other) Γ-limit groups W P HG(g_{1}, h_{1}, w, p, a). The elements (g_{0}^{1}, h_{0}^{1}, w_{0}, p_{0}, a) that appear in a proof system, contains representatives for all the boundedly many rigid and solid classes.

(ii) The specialization (h_{0}^{1}, w_{0}, p_{0}) is rigid or solid specialization of the corresponding Γ-limit group W P H, and it does not factor through any of the modular blocks that factor through one of the Γ-limit groups λW P GL(y, h, w, p, a) and correspond to the entire free group F_{y}.

(iii) For each of the (boundedly many) rigid or strictly solid families of specializations (g_{0}^{1}, h_{0}^{1}, w_{0}, p_{0}) there exist a finite collection of rigid or strictly solid families of specializations (h_{0}^{2}, g_{0}^{1}, h_{0}^{1}, w_{0}, p_{0}) of the rigid or strictly solid Γ-limit groups W P HGH(h_{2}, g_{1}, h_{1}, w, p, a), so that the (ungraded) resolutions corresponding to the specializations (h_{0}^{2}, g_{0}^{1}, h_{0}^{1}, w_{0}, p_{0}) form a covering closure of the (ungraded) resolution corresponding to the specialization (g_{0}^{1}, h_{0}^{1}, w_{0}, p_{0}).

(iv) For each of the (boundedly many) rigid or strictly solid families of specializations (h_{0}^{2}, g_{0}^{1}, h_{0}^{1}, w_{0}, p_{0}) there exists no specialization g_{0}^{2} of the variables g_{2} so that the specialization (g_{0}^{2}, h_{0}^{2}, g_{0}^{1}, h_{0}^{1}, w_{0}, p_{0}) factors through one of the (rigid or solid) Γ-limit groups W P HGHG(g_{2}, h_{1}, g_{1}, h_{1}, w, p, a).

We call a specialization of the form:

((h_{1}^{2}, g_{1}^{1}), …, (h_{ν(ps)}^{2}, g_{ν(ps)}^{1}), h_{0}^{1}, w_{0}, p_{0}, a)

that satisfies conditions (i)-(iv) above, where the integer ν(ps) depends on the fixed proof system, a valid P S statement.

The tree of stratified sets guarantees that there are finitely many proof systems of depth 2. Once we fix a proof system of depth 2, we have fixed the rigid or solid Γ-limit group W P H(h, w, p, a), the number of rigid or strictly solid families of specializations of each of the rigid or solid factor in the given free decomposition of the Γ-limit groups W P HG(g_{1}, h_{1}, w, p, a), and the number of families of each of the other factors that do not factor through completions of other (deeper) ungraded resolutions of these factors, and the number of rigid or solid specializations of each of the rigid or solid factor in the Γ-limit groups (h_{2}, g_{1}, h_{1}, w, p, a), and the number of families of embeddings of each of the other factors. We start the analysis of the set T_{2}(p) by enumerating all the possible proof systems, and for each proof system we collect all possible (configurations of) valid P S statements: ((h_{1}^{2}, g_{1}^{1}), …, (h_{ν(ps)}^{2}, g_{ν(ps)}^{1}), h_{0}^{1}, w_{0}, p_{0}, a) (the integer ν(ps) depends on the fixed proof system), which by the standard arguments presented in section 1, factor through a (canonical) collection of maximal Γ-limit groups P SHGH_{1}, …, P SHGH_{m}, which we call P S (proof system) Γ-limit groups.

By construction, for each p_{0} ∈ T_{2}(p) there exists some witness w_{0} and a corresponding proof system, so that a specialization of the form:

((h_{1}^{2}, g_{1}^{1}), …, (h_{ν(ps)}^{2}, g_{ν(ps)}^{1}), h_{0}^{1}, w_{0}, p_{0}, a)

that is associated with the specialization p_{0}, the witness w_{0} and that proof system, is a valid P S statement (i.e., it satisfies conditions (i)-(iv) of definition 6.4), and factors through a P S Γ-limit group P SHGH_{j}. Naturally, as in the free group case, we will try to understand the set of valid P S statements:

((h_{1}^{2}, g_{1}^{1}), …, (h_{ν(ps)}^{2}, g_{ν(ps)}^{1}), h_{0}^{1}, w_{0}, p_{0}, a)

that factor through a given P S limit group P SHGH_{j}. Our main goal will be to show that these valid P S statements are ”generic” in some modular blocks associated in the sequel with each of the P S limit groups P SHGH.

Let P =< p > be the group of defining parameters. With each of the limit groups P SHGH_{i} we associate its canonical graded Makanin-Razborov diagram (with respect to the parameter subgroup P), which contains finitely many graded resolutions which we denote P SHGHRes (omitting their index). As in the free group case, with (the completion of) the graded P S resolution P SHGHRes we associate a (canonical) finite collection of Non-Rigid and Non-Solid P S Γ-limit groups (definition 1.25 in [Se5]), which we call the non-rigid P S Γ-limit groups associated with the P S resolution P SHGHRes, NRgdP S_{1}^{j}, …, NRgdP S_{q}^{j}, and the non-solid P S Γ-limit groups associated with P SHGHRes, NSldP S_{1}^{j}, …, NSldP S_{r}^{j}.

We continue by collecting all the test sequences that factor through the completion of one of the P S resolutions P SHGHRes, Comp(P SHGHRes), and for which for at least one of the tuples: (h_{t}^{2}(n), g_{t}^{1}(n), h_{1}(n), w_{n}, p_{n}, a) there exists some specialization g_{m}^{2}(n) so that the (combined) specialization: (g_{t}^{2}(n), h_{t}^{2}(n), g_{t}^{1}(n), h_{1}(n), w_{n}, p_{n}, a) factors through (at least) one of the Γ-limit groups W P (HG)^{2}, or there exists a specialization g_{1}(n) so that the (combined) specialization: (g_{1}(n), h_{1}(n), w_{n}, p_{n}, a) factors through (at least) one of the Γ-limit groups W P HG, which is not associated with one of the paths associated with our fixed proof system (definition 1.31 in [Se5]). The collection of all these (graded) test sequences factor through a (canonical) collection of maximal left P S Γ-limit groups: LeftP S_{1}^{j}, …, LeftP S_{m_{j}}^{j}, and with them we associate the left P S resolutions that are graded formal closures of the resolutions P SHGHRes (see definition 1.31 in [Se5]).

”Generic” specializations that factor through the P S resolutions P SHGHRes can fail to be valid P S statements also if there exist additional rigid or strictly solid specializations of the Γ-limit groups P SHG(g_{1}, h_{1}, w, p, a) that are not specified by the given specializations. The ”generic” specializations for which there exists ”surplus” in rigid or strictly solid specializations are collected in extra P S (graded) Γ-limit groups and graded resolutions (definition 1.26 in [Se5]).

The extra P S Γ-limit groups and their associated graded formal closures collect all the ”generic” specializations (i.e., all the test sequences) of the P S limit groups P SHGH for which there exist rigid or strictly solid families in addition to those specified by the generic specializations. For a general specialization of the P S limit groups P SHGH, i.e., a specialization which is not necessarily ”generic”, it may as well be that the additional rigid or strictly solid specializations, collected by the extra P S limit groups and their associated graded formal closures, do become flexible or do coincide with the rigid or strictly solid families of the various specializations (g_{t}^{1}, h_{0}^{1}, w_{0}, p_{0}).

We collect all the test sequences of specializations that factor through an extra P S resolution, ExtraP SRes, and are collapsed specializations, in finitely many closures of the resolution P SHGHRes we have started with, which we call formal collapsed Extra P S (graded) resolutions. Collecting all ”collapsed” test sequences in a finite collection of formal collapsed extra P S resolutions, we still need to collect all the collapsed specializations that factor and are taut with respect to a given extra P S resolution ExtraP SRes. We go over all the graded auxiliary resolutions and all the collapse forms associated with the extra P S resolution, ExtraP SRes. Given a graded auxiliary resolution and a collapse form, we add elements that represent the primitive roots of pegs of abelian groups associated with the extra solid resolution, ExtraP SRes, and conjugating elements and the elements corresponding to flexible quotients associated with the given collapse form. We also add new elements that are set to be the primitive roots of pegs of (pegged) abelian groups along the extra P S resolution, ExtraP SRes, for all such pegs that do not belong to a non-QH, non-abelian vertex groups in the terminal (rigid or solid) Γ-limit group of the extra P S resolution, ExtraP SRes. Given the auxiliary limit group or one of its degenerate quotients, and the additional conjugating elements and variables corresponding to flexible quotients according to the given collapse form, and elements that represent primitive roots of pegs of abelian vertex groups, we look at all the specializations of the graded auxiliary Γlimit group (or its degenerate quotient) associated with the given graded auxiliary resolution, and corresponding specializations of primitive roots of the pegs along the extra P S resolution, ExtraP SRes, for which there exist corresponding specializations of the additional elements corresponding to the conjugating elements and flexible quotients, so that the (combined) specializations satisfy the system of equations associated with the given collapse form associated with the extra P S resolution ExtraP SRes. By our standard method presented in section 1, this collection of specializations factor through a canonical (finite) collection of maximal limit groups, which we call collapsed extra P S Γ-limit groups.

By construction, if p_{0} ∈ T_{1}(p) then there must exist a valid P S statement of the form: ((h_{1}^{2}, g_{1}^{1}), …, (h_{ν(ps)}^{2}, g_{ν(ps)}^{1}), h_{0}^{1}, w_{0}, p_{0}, a) that factors through one the of the P S resolutions P SHGHRes_{j} constructed with respect to all proof systems of depth 1. By proposition 3.8 in [Se5], that generalizes in a straight forward way to torsionfree hyperbolic groups, the sets T SP S(p) associated with the various P S resolutions P SHGHRes, i.e., the sets of specializations p_{0} of the defining parameters P =< p > for which there exists a test sequence of valid P S statements that factor through any of the P S resolutions P SHGHRes_{j}, is in the Boolean algebra of AE sets. As in the free group case, if there exists a valid P S statement that factors through a P S resolution P SHGHRes_{j}, then either there exists a test sequence of valid P S statements that factor through the P S resolution, or there must exist a specialization that factors through one of the graded auxiliary resolutions associated with one of the P S resolutions P SHGHRes, and one of its associated collapsed extra P S limit groups.

To analyze the remaining set of valid P S statements we construct an iterative sieve procedure that is similar to the sieve procedure over a free group, presented in [Se6]. Having generalized the core resolution to resolutions over a torsion-free hyperbolic group in the previous section, the structure of the sieve procedure over a torsion-free hyperbolic group and the proof of its termination, is identical to the sieve procedure over a free group, presented in [Se6]. Hence, we omit its details and refer the interested reader to [Se6]. This sieve procedure finally proves theorem 6.3, i.e., it shows that the set of specializations of the defining parameters p, for which there exists a valid PS statement of depth 2, is in the Boolean algebra of AE sets.

The tree of stratified sets has a finite depth, which (by definition) bounds the depth of all possible proof systems associated with the tree of stratified sets. For each integer d, we set T_{d}(p) to be the set of specializations p_{0} of the defining parameters P =< p > for which there exists a valid P S statement for some proof system of depth d. Clearly: EAE(p) = T_{1}(p) ∪ … ∪ T_{d_{0}}(p) where d_{0} is the depth of tree of stratified sets. Each of the sets T_{d}(p) is in the Boolean algebra of AE sets, by applying the same sieve procedure that was used to analyze the set T_{2}(p) (cf. [Se6]). Since a Boolean algebra is closed under finite unions, it follows that every EAE set is in the Boolean algebra of AE sets.

Theorem 6.5. Let Γ =< a_{1}, …, a_{k} > be a torsion-free hyperbolic group, and let the EAE set EAE(p) be defined as:

EAE(p) = ∃w ∀y ∃x (Σ_{1}(x, y, w, p, a) = 1 ∧ Ψ_{1}(x, y, w, p, a) ≠ 1) ∨ …
… ∨ (Σ_{r}(x, y, w, p, a) = 1 ∧ Ψ_{r}(x, y, w, p, a) ≠ 1).

Then EAE(p) is in the Boolean algebra of AE sets.

§7. The elementary theory of a hyperbolic group

In the first six sections of this paper we have modified the techniques presented in [Se1]-[Se6] to prove that every elementary set defined over a torsion-free hyperbolic group is in the Boolean algebra of AE sets (theorem 6.5). In [Se7] we were able to use the quantifier elimination procedure presented in [Se6] to classify those f.g. groups that are elementary equivalent to a free group, i.e., to show that a f.g. group is elementary equivalent to a free group if and only if it is an ω-residually free tower. In this section we use the quantifier elimination procedure for torsion-free hyperbolic groups, to classify those f.g. groups that are elementary equivalent to a given torsion-free hyperbolic group. We start with the following observation.

Proposition 7.1. Let Γ_{1}, Γ_{2} be non-elementary torsion-free rigid hyperbolic groups (i.e., Γ_{1} and Γ_{2} are freely-indecomposable and do not admit any non-trivial cyclic splitting). Then Γ_{1} is elementary equivalent to Γ_{2} if and only if Γ_{1} is isomorphic to Γ_{2}.

Proof: We fix a system of generators of Γ_{1}, Γ_{1} =< g_{1}, …, g_{t} >, and set X to be the Cayley graph of Γ_{1} with respect to the given generating system. By section 8 of [Se11], since Γ_{1} is rigid and Γ_{2} is hyperbolic, there exists a positive integer n_{1}, for which if h : Γ_{1} → Γ_{2} is a homomorphism that maps the elements in a ball of radius n_{1} in the Cayley graph X of Γ_{1} into distinct elements in Γ_{2}, then h is necessarily a monomorphism.

Suppose that Γ_{1} is elementary equivalent to Γ_{2}. Since the existence of a homomorphism from Γ_{1} to Γ_{2} that maps the elements that are in a ball of radius n_{1} in X into distinct elements in Γ_{2}, can be formulated by a (coefficient-free) existential sentence that is truth over Γ_{1}, and Γ_{1} is assumed elementary equivalent to Γ_{2}, there must exist a monomorphism from Γ_{1} to Γ_{2}. Similarly, there must exist a monomorphism from Γ_{2} to Γ_{1}. By the co-Hopf property for hyperbolic groups ([Se9]), Γ_{1} is necessarily isomorphic to Γ_{2}.

□

Proposition 7.1 implies that, in particular, a uniform lattice in a real rank 1 semi-simple Lie group that is not SL_{2}(R) is elementary equivalent to another such lattice if and only if the two lattices are isomorphic. Hence, by Mostow’s rigidity, the two lattices are conjugate in the same Lie group. By Margulis normality and super-rigidity theorems, the same hold in higher rank (real) Lie groups.

Theorem 7.2. Let L_{1}, L_{2} be uniform lattices in real semi-simple Lie groups that are not SL_{2}(R). Then L_{1} is elementary equivalent to L_{2} if and only if L_{1} and L_{2} are conjugate lattices in the same real Lie group G.

Proposition 7.1 shows that rigid hyperbolic groups are elementary equivalent if and only if they are isomorphic. To classify elementary equivalence classes of hyperbolic groups in general, we need to present elementary (hyperbolic) prototypes.

Definition 7.3. Let Γ be a non-elementary torsion-free hyperbolic group. We say that Γ is an elementary-prototype if:

(i) Γ is not an ω-residually free tower (i.e., Γ is not elementary equivalent to a free group).

(ii) Γ admits a (Grushko) free decomposition: Γ = H_{1}∗…∗H_{ℓ}, where H_{1}, …, H_{ℓ} are freely-indecomposable, non-cyclic and are not elementary free towers.

(iii) Each of the factors H_{i} does not admit an endomorphism h : H_{i} → H_{i} with non-trivial kernel, that maps (elementwise) each of the non-QH vertex groups and each of the edge groups in the JSJ decomposition of H_{i} to their conjugates, and each QH onto a non-abelian subgroup.

Like rigid hyperbolic groups, elementary prototypes that are elementary equivalent have to be isomorphic.

Proposition 7.4. Let Γ_{1}, Γ_{2} be two (hyperbolic) elementary-prototypes. Γ_{1} and Γ_{2} are elementary equivalent if and only if they are isomorphic.

Proof: First, suppose that both elementary-prototypes, Γ_{1} and Γ_{2}, are freely indecomposable. We fix a system of generators of Γ_{1}, Γ_{1} =< g_{1}, …, g_{t} >, and set X to be the Cayley graph of Γ_{1} with respect to the given generating system. Suppose that Γ_{1} is elementary equivalent to Γ_{2}. From the universal equivalence of Γ_{1} and Γ_{2}, for every index n, there exists a homomorphism v_{n} : Γ_{1} → Γ_{2} that maps the ball of radius n in X, the Cayley graph of Γ_{1}, monomorphically into Γ_{2}. Moreover, since Γ_{1} is an elementary-prototype, the equivalence of the EA theories of Γ_{1} and Γ_{2} implies that for every integer n, there exists a homomorphism h_{n}, so that for every modular automorphism, φ ∈ Mod(Γ_{1}), the composition h_{n} ∘ φ : Γ_{1} → Γ_{2}, maps the ball of radius n in X monomorphically into Γ_{2}.

The sequence of homomorphisms h_{n} : Γ_{1} → Γ_{2}, contains a subsequence (still denoted {h_{n}}) that converges into an action of Γ_{1} on a real tree Y. Hence, Γ_{1} is a Γ_{2}- limit group. Therefore, either Γ_{1} can be embedded into Γ_{2}, or a subsequence of the homomorphisms h_{n} : Γ_{1} → Γ_{2} factors through a non-trivial taut Makanin-Razborov resolution of the Γ_{2}-limit group Γ_{1}. However, the existence of a subsequence of homomorphisms h_{n} : Γ_{1} → Γ_{2} that factors through a non-trivial resolution of the Γ_{2}-limit group Γ_{1} contradicts our assumption that for every index n, and for every modular automorphism φ ∈ Mod(Γ_{1}), the composition h_{n} ∘ φ embeds the ball of radius n in X, the Cayley graph of Γ_{1}, into Γ_{2}. Hence, Γ_{1} can be embedded in Γ_{2}. In a similar way, Γ_{2} can be embedded in Γ_{1}. Since we assumed that Γ_{1} and Γ_{2} are freely-indecomposable, torsion-free hyperbolic groups, they are co-Hopf by [Se9], which finally implies that Γ_{1} is isomorphic to Γ_{2} in case Γ_{1} and Γ_{2} are elementary equivalent and freely indecomposable.

Suppose that Γ_{1} and Γ_{2} are (general) elementary equivalent prototypes. Let Γ_{1} = H_{1} ∗ … ∗ H_{ℓ} and Γ_{2} = M_{1} ∗ … ∗ M_{s}, where the factors H_{i} and M_{j} are (non-elementary) freely indecomposable and not ω-residually free towers. By the equivalence of the EA theories of Γ_{1} and Γ_{2}, for every n, there exists a homomorphism h_{n}, so that for every modular automorphism φ ∈ Mod(Γ_{1}), the composition h_{n}∘φ : Γ_{1} → Γ_{2}, maps the ball of radius n in X monomorphically into Γ_{2}. Moreover, we can further require that for any possible choice of elements: γ_{1}, …, γ_{ℓ} ∈ Γ_{2}, and every modular automorphism φ ∈ Mod(Γ_{1}), the homomorphism τ_{n} : Γ_{1} → Γ_{2} obtained by setting τ_{n}(H_{i}) = γ_{i}(h_{n} ∘ φ(H_{i}))γ_{i}^{−1}, maps the ball of radius n in X monomorphically into Γ_{2}.

From the sequence of homomorphisms: h_{n} : Γ_{1} → Γ_{2}, it is possible to extract a subsequence that converges into a faithful action of Γ_{1} on a real tree, hence, Γ_{1} and its factors H_{1}, …, H_{ℓ} are all Γ_{2}-limit groups. Since for every modular automorphism φ ∈ Mod(Γ_{1}), h_{n} ∘ φ embeds the ball of radius n in X, the Cayley graph of Γ_{1}, we can further extract a subsequence of homomorphisms (still denoted {h_{n}}) that embeds each of the factors H_{1}, …, H_{ℓ} into Γ_{2}. Similarly, there exist similar subsequence of homomorphisms v_{n} : Γ_{2} → Γ_{1} that have similar properties as the sequence {h_{n}}, and each of the homomorphisms v_{n} embeds the factors M_{1}, …, M_{s} into Γ_{1}.

The homomorphisms {h_{n} : Γ_{1} → Γ_{2}} embed each of the factors H_{i} into Γ_{2}, and the homomorphisms v_{n} : Γ_{2} → Γ_{1} embed each of the factors M_{j} into Γ_{1}. Since the factors H_{i} and M_{j} are freely indecomposable, for each index i, 1 ≤ i ≤ ℓ, h_{n}(H_{i}) is a subgroup of a conjugate of one of the factors M_{j}, and for each index j, 1 ≤ j ≤ s, v_{n}(M_{j}) is a subgroup of a conjugate of one of the factors H_{i}. Therefore, for each index n, with the pair of homomorphisms h_{n}, v_{n} we can associate a two sided directed graph Gr_{n}, where the vertices of the two sides correspond to the factors H_{1}, …, H_{ℓ} and M_{1}, …, M_{s}, from a vertex associated with H_{i} there is an edge connected to it and directed towards the vertex associated with the factor M_{j} that contains a conjugate of h_{n}(H_{i}), and from a vertex associated with M_{j} there is an edge connected to it and directed towards the vertex associated with the factor H_{i} that contains a conjugate of v_{n}(M_{j}).

Since there are only finitely many possibilities for the combinatorial types of the graphs Gr_{n}, we can pass to a further subsequence and assume that they are all identical, which we denote Gr. Since from each vertex in the two-sided directed graph Gr there exists an edge connected to it and directed towards another vertex in Gr, the graph Gr contains a (directed) circle. Let C be an innermost circle in the graph Gr. Since Gr is a two-sided graph, C contains an equal number of vertices corresponding to the factors H_{i} and to the factors M_{j}. Since the factors H_{i} and M_{j} are all assumed to be freely-indecomposable, these factors are co-Hopf. Since, in addition, for every index n, the homomorphism h_{n} embeds the factors H_{i} in Γ_{2}, and the homomorphism v_{n} embeds the factors M_{j} in Γ_{1}, the factors H_{i} and M_{j} that correspond to vertices along the innermost circle C in the directed graph Gr, are pairwise isomorphic, and the homomorphisms h_{n}, v_{n} restricted to the edges in the circle C are isomorphisms.

Since the homomorphisms h_{n}, v_{n} restricted to the edges in the circle C are isomorphisms, and since we assumed that for every index n, and any possible collection of elements γ_{1}, …, γ_{ℓ} ∈ Γ_{2}, and every modular automorphism φ ∈ Mod(Γ_{1}), the homomorphism τ_{n} : Γ_{1} → Γ_{2} obtained by conjugating h_{n}∘φ(H_{i}) by γ_{i} for 1 ≤ i ≤ ℓ, embeds the ball of radius n in X, the Cayley graph of Γ_{1}, and correspondingly for the homomorphism v_{n}, no vertex that is not in the innermost circle C in Gr is connected by an edge to a vertex in C. Applying the same argument for the subgraph Gr \ C, and continuing inductively, we finally obtain that ℓ = s, and up to a change of order the factor H_{i} of Γ_{1} is isomorphic to the factor M_{i} of Γ_{2}, hence, Γ_{1} is isomorphic to Γ_{2}.

□

After showing that the elementary class of an elementary prototype determines its isomorphism class (among the set of elementary prototypes), we (canonically) associate with any given torsion-free hyperbolic group a retract of it which is an elementary prototype, a retract that we call elementary core. As we will see in the sequel, a torsion-free hyperbolic group that is not elementary equivalent to a free group, is elementary equivalent to its elementary core.

Definition 7.5. Let Γ be a non-elementary torsion-free hyperbolic group. We construct the elementary core of Γ iteratively. Let the Grushko’s decomposition of Γ be: Γ = H_{1} ∗ … H_{m} ∗ F_{s}, where each of the factors H_{i} is non-cyclic and freelyindecomposable, and F_{s} is a (possibly trivial) free group. We omit the free factor F_{s}, as well as each of the freely-indecomposable factors H_{i} that are isomorphic to a (closed) surface group that is elementary equivalent to a free group, i.e., a hyperbolic surface group, where the surface is not the non-orientable surface of genus 2. Let H_{1}, …, H_{t} be the remaining factors. We continue by constructing the elementary core of each of the factors H_{i}, EC(H_{i}), and then set the core of the hyperbolic group Γ, EC(Γ), to be:

EC(Γ) = EC(H_{1}) ∗ … ∗ EC(H_{t}).

To construct the elementary core of a freely indecomposable, non-cyclic factor H_{i}, we associate with it its (cyclic) JSJ decomposition. If H_{i} is an elementary prototype (see definition 7.3), we set EC(H_{i}) = H_{i}, and conclude the construction of the elementary core of the factor H_{i}. If H_{i} is not an elementary prototype, there must exist an endomorphism ν : H_{i} → H_{i} with non-trivial kernel, that maps each of the non-QH vertex groups in the JSJ decomposition of H_{i} into a conjugate (elementwise), and each QH vertex group onto a non-abelian subgroup. The existence of such endomorphism ν, implies the existence of a proper retract, r : H_{i} → H_{i}, that maps the factor H_{i} onto the fundamental group of a (not necessarily connected) proper subgraph of the JSJ decomposition of H_{1}, maps (elementwise) each of the non-QH vertex groups into a conjugate and each QH vertex group onto a non-abelian subgroup (see the argument used to prove proposition 6 in [Se7] for the existence of the proper retract r, given the proper map ν).

The image of the retract r, is the fundamental group of a subgraph of the JSJ decomposition of the torsion-free hyperbolic factor H_{i}, hence, it is a torsion-free hyperbolic group. Continuing the construction iteratively, we set the elementary core of the factor H_{i} to be: EC(H_{i}) = EC(r(H_{i})). In each step along the iterative construction of the elementary core of the torsionfree hyperbolic group Γ, we replace a factor by a proper retract of it, which is a proper quotient of the factor, and a subgroup of the original torsion-free hyperbolic group Γ. Hence, the descending chain condition for Γ-limit groups (theorem 1.12) proves that the construction of the elementary core terminates after finitely many steps.

Note that by construction, the ambient torsion-free hyperbolic group Γ has the structure of a tower, in which the bottom level is a free product of the elementary core, EC(Γ), with a (possibly trivial) collection of a free group and surface groups, and in each level of the tower a punctured surface group is being added, so that the boundaries of the punctured surface are identified with non-trivial elements in the group associated with the previous level. In addition there are retracts associated with the tower, mapping the groups associated with the various levels to the groups associated with the previous ones (cf. the structure of ω-residually free towers in [Se7]).

By construction, the elementary core of a (non-elementary) torsion-free hyperbolic group is trivial if and only if the hyperbolic group is an ω-residually free tower, i.e., if it is elementary equivalent to a free group. Along the construction of the elementary core various choices can be made, and indeed, in general the elementary core of a torsion-free hyperbolic group is not necessarily a unique subgroup. The next theorem shows that an elementary core is an elementary submodel of a torsion-free hyperbolic group. Hence, every two elementary cores are elementary equivalent, and since an elementary core is an elementary prototype, proposition 7.4 implies that the isomorphism type of an elementary core is uniquely defined.

Theorem 7.6. Let Γ be a non-elementary torsion-free hyperbolic group that is not an ω-residually free tower, i.e., that is not elementary equivalent to a free group. Then Γ is elementary equivalent to its elementary core, EC(Γ). Furthermore, the embedding of the elementary core, EC(Γ), in the ambient group Γ is an elementary embedding.

Proof: Let EC = EC(Γ). By the construction of the elementary core, EC, from the torsion-free hyperbolic group Γ, it follows that Γ is the fundamental group of a tower over the elementary core, EC, free product with a (possibly trivial) finite collection of surface groups and a free group, that we denote T wr. With the structure of the tower T wr we associate a (completed) resolution over the coefficient group EC, that we denote Res_{Γ}. Note that the terminal group of Res_{Γ} is a free product of EC with a (possibly trivial) collection of surface groups and a free group.

Let EC =< a_{1}, …, a_{k} >, and let Σ(y, a) = 1 be a system of equations with coefficients in the elementary core, EC. With the system Σ(y, a) = 1, interpreted as a system of equations over EC, which is in particular a torsion-free hyperbolic group, we have associated a taut Makanin-Razborov diagram. With each resolution in this taut Makanin-Razborov diagram we have associated its completion. Let Comp(Res_{1})(z, y, a), …, Comp(Res_{d})(z, y, a) be the set of these completions.

Lemma 7.7. Let y′ be a solution of the system Σ(y, a) = 1, interpreted as a system of equations over the ambient torsion-free hyperbolic group Γ. Then there exist elements z′ in Γ, so that the tuple (z′, y′) is a specialization of (at least) one of the completions Comp(Res_{1})(z, y, a), …, Comp(Res_{d})(z, y, a), i.e., it is the image of a homomorphism from the Γ-limit group associated with one of these completions into Γ.

Proof: We look at a test sequence of the resolution, Res_{Γ}(b), associated with the tower T wr, in the core EC. Let y′_{n} ∈ EC be the sequence of specializations of the elements y′ ∈ Γ along the given test sequence. Since Σ(y′, a) = 1 in Γ, the sequence y′_{n} satisfies Σ(y′_{n}, a) = 1 in EC, for every index n. Hence, for every index n, there exist elements z′_{n} ∈ EC, so that the tuple (z′_{n}, y′_{n}, a) is a specialization of one of the completions Comp(Res_{1})(z, y, a), …, Comp(Res_{d})(z, y, a). If for every n we choose the shortest such z′_{n}, then the techniques used for the construction of a formal solution ([Se2],1.17), prove that there exists a subsequence of tuples (z′_{n}, y′_{n}, a) that are all specializations of the same completion, Comp(Res_{i})(z, y, a), that converge into tuple (z′, y′, a) ∈ Γ, and the tuple (z′, y′, a) is a specialization of the completion Comp(Res_{i})(z, y, a).

□

Clearly, the same argument used to prove lemma 7.7 applies to specializations of graded and multi-graded systems of equations, and the completions of the corresponding taut graded and multi-graded taut Makanin-Razborov diagrams. Let Θ(y, a) = 1 be a system of equations with coefficients in the elementary core, EC, and let:

(∀y) (Θ(y, a) = 1) ∃x Σ(x, y, a) = 1 ∧ Ψ(x, y, a) ≠ 1

be a sentence. Suppose that the sentence is a truth sentence over the elementary core, EC. By theorem 2.1, with each resolution Res(y, a) in the taut Makanin-Razborov diagram associated with the system Θ(y, a) = 1 over the elementary core, EC, it is possible to associate finitely many formal solutions x = x_{i}(s, z, y, a) defined over closures of that resolution, Cl_{i}(Res)(s, z, y, a), that for a covering closure of the resolution Res(y, a), for which for every index i:

(i) Σ(x(s, z, y, a), y) = 1 in the EC-limit group corresponding to the closure Cl_{i}(Res)(s, z, y, a).

(ii) there exists a specialization (s_{i}, z_{i}, y_{i}, a) (in the core EC), of the closure

Cl_{i}(Res)(s, z, y, a), for which Ψ(x(s_{i}, z_{i}, y_{i}, a), y_{i}, a) ≠ 1 (in EC). By lemma 7.7, if y′ is a solution of the system Θ(y, a) = 1 interpreted as a

system of equations over the ambient group Γ, then there exists elements z′ in Γ, so that the tuple (z′, y′) is a specialization of (at least) one of the completions Comp(Res_{1})(z, y, a), …, Comp(Res_{d})(z, y, a) of the resolutions in the taut Makanin-Razborov diagram associated with the system of equations Θ(y, a) = 1. Hence, there exists a closure of some of these completions, a formal solution x_{i}(s, z, y, a), and elements s′, for which: Θ(x_{i}(s′, z′, y′, a), y, a) = 1 over that closure. Clearly, the graded and multi-graded categories are completely analogous.

Proposition 7.8. Let:

∀y ∃x (Σ_{1}(x, y, a) = 1 ∧ Ψ_{1}(x, y, a) ≠ 1) ∨ … ∨ (Σ_{r}(x, y, a) = 1 ∧ Ψ_{r}(x, y, a) ≠ 1)

be an AE sentence with coefficients in the elementary core, EC. Then the AE sentence is a truth sentence over the EC if and only if it is a truth sentence over the ambient hyperbolic group Γ. i.e., the embedding of the elementary core of a torsion-free hyperbolic group into the ambient hyperbolic group is an AE embedding.

Proof: Suppose that

∀y ∃x (Σ_{1}(x, y, a) = 1 ∧ Ψ_{1}(x, y, a) ≠ 1) ∨ … ∨ (Σ_{r}(x, y, a) = 1 ∧ Ψ_{r}(x, y, a) ≠ 1)

is a sentence with coefficients in the elementary core, EC. If the sentence is a truth sentence over EC, then it is possible to apply the iterative procedure presented in section 4 (based on [Se4]), and associate iteratively with the sentence a (finite) sequence of anvils, developing resolutions and formal solutions defined over them, that prove the validity of the sentence over the elementary core EC. By the arguments given above, the proof given by the sequence of anvils, developing resolutions, and formal solutions defined over them, is valid over the non-elementary torsion-free hyperbolic group Γ.

Suppose that the given sentence is false over the elementary core, EC. By applying the iterative procedure for validation of a sentence over EC, there exists a resolution Res(z, y, a) over EC, so that there exists a test sequence of specializations of this resolution (over EC), for which for the corresponding specializations of the variables y, there is no specialization of the variables x (in EC) for which:

(Σ_{1}(x, y, a) = 1 ∧ Ψ_{1}(x, y, a) ≠ 1) ∨ … ∨ (Σ_{r}(x, y, a) = 1 ∧ Ψ_{r}(x, y, a) ≠ 1).

We want to show that the given sentence is false over the ambient hyperbolic group Γ. The resolution Res(z, y, a) is a resolution over the elementary core, EC, hence, it is also a resolution over the ambient hyperbolic group Γ. By our assumptions, the resolution Res(z, y, a) has a test sequence of specializations in EC, so that for the corresponding sequence of specializations of the variables y, there are no specializations of the variables x in EC, for which:

(Σ_{1}(x, y) = 1 ∧ Ψ_{1}(x, y) ≠ 1) ∨ … ∨ (Σ_{r}(x, y) = 1 ∧ Ψ_{r}(x, y) ≠ 1).

EC is a non-elementary quasi-convex subgroup of Γ, so the test sequence of specializations of the resolution Res(z, y, a) in EC is also a test sequence of specializations of the resolution Res(z, y, a) in the ambient group Γ. Suppose that our given sentence is a truth sentence over Γ. Then for each specialization of the variables y from our given test sequence, there exists a specialization of the variables x in Γ for which:

(Σ_{1}(x, y, a) = 1 ∧ Ψ_{1}(x, y, a) ≠ 1) ∨ … ∨ (Σ_{r}(x, y, a) = 1 ∧ Ψ_{r}(x, y, a) ≠ 1)

where the equalities and inequalities are in Γ. Using our machinery for constructing a formal solution (theorem 2.1), and after possibly passing to a subsequence of the test sequence in Γ, we obtain a formal solution x = x(s, z, y, a) defined over some closure Cl(s, z, y, a) of the resolution Res(z, y, a) over Γ. Since Γ retracts onto its elementary core, the existence of a formal solution over the ambient group Γ, implies the existence of a formal solution x′ = x′(s, z, y, a) defined over a closure Cl′(s, z, y, a) of the resolution Res(z, y, a) over the elementary core, EC, where the same test subsequence that factored through the closure, Cl(s, z, y, a), factors through the closure Cl′(s, z, y, a). This is a contradiction, since we assumed that for every specialization of the variables y in the test sequence, there does not exist a specialization of the variables x in the elementary core, EC, for which the set of equalities and inequalities defining the sentence hold.

□

Proposition 7.8 proves that the embedding of the elementary core into the ambient torsion-free hyperbolic group is an AE embedding (assuming the ambient group is not elementary equivalent to a free group). To prove that the embedding is an elementary embedding, it remains to prove that the quantifier elimination procedure conducted over EC, for predicates defined over the elementary core, EC, is valid over the the ambient hyperbolic group Γ. The quantifier elimination procedure presented in [Se5] (and section 6) is composed from two parts, the procedure for the construction of the tree of stratified sets, and the sieve procedure. We start by showing that the procedure for the construction of stratified sets remains valid over the ambient group.

The procedure for the construction of the tree of stratified sets analyzes the remaining set of y’s using multi-graded resolutions, and their associated developing resolutions, and then we associate with each developing resolution, its entire collection of formal solutions, which are encoded in the graded formal diagram. Since the predicates we consider are defined over the elementary core, EC, and the construction of the tree of stratified sets is conducted over EC, all the resolutions are defined over EC, and all the limit groups are EC-limit groups. Lemma 7.7 proves that the set of the remaining y’s over the group Γ at each step, can be completed to specializations that factor through the completions of the multi-graded resolutions at each step of the procedure for the construction of the tree of stratified sets (over EC). We have also argued that if p_{0} is in the definable set of the given predicate, interpreted as a predicate over Γ, then with each ungraded resolution associated with the (graded) developing resolution and p_{0}, there exists a formal solution (over Γ) that satisfies the properties of theorem 2.1. The ungraded resolution defined over Γ, can be approximated by a sequence of ungraded resolutions over the core, EC. From the existence of a formal solution defined over the given ungraded resolution over Γ, it follows that all the approximating resolutions over EC admit formal solutions that approximate the formal solution over |gamma. Hence, the given formal solution defined over Γ, factors through the completion of at least one of the graded formal resolutions associated with the given developing resolution over the elementary core EC.

The iterative procedure for validation of an AE sentence, shows that if an AE sentence over EC is a truth sentence, then it has a proof using a finite collection of formal solutions. By the proof of lemma 7.7, the same is true for sentences defined over Γ.

Let L(p, w) be an AE predicate defined over the elementary core, EC. Let Q_{EC}(w, p) be the set defined by L(p, w) over the EC, and Q_{Γ}(p, w) be the set defined by L(p, w) over Γ. The tree of stratified sets constructed over the free group EC, shows that if (p_{0}, w_{0}) ∈ Q_{EC}(p, w), then the sentence corresponding to the specialization (p_{0}, w_{0}) can be proved using a sequence of formal solutions according to one of the proof systems given by the tree of stratified sets over EC. The argument given above, shows that if (p_{0}, w_{0}) ∈ Q_{Γ}(p, w), then the sentence corresponding to the specialization (p_{0}, w_{0}) can be proved using a sequence of formal solutions according to one of the proof systems given by the same tree of stratified sets (over EC). Furthermore, if Rgd(x, p, a) (Sld(x, p, a)) is a rigid (solid) EC-limit group, then the maximal rigid (families of strictly solid) specializations of Rgd(x, p, a) (Sld(x, p, a)) for a specialization of the defining parameter p is identical over the elementary core EC, and the ambient group Γ. Hence, the collection of proof systems associated with the tree of stratified sets is identical over EC and over Γ, i.e., for the two sets Q_{EC}(w, p) and Q_{Γ}(w, p).

The collection of proof systems associated with the tree of stratified sets over EC and over Γ are identical. Any valid P S statement over Γ can be approximated by a sequence of valid P S statements over EC. Furthermore, any valid P S statement over Γ does not factor through any of the Non-Rigid, Non-Solid or Left P S resolutions constructed along the Sieve procedure over EC, and if it factors through an extra P S resolution, it has to factor through either one of the collapse extra P S EC-limit groups associated with it, or one of the formal collapse extra P S resolutions associated with it (constructed over EC). Hence, any valid P S statement over Γ, belongs to at least one of the T SP S(p) sets constructed along the sieve procedure (over the core EC). Therefore, the reduction of a predicate defined over the elementary core, EC, to a predicate in the Boolean algebra of AE sets, can be done uniformly for the towers defined over the elementary core EC, i.e., for all the torsion-free hyperbolic groups for which EC is their elementary core. Since the AE theories of these towers are equivalent by proposition 7.8, the elementary core EC is an elementary submodel of the ambient torsion-free hyperbolic group Γ.

□

Corollary 7.9. Let Γ_{1}, Γ2 be two non-elementary torsion-free hyperbolic groups.

Then Γ_{1} and Γ_{2} are elementary equivalent if and only if their elementary cores, EC(Γ_{1}) and EC(Γ_{2}), are isomorphic.

Proof: By the construction of the elementary core (definition 7.5), the elementary core of a torsion-free hyperbolic group is trivial if and only if the torsion-free hyperbolic group is a hyperbolic ω-residually free tower, i.e., if and only if it is elementary equivalent to a free group. Hence, to prove the corollary we may assume that both hyperbolic groups, Γ_{1} and Γ_{2}, are not elementary equivalent to a free group.

By theorem 7.6 Γ_{1} and Γ_{2} are elementary equivalent to their elementary cores, EC(Γ_{1}) and EC(Γ_{2}), in correspondence. An elementary core of a non-elementary, torsion-free hyperbolic group that is not elementary equivalent to a free group is an elementary prototype, hence, by proposition 7.4, EC(Γ_{1}) is elementary equivalent to EC(Γ_{2}) if and only if EC(Γ_{1}) is isomorphic to EC(Γ_{2}), and the corollary follows.

□

Corollary 7.9 determines the elementary classes of (torsion-free) hyperbolic groups. The next theorem shows that hyperbolicity is preserved under elementary equivalence.

Theorem 7.10. Let Γ be a torsion-free hyperbolic group, and let G be a f.g. group. If G is elementary equivalent to Γ, then G is a torsion-free hyperbolic group. Hence, either:

(i) Both G and Γ are either trivial or (infinite) cyclic.

(ii) Both G and Γ are ω-residually free groups, i.e., they are both elementary

equivalent to a non-abelian free group. (iii) Both G and Γ are non-elementary and not ω-residually free towers, and the

elementary core of Γ, EC(Γ), is isomorphic to the elementary core of G, EC(G).

Proof: Let Γ be a torsion-free hyperbolic group and G a f.g. group, and suppose that Γ is elementary equivalent to G. A f.g. group that is elementary equivalent to a trivial or an infinite cyclic group is trivial or infinite cyclic in correspondence. By [Se7] a f.g. group that is elementary equivalent to a free group is an ω-residually free tower, which is, in particular, a torsion-free hyperbolic group. Hence, to prove the theorem we may assume that the torsion-free hyperbolic group Γ is non-elementary, and not an ω-residually free tower, i.e., not elementary equivalent to a free group. Under these assumptions, we can associate with Γ its elementary core, EC(Γ), and by theorem 7.6 Γ is elementary equivalent to EC(Γ), so EC(Γ) is elementary equivalent to G.

Since the elementary core, EC(Γ), is a torsion-free hyperbolic group, and G is elementary equivalent to EC(Γ), G is, in particular, universally equivalent to EC(Γ), which implies that there exists a sequence of homomorphisms u_{n} : G → EC(Γ), so that for each index n, u_{n} embeds the elements in the ball of radius n in G into EC(Γ), hence, G is an EC(Γ)-limit group. Since G is an EC(Γ)-limit group, and G is elementary equivalent to a torsion-free hyperbolic group, G contains no non-cyclic abelian subgroups. Hence, by applying the construction presented in definition 7.5, one can associate with G a core, which we denote C(G), together with a sequence of retracts of G:

G → G_{1} → G_{2} → … → G_{t} = C(G)

that is used in the construction of the core, C(G), and in which all the retracts G_{i} are EC(Γ)-limit groups.

At this point we modify the argument used to prove that elementary equivalent elementary prototypes are isomorphic (proposition 7.4), in order to prove that EC(Γ) and the core of G, C(G), are isomorphic. This implies that the core, C(G), is a torsion-free hyperbolic group, which further implies, by the construction of the core and the combination theorem of M. Bestvina and M. Feighn [Be-Fe3], that G is a torsion-free hyperbolic group.

Let EC(Γ) = H_{1} ∗ … ∗ H_{ℓ} and C(G) = M_{1} ∗ … ∗ M_{s}, where the factors H_{i} and M_{j} are (non-elementary) freely indecomposable and not ω-residually free towers. By the equivalence of the EA theories of EC(Γ) and G, for every n, there exists a homomorphism h_{n} : C(G) → EC(Γ), so that for every modular automorphism φ ∈ Mod(C(G)), the composition h_{n} ∘ φ : C(G) → EC(Γ), maps the ball of radius n in the Cayley graph of C(G) monomorphically into EC(Γ). Moreover, we can further require that for any possible choice of elements: γ_{1}, …, γ_{s} ∈ EC(Γ), and every modular automorphism φ ∈ Mod(C(G)), the homomorphism τ_{n} : C(G) → EC(Γ) obtained by setting τ_{n}(M_{i}) = γ_{i}(h_{n} ∘ φ(M_{i}))γ_{i}^{−1}, maps the ball of radius n in X monomorphically into EC(Γ). From the sequence of homomorphisms: h_{n} : C(G) → EC(Γ), it is possible to extract a subsequence that converges into a faithful action of C(G) on a real tree. Since for every modular automorphism φ ∈ Mod(C(G)), h_{n} ∘ φ embeds the ball of radius n in the Cayley graph of C(G), we can further extract a subsequence of homomorphisms (still denoted {h_{n}}) that embeds each of the factors M_{1}, …, M_{s} into EC(Γ).

We continue by constructing a torsion-free hyperbolic group L, into which the f.g. group G is naturally embedded. By the above argument, each of the factors M_{i}, 1 ≤ i ≤ s, of the core, C(G), is embedded in the elementary core EC(Γ), hence, for each index i, 1 ≤ i ≤ s, we fix an embedding: ν_{i} : M_{i} → EC(Γ). By the construction of the core of the EC(Γ)-limit group G, C(G) (see definition 7.5), the EC(Γ)-limit group G is obtained from its core, C(G), which is a retract of G, by starting with a free product of C(G) with a (possibly trivial) free product of a free group and closed hyperbolic surface groups, and then iteratively adding hyperbolic punctured-surface groups that are amalgamated to the group associated with the previous steps along their boundary subgroups. We construct the hyperbolic group L, by imitating the construction of G from C(G). We start with s copies of the elementary core, EC(Γ), where with the i-th copy of EC(Γ) we associate the (fixed) image of the factor M_{i} by the i-th embedding: ν_{i} : M_{i} → EC(Γ). We continue with a free product of the s copies of EC(Γ) free product with a (possibly trivial) free product of a free group and closed hyperbolic surface groups, as in the free product associated with the bottom level of the construction of G from its core, C(G). We further continue the construction of the group L by iteratively adding hyperbolic punctured-surface groups that are amalgamated to the group associated with the previous steps along their boundary components, precisely as in the construction of G from its core, C(G). By construction, L is torsion-free and G is a subgroup of L, and by the combination theorem of M. Bestvina and M. Feighn [Be-Fe3], L is a hyperbolic group.

Recall that EC(Γ) = H_{1} ∗ … ∗ H_{ℓ} and C(G) = M_{1} ∗ … ∗ M_{s}, where the factors H_{i} and M_{j} are (non-elementary) freely indecomposable and not ω-residually free towers. By the equivalence of the EA theories of EC(Γ) and G, for every n, there exists a homomorphism v_{n} : EC(Γ) → G, so that for every modular automorphism φ ∈ Mod(EC(Γ)), the composition v_{n} ∘ φ : EC(Γ) → G, maps the ball of radius n in the Cayley graph of EC(Γ) monomorphically into G. Moreover, we can further require that for any possible choice of elements: g_{1}, …, g_{ℓ} ∈ G, and every modular automorphism φ ∈ Mod(EC(Γ)), the homomorphism τ_{n} : EC(Γ) → G obtained by setting τ_{n}(H_{i}) = g_{i}(v_{n}∘φ(H_{i}))g_{i}^{−1}, maps the ball of radius n in X monomorphically into G. Since G is embedded in the hyperbolic group L, we can further compose the sequence of homomorphisms {v_{n}}, with the embedding ν : G → L, and obtain a sequence of homomorphisms v̂_{n} : EC(Γ) → L. From the sequence of homomorphisms: v̂_{n} : EC(Γ) → L, it is possible to extract a subsequence that converges into a faithful action of EC(Γ) on a real tree. Since for every modular automorphism φ ∈ Mod(EC(Γ)), v_{n} ∘ φ embeds the ball of radius n in the Cayley graph of EC(Γ), we can further extract a subsequence of homomorphisms (still denoted {v_{n}}) that embeds each of the factors H_{1}, …, H_{ℓ} into G. By the construction of the core of the EC(Γ)-limit group G, C(G), since EC(Γ) is an elementary prototype and for every index n, the homomorphism v_{n} : EC(Γ) → G embeds each of the factors H_{1}, …, H_{ℓ} of EC(Γ) into G, for every index n, the composition of v_{n} with the projection from the EC(Γ)-limit group G to its core C(g), η : G → C(G), v′_{n} = η ∘ v_{n} : EC(Γ) → C(G), embeds each of the factors H_{1}, …, H_{ℓ} into the core C(G).

At this point we can continue in a similar way to the argument used to prove proposition 7.4. The homomorphisms h_{n} : C(G) → EC(Γ) embed each of the factors M_{j} into EC(Γ), and the homomorphisms v′_{n} : EC(Γ) → C(G) embed each of the factors H_{i} into C(G). Since the factors H_{i} and M_{j} are freely indecomposable, for each index i, 1 ≤ i ≤ ℓ, v′_{n}(H_{i}) is a subgroup of a conjugate of one of the factors M_{j}, and for each index j, 1 ≤ j ≤ s, h_{n}(M_{j}) is a subgroup of a conjugate of one of the factors H_{i}. Therefore, for each index n, with the pair of homomorphisms h_{n}, v′_{n} we can associate a two sided directed graph Gr_{n}, where the vertices of the two sides correspond to the factors H_{1}, …, H_{ℓ} and M_{1}, …, M_{s}, from a vertex associated with H_{i} there is an edge connected to it and directed towards the vertex associated with the factor M_{j} that contains a conjugate of v′_{n}(H_{i}), and from a vertex associated with M_{j} there is an edge connected to it and directed towards the vertex associated with the factor H_{i} that contains a conjugate of h_{n}(M_{j}).

Since there are only finitely many possibilities for the combinatorial types of the graphs Gr_{n}, we can pass to a further subsequence and assume that they are all identical, which we denote Gr. As in the proof of proposition 7.4, the directed graph Gr contains a (directed) circle, and an innermost circle, which we denote C, contains an equal number of vertices corresponding to the factors H_{i} and to the factors M_{j}. Since the factors H_{i} are all assumed to be freely-indecomposable, these factors are co-Hopf. Since, in addition, for every index n, the homomorphism v′_{n} embeds the factors H_{i} into C(G), and the homomorphism h_{n} embeds the factors M_{j} into EC(Γ), the factors H_{i} and M_{j} that correspond to vertices along the innermost circle C in the directed graph Gr, are pairwise isomorphic, and the homomorphisms h_{n}, v′_{n} restricted to the edges in the circle C are isomorphisms.

Since the homomorphisms h_{n}, v′_{n} restricted to the edges in the circle C are isomorphisms, and since we assumed that for every index n and any possible collection of elements g_{1}, …, g_{ℓ} ∈ G, and a modular automorphism φ ∈ Mod(EC(Γ)), the homomorphism τ_{n} : EC(Γ) → C(G) obtained by conjugating v′_{n} ∘ φ(H_{i}) by γ_{i} for 1 ≤ i ≤ ℓ, embeds the ball of radius n in the Cayley graph of EC(Γ), and correspondingly for the homomorphism h_{n}, no vertex that is not in the innermost circle C in Gr is connected by an edge to a vertex in C. Applying the same argument for the subgraph Gr \ C, and continuing inductively, we finally obtain that ℓ = s, and up to a change of order the factor H_{i} of EC(Γ) is isomorphic to the factor M_{i} of C(G), hence, EC(Γ) is isomorphic to C(G), and in particular, the core C(G) is a torsion-free hyperbolic group. By the construction of the core C(G) from the EC(Γ)-limit group G, the combination theorem of Bestvina-Feighn [Be-Fe3] implies that G is a torsion-free hyperbolic group. Therefore, the rest of the theorem follows from corollary 7.9.

□

Corollary 7.9 asserts that the elementary class of a torsion-free hyperbolic group that is not elementary equivalent to a free group is determined by the isomorphism class of its elementary core. Hence, in order to be able to decide if two torsion-free hyperbolic groups are elementary equivalent one needs to decide if they are elementary equivalent to a free group, and if they are not, to compute their elementary core, and to decide if the two elementary cores are isomorphic.

Theorem 7.11. Let Γ_{1}, Γ2 be two torsion-free hyperbolic groups. Then it is decidable if Γ_{1} is elementary equivalent to Γ_{2}.

Proof: According to corollary 7.9, in order to decide if two torsion-free hyperbolic groups, Γ_{1} and Γ_{2}, are elementary equivalent, we need to check the following:

(i) Decide if either Γ_{1} or Γ_{2} are trivial or elementary cyclic. To be elementary equivalent, if one of them is trivial or elementary cyclic, the other must be as well.

(ii) Assuming both Γ_{1} and Γ_{2} are non-elementary, we need to construct effec-

tively their elementary cores, EC(Γ_{1}) and EC(Γ_{2}). (iii) Once the elementary cores, EC(Γ_{1}) EC(Γ_{2}), are constructed, we need to

check effectively if they are isomorphic. Given a hyperbolic group there is an algorithm to find its hyperbolicity constant

δ ([Gr],[Pa]). Given δ, the word problem is decidable, hence, it is possible to decide if any of the two given torsion-free hyperbolic groups, Γ_{1} and Γ_{2}, are trivial or infinite cyclic. Hence, for the rest of the argument, we may assume that both Γ_{1} and Γ_{2} are non-elementary.

By the construction of the elementary core (definition 7.5), the core itself it is a torsion-free hyperbolic group. Hence, once the cores of Γ_{1} and Γ_{2} are constructed, the solution to the isomorphism problem for torsion-free hyperbolic groups ([Se12]) decides effectively if the cores, EC(Γ_{1}) and EC(Γ_{2}), are isomorphic. Therefore, to prove theorem 7.11, we are only required to give a procedure to construct the elementary core of a torsion-free hyperbolic group effectively.

The construction of the elementary core of a torsion-free hyperbolic group Γ is conducted iteratively. Given the group Γ, we first need to find effectively its 9possibly trivial) Grushko’s decomposition: Γ = H_{1} ∗…∗H_{m} ∗F_{s}, where the factors H_{i} are non-elementary and freely indecomposable. We need to decide effectively which of the freely-indecomposable factors is a (non-exceptional) surface groups, and for those that are not surface groups, we need to compute effectively the (essential) JSJ decomposition of each of the factors H_{i}, and once the JSJ is given, we need to check if there is proper retract of a given factor into the fundamental group of a proper subgraph of the JSJ decomposition, so that the retract maps each non-QH vertex group and each edge group in the JSJ to a conjugate (elementwise), and each QH vertex groups is mapped into a non-abelian subgroup. Once such a proper retract exists, for at least one of the factors, we continue iteratively. By theorem 1.12, the construction terminates after finitely many steps (see definition 7.5).

The Grushko factorization of a torsion-free hyperbolic group can be found effectively by either the procedure suggested by Gerasimov in [Ge], or the procedure presented in [Se12] for the same purpose, as part of the solution of the isomorphism problem. The JSJ decomposition of a freely-indecomposable, torsion-free hyperbolic group is constructed effectively in [Se12] (see also section 9 in [Se11]), and using its construction it is also possible to decide which of the freely indecomposable factors in the Grushko’s decomposition are (non-exceptional) surface groups. Once the JSJ decomposition of the various factors is constructed, we still need to decide effectively which of them admits a proper retract onto a fundamental group of the subgraph of the JSJ decomposition, so that each non-QH vertex group and each edge group is mapped to a conjugate (elementwise) and each surface group is mapped into a non-trivial subgroup.

Given a factor in the Grushko decomposition of Γ, to check if there exists such a retract, we go over all the proper (not necessarily connected) subgraphs of the JSJ that contain all the non-QH vertex groups and all the edges between them, in parallel. Given such a subgraph, we need to check effectively if there is a map of each of the remaining QH vertex groups into the fundamental group of the subgraph, that maps the boundary of each of the QH vertex groups into the edge group it is connected to, and so that the image of each of the QH vertex groups is non-abelian.

The fundamental group of a subgraph of the JSJ decomposition is a torsion-free hyperbolic group. The existence of a homomorphism of a QH vertex group into the fundamental group of the given subgraph, that maps the boundary elements of the QH vertex into the edge groups it is connected to, naturally translates into a finite system of equations (with coefficients), over the fundamental group of the subgraph. To impose the image of each QH vertex group to be non-abelian, we further need to replace the finite system of equations, by a finite disjunction of finite systems of equalities and inequalities. Hence, it is sufficient to show that it is decidable if a finite system of equalities and inequalities has a solution, i.e., to show that the universal theory of a torsion-free hyperbolic group is decidable (note that the Diophantine theory of a torsion-free hyperbolic group is decidable by [Ri-Se3]).

Theorem 7.12. The universal theory of a torsion-free hyperbolic group is decidable.

Proof: Let Γ =< a_{1}, …, a_{k} > be a non-elementary torsion-free hyperbolic group, and let F_{k} =< f_{1}, …, f_{k} > be a free group of rank k. With the hyperbolic group Γ, we naturally associate the quotient map τ : F_{k} → Γ, that map f_{i} to a_{i}, for i = 1, …, k. Let Σ(y, a) = 1 be a finite system of equations over Γ, and letΨ(y, a) ≠ 1 be a finite system of inequalities over Γ. To show that the universal theory over Γ is decidable, we need an effective procedure to decide if the conjunction of Σ and Ψ has a solution.

By [Ri-Se3], with the system Σ it is possible to associate effectively finitely many systems of equations over the free group F_{k}:

Σ_{1}(x_{1}, f) = 1, …, Σ_{ℓ}(x_{ℓ}, f) = 1

so that for every index i, 1 ≤ i ≤ ℓ, there exists a tuple of elements ŷ_{i} ∈< x_{i}, f >, and for every solution x_{i}^{0} of the system of equations Σ_{i}, i.e., for every x_{0}^{i} that satisfies Σ_{i}(x_{i}^{0}, a) = 1, τ(y_{i}^{0}) is a solution of the system Σ, i.e., Σ(τ(y_{i}^{0}), a) = 1. Furthermore, every solution of the system Σ(y, a) = 1 over Γ, is obtained in that way from one of the systems Σ_{i}(x_{i}, a) = 1 over the free group F_{k}.

By the Bulitko lemma (cf. lemma 1.4 in [Ma]), if a system of equations over a free group has a solution, then it has a solution with periodicity bounded by a constant that can be computed from the combinatorial complexity of the system of equations (see lemma 1.4 in [Ma] for this constant). The Bulitko lemma naturally generalizes to a conjunction of a system of equalities and inequalities over a free group, and using the canonical representatives presented in [Ri-Se3], it generalizes to the conjunction of systems of equalities and inequalities over a torsion-free hyperbolic group.

Therefore, if the conjunction of the systems Σ(y, a) = 1 and Ψ(y, a) ≠ 1 has a solution in the hyperbolic group Γ, then there exists an index i, 1 ≤ i ≤ ℓ, and a solution x_{i}^{0} of the system Σ_{i}(x_{i}, f) = 1 for which:

(i) Σ(τ(y_{i}^{0}), a) = 1 and Ψ(τ(y_{i}^{0}), a) ≠ 1 (in Γ).

(ii) the periodicity of x_{0}^{i} is bounded by a constant that can be effectively computed, and depends only on the given presentation of Γ, Γ =< a_{1}, …, a_{k} >, and the combinatorial structures of the systems Σ and Ψ.

Given the generalization of the Bulitko lemma, to decide effectively if the conjunction of the systems Σ(y, a) = 1 and Ψ(x, a) ≠ 1 has a solution over the torsionfree hyperbolic group Γ, we use [Ri-Se3] to construct effectively the systems of equations:

Σ_{1}(x_{1}, f) = 1, …, Σ_{ℓ}(x_{ℓ}, f) = 1.

By the work of A. Razborov [Ra], given the systems of equations, Σ_{i}, over the free group F_{k}, and the effective bound on the periodicity given by the Bulitko lemma, it is possible to extract finitely many fundamental sequences, so that all the solutions of the systems Σ_{i} with periodicity bounded by the prescribed bound, factor factor through.

These fundamental sequences, constructed by the Makanin-Razborov machinery, correspond to resolutions of the (F_{k}) limit groups associated with the various systems Σ_{i}. To decide if the conjunction of the systems Σ(y, a) = 1 and Ψ(y, a) ≠ 1 has a solution, we continue by replacing each resolution constructed by the Makanin-Razborov machinery from the various systems Σ_{i}, with a strict resolution over the hyperbolic group Γ. Once the resolutions over Γ are strict, it is rather straightforward to decide effectively if there is a homomorphism that factors through one of them and satisfy the system of inequalities Ψ (the equalities in the system Σ hold by construction for any homomorphism that factors through one of the strict resolutions we construct).

With the systems of equations Σ_{1}, …, Σ_{ℓ}, the Makanin-Razborov machinery associates finitely many resolutions (over the free group F_{k}). Given one of these resolutions, Res(x, f), that is defined over the free group F_{k}, we transform it into a strict resolution over the torsion-free hyperbolic group Γ iteratively, from bottom to top.

The terminal group of the resolution Res(x, f) is a free group of the form F_{k} ∗ F_{s}, where F_{s} may be trivial, and F_{k} is the coefficient group. With the coefficient group F_{k}, there is an associated quotient map onto Γ. We start the modification of Res(x, f) by replacing the terminal group F_{k} ∗ F_{s} with a group of the form Γ ∗ F_{s}, with a naturally associated quotient map, and where Γ is considered to be the coefficient group of the newly obtained resolution.

At this stage we start modifying the next level of the resolution Res(x, f), i.e., the group L_{t−1}, the abelian decomposition Λ_{t−1}, and the quotient map η_{t−1} : L_{t−1} → F_{k} ∗ F_{s}, associated with the level above the terminal level. L_{t−1} is mapped by the quotient map η_{t−1} onto the terminal group F_{k} ∗ F_{s}, so this map extends naturally to an epimorphism ν_{t_{1}} : L_{t−1} → Γ ∗ F_{s}. We continue by checking all the possible degeneracies of the abelian decomposition Λ_{t−1} given the map ν_{t−1}.

(1) an edge group in Λ_{t−1} is mapped by ν_{t−1} to the trivial subgroup.

(2) a non-abelian vertex group in Λ_{t−1} is mapped to an abelian subgroup or the trivial subgroup by ν_{t−1}.

(3) some of the boundary elements of a QH vertex group in Λ_{t−1} are mapped to the trivial subgroup by ν_{t−1}.

(4) the image of a QH vertex group in Λ_{t−1} is mapped to to an abelian (cyclic) subgroup by ν_{t−1}.

Clearly, there are finitely many possibilities for degenerations in the abelian decomposition Λ_{t−1}, and they can all be checked using the solution to the word problem in the hyperbolic group Γ ∗ F_{s}.

If there are no degenerations in the graph of groups Λ_{t−1}, we associate with it a completion over the torsion-free hyperbolic group Γ, constructed by starting with the group Γ∗F_{s} associated with the terminal level, and then follow the construction of the completion presented in definition 1.12 of [Se2] according to the abelian decomposition Λ_{t−1}. Suppose that Λ_{t−1} has degenerations, and contains no QH vertex groups. In this case we modify Λ_{t−1} by collapsing all the edge groups that are mapped to the trivial subgroup in Γ ∗ F_{s} by ν_{t−1}, all the abelian vertex groups that are mapped to the trivial subgroup, and all the non-QH, non-abelian vertex groups that are mapped to an abelian subgroup in Λ_{t−1}. The obtained graph of groups, denoted Δ_{t−1}, admits no degenerations, hence, we can associate a completion over Γ with it, as in the non-degenerate case.

Suppose that Λ_{t−1} contains QH vertex groups. We start by checking which QH vertex groups are mapped into trivial or abelian subgroups in the terminal group Γ∗F_{s} by the map ν_{t−1}. We modify Λ_{t−1} by collapsing each of the QH vertex groups that are mapped into the trivial subgroup, as well as all the edges connected to such a QH vertex group. We replace each of the QH vertex groups that are mapped into non-trivial abelian subgroups, with the maximal free abelian quotient of the QH vertex group, in which the boundary elements are fixed. We denote the obtained abelian decomposition Λ′_{t−1}. Note that every QH vertex group in Λ′_{t−1} is mapped onto a non-abelian subgroup by ν_{t−1}. We continue by modifying the abelian decomposition Λ′_{t−1} as we did in case there were no QH subgroups. We collapse all edge groups that connect between two non-QH vertex groups and are mapped to the trivial group by ν_{t−1}. If V is a non-abelian, non-QH vertex group in Λ′_{t−1} that is mapped to an abelian subgroup by ν_{t−1}, and V is connected to a non-QH vertex group, we collapse the edge that connects these two vertices. We further iteratively erase all edge groups that are connected to QH vertex groups in the obtained graph of groups, and are mapped to the trivial group by ν_{t−1}. If such an edge is contained in a circle in the obtained graph of groups, we introduce a new free factor in our abelian decomposition, generated by the Bass-Serre generator associated with that circle. Let U be a vertex group that remains isolated after we erase the edge groups that are connected to QH vertex groups and mapped to the trivial subgroup by ν_{t−1}. If U is mapped to the trivial subgroup by ν_{t−1}, we erase it.

We continue by modifying QH vertex groups that are mapped to non-abelian subgroups by ν_{t−1}. Let Q be such a vertex group and let S_{Q} be its associated surface. If none of the edge groups connected to Q is mapped to the trivial subgroup by ν_{t−1}, we leave Q unchanged. Suppose that there exist edge groups connected to Q that are mapped into the trivial subgroup. We modify the QH subgroup Q, by the fundamental group of the surface obtained from S_{Q} by filling with disks all the boundary components that are mapped into the trivial subgroup by ν_{t−1}. If the obtained surface is a closed orientable surface of genus 2, a 3 punctured sphere, a 2 punctured projective plane, we declare the obtained group as a non-QH, non-abelian vertex group. If the obtained surface is a 1-punctured Klein bottle, we replace it by one non-abelian, non-QH vertex group and a loop based on it, obtained by cutting the 1-punctured Klein bottle along its non-boundary parallel s.c.c.

For each connected component in the obtained graph of groups that does not contain the coefficient group Γ, we add a new generator, so that the fundamental group of that connected component is mapped into Γ ∗ F_{s} conjugated by the new free generator. With the obtained abelian decomposition, we associate a completion over the hyperbolic group Γ, constructed by starting with the terminal group Γ∗F_{s}, and continuing using the given abelian decomposition according to definition 1.12 in [Se2].

The obtained completion over Γ, associated with the 2 bottom levels of given resolution over F_{k}, is a Γ-limit group by theorem 1.31, and it is f.p. by construction. The word problem is solvable for f.p. Γ-limit groups, In the similar way to its solution for f.p. residually finite groups, i.e., by using two parallel processes, the first looks for a presentation of the given word in the normal closure of the given relations, and the second looks for a homomorphism into Γ that maps the given word into a non-trivial element (clearly, one of the two processes must terminate). Hence, the word problem for the obtained completion over Γ is decidable. Since in order to construct the completion associated with the bottom 2 levels, only a solution to the word problem in the terminal hyperbolic group is required, the construction used for the bottom 2 levels generalizes to the higher levels of the resolution, and finally associates with it a completion over Γ.

Once completions over Γ are associated with the resolutions associated with the systems of equations Σ_{1}, …, Σ_{ℓ}, to decide if there exists a solution of the system Σ over Γ, for which the inequalities Ψ hold, we only need to check if the words that appear in the system Ψ are all non-trivial in at least one of the completions over Γ we constructed. Since the word problem is decidable over these completions, this can be decided effectively. Hence, it is possible to decide effectively if the conjunction of the systems Σ and Ψ have a solution in the torsion-free hyperbolic group Γ.

□

Theorem 7.12 enables us to decide if there exists a proper retract from a freelyindecomposable factor in the Grushko decomposition of a torsion-free hyperbolic group onto the fundamental group of a proper subgrpaph of its JSJ decomposition, that maps each of the non-QH vertex groups and all the edge groups in the JSJ decomposition into their conjugates, and so that the image of each QH is nonabelian.

If no such retract exists for any of the factors, the construction of the elementary core is completed. If such a retract exists for at least one of the factors, we continue iteratively. The construction terminates after finitely many iterations, by the descending chain condition for Γ-limit groups (theorem 1.12) and the co-Hopf property for non-elementary, freely-indecomposable, torsion-free hyperbolic groups. Hence, the effective construction of the elementary core of a torsion-free hyperbolic group is completed, and so is the procedure for deciding if two such groups are elementary equivalent (theorem 7.11).

□

References

[Be] M. Bestvina, R-trees in topology, geometry, and group theory, preprint.

[Be-Fe1] M. Bestvina and M. Feighn, Stable actions of groups on real trees, Inventiones Math. 121 (1995), 287-321.

[Be-Fe2] , Bounding the complexity of simplicial group actions, Inventiones Math. 103 (1991), 449-469.

[Be-Fe3] , A combination theorem for negatively curved groups, Jour. of Differential Geometry 35 (1992), 85-101.

[Du-Sa] M. Dunwoody and M. Sageev, JSJ-splittings for finitely presented groups over slender groups, Inventiones Math. 135 (1999), 25-44.

[Fu-Pa] K. Fujiwara and P. Papasoglu, JSJ decompositions and complexes of groups, preprint.

[Ge] V. Gerasimov, Detecting connectedness of the boundary of a hyperbolic group, preprint.

[Gu] V. S. Guba, Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems, Math. Zametki 40 (1986), 321-324.

[Ma1] G. S. Makanin, Equations in a free group, Math. USSR Izvestiya 21 (1983), 449-469.

[Ma2] , Decidability of the universal and positive theories of a free group, Math. USSR Izvestiya 25 (1985), 75-88.

[Me] Yu. I. Merzlyakov, Positive formulae on free groups, Algebra i Logika 5 (1966), 257-266.

[Pa] F. Paulin, Outer automorphisms of hyperbolic groups and small actions on R-trees,

Arboreal Group Theory (ed. R. C. Alperin), 331-343.

[Ra1] A. A. Razborov, On systems of equations in a free group, Math. USSR Izvestiya 25 (1985), 115-162.

[Ra2] , On systems of equations in a free group, Ph.D. thesis, Steklov Math. institute, 1987.

[Ri-Se1] E. Rips and Z. Sela, Structure and rigidity in hyperbolic groups I, GAFA 4 (1994),

337-371.

[Ri-Se2] , Cyclic splittings of finitely presented groups and the canonical JSJ decompo-

sition, Annals of Mathematics 146 (1997), 53-104.

[Ri-Se3] , Canonical representatives and equations in hyperbolic groups, Inventiones

Math. 120 (1995), 489-512.

[Se1-Se7] Z. Sela, Diophantine geometry over groups I-VII, preprints.

[Se8] , Acylindrical accessibility for groups, Inventiones Mathematicae 129 (1997), 527-565.

[Se9] , Structure and rigidity in (Gromov) hyperbolic groups and discrete groups in rank 1 Lie Groups II, GAFA 7 (1997), 561-593.

[Se10] , Endomorphisms of hyperbolic groups I: The Hopf property, Topology 38 (1999), 301-321.

[Se11] , The isomorphism problem for hyperbolic groups I, Annals of Math. 141 (1995), 217-283.

[Se12] , The isomorphism problem for hyperbolic groups II, in preparation.