DIOPHANTINE GEOMETRY OVER GROUPS I:

MAKANIN-RAZBOROV DIAGRAMS

Z. Sela^{1,2}

posted Nov. 26, 2000

This paper is the first in a sequence 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. In the first paper we present the (canonical) Makanin-Razborov diagram that encodes the set of solutions of a system of equations. We continue by studying parametric families of sets of solutions, and associate with such a family a canonical graded Makanin-Razborov diagram, that encodes the collection of Makanin-Razborov diagrams associated with the individual members in the parametric family.

Sets of solutions to equations defined over a free group have been studied extensively, mostly since Alfred Tarski presented his fundamental questions on the elementary theory of free groups around 1945. Considerable progress in the study of such sets of solutions was made by G. S. Makanin, who constructed an algorithm that decides if a system of equations defined over a free group has a solution [Ma1], and showed that the universal and positive theories of a free group are decidable [Ma2]. A. A. Razborov was able to give a description of the entire set of solutions to a system of equations defined over a free group [Ra1], a description that was further developed by O. Kharlampovich and A. Myasnikov [Kh-My].

A set of solutions to equations defined over a free group is clearly a discrete set, and all the previous techniques and methods that studied these sets are combinatorial in nature. Naturally, the structure of sets of solutions defined over a free group is very different than the structure of sets of solutions (varieties) to systems of equations defined over the complexes, reals or a number field. Still, perhaps surprisingly, concepts from complex algebraic geometry and from Diophantine geometry can be borrowed to study varieties defined over a free group.

In this paper we start a sequence that borrows concepts and techniques from geometric group theory, low dimensional topology, and Diophantine geometry to study the structure of varieties defined over a free group. Our techniques and point of view on the study of these varieties is rather different than any of the pre-existing techniques in this field, though, as one can expect, some of our preliminary results overlap with previously known ones. As we will see in this paper and mostly in the following ones, the techniques and concepts we use enable the study of the structure of varieties defined over a free group and their projections, and in particular, give us the possibility to answer some questions that seem to be essential in any attempt to understand the structure of elementary sentences and predicates defined over a free group. At this stage, at least as it seems to us, none of the pre-existing (combinatorial) techniques can approach the difficulties involved in tackling these questions.

1Hebrew University, Jerusalem 91904, Israel.

2Partially supported by an Israel academy of sciences fellowship.

The sequence of papers on Diophantine geometry over groups is organized as follows. In the first paper we associate a canonical Makanin-Razborov diagram with a given system of equations defined over a free group. This Makanin-Razborov diagram encodes the entire set of solutions to the system. Later on we study systems of equations with parameters. With each such system we associate a (canonical) graded Makanin-Razborov diagram, that encodes the Makanin-Razborov diagrams of the systems of equations associated with each specialization of the defining parameters. In the second paper of the sequence, we generalize Merzlyakov theorem on the existence of a formal solution associated with a positive sentence [Me]. We first construct a formal solution to a general AE sentence which is known to be true over some variety, and then develop tools that enable us to analyze the collection of all such formal solutions. In the third paper, we use techniques developed in the first two, to further study exceptional solutions of parametric systems of equations, which are one of the inherent pathologies in the theory that must be understood in studying the first order theory of a free group. Perhaps the main result of this paper is the existence of a global bound (independent of the parameters specialization) on the number of families of exceptional solutions. In the fourth paper we study AE sentences, and present a terminating iterative procedure for validation of such sentences. This terminating iterative procedure is the basis for our analysis of elementary sets defined over a free group presented in the last two papers. In the fifth paper we analyze the Boolean Algebra of AE sets and show that this Boolean algebra is invariant under projections. This implies that every elementary set defined over a free group is in the Boolean algebra of AE sets. The sixth paper uses the results of the fifth one to study elementary sets defined over a free group and more generally, ω-residually free groups. In particular, we obtain a classification of the f.g. groups that are elementary equivalent to a non-abelian f.g. free group.

We start the first paper of the sequence by studying limit groups that are obtained from (Gromov) limits of sequences of homomorphisms. In section 2 we study the (canonical) abelian JSJ decomposition of these groups, which is shown to be non-trivial. In the third section we study the (canonical) cyclic JSJ decomposition of a limit group, and show that this cyclic decomposition can not be trivial as well. In the fourth section we use the canonical cyclic JSJ decomposition to associate an analysis lattice with a limit group, which, in particular, implies that limit groups are finitely presented, and that a f.g. group is a limit group if and only if it is an ω-residually free group (f.g. ω-residually free groups were also shown to be f.p. by Kharlampovich and Myasnikov in [Kh-My]). The fifth section associates a canonical Makanin-Razborov diagram with a limit group. The properties of this diagram are similar to the ones obtained by Razborov [Ra2], and Kharlampovich and Myasnikov [Kh-My]. However, for the structure theory we develop, and for analyzing elementary predicates, it seems essential to have its canonical properties (which can not be guaranteed by combinatorial approaches), and to be able to have a ”close relation” between the algebraic structure of a limit group and some of its (canonical) quotients with the structure of the diagram and the modular groups associated with it. In the sixth section we present a family of ω-residually free groups that is more geometric in nature. The family of towers we present, plays an essential role when we classify f.g. groups that are elementary equivalent to a non-abelian free group in the last paper in the sequence. In section 7 we use our study of limit groups to study residually free groups, and in the ninth section we present configuration limit groups that seem to be an important part of the theory, and later used in the third paper in our study of families of exceptional solutions.

At this point we begin our study of systems of equations with parameters. In section 10 we present graded limit groups, and in section 11 we associate a canonical graded Makanin-Razborov diagram with a graded limit group. We view the set of solutions to a system of equations with parameters as a bundle, where the groups of parameters lies in the base of this bundle. The graded Makanin-Razborov diagram is then a (flat) ”connection” that allows one to compare different fibers associated with different specializations of the defining parameters. Section 12 studies the singular locus of that bundle, which is equivalent to studying the degeneracies in the graded Makanin-Razborov diagram. Section 13 generalizes our study of graded limit groups and diagrams to the study of multi-graded ones. Graded and multigraded limit groups and diagrams are the basic objects needed in our analysis of sentences and elementary sets defined over a free group.

Quite a few people helped us while this work was conducted. We would like to thank Mladen Bestvina, Mark Feighn and the referees for their comments and suggestions. Especially, I am indebted to my former advisor Eliyahu Rips who introduced me to Tarski’s problems, shared his knowledge and ideas with me, and suggested the possibility of a connection between the JSJ theory and the study of varieties defined over a free group, not long after the JSJ decomposition was introduced.

§1. Limit Groups

Following [Ra1] with a finite system of equations Φ over a free group F_{k} = < a_{1}, …, a_{k} > it is natural to associate a f.p. group G(Φ). If the system Φ is defined by the coefficients a_{1}, …, a_{k}, the unknowns x_{1}, …, x_{n} and the equations:

w_{1}(a_{1}, …, a_{k},x_{1}, …, x_{n}) = 1
⋮
w_{s}(a_{1}, …, a_{k},x_{1}, …, x_{n}) = 1

we set the associated f.p. group G(Φ) to be:

G(Φ) = < a_{1}, …, a_{k}, x_{1}, …, x_{n} | w_{1}, …, w_{s} >

Clearly, every solution of the system Φ corresponds to a homomorphism h : G(Φ) → F_{k} for which h(a_{i}) = a_{i}, and every such homomorphism corresponds to a solution of the system Φ. Therefore, the study of sets of solutions to systems of equations in a free group is equivalent to the study of all homomorphisms from a fixed f.p. group G into a free group F_{k} for which a given prescribed set of elements in G is mapped to a fixed basis of the free group F_{k}.

Throughout this paper, this is the point of view we adapt in order to study sets of solutions to systems of equations in a free group. Since the techniques we use and the structure theory we obtain are valid for f.g. groups and not only for f.p. ones, we set G to be a f.g. group G =< g_{1}, …, g_{m} >, γ_{1}, …, γ_{k} ∈ G to be a prescribed set of elements in G, and F_{k} to be a free group with a fixed basis F_{k} =< a_{1}, …, a_{k} >. With these notation our main goal is to get a structure theory for understanding the set of all homomorphisms:

Hom((G, {γ_{i}}), (F_{k}, {a_{i}})) = { h | h : G → F_{k} , h(γ_{i}) = a_{i} }

which for brevity we will denote Hom(G, F_{k}). We set X to be the Cayley graph of F_{k} with respect to its given basis a_{1}, …, a_{k}. Given any homomorphism h ∈ Hom(G, F_{k}), G admits a natural action λ_{h} on X given by λ_{h}(g, x) = h(g)(x) for every g ∈ G and x ∈ X.

Let {h_{j}} ⊂ Hom(G, F_{k}) be a set of distinct homomorphisms from G to F_{k} satisfying the prescribed conditions. For each index j we fix an element f_{j} ∈ F_{k} having ”minimal displacement” under the action λ_{h_{j}} and set μ_{j} to be:

μ_{j} = max_{1≤u≤m} d_{X}(id., f_{j}h_{j}(g_{u})f_{j}^{−1}) = min_{f∈F_{k}} max_{1≤u≤m} d_{X}(id., fh_{j}(g_{u})f^{−1})

Since the homomorphisms in the sequence {h_{j}} ⊂ Hom(G, F_{k}) are distinct, 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 F_{k}, (X, id.), by μ_{j}. (X_{j}, x_{j}) is endowed with a left isometric action of our f.g. group G via the homomorphisms τ_{f_{j}} ∘ h_{j} where τ_{f_{j}} is the inner automorphism of F_{k} defined by f_{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} < ∞. 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 f_{j_{n}}h_{j_{n}}f_{j_{n}}^{−1} : G → F_{k} by h_{n}.

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 limit group. The first goal in our approach to the structure of sets of solutions to equations in a free group is understanding some of the basic properties of limit groups, and in particular to show they are f.p. groups and that every maximal abelian subgroup of them is a f.g. free abelian 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 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 limit group are important observations and will serve us throughout the rest of the paper.

Lemma 1.3. With the notation above:

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

(ii) if Y is isometric to a real line then the 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}])

Proof: L_{∞} is a quotient of the f.g. group G, so it is f.g. as well. To prove (ii) note that if Y is isometric to a real line then L_{∞} is a f.g. subgroup of Isom(R). If g ∈ G preserves the orientation of Y and g′ ∈ G reverses it, then for large enough n, h_{n}(g′)h_{n}(g)h_{n}(g′)^{−1} = h_{n}(g^{−1}), and since the image of the homomorphisms h_{n} is a subgroup of the free group F_{k}, necessarily h_{n}(g) = 1 for all but finitely many n’s, hence, g ∈ K_{∞}. In addition, since g′^{2} preserves the orientation of Y, h_{n}(g′^{2}) = 1 for all but finitely many n’s, so h_{n}(g′) = 1 for all but finitely many n’s and g′ ∈ K_{∞}. Therefore, the ambient group G preserves the orientation of Y, and since L_{∞} is a f.g. subgroup of Isom(R), L_{∞} is f.g. free abelian group.

To prove (iii) let T (A, B, C) be a tripod in Y and let N be the three valence vertex in that tripod. Let g ∈ G fix T (A, B, C) and let (A_{n}, B_{n}, C_{n}) ⊂ X_{n} be a sequence of triples of points converging into the triple (A, B, C). Let ℓ = min{d_{Y} (A, N), d_{Y} (B, N), d_{Y} (C, N)}. From the convergence of the metric spaces {(X_{n}, x_{n})}_{n=1}^{∞} to the real tree (Y, y_{0}) we get for large enough n:

max\{d_{X_{n}}(A_{n}, h_{n}(g)(A_{n})), d_{X_{n}}(B_{n}, h_{n}(g)(B_{n})), d_{X_{n}}(C_{n}, h_{n}(g)(C_{n}))\} < \frac{ℓ}{3}

Let N_{n} be a three valence vertex of a geodesic approximating tree with vertices A_{n}, B_{n}, C_{n} in X_{n}. By the bound on the displacement of A_{n}, B_{n}, C_{n} by h_{n}(g), for large enough n h_{n}(g)(N_{n}) = N_{n}, so h_{n}(g) = 1 for all but finitely many n’s, and in particular g ∈ K_{∞}.

To prove (iv) suppose h_{n_{v}}(g) = 1 for an infinite subsequence of indices {n_{v}}. Since the actions of G on the metric spaces (X_{n}, x_{n}) via the homomorphisms h_{n} converge in the Gromov-Hausdorff topology into an action of G on the real tree Y, the subsequence of actions of G on the metric spaces (X_{n_{v}}, x_{n_{v}}) via the homomorphisms h_{n_{v}} converges into the same action of G on the real tree Y. Since we assume h_{n_{v}} = 1 for all v, g acts trivially on the limit tree Y, so g ∈ K_{∞} and we may conclude part (iv) of the lemma. To prove L_{∞} is torsion-free suppose g ∈ G and g^{p} ∈ K_{∞}. Note that if the limit tree Y is isometric to a real line then L_{∞} is a f.g. free abelian group, and in particular torsion-free. Hence, we may assume Y is not isometric to a real line, which implies that g^{p} stabilizes a tripod in Y so by part (iii) of the lemma h_{n}(g^{p}) = 1 for all but finitely many n’s, and necessarily h_{n}(g) = 1 for all but finitely many n’s and g ∈ K_{∞} which concludes part (v). The proof of part (vi) is identical with the proof of proposition 4.2 of [Ri-Se1].

□

Lemma 1.3 gives us the basic properties of the action of the limit group L_{∞} on the real tree Y. These properties are essential in applying Rips’ classification of (stable) actions of groups on real trees which is going to be used extensively in the sequel. In addition to the properties of the action we will need the following basic algebraic facts on the limit group L_{∞}. In a free group every solvable subgroup is infinite cyclic and every maximal cyclic subgroup is malnormal. These properties are naturally inherited by the limit group L_{∞}.

Lemma 1.4. With the notation above:

(i) Let g, g_{1}, g_{2} be elements of G which project to non-trivial elements of L_{∞}, [η(g), η(g_{1})] = 1 and [η(g), η(g_{2})] = 1. Then [η(g_{1}), η(g_{2})] = 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 limit group L_{∞} is abelian.

Proof: Since g, g_{1}, g_{2} project to non-trivial elements in L_{∞}, part (iv) of lemma 1.3 implies that for all but finitely many n’s h_{n} maps g, g_{1}, g_{2} to non-trivial elements in F_{k}. Since η(g) commutes with both η(g_{1}) and η(g_{2}), part (iii) of lemma 1.3 implies that for all but finitely many n’s h_{n}(g) commutes with both h_{n}(g_{1}) and h_{n}(g_{2}). Hence, for all but finitely many n’s the subgroup generated by h_{n}(g), h_{n}(g_{1}), h_{n}(g_{2}) is infinite cyclic, and, in particular, h_{n}(g_{1}) commutes with h_{n}(g_{2}). By part (iv) of lemma 1.3 η(g_{1}) commutes with η(g_{2}) and we get part (i) of the lemma.

To prove part (ii) let A be a maximal abelian subgroup of L_{∞}. If A is not malnormal there must exist elements g_{1}, g_{2}, g ∈ G so that η(g_{1}), η(g_{2}) ∈ A, η(g_{1}) ≠ 1 and η(g)η(g_{1})η(g^{−1}) = η(g_{2}). Since by part (iii) of lemma 1.3 if r ∈ K_{∞} then for all but finitely many n’s h_{n}(r) = 1, for all but finitely many n’s h_{n}(g)h_{n}(g_{1})h_{n}(g^{−1}) = h_{n}(g_{2}) and [h_{n}(g_{1}), h_{n}(g_{2})] = 1, so < h_{n}(g_{1}), h_{n}(g_{2}) > is a cyclic subgroup of F_{k}. Since a maximal cyclic subgroup of F_{k} is malnormal, for all but finitely many n’s h_{n}(g) commutes with both h_{n}(g_{1}) and h_{n}(g_{2}), so part (iv) of lemma 1.3 implies that η(g) commutes with both η(g_{1}) and η(g_{2}) so η(g) ∈ A and A is malnormal.

To prove part (iii) let S be a solvable subgroup of L_{∞} and let g_{1}, g_{2} ∈ G be non-trivial elements for which η(g_{1}), η(g_{2}) ∈ S. Clearly, < η(g_{1}), η(g_{2}) > < L_{∞}, the subgroup generated by η(g_{1}) and η(g_{2}), is solvable. Recall that the limit group L_{∞} is obtained from a converging subsequence of homomorphisms h_{n} : G → F_{k}. For each n, < h_{n}(g_{1}), h_{n}(g_{2}) > is a 2-generated subgroup of F_{k}, hence, it is either infinite cyclic or a rank 2 free subgroup of F_{k}. If < h_{n}(g_{1}), h_{n}(g_{2}) > is a rank 2 free subgroup of F_{k} for infinitely many n’s, then part (iii) of lemma 1.3 implies that < η(g_{1}), η(g_{2}) > is a rank 2 free subgroup of L_{∞} which contradicts its solvability. Therefore, < h_{n}(g_{1}), h_{n}(g_{2}) > is an infinite cyclic subgroup of F_{k} for all but at most finitely many n’s, so [h_{n}(g_{1}), h_{n}(g_{2})] = 1 for all but at most finitely many n’s, hence, by part (iv) of lemma 1.3 [η(g_{1}), η(g_{2})] = 1, so η(g_{1}) commutes with η(g_{2}) and S is abelian.

□

Proposition 1.3 shows 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 [Se3]. In [Se3], 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 [Se3] 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 ([Se3],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 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) The group G admits a (canonical) graph of groups with:

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

(ii) Vertices corresponding to 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.

(iv) 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.

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

Before concluding our preliminary study of limit groups and their action on the limit real tree, we present the following basic fact which is necessary in the sequel.

Lemma 1.6. If L_{∞} is a limit group acting on a limit tree Y obtained from a converging sequence of homomorphisms from a f.g. group G into a free group F_{k} 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_{∞}.

Proof: identical to the proof of part (iii) of proposition 1.8 in [Se4].

□

§2. The Canonical Abelian JSJ Decomposition of a Limit Group

In the previous section we defined limit groups and studied their basic algebraic structure. To further study the algebraic structure of a limit group L_{∞} and in particular to understand what are all the possible splittings of L_{∞} along abelian subgroups, we need to construct the canonical JSJ decomposition of L_{∞}. A canonical JSJ decomposition was first introduced in [Se2] in the case of hyperbolic groups and then generalized to cyclic splittings of f.p. groups in [Ri-Se2]. Until this point, we only know that L_{∞} is f.g. (lemma 1.3), still the JSJ theory can be applied using acylindrical accessibility [Se3] (cf. ([Se4],2)).

To construct the JSJ decomposition of L_{∞} we need to study some basic properties of abelian splittings. We first look how maximal abelian subgroups of L_{∞} act on (simplicial) Bass-Serre trees corresponding to abelian splittings of L_{∞}. Recall that by lemma 1.4 every maximal abelian subgroup of L_{∞} is malnormal.

Lemma 2.1. Let M be a maximal abelian subgroup and A 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 so that L_{∞} = U ∗_{A} M.

Proof: To prove (i) suppose M is not cyclic and M can not be conjugated into U or V in the amalgamated product L_{∞} = U ∗_{A} V. Let T be the Bass-Serre tree corresponding to this amalgamated product. Since M is abelian and is not elliptic when acting on T it must preserve an axis in T. By conjugating M we may assume A fix an edge in this axis, and since M is a maximal non-cyclic abelian subgroup of L_{∞} and by lemma 1.4 an abelian subgroup in L_{∞} is contained in a unique maximal abelian subgroup, the abelian subgroup A is a subgroup of M, and A fixes the entire axis preserved by M. This last observation implies that there must exists an element u ∈ U so that u ∉ A and u commutes with A. u centralizes A, so by proposition 1.4 it must be an element of the maximal abelian subgroup containing A so u ∈ M. But clearly, u can not be an element of M, since the only elliptic elements in M are the elements of A, a contradiction.

To prove (ii) suppose M is non-cyclic and M can not be conjugated into the vertex group U in the cyclic splitting L_{∞} = U∗_{A}. Let T be the Bass-Serre tree corresponding to that HNN extension. M is abelian and not elliptic so it must fix an axis in T, and by conjugating M we may assume the abelian subgroup A fixes that entire axis. By the argument used to prove part (i), the vertex group U intersects M only in the subgroup A, so by replacing the Bass-Serre generator t by tu for some u ∈ U we may assume that the Bass-Serre generator t is an element of M. Since the Bass-Serre generator t centralizes the cyclic subgroup A, L_{∞} = U ∗_{A} M.

□

By lemma 2.1 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 2.2 [Se3]. 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.

By Lemma 1.4 every maximal abelian subgroup of L_{∞} is malnormal. Hence:

lemma 2.3. 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 2.3 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 2.1 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.

Following [Se2] and [Ri-Se2] in order to understand all possible splittings of L_{∞} along abelian subgroups, we need to study carefully the ”interaction” between any two given one-edge splittings of L_{∞} over abelian subgroups. Let H be a group and T a (simplicial) H-tree. An element h ∈ H is either elliptic in which case it fixes a point in T, or hyperbolic, in which case it preserves a line in T and acts along it as a translation. We consider two elementary splittings of L_{∞} along abelian subgroups H_{∞} = D_{1} ∗_{A_{1}} E_{1} (or L_{∞} = D_{1}∗_{A_{1}} in which case we assume that A_{1} is a subgroup of a maximal abelian subgroup M in L_{∞} and M is a subgroup of the vertex group D), and L_{∞} = D_{2} ∗_{A_{2}} E_{2} (or L_{∞} = D_{2}∗_{A_{2}} under the above conditions on A_{2}) where A_{1} and A_{2} are abelian subgroups. Let T_{1} and T_{2} be the Bass-Serre trees corresponding to the given splittings. The two given splittings are called elliptic-elliptic if A_{1} is elliptic in T_{2} and A_{2} is elliptic in T_{1}, elliptic-hyperbolic if A_{1} is elliptic in T_{2} and A_{2} is not elliptic in T_{1} and hyperbolic-hyperbolic if A_{1} is not elliptic in T_{2} and A_{2} is not elliptic in T_{1}.

Lemma 2.1 shows that an abelian subgroup of L_{∞} which is not cyclic is necessarily elliptic in all abelian splitting of L_{∞} under consideration. Following [Se2] we can also exclude the case of elliptic-hyperbolic maximal abelian splittings in case L_{∞} is freely indecomposable (the arguments given in [Se2] and [Ri-Se2] for cyclic splittings of groups remain valid for abelian splittings of L_{∞}).

Theorem 2.4 ([Se2],2.2),([Ri-Se2],2.1). If L_{∞} is freely indecomposable then any two one-edge abelian splittings of L_{∞} in which all non-cyclic abelian subgroups are elliptic, are either elliptic-elliptic or hyperbolic-hyperbolic.

Since by lemma 2.1 every abelian subgroup of L_{∞} which is not cyclic is elliptic in all abelian splittings of L_{∞} under consideration, pairs of hyperbolic-hyperbolic one edge splittings of L_{∞} along abelian subgroups are splittings along cyclic subgroups. Hence, we may borrow the canonical quadratic decomposition constructed in [Ri-Se2] in order to understand all the hyperbolic-hyperbolic splittings of L_{∞} along cyclic subgroups. By a Z-splitting of a group we mean a splitting in which all edge groups are infinite cyclic. For the notion of a CMQ subgroup and a weakly essential s.c.c. on a 2orbifold we refer the reader to section 4 of [Ri-Se2].

Theorem 2.5 ([Ri-Se2],5.6). Let H be a f.g. group with a single end which is not a 2-orbifold group. There exists a (canonical) reduced Z-splitting of H which we call the quadratic decomposition of H with the following properties:

(i) Every canonical maximal QH subgroup (CMQ) of H is conjugate to a vertex group in the quadratic decomposition. In particular, there are only finitely many conjugacy classes of CMQ subgroups. Every edge group is a cyclic boundary subgroup of one of the CMQ subgroups, and every vertex with a non-CMQ vertex group is adjacent only to vertices stabilized by CMQ subgroups in the canonical quadratic decomposition.

(ii) an elementary Z-splitting H = A ∗_{C} B or H = A∗_{C} which is hyperbolic in another elementary Z-splitting is obtained from the quadratic decomposition of H by cutting a 2-orbifold corresponding to a CMQ subgroup of H along a weakly essential s.c.c.

(iii) the edge group of any elementary Z-splitting H = A ∗_{C} B or H = A∗_{C} can be conjugated into a vertex group of the quadratic decomposition. In case it can be conjugated into a vertex group which is not a CMQ subgroup, the given elementary Z-splitting is elliptic-elliptic with respect to any other elementary Z-splitting of H.

(iv) The quadratic decomposition of H is unique up to sliding, conjugation and modifying boundary monomorphisms by conjugation (see section 1 of [Ri-Se2] for the definition of these notions).

To construct the JSJ decomposition of L_{∞} we need to further refine the quadratic decomposition to include the set of elliptic-elliptic abelian decompositions. In general, such refinement can not be obtained for a f.g. group as was shown by Dunwoody [Du]. Fortunately, the abelian splittings of L_{∞} we consider are 2-acylindrical according to lemma 2.3 which allows us to apply acylindrical accessibilty in order to complete the construction of the JSJ decomposition.

Theorem 2.6 ([Se3],4.1). Let H be a f.g. freely indecomposable group. For a given k there exists an integer λ(k, H) so that the number of vertices and edges in all k-acylindrical splittings of H does not exceed λ(k, H).

To include elliptic-elliptic abelian splittings in the JSJ decomposition of a f.p. group the generalized accessibility of M. Bestvina and M. Feighn [Be-Fe2] is being used (see ([Ri-Se2],7.1)). Replacing generalized accessibility by acylindrical accessibility which applies to the abelian splittings of L_{∞} under consideration, the construction of the JSJ decomposition for cyclic splittings of a f.p. group ([Ri-Se2],7.1) generalizes to give a JSJ decomposition for abelian splittings of L_{∞} in case it is freely indecomposable.

Theorem 2.7 (cf. ([Ri-Se2],7.1). Suppose L_{∞} is freely indecomposable. 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)

Theorem 2.7 gives us the canonical abelian JSJ decomposition of L_{∞} which essentially describes all the abelian splittings of L_{∞} along abelian subgroups. This decomposition is a basic tool in our approach to obtaining a structure theory for sets of solutions of equations in a free group.

§3. The Canonical Cyclic JSJ Decomposition of a Limit Group

In section 2 we have constructed the (canonical) abelian JSJ decomposition of a limit group L_{∞}, which includes (in an appropriate sense) all abelian splittings of L_{∞}. To analyze sets of solutions to systems of equations in a free group we will be interested not in all abelian splittings but rather in cyclic ones. Theorem 1.5 shows that if L_{∞} is freely-indecomposable and not abelian it must admit a non-trivial abelian splitting, hence, it’s abelian JSJ decomposition is not the trivial one. In this section our goal is to prove analogous statements for cyclic splittings of L_{∞}, i.e., we prove that if L_{∞} is freely indecomposable and not abelian it must admit an (essential) cyclic splitting, and we define it’s non-trivial canonical cyclic JSJ decomposition. We prove the existence of a cyclic splitting of L_{∞} by showing that if the JSJ decomposition of L_{∞} contains only non-cyclic abelian edge groups, one may further refine the abelian JSJ decomposition of L_{∞}, which clearly contradicts the canonical properties of the JSJ (theorem 2.7).

With the notation of the first section let G be a f.g. group, let {h_{n} | h_{n} : G → F_{k}} be a convergent sequence of homomorphisms, and let L_{∞} be the corresponding limit group and (Y, y_{0}) the corresponding limit tree.

Definition 3.1. We say that a cyclic splitting of a limit group, L_{∞} = A ∗_{Z} B or L_{∞} = A∗_{Z}, is essential, if both vertex groups A and B are not cyclic. We say it is principal if it is essential, and either A is abelian or the centralizer of the edge group Z in L_{∞} is cyclic.

Theorem 3.2. With the above notation and assumptions if L_{∞} is non-abelian and freely-indecomposable, then L_{∞} admits a principal cyclic splitting.

Proof: Since L_{∞} is freely-indecomposable it admits a canonical abelian JSJ decomposition by theorem 2.7. Note that since every abelian subgroup in L_{∞} is contained in a unique maximal abelian subgroup by lemma 1.4, all vertex groups which are adjacent to an abelian vertex group in the abelian JSJ decomposition of L_{∞} are non-abelian. We construct an abelian splitting Λ_{L_{∞}} of L_{∞} in the following way. If the abelian JSJ decomposition of L_{∞} contains no cyclic vertex groups we set Λ_{L_{∞}} to be the abelian JSJ decomposition. Otherwise, for each cyclic vertex group in the abelian JSJ decomposition we collapse an edge which connects the cyclic vertex group to a neighbor. We set Λ_{L_{∞}} to be the obtained abelian decomposition. Since, L_{∞} is a limit group, i.e., it is obtained from a convergent sequence of homomorphisms {h_{n}|h_{n} : G → F_{k}}, Λ_{L_{∞}} is a non-trivial abelian decomposition. Clearly, if Λ_{L_{∞}} contains an edge with cyclic stabilizer, L_{∞} admits an essential cyclic splitting. If the centralizer of this edge stabilizer is also cyclic, L_{∞} admits a principal cyclic splitting. Hence, we may assume that the centralizers of all edge groups in Λ_{L_{∞}} are abelian and non-cyclic, and that Λ_{L_{∞}} contains no vertex with an abelian non-cyclic vertex group A so that all edge stabilizers connected to this vertex generate a cyclic subgroup in A.

Let g_{1}, …, g_{q} be a set of generators of G. Clearly, L_{∞} =< η(g_{1}), …, η(g_{q}) >. Let V_{∞}^{1}, …, V_{∞}^{m} be the vertex groups and let E_{∞}^{1}, …, E_{∞}^{s} be the (abelian) edge groups and let t_{∞}^{1}, …, t_{∞}^{b} be the set of Bass-Serre generators in Λ_{L_{∞}}. Since we assume that L_{∞} admits no principal cyclic splitting, the centralizers of all the edge groups E_{∞}^{j} are abelian and non-cyclic and, in particular, the abelian JSJ decomposition of L_{∞} contains no CMQ subgroups. Let v_{1}^{1}, …, v_{ℓ_{1}}^{1}, …, v_{1}^{m}, …, v_{ℓ_{m}}^{m}, t_{1}, …, t_{b} be elements in G for which η(v_{1}^{i}), …, η(v_{ℓ_{i}}^{i}) ∈ V_{∞}^{i} for every 1 ≤ i ≤ m, η(t_{j}) = t_{∞}^{j} and for every generator g_{j} of G:

g_{j} = w_{j}(v_{1}^{1}, …, v_{ℓ_{m}}^{m}, t_{1}, …, t_{b})

Clearly, we may assume that each of the vertex groups V_{∞}^{i} is generated by η(v_{1}^{i}), …, η(v_{ℓ_{i}}^{i}) and the edge groups E_{∞}^{j} connected to the vertex stabilized by V_{∞}^{i} in Λ_{L_{∞}}. For each j let e_{1}^{j}, e_{2}^{j}, … ∈ G be a set of elements for which η(e_{p}^{j}) ∈ E_{∞}^{j} and in addition η(e_{1}^{j}), η(e_{2}^{j}), … generate the edge group E_{∞}^{j}.

At this point we define a sequence of finitely presented groups {U_{n}} together with homomorphisms τ_{n} : U_{n−1} → U_{n} which approximate the f.g. group L_{∞}. The groups U_{n} admit homomorphisms into F_{k}, and the abelian decomposition Λ_{L_{∞}} of L_{∞} can be ”lifted” to (f.g. abelian) decompositions of each of the U_{n}’s. This lifting property of the U_{n}’s is crucial in applying our shortening argument ([Se3],[Ri-Se1]) for obtaining further refinements of the abelian JSJ decompositions of L_{∞} in case L_{∞} does not admit a principal cyclic splitting, and was first introduced in proving the Hopf property for hyperbolic groups [Se4]. We define the groups U_{n} iteratively. We set U_{1} to be a free group generated by the elements:

U_{1} =< x_{1}^{1}, …, x_{ℓ_{1}}^{1}, …, x_{1}^{m}, …, x_{ℓ_{m}}^{m}, y_{1}, …, y_{b}, z_{1}^{1}, …, z_{1}^{s} >

Clearly, the homomorphism h_{1} : G → F_{k} lifts to a homomorphism λ_{1} : U_{1} → F_{k} by setting: λ_{1}(x_{p}^{i}) = h_{1}(v_{p}^{i}), λ_{1}(y_{r}) = h_{1}(t_{r}) and λ_{1}(z_{1}^{j}) = h_{1}(e_{1}^{j}). We define U_{2} to be the group generated by:

U_{2} =< x_{1}^{1}, …, x_{ℓ_{1}}^{1}, …, x_{1}^{m}, …, x_{ℓ_{m}}^{m}, y_{1}, …, y_{b}, z_{1}^{1}, …, z_{1}^{s}, z_{2}^{1}, …, z_{2}^{s} >

together with the relations [z_{1}^{j}, z_{2}^{j}] = 1 for j = 1, …, s. Clearly, there exists a natural homomorphism τ_{1} : U_{1} → U_{2}. By part (iii) of lemma 1.3, for a_{2} large enough the homomorphism h_{a_{2}} : G → F_{k} lifts to a homomorphism λ_{2} : U_{2} → F_{k} by setting: λ_{2}(x_{p}^{i}) = h_{a_{2}}(v_{p}^{i}), λ_{2}(y_{r}) = h_{a_{2}}(t_{r}), λ_{2}(z_{1}^{j}) = h_{a_{2}}(e_{1}^{j}) and λ_{2}(z_{2}^{j}) = h_{a_{2}}(e_{2}^{j}).

Defining U_{1} and U_{2} we continue by defining the groups U_{n}, the homomorphisms τ_{n} and the homomorphisms λ_{n} iteratively. We first define the group H_{n} to be the group generated by:

H_{n} =< x_{1}^{1}, …, x_{ℓ_{1}}^{1}, …, x_{1}^{m}, …, x_{ℓ_{m}}^{m}, y_{1}, …, y_{b}, z_{1}^{1}, …, z_{1}^{s}, …, z_{n}^{1}, …, z_{n}^{s} >

together with the relations [z_{p_{1}}^{j}, z_{p_{2}}^{j}] = 1 for j = 1, …, s and p_{1}, p_{2} = 1, …, n. The group H_{n} admits a natural epimorphism σ_{n} onto L_{∞} defined by setting σ_{n}(x_{p}^{i}) = η(v_{p}^{i}), σ_{n}(y_{r}) = t_{∞}^{r}, and σ_{n}(z_{d}^{j}) = η(e_{d}^{j}). We define the group U_{n} to be a quotient of the group H_{n}. To the existing set of relations of H_{n} we add all words w in the given defining generators of H_{n} for which σ_{n}(w) = 1, the length of w in the defining generators of H_{n} is at most n, and all the generators appear in the word w are mapped by σ_{n} into the same vertex group V_{∞}^{i} in the abelian decomposition Λ_{L_{∞}} of L_{∞}. Clearly, there exists a natural map τ_{n} : U_{n−1} → U_{n}, and by part (iii) of lemma 1.3, there exists some integer a_{n} > a_{n−1} so that the homomorphism h_{n} : G → F_{k} lifts to a homomorphism λ_{n} : U_{n} → F_{k} defined by: λ_{n}(x_{p}^{i}) = h_{a_{n}}(v_{p}^{i}), λ_{n}(y_{r}) = h_{a_{n}}(t_{r}), and λ_{n}(z_{d}^{j}) = h_{a_{n}}(e_{d}^{j}).

Since the second set of defining relations of the group U_{n} are all words in generators which are mapped by σ_{n} into the same vertex group in Λ_{L_{∞}}, each of the groups U_{n} admits an abelian splitting Λ_{n} which projects by σ_{n} into the abelian decomposition Λ_{L_{∞}} of L_{∞}, i.e., each of the vertex groups V_{n}^{i} in Λ_{n} satisfies σ_{n}(V_{n}^{i}) < V_{∞}^{i}, each of the edge groups E_{n}^{j} =< z_{1}^{j}, …, z_{n}^{j} > satisfies σ_{n}(E_{n}^{j}) < E_{∞}^{j}, and each of the Bass-Serre generators in Λ_{n} satisfies σ_{n}(y_{r}) = t_{∞}^{r}. We will denote by Mod(U_{n}) the subgroup of Aut(U_{n}) generated by inner automorphisms and Dehn twists along edges of Λ_{n}. We set W_{n} to be the subgroup of U_{n} generated by the x_{p}^{i}’s and the y_{r}’s. Clearly, the homomorphism τ_{n} : U_{n−1} → U_{n} restricts to an epimorphism from W_{n−1} onto W_{n}, and λ_{n} restricts to a homomorphism from W_{n} into F_{k}. Definining the groups U_{n}’s and W_{n}’s and the homomorphisms between them we have obtained the following diagram:

W_{1}  ⟶^{τ_{1}}  W_{2}  ⋯ ⟶^{τ_{n−1}}  W_{n−1}  ⟶^{τ_{n}}  W_{n}
↓  ↓  ↓  ↓
U_{1}  ⟶^{τ_{1}}  U_{2}  ⋯ ⟶^{τ_{n−1}}  U_{n−1}  ⟶^{τ_{n}}  U_{n}
λ_{1} ↓  λ_{2} ↓  λ_{n−1} ↓  λ_{n} ↓
F_{k}  F_{k}  F_{k}  F_{k}

where the direct limit of the {W_{n}}’s and the maps τ_{n}’s is the limit group L_{∞}. At this stage we are finally ready to modify the shortening argument of ([Se3],[Ri-

Se1]) in order to further refine the abelian JSJ decomposition of L_{∞} in case L_{∞} does not admit a principal cyclic splitting. Let T be a maximal tree in Λ_{L_{∞}}. We may order the m vertices q_{i} in T, so that q_{1} is connected to q_{2}, q_{3} is connected to the subtree of T spanned by q_{1} and q_{2}, and in general q_{p} is connected to the subtree of T spanned by the pre-chosen vertices q_{1}, q_{2}, …, q_{p−1}. W.l.o.g. we may assume that this is the original order defined on the vertex groups V_{∞}^{i} of the abelian decomposition Λ_{L_{∞}} of L_{∞}. Let X be the Cayley graph of the free group F_{k} with respect to a (fixed) finite set of generators, and let d_{X} be the standard simplicial metric on X. For each element f ∈ F_{k}, each positive integer n, and each automorphism φ ∈ Mod(U_{n}) we define the following (stretching) constants:

μ_{i}(n, f, φ) = max (d_{X}(id., fλ_{n}(φ(x_{1}^{i}))f^{−1}), …, d_{X}(id., fλ_{n}(φ(x_{ℓ_{i}}^{i}))f^{−1}))
χ_{r}(n, f, φ) = d_{X}(id., fλ_{n}(φ(y_{r}))f^{−1})

and the corresponding (m + b)-tuple:

tup(n, f, φ) = (μ_{1}(n, f, φ), …, μ_{m}(n, f, φ), χ_{1}(n.f, φ), …, χ_{b}(n, f, φ))

On the set of (m + b)-tuples we define the natural lexicographical order, and for each n we choose f_{n} ∈ F_{k} and φ_{n} ∈ Mod(U_{n}) for which tup(n, f_{n}, φ_{n}) is a minimal (m+b)-tuple in the set {tup(n, f, φ)} with respect to the lexicographical order. We set disp_{n} to be the sum of the elements in the (m + b)-tuple tup(n, f_{n}, φ_{n}).

If w_{1}, w_{2} ∈ W_{1} are a pair of elements for which σ_{1}(w_{1}), σ_{1}(w_{2}) ∈ V_{∞}^{i} for some i, then for some index n_{0} and for every n > n_{0}, τ_{n} ∘ … ∘ τ_{0}(w_{1}) and τ_{n} ∘ … ∘ τ_{0}(w_{2}) belong to the same (i-th) vertex group V_{n}^{i} in the (f.g. abelian) splitting Λ_{n} of U_{n}. Hence, for every n > n_{0} both τ_{n} ∘…∘τ_{0}(w_{1}) and τ_{n} ∘…∘τ_{0}(w_{2}) are being mapped to their (same) conjugates by every modular automorphism φ ∈ Mod(U_{n}), and in particular, by the chosen one φ_{n}. Since in addition at least one of the vertex groups V_{∞}^{i} contains abelian non-cyclic subgroups, there could not exist a sequence of indices n_{1} < n_{2} < … and corresponding elements f_{n_{j}} ∈ F_{k} so that for every index j, f_{n_{j}} conjugates λ_{n_{j}} ∘ φ_{n_{j}}(x_{p}^{i}) into λ_{n_{1}} ∘ φ_{n_{1}}(x_{p}^{i}) for i = 1, …, m and p = 1, …, ℓ_{i} and conjugates λ_{n_{j}} ∘ φ_{n_{j}}(y_{r}) into λ_{n_{1}} ∘ φ_{n_{1}}(y_{r}) for every r = 1, …, b. Therefore, in particular, the sequence of displacement constants {disp_{n}} does not contain a bounded subsequence, i.e., disp_{n} → ∞.

The groups W_{n} admit a natural action on the Cayley graph X of F_{k} which we denote ρ_{n} : W_{n}×X → X, by setting ρ_{n}(w, x) = λ_{n}∘φ_{n}(w)(x) for every w ∈ W_{n} and x ∈ X. Since the sequence of displacements {disp_{n}} is not bounded, and the group W_{n} is a natural quotient of the group W_{1}, we may rescale the metric on the Cayley graph X by disp_{n}, and apply proposition 1.1 ([Pa],2.3) for the sequence of actions {ρ_{n}} to obtain a subsequence (still denoted {ρ_{n}}) converging into a (pointed) real tree (R, r_{0}) equipped with a non-trivial isometric action of W_{1}. We set KW_{∞} to be the kernel of the action of W_{1} on the real tree R, and the f.g. group Q_{∞} to be the quotient Q_{∞} = W_{1}/KW_{∞}. Q_{∞} is also a limit group so it satisfies lemmas 1.2, 1.3 and 1.4 and its action on the pointed limit tree (R, r_{0}) satisfies the properties given in theorem 1.5. L_{∞} is the direct limit of the groups {W_{n}} and the epimorphisms {τ_{n}} between them. Since if w_{1}, w_{2} ∈ W_{0} are a pair of elements for which η ∘ λ_{1}(w_{1}), η ∘ λ_{1}(w_{2}) ∈ V_{∞}^{i} for some i, then for some index n_{0} and for every n > n_{0}, τ_{n} ∘ … ∘ τ_{0}(w_{1}) and τ_{n} ∘ … ∘ τ_{0}(w_{2}) belong to the same (i-th) vertex group V_{n}^{i} in the (f.g. abelian) splitting Λ_{n} of U_{n}, for every n > n_{0} both τ_{n} ∘ … ∘ τ_{0}(w_{1}) and τ_{n} ∘ … ∘ τ_{0}(w_{2}) are being mapped to their (same) conjugates by the chosen automorphism φ_{n}. Hence, V_{∞}^{i} is naturally embedded in the group Q_{∞}. By our construction, Q_{∞} is generated by the subgroups V_{∞}^{i} and the images of the elements y_{r} ∈ W_{1} in Q_{∞}.

Proposition 3.3. With the notation and assumptions above, if all the subgroups V_{∞}^{1}, …, V_{∞}^{m} (the vertex groups in the abelian decomposition Λ_{L_{∞}} of L_{∞}) fix points in the pointed real tree (R, r_{0}), then they all fix the base point r_{0} ∈ R.

Proof: By our assumptions V_{∞}^{1} fixes a point r ∈ R. For fixed index n, the conjugating elements {f_{n}} and the modular automorphisms {φ_{n}} were chosen to minimize the (m + b)-tuple tup(n, f, φ), so in particular for fixed n, the chosen elements have to minimize the stretching constant μ_{1}(n, f, φ). If V_{∞}^{1} does not fix the base point r_{0} ∈ R, then for some n_{0} and all n > n_{0} it is possible to find elements h_{n} ∈ F_{k} for which:

max_{1≤p≤ℓ_{1}} d_{X}(id., h_{n}f_{n}λ_{n}(φ_{n}(x_{p}^{1}))f_{n}^{−1}h_{n}^{−1}) < max_{1≤p≤ℓ_{1}} d_{X}(id., f_{n}λ_{n}(φ_{n}(x_{p}^{1}))f_{n}^{−1})

Hence, μ_{1}(n, h_{n}f_{n}, φ_{n}) < μ_{1}(n, f_{n}, φ_{n}), which implies tup(n, h_{n}f_{n}, φ_{n}) < tup(n, f_{n}, φ_{n}), a contradiction to the choice of the pair f_{n}, φ_{n}. Therefore, V_{∞}^{1} fixes the base point r_{0} ∈ R.

V_{∞}^{1} fixes the base point r_{0} ∈ R, so if the claim of proposition 3.2 does not hold there must exist a minimal index i_{0}, so that V_{∞}^{1}, …, V_{∞}^{i_{0}−1} fix the base point r_{0} ∈ R whereas V_{∞}^{i_{0}} does not fix r_{0} ∈ R. To prove the proposition we adapt the shortening argument of [Se3] and [Ri-Se1] to show that in this last case it is possible to find a sequence of modular automorphisms {α_{n} ∈ Mod(U_{n})} so that for some index n_{0} and every n > n_{0}:

tup(n, f_{n}, φ_{n} ∘ α_{n}) < tup(n, f_{n}, φ_{n})

Lemma 3.4. With the notation and assumptions above, if V_{∞}^{1}, …, V_{∞}^{i_{0}−1} fix the base point r_{0} ∈ R and V_{∞}^{i_{0}} does not fix the point r_{0}, then there exists some index n_{0} so that for all n > n_{0} there exist modular automorphisms α_{n} ∈ Mod(U_{n}) for which:

(i) α_{n}(V_{n}^{i}) = V_{n}^{i} for i = 1, …, i_{0} − 1.

(ii) μ_{i_{0}}(n, f_{n}, φ_{n} ∘ α_{n}) < μ_{i_{0}}(n, f_{n}, φ_{n}).

Proof: identical to the proof of theorem 6.10 in [Ri-Se1].

□

By lemma 3.3 if i_{0} is the first index for which V_{∞}^{i_{0}} does not fix the base point r_{0} ∈ R, then for some index n_{0} and all n > n_{0} it is possible to find modular automorphisms α_{n} ∈ Mod(U_{n}) for which:

(1) μ_{i}(n, f_{n}, φ_{n} ∘ α_{n}) = μ_{i}(n, f_{n}, φ_{n}) for i = 1, …, i_{0} − 1

(2) μ_{i_{0}}(n, f_{n}, φ_{n} ∘ α_{n}) < μ_{i_{0}}(n, f_{n}, φ_{n}). Hence, tup(n, f_{n}, φ_{n} ∘ α_{n}) < tup(n, f_{n}, φ_{n}) in the lexicographical order on the (m + b)-tuples tup(n, f, φ), which clearly contradicts the way the pair (f_{n}, φ_{n}) were chosen. Therefore, all the groups V_{∞}^{i} have to fix the base point r_{0} ∈ R and the proof of proposition 3.2 is concluded.

□

Showing that all vertex groups V_{∞}^{i} fix the base point r_{0} ∈ R, we continue by showing that the images of the elements y_{1}, …, y_{b} in Q_{∞} fix r_{0} as well. Since Q_{∞} is generated by the V_{∞}^{i}’s and the images of the y_{j}’s, we will get that the entire group Q_{∞} fixes the base point r_{0}, a contradiction to the non-triviality of the action of Q_{∞} on the real tree R, hence, at least one of the groups V_{∞}^{1}, …, V_{∞}^{m} does not a fix a point while acting on the real tree R.

Lemma 3.5. With the notation and assumptions above, let j_{0} be the minimal index for which y_{j_{0}} does not fix the base point r_{0} ∈ R. then there exists some index n_{0} so that for all n > n_{0} there exist modular automorphisms β_{n} ∈ Mod(U_{n}) for which:

(i) β_{n}(V_{n}^{i}) = V_{n}^{i} for i = 1, …, m.

(ii) β_{n}(y_{j}) = y_{j} for j = 1, …, j_{0} − 1.

(iii) χ_{j_{0}}(n, f_{n}, φ_{n} ∘ β_{n}) < χ_{j_{0}}(n, f_{n}, φ_{n}).

Proof: identical to the proof of theorem 6.13 in [Ri-Se1].

□

By lemma 3.4 if j_{0} is the first index for which y_{j_{0}} does not fix the base point r_{0} ∈ R, then for some index n_{0} and all n > n_{0} it is possible to find modular automorphisms β_{n} ∈ Mod(U_{n}) for which:

(1) μ_{i}(n, f_{n}, φ_{n} ∘ β_{n}) = μ_{i}(n, f_{n}, φ_{n}) for i = 1, …, m

(2) χ_{j}(n, f_{n}, φ_{n} ∘ β_{n}) = χ_{j}(n, f_{n}, φ_{n}) for j = 1, …, j_{0} − 1

(3) χ_{j_{0}}(n, f_{n}, φ_{n} ∘ β_{n}) < χ_{j_{0}}(n, f_{n}, φ_{n}). Hence, tup(n, f_{n}, φ_{n} ∘ β_{n}) < tup(n, f_{n}, φ_{n}) in the lexicographical order on the (m + b)-tuples tup(n, f, φ), which clearly contradicts the way the pair (f_{n}, φ_{n}) were chosen. Therefore, if all the groups V_{∞}^{1}, …, V_{∞}^{m} fix points in the real tree (R, r_{0}) then all the groups V_{∞}^{i} and all the elements y_{j} have to fix the base point r_{0} ∈ R. Since Q_{∞} is generated by the groups V_{∞}^{i} and the elements y_{j}, the entire group Q_{∞} fixes the base point r_{0} ∈ R. This clearly contradicts the non-triviality of the action of Q_{∞} on the real tree R, and therefore:

Proposition 3.6. With the notation and assumptions above, at least one of the vertex groups in the abelian decomposition Λ_{L_{∞}} of L_{∞}, V_{∞}^{1}, …, V_{∞}^{m}, acts nontrivially on the pointed real tree (R, r_{0}).

Since the limit group L_{∞} was assumed non-abelian, and since by lemma 1.4 every abelian subgroup of L_{∞} is contained in a unique maximal abelian subgroup and every maximal abelian subgroup is malnormal, not all vertex groups in Λ_{L_{∞}}, V_{∞}^{1}, …, V_{∞}^{m} are abelian.

Lemma 3.7. With the notation and assumptions above, Let A be an abelian subgroup of one of the groups V_{∞}^{i}. Then either A fixes a point in the real tree R, or A can be written as a direct sum A = Â + < a_{1}, …, a_{c} > where < a_{1}, …, a_{c} >≃ Z^{c}, Â fixes a point in the real tree R and no non-trivial element a ∈< a_{1}, …, a_{c} > fixes a point in R.

Proof: The lemma is obvious if A is cyclic, so suppose A is non-cyclic. Since A < V_{∞}^{i} it is naturally embedded in Q_{∞}. If Q_{∞} is freely decomposable A is a subgroup of one of the freely-indecomposable factors of Q_{∞}, Q̂_{∞}. The action of Q̂_{∞} on the real tree (R, r_{0}) can be analyzed using theorem 1.5 ([Se3],3.1). It follows from that theorem that an abelian subgroup can either fix a point in (R, r_{0}), preserve an axial component in (R, r_{0}), or fix an axis of one of its elements and this axis is not an axial component in (R, r_{0}). If A fixes an axial component then A can be expressed as a subgroup Stab < A that pointwise stabilizes this component, direct sum with a f.g. free abelian subgroup of A, where this f.g. free abelian subgroup acts faithfully on the axial component preserved by A. If A preserves a line in (R, r_{0}) which is not an axial component, A can be expressed as a subgroup Stab < A which fixes this line direct sum with a cyclic subgroup C of A that acts discretely on the line preserved by A.

□

Proposition 3.8. With the notation and assumptions above, if Λ_{L_{∞}} contains no principal cyclic splitting then every non-abelian vertex group V_{∞}^{i} in Λ_{L_{∞}} fixes a point r_{i} ∈ R when acting on the real tree (R, r_{0}).

Proof: Suppose V_{∞}^{i} is not abelian and it does not fix a point in the real tree (R, r_{0}). V_{∞}^{i} is generated by the abelian edge groups E_{∞}^{j} together with the finite set of elements v_{1}^{i}, …, v_{ℓ_{1}}^{i}. Hence, by lemma 3.6 V_{∞}^{i} is generated by finitely many abelian subgroups A_{1}^{i}, …, A_{u}^{i} that admit fix points while acting on (R, r_{0}) together with a finite set of elements v_{1}^{i}, …, v_{ℓ′_{1}}^{i}. Therefore, by theorem 1.5 V_{∞}^{i} inherits a finite graph of groups from its action on (R, r_{0}), a graph of groups which is nontrivial and in which all edge stabilizers are abelian. By lemma 2.1 we can modify this finite graph of groups to get a non-trivial abelian splitting Γ^{i} of V_{∞}^{i} in which all non-cyclic maximal abelian subgroups are elliptic, and by theorem 1.5 if Γ^{i} contains a cyclic edge group then V_{∞}^{i} admits a principal cyclic splitting in which all non-cyclic maximal abelian subgroups are elliptic. Now, we can properly refine the abelian decomposition Λ_{∞}^{i} by replacing the vertex stabilized by V_{∞}^{i} with Γ^{i}. If Γ^{i} contains a cyclic edge group, L_{∞} admits a principal cyclic splitting and the theorem follows. Otherwise, the obtained proper refinement can not be obtained from the abelian JSJ decomposition of L_{∞} by a sequence of foldings, collapsings, slidings, and modifying boundary monomorphisms which clearly contradicts the canonical properties of the abelian JSJ decomposition of L_{∞} (theorem 2.7) and the proposition follows.

□

Since by proposition 3.8 all non-abelian vertex groups V_{∞}^{i} in the abelian decomposition Λ_{L_{∞}} are elliptic when acting on the real tree (R, r_{0}), and since by proposition 3.3 not all the vertex groups V_{∞}^{1}, …, V_{∞}^{m} fix points in (R, r_{0}), there must exist at least one abelian vertex group V_{∞}^{i_{0}} that does not fix a point in (R, r_{0}). By lemma 3.7 V_{∞}^{i_{0}} = A^{i_{0}} + D^{i_{0}} where A^{i_{0}} fixes a point in the real tree (R, r_{0}) and D^{i_{0}} is a f.g. free abelian group that acts faithfully on the line preserved by V_{∞}^{i_{0}}. Since every maximal abelian subgroup in L_{∞} is malnormal, all adjacent vertex groups to an abelian vertex group in Λ_{L_{∞}} are non-abelian. Since all non-abelian vertex groups fix points in (R, r_{0}) all edge groups connected to V_{∞}^{i_{0}} are subgroups of A^{i_{0}}. If A^{i_{0}} is an infinite cyclic subgroup of V_{∞}^{i_{0}} we have found a principal cyclic splitting of the limit group L_{∞}, hence, we may assume that A^{i_{0}} is non-cyclic.

We set L_{∞}^{1} to be the fundamental group of the graph of groups obtained from Λ_{L_{∞}} by replacing the vertex group V_{∞}^{i_{0}} with its subgroup A^{i_{0}}. Clearly, L_{∞}^{1} is a subgroups of L_{∞}, and since V_{∞}^{i_{0}} = A^{i_{0}} + D^{i_{0}}, L_{∞}^{1} is also a quotient of L_{∞}. Hence, L_{∞}^{1} is f.g. as well, and the first betty number of L_{∞}^{1} is strictly smaller than that of L_{∞}: b_{1}(L_{∞}^{1}) < b_{1}(L_{∞}). If L_{∞}^{1} is freely decomposable, then the abelian subgroup A^{i_{0}} can be conjugated into one of the free factors, so necessarily L_{∞} must be freely decomposable as well, a contradiction to our assumptions. Hence, we may conclude that L_{∞}^{1} is freely-indecomposable.

L_{∞}^{1} is also a limit group, so we may repeat the shortening argument for L_{∞}^{1} and the abelian splitting it inherits from the abelian decomposition Λ_{L_{∞}} of L_{∞} to obtain a new limit group Q_{∞}^{1} acting on a new real tree (R^{1}, r_{0}^{1}). By propositions 3.3-3.8 either one of the non-abelian groups V_{∞}^{i} acts non-trivially on the new limit tree (R^{1}, r_{0}^{1}), in which case it is either possible to obtain a principal cyclic decomposition of L_{∞} or to refine the abelian JSJ decomposition of L_{∞} which contradicts its canonical properties (theorem 2.7), or we obtain a new limit group L_{∞}^{2} which is a subgroup and a quotient of L_{∞}^{1}, and b_{1}(L_{∞}^{2}) < b_{1}(L_{∞}^{1}) < b_{1}(L_{∞}). Therefore, after repeating this process finitely many times (depending on the first betti number of L_{∞}) we must obtain a non-trivial abelian splitting of one of the non-abelian groups V_{∞}^{i}, which allows us to either obtain a principal cyclic decomposition of L_{∞} or to refine the abelian JSJ decomposition of L_{∞} and contradict its canonical properties. This finally concludes the proof of theorem 3.2.

□

Thoerem 3.2 proves the existence of a principal cyclic splitting of a freelyindecomposable non-abelian limit group. In [Ri-Se2] a canonical (cyclic) JSJ decomposition that ”encodes” all cyclic splittings of a f.p. freely-indecomposable group is being constructed. Since all cyclic splittings can be modified to be 2-acylindrical, we may replace the generalized accessibility of M. Bestvina and M. Feighn [Be-Fe2] used in the construction of the cyclic JSJ decomposition of f.p. groups in [Ri-Se2] by acylindrical accessibility (theorem 2.6) to obtain the canonical cyclic decomposition of a limit group. The cyclic JSJ decomposition is basically obtained by collapsing all edges with non-cyclic edge groups in the abelian JSJ decomposition of a limit group. Theorem 3.2 shows it is non-trivial in case the limit group is not abelian.

Theorem 3.9 (cf. ([Ri-Se2],7.1). Suppose L_{∞} is freely indecomposable. There exists a reduced unfolded Z-splitting of L_{∞}, which we call the cyclic 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 cyclic JSJ decomposition which is not a CMQ subgroup of L_{∞} is elliptic in any Z-splitting of L_{∞} under consideration.

(ii) A one edge Z-splitting L_{∞} = D ∗_{Z} E or H_{∞} = D∗_{Z} under consideration which is hyperbolic in another elementary Z-splitting is obtained from the cyclic 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 Z-splitting L_{∞} = D ∗_{Z} E or L_{∞} = D∗_{Z}, which is elliptic with respect to any other one edge Z-splitting of L_{∞}. Then Θ is obtained from the cyclic JSJ decomposition of L_{∞} by a sequence of collapsings, foldings, and conjugations.

(iv) Let Λ be a general Z-splitting of L_{∞}. There exists a Z-splitting Λ_{1} obtained from the cyclic JSJ decomposition by splitting the CMQ subgroups along weakly essential s.c.c. on their corresponding 2-orbifolds, so that there exists a L_{∞}-equivariant simplicial map between a subdivision of the Bass-Serre tree T_{Λ_{1}} to T_{Λ}.

(iv) If JSJ_{1} is another cyclic 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)

(vi) If L_{∞} is non-abelian then the cyclic JSJ decomposition of L_{∞} is non-trivial. Furthermore, the cyclic JSJ decomposition can be collapsed to give a principal cyclic splitting of L_{∞} in this case.

§4. Finite Presentability of Limit Groups and ω-Residually Free Groups

In the first section we defined limit groups and studied the basic properties of their action on the corresponding limit tree. Since a limit group is a quotient of a f.g. group, it is naturally f.g. as well. To get a structure theory for spaces of solutions of equations in a free group, we will have to show limit groups are f.p. and not only f.g. . This will imply, in particular, that a limit group is a ω-residually free group (definition 4.5 below). To study some of the basic algebraic properties of limit groups we associate a canonical analysis lattice with a limit group.

Let L_{∞} be a limit group. We construct the analysis lattice associated with L_{∞} as follows. At the 0-th level of the hierarchy we place L^{0} = L_{∞}. If L_{∞} is either a free group, a surface group, or an abelian group this 0-th level is the entire analysis lattice. Otherwise, we first factor L^{0} = L_{∞} into freely indecomposable groups, then in each factor which is not abelian or a surface group, we define the groups in the 1-st level of the analysis lattice of L_{∞}, L_{1}^{1}, …, L_{m_{1}}^{1} to be the vertex groups in the canonical cyclic JSJ decompositions of the freely indecomposable factors of L_{∞}. Note that since L_{∞} is f.g. , the groups L_{i}^{1} are f.g. as well, hence, they are also limit groups.

To define the next levels we continue iteratively. If a group in the i-th level L_{j}^{i} is either a free group, a surface group or an abelian group we don’t continue to the i + 1-st level from this branch. Otherwise, we first factor L_{j}^{i} into freely indecomposable factors, and then define the successive groups in the i + 1 level to be the vertex groups in canonical JSJ decompositions of the freely indecomposable factors of L_{j}^{i}.

Our main technical goal in this section is to show that the construction of the ”analysis” lattice of a limit group terminates. To do that we will show that the complexity of limit groups appear in higher levels in the lattice is smaller than the complexity of limit groups in lower levels. To measure the complexity of the limit groups L_{j}^{i} we will use their first betti number which we denote b_{1}.

Theorem 4.1. With the notation and assumptions above, the number of levels in the canonical ”analysis” lattice associated with the limit group L_{∞} is bounded by 2b_{1}(L_{∞}).

Proof: Since we are going to use the first betti number to measure the complexity of a limit group, our first step in obtaining theorem 4.1 is showing the first betti number of a non-cyclic limit group is at least 2.

Lemma 4.2. With the notation of the first section let G be a f.g. group, let h_{n} be a convergent sequence of homomorphisms of G into F_{k}, and let L_{∞} be the corresponding limit group and Y the corresponding limit tree. If L_{∞} is non-cyclic then b_{1}(L_{∞}) ≥ 2.

Proof: We may assume L_{∞} is non-abelian. The image of the homomorphisms h_{n} : G → F_{k} is a subgroup of the free group F_{k}. If there exists a sequence of indices for which the image is cyclic, then by part (iv) of lemma 1.3 L_{∞} is abelian, which contradicts our assumptions. Hence, except for at most finitely many n’s the image of the homomorphisms h_{n} is a non-abelian free subgroup of F_{k}.

The limit group L_{∞} is f.g. and a quotient of the f.g. group G, so let L_{∞} = G/ < r_{1}, r_{2}, … >. We denote by G_{i} the group G_{i} = G/ < r_{1}, …, r_{i} >. Clearly there is a canonical epimorphism from G_{i} onto G_{i+1}, and the direct limit of the groups {G_{i}} is L_{∞}. Since for each fixed index i, for all but finitely many n’s, the homomorphisms h_{n} : G → F_{k} split through G_{i}, i.e., they can be written as a composition h_{n} = f_{n}^{i} ∘ p^{i} where p^{i} is the canonical quotient map from G onto G_{i}, and f_{n}^{i} is a homomorphism from G_{i} into F_{k}, G_{i} admits a non-abelian free quotient, so b_{1}(G_{i}) ≥ 2. Since L_{∞} is the direct limit of the groups G_{i} and the canonical epimorphisms between them:

b_{1}(G) ≥ b_{1}(G_{1}) ≥ b_{1}(G_{2}) ≥ … ≥ b_{1}(G_{i}) ≥ … ≥ b_{1}(L_{∞})

If A_{1}, A_{2}.A_{3}, … is a sequence of f.g. abelian groups so that there exist epimorphisms from A_{s} to A_{s+1} for every s, then there must exist some s_{0} for which A_{s_{0}} ≃ A_{s_{0}+1} ≃ A_{s_{0}+2} ≃ . . .. Applying that for the first homology groups of the G_{i}’s it follows that there exists some index i_{0} for which:

b_{1}(G_{i_{0}}) = b_{1}(G_{i_{0}+1}) = b_{1}(G_{i_{0}+2}) = … = b_{1}(L_{∞})

so b_{1}(L_{∞}) ≥ 2.

□

We will prove theorem 4.1 by induction on the first betti number of a limit group. By lemma 4.2 a limit group L_{∞} with b_{1}(L_{∞}) = 1 is cyclic, the analysis lattice of a cyclic group has only 1 level, so theorem 4.1 is valid for limit groups with first betti number 1. To be able to use the inductive hypothesis for proving the termination of the construction of the analysis lattice, and bound the number of its levels by 2b_{1}(L_{∞}) we need the following fact.

Proposition 4.3. With the notation and assumptions above, if L_{j}^{i} is a group in the i − th level of the analysis lattice of a limit group L_{∞}, L_{j′}^{i+1} is connected to L_{j}^{i} and L_{j′′}^{i+2} is connected to L_{j′}^{i+1} in this lattice then either:

(i) b_{1}(L_{j′′}^{i+2}) < b_{1}(L_{j}^{i})

(ii) L_{j′}^{i+1} is a subgroup of another limit group D_{j′}^{i+1} for which: b_{1}(D_{j′}^{i+1}) < b_{1}(L_{j}^{i})

Proof: Since L_{j}^{i} is connected to groups in the i+1-level of the analysis lattice, L_{j}^{i}, and similarly L_{j′}^{i+1}, are not abelian. If M = A ∗ B then b_{1}(M) = b_{1}(A) + b_{1}(B). Since the groups connected to L_{j}^{i} in the i + 1-level are vertex groups in the cyclic JSJ decomposition of freely-indecomposable factors of L_{j}^{i}, if L_{j′}^{i+1} is connected to L_{j}^{i} in the analysis lattice then b_{1}(L_{j′}^{i+1}) ≤ b_{1}(L_{j}^{i}). If b_{1}(L_{j′}^{i+1}) = b_{1}(L_{j}^{i}) then L_{j}^{i} must be freely-indecomposable, and by lemma 4.2 and a simple homological computation only one vertex in its canonical cyclic JSJ decomposition is non-cyclic. By theorem 3.2 a limit group admits a principal cyclic splitting, so if b_{1}(L_{j′}^{i+1}) = b_{1}(L_{j}^{i}) the cyclic JSJ decomposition of L_{j}^{i} is not a tree of groups with one non-cyclic vertex group. Hence, if we suppose case (i) of the proposition does not hold, i.e., b_{1}(L_{j}^{i}) = b_{1}(L_{j′}^{i+1}) = b_{1}(L_{j′′}^{i+2}), then the cyclic JSJ decompositions of L_{j}^{i} and L_{j′}^{i+1} contain one vertex with non-cyclic vertex group, bouquet of circles based on this vertex and, perhaps, some additional vertices with cyclic stabilizers located either in the interior of a circle or connected by a unique edge to the vertex with non-trivial stabilizer.

To simplify notation we set L_{1} = L_{j}^{i}, L_{2} = L_{j′}^{i+1} and L_{3} = L_{j′′}^{i+2}. We set Λ_{1} to be the cyclic JSJ decomposition of L_{1}, and Λ_{2} to be the cyclic JSJ decomposition of L_{2}. The cyclic splitting Λ_{1} has one vertex group, L_{2}, bouquet of circles, with cyclic edge groups < c_{1} >, …, < c_{k} > and Bass-Serre generators t_{1}, …, t_{k} so that t_{i}c_{i}t_{i}^{−1} = c′_{i}, and perhaps some additional vertices stabilized by cyclic vertex groups each connected by a single edge to the vertex stabilized by L_{2}. We set L̂_{2} to be the subgroup of L_{1} generated by L_{2} and the cyclic vertex groups connected to the vertex stabilized by L_{2}. The cyclic splitting Λ_{2} has one vertex group, L_{3}, and bouquet of circles, with cyclic edge groups < e_{1} >, …, < e_{ℓ} > and Bass-Serre generators b_{1}, …, b_{ℓ} so that b_{j}e_{j}b_{j}^{−1} = e′_{j}, and perhaps some additional vertices stabilized by cyclic vertex groups each connected by a single edge to the vertex stabilized by L_{3}. Let e_{1}, …, e_{q} be the entire collection of edge groups in Λ_{2}. We set L̂_{3} to be the subgroup of L_{2} generated by L_{3} and the cyclic vertex groups connected to the vertex stabilized by L_{3}.

At this point we use the shortening process used in proving theorem 3.2, applied to the cyclic splitting Λ_{1} of L_{1}, and obtain a (new) limit group D_{∞}, together with a canonical map ν : L_{1} → D_{∞}. By construction ν maps the group L̂_{2} monomorphically into D_{∞}. If D_{∞} is freely decomposable, then either L̂_{2} is freely decomposable or b_{1}(L_{2}) ≤ b_{1}(L̂_{2}) < b_{1}(D_{∞}) ≤ b_{1}(L_{1}), so in both cases part (i) of the proposition holds. Hence, we may assume that D_{∞} is freely-indecomposable, and D_{∞} is clearly not abelian, so D_{∞} admits a canonical (non-trivial) cyclic JSJ decomposition. According to lemma 2.1 we may modify the canonical JSJ decomposition of D_{∞}, to get a cyclic splitting of D_{∞} in which every non-cyclic abelian group is elliptic. We denote the cyclic splitting obtained by this modification by Λ_{D}. Note that by lemma 2.3, Λ_{D} is a 2-acylindrical splitting.

D_{∞} is generated by the images (under the homomorphism ν) of L_{2}, the Bass-Serre generators t_{1}, …, t_{k} and the cyclic vertex groups in Λ_{1}. By the way the shortening argument was defined if ν(L_{2}) fixes a vertex in Λ_{D}, or more generally, if all the elements ν(c_{1}), …, ν(c_{k}) fix the same vertex in Λ_{D}, the cyclic splitting Λ_{D} is either degenerate or it is a tree of groups with only one non-cyclic vertex group, so D_{∞} does not admit a principal cyclic splitting, a contradiction to theorem 3.2. Furthermore, since Λ_{2} contains a unique non-cyclic vertex group, if all the elements ν(c_{1}), …, ν(c_{k}) are elliptic in Λ_{D}, they must fix the same vertex in Λ_{D}. Hence, ν(L_{2}) does not fix a vertex in Λ_{D}, so it inherits a cyclic decomposition Γ_{2} from Λ_{D}, L_{3} fixes a vertex in Γ_{2}, this vertex is the only one stabilized by a non-cyclic group in Γ_{2}, and, at least some of the elements ν(c_{i}) are not elliptic in Γ_{2}.

Let V_{D} be the vertex group stabilized by L_{3} in Λ_{D}. Since the cyclic JSJ decomposition of L_{2} contains a unique non-cyclic vertex group (L_{3}), if ν(c_{i}) is elliptic in Λ_{D} for some i, ν(c_{i}) fixes either the vertex stabilized by V_{D} or a vertex connected to V_{D} and stabilized by a cyclic vertex group in Γ_{2}. Since ν(c_{i}) = ν(t_{i})ν(c′_{i})ν(t_{i}^{−1}), if ν(c_{i}) is hyperbolic in Λ_{D} so is ν(c′_{i}). Since L_{2} is freely-indecomposable, and the cyclic JSJ decomposition of L_{2} is Λ_{2}, each edge in the axis of ν(c_{i}) and ν(c′_{i}) has to be stabilized by some conjugates (by elements in the subgroup ν(L_{2})) of the elements ν(e_{1}), …, ν(e_{q}). ν(t_{i}) maps the axis of ν(c_{i}) to the axis of ν(c′_{i}).

First, suppose ν(t_{i}) maps an edge E stabilized by ν(a_{1}e_{j}a_{1}^{−1}) for some a_{1} ∈ L_{2} in the axis of ν(c_{i}), to an edge E′ stabilized by ν(a_{2}e_{j}a_{2}^{−1}) for some a_{2} ∈ L_{2}. If we denote a_{3} = a_{2}a_{1}^{−1} then the element d_{i} = ν(t_{i})ν(a_{3}^{−1}) fixes the edge E. Hence, there exists some element e in the (cyclic) stabilizer of the edge E, for which d_{i} = e and ν(t_{i}) = eν(a_{3}^{−1}). Since e and ν(a_{1}e_{j}a_{1}^{−1}) belong to the same cyclic subgroup in D_{∞}, and ν(t_{i}) conjugates ν(c_{i}) to ν(c′_{i}), b_{1}(< e, ν(L_{2}) >) ≤ b_{1}(L_{2}) − 1 < b_{1}(L_{1}). Hence, in this case we set D_{j′}^{i+1} to be the subgroup < e, ν(L_{2}) > of D_{∞}, then b_{1}(D_{j′}^{i+1}) < b_{1}(L_{1}), and case (ii) holds.

Now, suppose ν(t_{i}) maps an edge E_{1} which is in the axis of ν(c_{i}) to an edge E_{2} that is in the axis of ν(c′_{i}), and E_{1} is not in the orbit of E_{2} under the action of ν(L_{2}). In this case there is an element a_{1} ∈ ν(L_{2}) that maps the edge E_{2} into an edge E_{3} in the axis of ν(c_{i}). ν(t_{i}) maps E_{3} into an edge E_{4} in the axis of ν(c′_{i}). Since there are finitely many orbits of edges along the axis of ν(c_{i}) (and ν(c′_{i})), after finitely many iterations, we get an element w = ν(t_{i})a_{1}ν(t_{i})a_{2} … ν(t_{i})a_{n} that stabilizes the edge E_{i}, where a_{1}, …, a_{n} ∈ ν(L_{2}). Hence, b_{1}(< ν(t_{i}), ν(L_{2}) >) ≤ b_{1}(L_{1}) − 1 < b_{1}(L_{1}), so setting D_{j′}^{i+1} =< ν(t_{i}), ν(L_{2}) > case (ii) of the proposition holds.

□

At this point we are ready to complete the proof of theorem 4.1 by induction on the first betti number of L_{∞}. If b_{1}(L_{∞}) = 1, L_{∞} is cyclic by lemma 4.2 and its analysis lattice contains only one level. Suppose b_{1}(L_{∞}) > 1. We need to show that all branches in the analysis lattice of L_{∞} have depth bounded by 2b_{1}(L_{∞}). For every group L_{j′′}^{2} in the second level of the analysis lattice of L_{∞} for which b_{1}(L_{j′′}^{2}) < b_{1}(L_{∞}), all branches containing it have depth bounded by 2b_{1}(L_{∞}) by our inductive hypothesis.

If L_{j′′}^{2} is a group in the second level of the analysis lattice of L_{∞} for which b_{1}(L_{j′′}^{2}) = b_{1}(L_{∞}) then by proposition 4.3 L_{j′′}^{2} is a vertex group in the cyclic JSJ decomposition of L_{j′}^{1} and L_{j′}^{1} is a subgroup of some limit group D_{j′}^{1} for which b_{1}(D_{j′}^{1}) < b_{1}(L_{∞}). Since L_{j′}^{1} is a subgroup of D_{j′}^{1}, and by the canonical properties of the cyclic JSJ decomposition of L_{j′}^{1}, every group in level k of the analysis of L_{j′}^{1} is a subgroup of a group in level k of the analysis lattice of D_{∞}^{1}. Since a f.g. subgroup of a free abelian group is free abelian, a f.g. subgroup of a free group is free and a f.g. subgroup of a surface group is either free or a surface group, the construction of the analysis lattice of L_{j′}^{1} terminates not after the termination of the construction of analysis lattice of D_{j′}^{1}. By the inductive hypothesis the analysis lattice of D_{∞}^{1} contains at most 2b_{1}(D_{j′}^{1}) < 2b_{1}(L_{∞}) − 2 levels, so the analysis lattice of L_{j′}^{1} contains at most 2b_{1}(L_{∞}) − 2 levels and the theorem follows.

□

The termination of the construction of the analysis lattice is the key technical tool for understanding the algebraic structure of Limit groups. In fact it can be viewed as a (canonical) ”Haken Hierarchy” for limit groups. The following algebraic properties of limit groups are an immediate corollary.

Corollary 4.4. Let L_{∞} be a limit group. Then:

(i) L_{∞} is finitely presented.

(ii) An abelian subgroup of L_{∞} is a f.g. free abelian group. The rank of the free

abelian subgroup is bounded by the first betti number of L_{∞}. (iii) If L_{∞} does not contain a non-cyclic abelian subgroup then L_{∞} is (Gromov)

hyperbolic.

Proof: The analysis lattice shows that a limit group can be constructed from abelian, free, and surface groups by a finite sequence of amalgamated products and HNN extensions over cyclic groups and free products, hence, it is finitely presented, and we get (i). Every abelian subgroup of a limit group which is not cyclic or Z +Z is elliptic in its cyclic JSJ decomposition. Therefore, such abelian subgroup of L_{∞} must appear as a terminal vertex group in the analysis lattice, so it must be f.g. and its rank is bounded by the first betti number of L_{∞}. A limit group is torsionfree by lemma 1.3 which gives us part (ii). If L_{∞} does not contain non-cyclic abelian groups, it is constructed from free and surface groups by a sequence of amalgamated products and HNN extensions along cyclic groups and free products, and since every cyclic subgroup of a limit group is contained in a unique maximal cyclic one by lemma 1.4 and part (ii), such limit group is hyperbolic group by the combination theorem of M. Bestvina and M. Feighn [Be-Fe3].

□

The finite presentability of limit groups is a key tool in our analysis of sets of solutions to equations. It is the source for all the finiteness results we will get both for these sets and in dealing with the elementary theory of free groups in our continuation papers. An immediate implication of the finite presentability is equivalence between limit groups and f.g. ω-residually free groups.

Definition 4.5. Let H be a group. H is called residually free if for every element h ≠ 1 in H, there exist a free group F_{k} and a homomorphism ϕ : H → F_{k} so that ϕ(h) ≠ 1. H is called ω-residually free if for any integer m and every set of m elements h_{1}, …, h_{m} ≠ 1 in H, there exist an integer k and a homomorphsim ϕ : H → F_{k} so that ϕ(h_{1}), …, ϕ(h_{n}) ≠ 1.

Theorem 4.6. A f.g. group R is a limit group if and only if it is ω-residually free.

Proof: The theorem is obvious for f.g. free abelian groups, so we may assume the f.g. group R is not abelian. Suppose R is a limit group. By definition there exists a f.g. group G, an integer k and a sequence of homomorphisms h_{n} : G → F_{k}, so that the limit of the actions of G on the Cayley graph of F_{k} via the homomorphisms h_{n} is a faithful action of R on some real tree Y. By corollary 4.4 R is f.p. so by lemma 1.3 for all but finitely indices n, the homomorphisms h_{n} split through the limit group R, i.e.. h_{n} = ψ_{n} ∘ p where p : G → R is the canonical projection map, and the ψ_{n}’s are homomorphisms ψ_{n} : R → F_{k}. By lemma 1.3 if r ≠ 1 in R, then for all but finitely many n’s ψ_{n}(r) ≠ 1. Hence, for every integer m and every set of m elements r_{1}, …, r_{m} ≠ 1 in R, for all but finitely many indices n, ψ_{n}(r_{1}), …, ψ_{n}(r_{m}) ≠ 1, so R is ω-residually free.

To prove the other direction, suppose R =< r_{1}, …, r_{s} > is f.g. and ω-residually free. Since R is ω-residually free there exist a sequence of homomorphisms ϕ_{n} : R → F_{2}, so that ϕ_{n} maps the elements in a ball of radius m in the Cayley graph of R to distinct elements in F_{2}. By rescaling the metric on F_{2}, proposition 1.1 implies that there exists a subsequence of the homomorphisms ϕ_{n} which converges to an action of a limit group L on a real tree Y. In general, the limit group L is a quotient of the f.g. group R, but since the homomorphisms were chosen so that ϕ_{n} maps a ball of radius n ”monomorphically” into F_{2}, part (iii) of lemma 1.3 implies that R is isomorphic to L and, therefore, R is a limit group.

□

Clearly, since f.g. ω-residually free groups are limit groups and vice versa, all the algebraic properties proven for limit groups are valid for ω-residually free groups. In particular, they admit a principal cyclic decomposition (theorem 3.2), a canonical cyclic JSJ decomposition (theorem 3.9), a (canonical) analysis lattice, they are f.p. , every abelian subgroup of a f.g. ω-residually free group is a f.g. free abelian group and its rank is bounded by the first betti number of the ambient ω-residually free group, and if a f.g. ω-residually free group does not contain a non-cyclic abelian subgroup it is (Gromov) hyperbolic. Also, since a f.g. ω-residually free group is, in particular, residually finite, it satisfies the Hopf property.

If a limit group does not contain a non-cyclic abelian subgroup, it is (Gromov) hyperbolic. In general, a limit group is probably hyperbolic relative to its maximal (non-cyclic) abelian groups (e.g. in the sense of B. Farb [Fa]), and non-positively curved. Since we will not need these properties of limit groups in our study, we are not going to discusss them in this paper.

§5. The (Canonical) Makanin-Razborov Diagrams

The algebraic properties of limit groups proved in the previous sections introduce tools that initialize the analysis of these groups, but are still short of obtaining any kind of classification of them. i.e., the cyclic JSJ decomposition and the analysis lattice associated with a limit group, are helpful in proving properties of limit groups but they are not enough for getting a necessary and sufficient conditions for a f.p. group to be a limit group (or equivalently an ω-residually free group). To get such criteria, we need to introduce canonical resolutions of limit groups, resolutions which will capture all the possible homomorphisms from a limit group into a free group and which are similar in nature to the ones appear in works of Makanin [Ma] and Razborov [Ra1], obtained there under some additional combinatorial hypothesis (bounded periodicity), and generalized later by Razborov in his dissertation [Ra2].

On the set of limit groups (ω-residually free groups) we define a partial order. Given two limit groups R_{1}, R_{2} we say that R_{1} > R_{2} if R_{2} is a proper quotient of R_{1}. Note that since a limit group is Hopf, if R_{2} is a proper quotient of R_{1} then R_{1} can not be a quotient of R_{2}. A first implication of the finite presentability of limit groups to their partial order is the termination of decreasing sequences.

Proposition 5.1. Every sequence of decreasing limit groups R_{1} > R_{2} > R_{3} > … terminates.

Proof: Suppose there is a decreasing sequence which does not terminate. The limit groups {R_{m}} are all quotients of R_{1}, so we may assume their fixed finite set of generators is the image of a fixed finite set of generators of R_{1}. The limit groups R_{m} are ω-residually free by theorem 4.6, so for each fixed m we can define a sequence of homomorphisms h_{n}^{m} : R_{m} → F_{k} so that h_{n}^{m} maps the n-ball in the Cayley graph of R_{m} to distinct elements in F_{k}. From the sequences {h_{n}^{m}} we extract the diagonal sequence of homomorphisms ϕ_{m} : R_{1} → F_{k} by setting ϕ_{m} = h_{m}^{m} ∘ p_{m} where p_{m} : R_{1} → R_{m} is the natural projection. By rescaling the metric on F_{k}, proposition 1.1 implies the the actions of R_{1} on the Cayley graph of F_{k} via the homomorphisms {ϕ_{m}} subconverge into an action of a limit group R on a real tree Y (see section 1).

R is a quotient of all the groups R_{m} in the decreasing sequence and it is a limit group by construction. By corollary 4.4 R is f.p. and by part (iii) of lemma 1.3 for all but finitely many indices m, the (finite) defining relations of R are mapped to the trivial element by the homomorphisms ϕ_{m}. Since the homomorphisms h_{m}^{m} were chosen to map the ball of radius m in the Cayley graph of R_{m} into distinct elements, and since the defining relations of R are mapped to the identity by ϕ_{m}, for all but finitely many m’s, there exists some index m_{0}, so that R_{m_{0}}, R_{m_{0}+1}, … are all quotients of the limit group R. But R is a proper quotient of the R_{m}’s, so we obtain a contradiction to the Hopf property of the limit group R, and a decreasing sequence must terminate.

□

To get an understanding of the structure of limit groups (ω-residually free groups) we need to find a way to ”encode” all possible homomorphisms from a limit group into free groups. To get such ”encoding” we will construct a canonical resolution associated with a limit group. To construct this canonical resolution we need to introduce shortening quotients of a limit group. To construct a shortening quotient of a limit group we need to define its associated modular group.

Definition 5.2. Let R be a freely-indecomposable limit group. We define the modular group Mod(R) to be the subgroup of Aut(R) generated by the following families of automorphisms of R:

(i) inner automorphisms.

(ii) Dehn twists along edges of the cyclic JSJ decomposition of R.

(iii) Dehn twists along essential s.c.c. in CMQ (canonical maximal quadratically

hanging) vertex groups in the cyclic JSJ decomposition of R. (iv) Let A be an abelian vertex group in the cyclic JSJ decomposition of R, and

let A_{1} < A be the subgroup generated by all the edge groups connecting A to the other vertex groups in the cyclic JSJ decomposition of R. Every automorphism of A that fixes A_{1} (elementwise) can be naturally extended to an automorphism of the ambient limit group R. We call these generalized Dehn twists and they form the fourth family of automorphisms that generate Mod(R).

At this stage we are ready to modify the shortening argument presented in section 3 in order to obtain the shortening quotients of a freely-indecomposable limit group R. Let {h_{n} | h_{n} : R → F_{k}} be a sequence of homomorphisms from R into a free group F_{k}. Let r_{1}, …, r_{m} ∈ R be a generating set of R, and let V_{1}, …, V_{ℓ} be the vertex groups in the cyclic JSJ decomposition of R. Let X be the Cayley graph of the free group F_{k} with respect to a (fixed) finite set of generators, and let d_{X} be the standard simplicial metric on X. For each element f ∈ F_{k}, each positive integer n, and each automorphism φ ∈ Mod(R) we define the following (stretching) constant:

μ(n, f, φ) = max (d_{X}(id., fh_{n}(φ(r_{1}))f^{−1}), …, d_{X}(id., fh_{n}(φ(r_{m}))f^{−1}))

For each n we choose f_{n} ∈ F_{k} and φ_{n} ∈ Mod(R) for which μ(n, f_{n}, φ_{n}) is minimal in the set {μ(n, f, φ)}. We set disp_{n} = μ(n, f_{n}, φ_{n}).

The limit group R admits a natural action on the Cayley graph X of F_{k} which we denote ρ_{n} : R×X → X, by setting ρ_{n}(r, x) = τ_{f_{n}} ∘h_{n} ∘φ_{n}(r)(x) for every r ∈ R and x ∈ X, where τ_{f_{n}} is the inner automorphism of F_{k} defined by f_{n}. Since X is a simplicial tree, for the n-th action ρ_{n} we may rescale the metric on the Cayley graph X by disp_{n}, and apply proposition 1.1 ([Pa],2.3) for the sequence of actions {ρ_{n}} to obtain a subsequence (still denoted {ρ_{n}}) converging into a (pointed) real tree (T, t_{0}) equipped with a non-trivial isometric action of R. We set KS_{∞} to be the kernel of the action of R on the real tree T, and the limit group S_{∞} to be the quotient S_{∞} = R/KS_{∞}. We say that the limit group S_{∞} associated with the canonical quotient map η : R → S_{∞} is a shortening quotient of the limit group R. Note that the construction of a shortening quotient of R does depend on the sequence of homomorphisms h_{n} : R → F_{k} and the specific generating set r_{1}, …, r_{m} ∈ R pre-chosen for R.

We say that two 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.

Since all the homomorphisms h_{n} map the limit group R into a free group F_{k}, a shortening quotient of a limit group R is indeed a quotient of R. In fact, it is a proper quotient of it.

Claim 5.3. Let R be a freely-indecomposable limit group. Then every shortening quotient of R is a proper quotient of R.

Proof: Let R be a freely-indecomposable limit group, let {h_{n} : R → F_{k}} be a sequence of homomorphisms, suppose the sequence of actions of R on the Cayley graph of F_{k} via the homomorphisms {h_{n}} converge into an action of a shortening quotient S of R on some real tree Y_{S}, and suppose each of the homomorphisms h_{n} is the ”shortest” possible under compositions with modular automorphisms of R and inner automorphisms of F_{k}. Now, assume that the shortening quotient S is isomorphic to R, so the canonical map η : R → S is an isomorphism. Let Γ_{R} be the abelian JSJ decomposition of R (see theorem 2.7). By theorem 3.2 R obtains a principal cyclic splitting, so some of the edge groups in Γ_{R} are cyclic.

To obtain a contradiction to the isomorphism between R and its shortening quotient S, suppose first that all the edge groups in the abelian JSJ decomposition of R are cyclic. By theorem 1.5, the shortening quotient S inherits an abelian splitting from its action on the limit tree Y_{S}. Since R is assumed isomorphic to its shortening quotient S, R inherits an abelian splitting from its action on Y_{S}. The limit action of S on Y_{S} was obtained from a sequence of homomorphisms {h_{n} : R → F_{k}} that were assume the ”shortest” possible under compositions with modular automorphisms of R and inner automorphisms of F_{k}. Therefore, the real tree Y_{S} can not contain an IET component, since otherwise, for large enough n, it was possible to ”shorten” the homomorphism h_{n} by pre-composing with a modular automorphism of R by the canonical properties of the abelian JSJ decomposition of R (theorem 2.7) and the shortening argument given in ([Ri-Se1],5.1), which contradicts our assumptions on the homomorphisms {h_{n}}. By a similar argument Y_{S} does not contain an axial component. Hence, the action of R on Y_{S} is discrete. But again, when the action of R on Y_{S} is discrete, for large enough n, it is possible to ”shorten” the homomorphisms h_{n} by precomposing with a modular automorphism of R by the canonical properties of the abelian JSJ decomposition of R (theorem 2.7) and the shortening argument given in ([Se3],2.5), a contradiction to our assumptions on the homomorphisms {h_{n}}. Hence, the abelian JSJ decomposition of R, Γ_{R}, must contain some abelian, non-cyclic, edge groups.

Let E_{1}, …, E_{ℓ} be the abelian non-cyclic edge groups in Γ_{R}, let Λ_{1}, …, Λ_{q} be the subgraphs of Γ_{R} which are the connected components of the graph obtained from Γ_{R} by deleting the edges stabilized by E_{1}, …, E_{ℓ}. Since R admits a principal cyclic splitting by theorem 3.2, the abelian JSJ decomposition Γ_{R} contains an edge with cyclic edge group which corresponds to a principal cyclic splitting of R, and this edge must be contained in one of the connected subgraphs Λ_{1}, …, Λ_{q}, w.l.o.g., Λ_{1}. Let R_{1} be the subgroup of R which is the fundamental group of the subgraph Λ_{1}. Let {h_{n}^{1} : R_{1} → F_{k}} be the restrictions of the homomorphisms {h_{n} : R → F_{k}} to the subgroup R_{1}. From the sequence of actions of R_{1} on the Cayley graph of F_{k} via the homomorphisms {h_{n}^{1}} it is possible to extract a subsequence (still denoted {h_{n}^{1}}) that converge into an action of R_{1} on some real tree Y_{1}. By theorem 1.5 R_{1} inherits a (non-trivial) abelian splitting Γ_{1} from its action on Y_{1}.

Let E_{1}, …, E_{u} be the abelian non-cyclic edge groups in Γ_{R} which are the stabilizers of edges connected to Λ_{1}, i.e., E_{1}, …, E_{u} are the edge groups in Γ_{R} which are also subgroups of R_{1}. If any of the groups E_{1}, …, E_{u} is not elliptic when acting on the limit tree Y_{1}, it is possible to further refine the abelian JSJ decomposition Γ_{R} of R, which contradicts its canonical properties (theorem 2.7). Hence, the subgroups E_{1}, …, E_{u} can all be conjugated into vertex groups in Γ_{1}, so Γ_{1} can be extended to an abelian splitting on the ambient group R, so by the canonical properties of the abelian JSJ decomposition of R, Γ_{1} can be obtained from the connected subgraph Λ_{1} of the abelian JSJ decomposition of R, Γ_{R}.

Now, modifying the ”shortening argument” in case all edge groups in Γ_{R} are cyclic, if the real tree R_{1} contains an IET component, for large enough n, it is possible to ”shorten” the homomorphisms h_{n}^{1} by pre-composing with a modular automorphism of R that preserve R_{1} by the canonical properties of the abelian JSJ decomposition of R (theorem 2.7) and the shortening argument given in ([Ri-Se1],5.1). By construction a composition of these shortening modular automorphisms with the ambient homomorphisms {h_{n} : R → F_{k}} make these ”shorter”, which contradicts our assumptions on the homomorphisms {h_{n}}. By a similar argument Y_{1} does not contain an axial component. Hence, the action of R_{1} on Y_{1} is discrete. But again, when the action of R_{1} on Y_{1} is discrete, for large enough n, it is possible to ”shorten” the homomorphisms h_{n}^{1} by precomposing with a modular automorphism of R by the canonical properties of the abelian JSJ decomposition of R (theorem 2.7) and the shortening argument given in ([Se3],2.5). By construction a composition of these shortening modular automorphisms with the ambient homomorphisms {h_{n} : R → F_{k}} make these ”shorter”, a contradiction to our assumptions on the homomorphisms {h_{n}}.

□

Let SQ(R, r_{1}, …, r_{m}) be the set of shortening quotients of R. On the set SQ(R, r_{1}, …, r_{m}) we define a partial order as follows. For given elements 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 5.4. 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 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: Let S_{1} < S_{2} < S_{3} < … be an infinite properly increasing sequence of shortening quotients of the freely-indecomposable limit group R. Since each of the groups S_{j} is a shortening quotient of R, for each j there exists a sequence of homomorphisms h_{n}^{j} : R → F_{k}, so that h_{n}^{j} can not be shortened by compositions with both a modular automorphism of R and an inner automorphism of F_{k}, and if r ∈ R for which η_{j}(r) is not the identity element in S_{j} and η_{j}(r) is contained in the ball of Radius n in the Cayley graph of S_{j}, then h_{n}^{j}(r) ≠ 1.

Now, we look at the diagonal sequence h_{j}^{j} : R → F_{k}. By the construction used in section 1, we may choose a converging subsequence (to simplify notation still denoted h_{j}^{j}), so that the sequence of homomorphisms h_{j}^{j} : R → F_{k} converges into an action of a limit group S on some real tree Y. By our assumptions of the homomorphisms h_{n}^{j} : R → F_{k}, the diagonal sequence h_{j}^{j} : R → F_{k} can not be shortened by compositions with both a modular automorphism of R and an inner automorphism of F_{k}, so the limit group S is a shortening quotient of R, hence, S ∈ SQ(R, r_{1}, …, r_{m}).

The shortening quotient S is in particular a limit group, so by corollary 4.4 it is f.p. . By lemma 1.3 there must exist some index j_{0} so that for all indices j > j_{0}, the homomorphisms h_{j}^{j} map the (finite set of) defining relations of S to the trivial element in F_{k}. Since by the way the homomorphisms h_{n}^{j} were chosen, h_{j}^{j} maps a ball of radius j/2 in S_{j} monomorphically into F_{k}, all the defining relations of S must be trivial in S_{j} for large enough j. Therefore, S > S_{j} for large enough j which clearly implies that S > S_{j} for all indices j.

□

Lemma 5.4 proves the existence of maximal elements with respect to the partial order on the set of 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 shortening quotients.

Lemma 5.5. Let R be a freely-indecomposable limit group. The set of 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: Suppose there are infinitely many non-equivalent maximal shortening quotients S_{1}, S_{2}, S_{3}, … of some freely-indecomposable limit group R. As we did in the proof of lemma 5.4 since each of the groups S_{j} is a shortening quotient of R, for each j there exists a sequence of homomorphisms h_{n}^{j} : R → F_{k}, so that h_{n}^{j} can not be shortened by compositions with both a modular automorphism of R and an inner automorphism of F_{k}, and if r ∈ R for which η_{j}(r) is not the identity element in S_{j} and η_{j}(r) is contained in the ball of Radius n in the Cayley graph of S_{j}, then h_{n}^{j}(r) ≠ 1.

From the diagonal sequence h_{j}^{j} : R → F_{k} we can extract a convergent subsequence (still denote h_{j}^{j}), so that the sequence of homomorphisms h_{j}^{j} : R → F_{k} converges into an action of a limit group S on some real tree Y, and by our assumptions of the homomorphisms h_{n}^{j} : R → F_{k} the limit group S is a shortening quotient of R, i.e., S ∈ SQ(R, r_{1}, …, r_{m}).

The shortening quotient S is in particular a limit group, so by corollary 4.4 it is f.p. . By lemma 1.3 there must exist some index j_{0} so that for all indices j > j_{0}, the homomorphisms h_{j}^{j} map the (finite set of) defining relations of S to the trivial element in F_{k}. Since by the way the homomorphisms h_{n}^{j} were chosen, h_{j}^{j} maps a ball of radius j/2 in S_{j} monomorphically into F_{k}, all the defining relations of S must be trivial in S_{j} for some j > j_{1}. Therefore, for every j > j_{1} either S > S_{j} or S is equivalent to S_{j}. But all the shortening quotients S_{j} are assumed maximal in SQ(R, r_{1}, …, r_{m}), so for all j > j_{1} S is equivalent to S_{j}, and that contradicts our assumption on the S_{j}’s being from different equivalence classes of shortening quotients of R.

□

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

Proposition 5.6. 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 shortening quotients in SQ(R, r_{1}, …, r_{m}), and for i = 1, …, k let η_{i} : R → M_{i} be the canonical projection maps. Let h : R → F_{k} be a homomorphism. 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} → F_{k} is a homomorphism.

Proof: Given a homomorphism h : R → F_{k} we can choose a modular automorphism φ_{h} ∈ Mod(R) and an inner automorphism τ_{f} ∈ Inn(F_{k}) so that the composition ĥ = τ_{f} ∘ h ∘ φ_{h} is the shortest possible among all such compositions. The constant sequence of homomorphisms ĥ, ĥ, … converges into a free limit group F which is a subgroup of F_{k}. By our assumption on ĥ, F is a shortening quotient and the map ĥ : R → F is its associated canonical map. By lemmas 5.4 and 5.5, either there exists some maximal element M_{i} > F, or one of the M_{i}’s is equivalent to F. In both cases the homomorphism ĥ : R → F splits through the maximal shortening quotient M_{i} and the proposition follows.

□

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 limit group (ω-residually free group). The Makanin-Razborov diagram ”encodes” all possible homomorphisms from a limit group into a free group, and as we will later show, some of its properties can be stated as a criteria for a general f.g. group to be a limit group.

Let R be a limit group and let R = R_{1} ∗ … R_{ℓ} ∗ F_{g_{1}} be a factorization of R, where each of the R_{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 R_{1}, r_{1}^{2}, …, r_{m_{2}}^{2} be a generating set of R_{2} etc. . By lemma 5.4 the sets of shortening quotients of the freely-indecomposable limit groups R_{1}, …, R_{ℓ} contain maximal elements (with respect to the partial order defined above) and by lemma 5.5 there are only finitely many equivalence classes of maximal shortening quotients of each of the limit groups R_{1}, …, R_{ℓ}. For i = 1, …, ℓ let M_{1}^{i}, …, M_{k_{i}}^{i} be a collection of representatives of equivalence classes of maximal shortening quotients in SQ(R_{i}, r_{1}^{i}, …, r_{m_{i}}^{i}), and let η_{j}^{i} : R_{i} → M_{j}^{i} be the canonical projection maps.

We define the Makanin-Razborov diagram of the limit group R iteratively. We start by factoring R into its freely-indecomposable factors R_{1}, …, R_{ℓ} and the free factor F_{g}. From each of the factors R_{i} we associate k_{i} directed edges, starting at R_{i} and terminating at the maximal shortening quotient M_{j}^{i}. To each such directed edge we associate the canonical projection η_{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 shortening quotients. Since each (maximal) shortening quotient of a limit group is a proper quotient of that limit group by claim 5.3, and each sequence of properly decreasing sequence of limit groups terminates by proposition 5.1, the construction of the Makanin-Razborov diagram terminates.

By proposition 5.6 all the homomorphisms from a limit group R into a free group F_{k} are encoded by the canonical Makanin-Razborov diagram. i.e., they are all given by compositions of modular automorphisms of the limit groups in the diagram with the canonical maps from the limit groups into their maximal shortening quotients and finally with general homomorphisms (”substitutions”) of the terminal free groups that appear in the diagram into the target free group. By Grushko’s theorem the factorization of a f.g. group into freely indecomposable factors is canonical. In the third paper in this sequence we will use test sequences associated with a Makanin-Razborov diagram to show that the diagram is canonical, i.e., that the structure of the Makanin-Razborov diagram does not depend on the the (finite) set of generators that was used for its construction.

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

Definition 5.7. A subdiagram of the Makanin-Razborov diagram in which for each free factor R_{i} of the limit group R we choose a unique edge connecting R_{i} to one of its maximal shortening quotients, and proceed iteratively choosing only one maximal 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 5.8. Let R be a freely-indecomposable limit group. We say that a shortening quotient S of R is a strict shortening quotient if:

(i) each non-CMQ, non-abelian vertex group and each cyclic edge group in the cyclic JSJ decomposition of R is mapped monomorphically into the 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.

Finally, the existence of strict Makanin-Razborov quotients is a criteria for a f.g. group to be a limit group (ω-residually free group). We first show that a limit group admits a strict Makanin-Razborov resolution.

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

Proof: Let R be a freely-indecomposable limit group. R is an ω-residually free group, so there exists a sequence of homomorphisms h_{n} : R → F_{k} so that h_{n} maps the ball of radius n in R monomorphically into F_{k} and the sequence of actions of R on the Cayley graph of F_{k} via the sequence of homomorphisms {h_{n}} converges into a faithful action of R on some real tree Y.

By composing each of the elements h_{n} with an appropriate modular automorphism φ_{n} ∈ Mod(R) and an inner automorphism τ_{f_{n}} ∈ Inn(F_{k}) we obtain homomorphisms ĥ_{n} : R → F_{k}, ĥ_{n} = τ_{f_{n}} ∘ h_{n} ∘ φ_{n}, which are the shortest with respect to all such compositions. From the sequence ĥ_{n} we can extract a subsequence (still denoted ĥ_{n}) that converge into an action of a shortening quotient S on some real tree T. Let η : R → S be the canonical map from R onto its shortening quotient S.

If r ∈ R is contained in a non-CMQ, non-abelian vertex group or a in a cyclic edge group in the cyclic JSJ decomposition of R, then φ(r) is conjugate to r for all φ ∈ Mod(R), hence, for all indices n > n_{r}: h_{n}(r) ≠ 1 in F_{k}, so by lemma 1.3 η(r) ≠ 1 in the shortening quotient S and every non-CMQ, non-abelian vertex group and every cyclic edge group in the cyclic JSJ decomposition of R is mapped monomorphically into S by the canonical map η. Similarly, if A is an abelian vertex group in the cyclic JSJ decomposition of R and A_{1} < A is the subgroup generated by all edges connected to the vertex stabilized by A in the cyclic JSJ decomposition, then every modular automorphism φ ∈ Mod(R) maps the subgroup A_{1} into a conjugate, hence, the canonical map η maps A_{1} monomorphically into the shortening quotient S.

Let V be a CMQ-vertex group in the cyclic JSJ decomposition of R. Since the homomorphism h_{n} is supposed to map the ball of radius n in R monomorphically into F_{k}, and since V is non-abelian in R, there must exist some index n_{0}, so that for all indices n > n_{0}, h_{n}(V) is a non-abelian subgroup of F_{k}. Since for every modular automorphism φ ∈ Mod(R), φ(V) is conjugate to V, ĥ_{n}(V) is non-abelian subgroup of F_{k} for all n > n_{0} as well. By lemma 1.3 this implies that η(V) is a non-abelian subgroup of F_{k}. A modular automorphism of R map the edge groups in the canonical JSJ decomposition of R into their conjugates, hence, the edge groups in the cyclic JSJ decomposition of R are mapped to non-trivial subgroups of S by the canonical map η.

So far we have shown that the shortening quotient S is a strict shortening quotient of R. If S is not maximal shortening quotient of R then there must exists a maximal shortening quotient M of R so that M > S. Clearly, since S is a strict shortening quotient of R, the maximal shortening quotient M > S must be strict as well.

Therefore, we have shown that for every freely-indecomposable limit group there exists a strict maximal shortening quotient. Now, by the way the Makanin-Razborov diagram of a limit group is constructed together with the existence of a strict maximal shortening quotient for every freely-indecomposable limit group, it follows that every Makanin-Razborov diagram contains a strict Makanin-Razborov resolution.

□

Proposition 5.9 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 5.10. Let G be a f.g. group. We say that G admits a strict MR resolution if there exists a finite resolution of G constructed iteratively as follows. First, we start with a (possible) free factorization of G, G = G_{1} ∗…∗G_{n} ∗F_{u} where F_{u} is a free subgroup of G. Each of the factors G_{i} of G is mapped onto a unique group Q_{i} in the diagram by a map ν_{i} : G_{i} → Q_{i}. We suppose that each G_{i} admits a non-trivial cyclic splitting Λ_{G_{i}} with the following properties:

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

(ii) ν_{i} maps each of the non-QH (quadratically hanging), non-abelian vertex

groups and each of the cyclic edge groups in Λ_{G_{i}} monomorphically into Q_{i}. iii) ν_{i} maps each QH vertex group in Λ_{G_{i}} into a non-abelian subgroup of Q_{i} (iv) every abelian vertex group in Λ_{G_{i}} is free abelian, and that if A is an abelian

vertex group in Λ_{G_{i}}, and A_{1} < A is the subgroup generated by all edge groups connected to the vertex stabilized by A in Λ_{G_{i}}, then A_{1} is mapped monomorphically into Q_{i} by the map ν_{i}.

The construction of the next levels in a strict MR resolution of G continues iteratively and terminates when target groups are free (like in the construction of a Makanin-Razborov resolution of a limit group).

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

Theorem 5.11. A f.g. group G is a limit group (ω-residually free group) if and only if it admits a strict MR resolution

Proof: Let:

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

be a strict MR-resolution of a f.g. group G, 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 {varphi_{i}(n) ∈ Mod(G_{i})} for i = 0, …, m − 1 so that the limit group corresponding to the sequence of homomorphisms:

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

is the group G itself. 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 5.12. Let Q be the fundamental group of a (possibly punctured) surface S_{Q} of Euler characteristic at most −2. Let μ : Q → F_{k} be a homomorphism and suppose Q is mapped into a non-abelian subgroup of F_{k} 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 F_{k}, and the image in F_{k} 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 F_{k}, and the image of the fundamental group of the connected component obtained by cutting S_{Q} along γ is non-abelian.

Proof: First, assume S_{Q} is orientable. If S_{Q} is a closed surface or a surface with a single puncture then clearly either (i) or (ii) holds. If S_{Q} has more than one boundary component and S_{Q} is not a planar surface, then S_{Q} is the connected sum of two orientable surfaces S_{1} and S_{2}, so that S_{1} has only one boundary component and S_{2} is a planar surface. If the fundamental group of S_{1} is mapped into a nonabelian subgroup of F_{k}, then either (i) or (ii) hold as in the case of a surface with at most one puncture. If the fundamental group of S_{1} is mapped into a cyclic subgroup of F_{k}, then the cyclic subgroup corresponding to the boundary of S_{1} is necessarily mapped into the trivial subgroup in F_{k}. If the fundamental group of S_{1} is mapped into a non-trivial cyclic subgroup of F_{k}, then there must exists a non-separating s.c.c. in S_{1} that is mapped non-trivially into F_{k}, so case (ii) holds. If the fundamental group of S_{1} is mapped trivially into F_{k}, then there exists a non-boundary-parallel non-separating s.c.c. in S_{Q} that is mapped non-trivially into F_{k}, and again case (ii) holds.

If S_{Q} is a planar surface, we order its boundary components b_{1}, …, b_{n}. Note that by our assumptions each boundary component b_{i} is mapped non-trivially into F_{k}, and not all the images of the b_{i}’s in F_{k} commute. It is not hard to see that there must exist a couple of consecutive boundary components b_{i}, b_{i+1} so that the images of b_{i} and b_{i+1} in F_{k} do not commute, and the images of the elements b_{1}, …, b_{i−1}, b_{i}b_{i+1}, b_{i+2}, …, b_{n} generate a nonabelian subgroup in F_{k}. Hence, the separating s.c.c. in S_{Q} corresponding to the element b_{i}b_{i+1} is mapped to a nontrivial element in F_{k}, and the fundamental groups of each of the connected components obtained by cutting S_{Q} along this separating s.c.c. are mapped onto nonabelian subgroups of F_{k}.

Now assume S_{Q} is non-orientable. We can view S_{Q} as the connected sum of an orientable surface O (with boundary) and a Mobius band M. If the fundamental group of M is mapped non-trivially into F_{k}, all the boundary components of O are mapped non-trivially into F_{k}, and the fundamental group of O is mapped onto a non-abelian subgroup of F_{k}, so our arguments above apply for the orientable surface O, and there exists a s.c.c. γ with the required properties. If S_{Q} is a closed non-orientable surface, then O is an orientable surface with only one boundary component, and the fundamental group of O is mapped to a nonabelian subgroup of F_{k}, hence, there exists a non-separating s.c.c. γ ⊂ O so that γ is mapped non-trivially into F_{k} and the fundamental group of the connected component obtained by cutting S_{Q} along γ is mapped to a non-trivial subgroup of F_{k}. If S_{Q} has boundary, and the fundamental group of M is mapped to the identity in F_{k}, then there exists a non-separating s.c.c. γ ⊂ S_{Q} that cuts the Mobius band M, so that γ is mapped non-trivially into F_{k} and the fundamental group of the connected component obtained by cutting S_{Q} along γ is mapped to a non-abelian subgroup of F_{k}.

□

By recursively applying lemma 5.12, for each surface S_{Q_{j}} corresponding to a QH-vertex group in the cyclic splitting Λ_{G_{i}}, 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 monomorphically into G_{i+1} under the map ν_{i}. If we extend each of the cyclic splittings Λ_{G_{i}} by further splitting the QH-vertex groups along the families of s.c.c. chosen according to lemma 5.13, the used to prove theorem 5.11 in the absence of QH-subgroups generalizes to a give a proof in their presence.

□

§6. An Example: ω-Residually Free Towers

In the first 5 sections of this paper we studied the structure of ω-residually free groups, using their JSJ decomposition, the analysis lattice and the Makanin-Razborov diagram and resolutions. Before applying the results and techniques used in studying ω-residually free groups to study residually free groups and sets of solutions to equations in a free group which is the goal of this paper, we devote this section to some natural families of examples of ω-residually free groups.

If R_{1} and R_{2} are ω-residually free groups then R_{1} ∗ R_{2} is clearly an ω-residually free group as well. If R is an ω-residually free group, and r ∈ R is an element with cyclic centralizer and no non-trivial roots in R, then the ”double of R along < r >”, D_{R} = R ∗_{<r>} R, admits an obvious strict MR resolution, so by theorem 5.11 it is ω-residually free. In particular, since a free and surface groups are ω-residually free, every double of a free or a surface group along a maximal cyclic subgroup is an ωresidually free group. Another more ”geometric” family of ω-residually free groups, which in some way is the motivation for most of the objects we have associated with a general ω-residually free group, is the family of ω-residually free towers.

Definition 6.1. We say that a f.p. group G is an ω-residually free tower, if it is possible to find a finite set set of generators G =< {y_{j}^{ℓ}} > and defining relations {φ_{b}^{ℓ}} for G, where 1 ≤ ℓ ≤ ℓ(G), 1 ≤ j ≤ m_{ℓ} and 1 ≤ b ≤ r_{ℓ}, so that G can be presented using the following hierarchical structure which we define inductively:

(i) G^{0} is the trivial subgroup of G. (ii) with each level ℓ of the hierarchy we associate a group G^{ℓ}. G^{ℓ} is the subgroup

of G generated by the elements G^{ℓ} =< {y_{j}^{i}} > where 1 ≤ i ≤ ℓ and 1 ≤ j ≤ m_{i} in G. G^{ℓ} is the quotient of the free group generated by the elements {y_{j}^{i}} for 1 ≤ i ≤ ℓ and 1 ≤ j ≤ m_{i} divided by the normal closure of the set of relations φ_{b}^{i} where 1 ≤ i ≤ ℓ and 1 ≤ b ≤ r_{i}.

(iii) To define the the ℓ-th level, the generators y_{1}^{ℓ}, …, y_{m_{ℓ}}^{ℓ} are divided into s^{ℓ} disjoint blocks y_{1}^{ℓ}, …, y_{b_{1}^{ℓ}}^{ℓ}, y_{b_{1}^{ℓ}+1}^{ℓ}, …, y_{b_{2}^{ℓ}}^{ℓ}, …, y_{b_{s^{ℓ}−1}^{ℓ}+1}^{ℓ}, …, y_{m_{ℓ}}^{ℓ} where to

the p-th block of y_{j}^{ℓ}’s one of the following sets of defining relations is associated:

(1) a free block. no relation is associated to a free block of generators.

(2) an Abelian block. the relations [y_{j_{1}}^{ℓ}, y_{j_{2}}^{ℓ}] = 1 for every b_{p−1}^{ℓ} +1 ≤ j_{1} < j_{2} ≤ b_{p}^{i}, and in addition the relation [r̄, y_{j}^{ℓ}] = 1 for every b_{p−1}^{ℓ}+1 ≤ j ≤ b_{p}^{ℓ} and some element r̄ ∈ G^{ℓ−1} where r̄ may be the identity element, if r̄ is non-trivial it can not be conjugated into an Abelian block in lower levels, and r̄ is not a proper power of an element in G^{ℓ−1}.

(3) a quadratic block. A single relation which is in one of the following two forms is being associated with a quadratic block. To save notation we denote the set of generators in the p-th block of y_{j}^{ℓ} which is a quadratic block by y_{1}, …, y_{2g}, z_{1}, …, z_{n} in the first case and by y_{1}, …, y_{g}, z_{1}, …, z_{n} in the second. With this notation the relation associated with a quadratic block is either (orientable):

[y_{1}, y_{2}] … [y_{2g−1}, y_{2g}]z_{1}r̄_{1}z_{1}^{−1} … z_{n}r̄_{n}z_{n}^{−1} =
[ȳ_{1}, ȳ_{2}] … [ȳ_{2g−1}, ȳ_{2g}]z̄_{1}r̄_{1}z̄_{1}^{−1} … z̄_{n}r̄_{n}z̄_{n}^{−1}

or (non-orientable):

y_{1}^{2} … y_{2g}^{2}z_{1}r̄_{1}z_{1}^{−1} … z_{n}r̄_{n}z_{n}^{−1} =
ȳ_{1}^{2} … ȳ_{2g}^{2}z̄_{1}r̄_{1}z̄_{1}^{−1} … z̄_{n}r̄_{n}z̄_{n}^{−1}

where r̄_{j}, ȳ_{j} and z̄_{j} are elements in the group G^{ℓ−1}, the subgroups < {r̄_{j}}, {ȳ_{j}} > and < {r̄_{j}}, {z̄_{j}} > are non-abelian subgroups of G^{ℓ−1}, the element r_{i} is conjugate to the element r̄_{i} in G^{ℓ}, and the (punctured) surface corresponding to one of the above relations has Euler characteristic at most -2, or it is a punctured torus.

Since the tower G can be described as an iterated sequence of amalgamated products, its level groups G^{ℓ} are naturally embedded in the ω-residually free tower G. From the definition of towers it is clear they admit a strict MR resolution, so by theorem 5.11 they are ω-residually free groups. It is also easy to find their cyclic JSJ decomposition and their analysis lattice. With an ω-residually free tower G we can naturally associate a 2-complex T (G), constructed hierarchically by adding a bouquet of circles for each free block, a collection of 2-tori for each Abelian block, and a (punctured) surface for each quadratic block. Clearly, π_{1}(T (G)) = G.

§7. Residually Free Groups

In the previous 6 sections we have studied the algebraic structure of limit groups which are ω-residually free groups. When we get to study the structure of sets of solutions to equations in a free group in the next section, which we view as the analogue of algebraic varieties, ω-residually free groups are going to serve as the (dual of the) analogue of irreducible varieties.

As we have already pointed out in the first section sets of solutions to a system of equations Φ in a free group F_{k} are equivalent to the set of all homomorphisms from the naturally associated group G(Φ) into F_{k} (if the system Φ is with coefficients, we look only at homomorphisms that send the coefficients to the appropriate elements in F_{k}). In studying all homomorphisms from G(Φ) into a free group F_{k}, we are not really recovering the algebraic structure of the group G(Φ) itself, but rather the algebraic structure of its residually free quotient.

Definition 7.1. Let G be a f.g. group. We denote by KF (G) the intersection of all the kernels of homomorphisms from G into a free group. We call RF (G) = G/KF (G) the residually free quotient of G.

Clearly, a residual free quotient is always a residually free group (see definition 4.5) and the residually free quotient of a residually free group H is the group H itself. Therefore, to understand the structure of residually free quotients of f.g groups, which is equivalent to the understanding of sets of solutions to equations in a free group, we need to study the algebraic structure of residually free groups. In this section we will use some of the arguments and results obtained in earlier sections on the structure of ω-residually free groups, to recover the structure of residually free groups.

Let RF be a f.g. freely-indecomposable residually free group. On the set of ordered couples {(τ, R)}, where R is an ω-residually free quotient of RF, and τ is an epimorphism τ : RF → R, we define an equivalence relation. We say that (R_{1}, τ_{1}) is equivalent to (R_{2}, τ_{2}) if there exists an isomorphism ν : R_{1} → R_{2} so that τ_{2} = ν ∘ τ_{1}. On the same set of ordered couples we also define a partial order. We say that (R_{1}, τ_{1}) > (R_{2}, τ_{2}) if R_{2} is a proper quotient of R_{1} and there exists some epimorphism λ : R_{1} → R_{2} so that τ_{2} = λ ∘ τ_{1}.

An algebraic variety over an algebraically closed field is a union of irreducible varieties. The following, which is the main result of this section, is the analogue of this statement for varieties of solutions over a free group.

Theorem 7.2. Let RF be a f.g. residually free group. Then there exists a (canonical) finite collection of ω-residually free quotients of RF: R_{1}, …, R_{ℓ} and for each i an epimorphism τ_{i} : RF → R_{i} with the following properties:

(i) for each homomorphism h : R → F_{k} there exists some index i (not necessarily unique!) and a homomorphism f : R_{i} → F_{k} so that h splits as: h = f ∘ τ_{i}.

(ii) if R is an ω-residually free quotient of RF, and τ is an epimorphism τ : RF → R, then there exists some index i and an epimorphism λ : R_{i} → R so that τ = λ ∘ τ_{i}.

(iii) the couples {(R_{i}, τ_{i})} represent distinct equivalence classes, and if i ≠ j then the couple (R_{i}, τ_{i}) can not be compared with (R_{j}, τ_{j}) in the partial order defined on these couples.

(iv) if R̂_{1}, … R̂_{u} and {τ̂_{j} : RF → R̂_{j}} is another collection of ω-residually free quotients of RF and epimorphisms from RF to the R̂_{i}’s that satisfy properties (i)-(iii) then u = ℓ and up to permutation the couple (R_{i}, τ_{i}) is equivalent to the couple (R̂_{i}, τ̂_{i}).

Proof: The collection of ordered couples {(R, τ)} where R is an ω-residually free quotient of RF and τ : RF → R is an epimorphism, has similar properties to the partial order defined on shortening quotients of an ω-residually free group in section 5.

Lemma 7.3. Let RF be a f.g. residually free group. Let (R_{1}, τ_{1}), (R_{2}, τ_{2}), (R_{3}, τ_{3}), … be a sequence of ω-residually free quotients of RF and suppose (R_{1}, τ_{1}) < (R_{2}, τ_{2}) < (R_{3}, τ_{3}) < … is an infinite properly increasing sequence. Then there exists an ω-residually free quotient R of RF and an epimorphism τ : RF → R so that (R, τ) > (R_{j}, τ_{j}) for every ω-residually free quotient (R_{j}, τ_{j}) in the increasing sequence.

Proof: identical with the proof of lemma 5.4.

□

Lemma 7.3 proves the existence of maximal elements with respect to the partial order on the set of ω-residually free quotients of the residually free group R. The next lemma shows that there are only finitely many equivalence classes of maximal elements in the set of ω-residually free quotients of RF.

Lemma 7.4. Let RF be a f.g. residually free group. The set of ordered couples {(R, τ)}, where R is an ω-residually free quotient of RF and τ : RF → R is an epimorphism, contains only finitely many equivalence classes of maximal elements with respect to its partial order.

Proof: identical with the proof of lemma 5.5.

□

Now, if (R_{1}, τ_{1}), …, (R_{k}, τ_{k}) are representatives for the distinct equivalence classes of maximal ω-residually free quotients of the residually free group RF, then (R_{1}, τ_{1}), …, (R_{k}, τ_{k}) satisfy the conclusion of theorem 7.2.

□

We will call the groups R_{1}, …, R_{k} together with the epimorphisms τ_{i} : RF → R_{i} that appear in the formulation of theorem 7.2, the (canonical) (maximal) ωresidually free groups associated with the f.g. residually free group RF. By theorem 7.2 these are canonically defined up to equivalence.

In section 5 we have associated a Makanin-Razborov diagram with each ωresidually free group. This diagram was canonically defined and encodes all homomorphisms from an ω-residually free group into free groups. Theorem 7.2 allows us to generalize the construction of the Makanin-Razborov diagram to residuallyfree groups. Let RF be a f.g. residually free group. We start with one vertex labeled RF and continue the diagram by adding an edge from this vertex to each of its associated maximal ω-residually free quotients, and from each of the maximal ω-residually free quotients we continue by adding its Makanin-Razborov diagram. By theorem 7.2 and the properties of the Makanin-Razborov diagram of ω-residually free groups (see proposition 5.6), each homomorphism from the residually free group RF into some free group F_{k} can be ”read” from the Makanin-Razborov diagram of RF.

In theorem 5.11 we have shown that a f.g. group is ω-residually free if and only if it admits a strict MR resolution. Theorem 7.2 allows us to get corresponding classification of residually free groups.

Claim 7.5. A f.g. group G is a residually free group if and only if G is a sub-direct product of a finite collection of ω-residually free groups.

Proof: Clearly, a sub-direct product of a finite collection of residually free groups is residually free, so one direction is obvious. The other direction of the claim follows from theorem 7.2, since a residually free group is a sub-direct product of its associated maximal ω-residually free quotients.

□

Remarks:

(i) Corollary 4.4 shows that ω-residually free groups are f.p. . However f.g. residually-free groups need not be f.p. . If F_{g} is a free group then F_{g} + F_{g} is residually free, so every subgroup of F_{g} + F_{g} is residually free, and F_{g} + F_{g} contains f.g. subgroups which are not f.p. .

(ii) There is no global bound for the length of a sequence of proper residuallyfree quotients of a residually-free group.

§8. Sets of Solutions to Equations in a Free Group

In the first section we have pointed out that the sets of solutions to a system of equations Φ in a free group is equivalent to the sets of homomorphisms from a corresponding f.p. group G(Φ) to a free group. If the system of equations is without coefficients, then the sets of homomorphisms from G(Φ) into a free group can be ”read” from the Makanin-Razborov diagram corresponding to G(Φ) as was shown in the previous section. If the system Φ is with coefficient one needs to modify the whole theory developed in the previous sections to the presence of prescribed coefficients. The rest of this section is devoted to this modification.

Let Φ be a finite system of equations defined over a free group F_{k} =< a_{1}, …, a_{k} >. Recall that with Φ it is natural to associate a f.p. group G(Φ). If the system Φ is defined by the coefficients a_{1}, …, a_{k}, the unknowns x_{1}, …, x_{n} and the equations:

w_{1}(a_{1}, …, a_{k},x_{1}, …, x_{n}) = 1
⋮
w_{s}(a_{1}, …, a_{k},x_{1}, …, x_{n}) = 1

we set the associated f.p. group G(Φ) to be:

G(Φ) = < a_{1}, …, a_{k}, x_{1}, …, x_{n} | w_{1}, …, w_{s} >

Clearly, every solution of the system Φ corresponds to a homomorphism h : G(Φ) → F_{k} for which h(a_{i}) = a_{i}, and every such homomorphism corresponds to a solution of the system Φ. Therefore, the study of sets of solutions to systems of equations in a free group is equivalent to the study of all homomorphisms from a fixed f.p. group G into a free group F_{k} for which a given prescribed set of elements in G is mapped to a fixed basis of the free group F_{k}.

For the rest of this section, we set G to be a f.g. group G =< g_{1}, …, g_{m} >, γ_{1}, …, γ_{k} ∈ G to be a prescribed set of elements in G, and F_{k} to be a free group with a fixed basis F_{k} =< a_{1}, …, a_{k} >. With these notation our main goal is to get a structure theory for understanding the set of all homomorphisms:

Hom((G, {γ_{i}}), (F_{k}, {a_{i}})) = { h | h : G → F_{k} , h(γ_{i}) = a_{i} }

which for brevity we will denote Hom(G, F_{k}). We set X to be the Cayley graph of F_{k} with respect to its given basis a_{1}, …, a_{k}. Given any homomorphism h ∈ Hom(G, F_{k}), G admits a natural action λ_{h} on X given by λ_{h}(g, x) = h(g)(x) for every g ∈ G and x ∈ X.

Let {h_{j}} ⊂ Hom(G, F_{k}) be a set of distinct homomorphisms from G to F_{k} satisfying the prescribed conditions. We set μ_{j} to be: μ_{j} = max_{1≤u≤m} d_{X}(id., h_{j}(g_{u})) (note that unlike what we did in section 1, here, due to the presence of coefficients, we do not compose with an inner automorphism of F_{k}). Since the homomorphisms in the sequence {h_{j}} ⊂ Hom(G, F_{k}) are distinct, 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 F_{k}, (X, id.), by μ_{j}. (X_{j}, x_{j}) is endowed with a left isometric action of our f.g. group G via the homomorphisms {h_{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 (Y, y_{0}) by passing to a Gromov-Hausdorff limit of a convergent subsequence (proposition 1.1).

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 restricted limit group. We will denote the restricted limit group by RL_{∞}, and the canonical quotient map by η : G → RL_{∞}. Note that since a restricted limit group is a limit group in the sense of section 1, all the algebraic properties of limit groups hold for restricted limit groups. Still, for the purpose of understanding the set of all restricted homomorphisms from G to the (fixed) free group F_{k} we will need to modify some of the algebraic objects associated in the previous sections with limit groups, to study restricted limit groups.

The abelian JSJ decomposition of a freely-indecomposable limit group ”encodes” all the possible splittings of such limit group with abelian edge groups. In studying restricted limit groups we will be interested only abelian splittings in which the subgroup < η(γ_{1}), …, η(γ_{k}) > is elliptic. The construction of the abelian JSJ decomposition of a limit group described in section 2, naturally generalizes to a restricted abelian JSJ decomposition of a restricted limit group.

Theorem 8.1 (cf. theorem 2.7). Suppose RL_{∞} is a restricted limit group which does not split to a non-trivial free decomposition in which the subgroup η(Γ) =< η(γ_{1}), …, η(γ_{k}) > is contained in one of the factors. Suppose that η(Γ) is a proper subgroup of RL_{∞}. Then there exists a reduced unfolded splitting of RL_{∞} with abelian edge groups, which we call an abelian restricted JSJ (Jaco-Shalen-Johannson) decomposition of RL_{∞} with the following properties:

(i) η(Γ) is elliptic in the restricted abelian JSJ decomposition.

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

(iii) A one edge abelian splitting RL_{∞} = D ∗_{A} E or RL_{∞} = D∗_{A} in which η(Γ) is elliptic which is hyperbolic in another such elementary abelian splitting is obtained from the restricted abelian JSJ decomposition of RL_{∞} by cutting a 2-orbifold corresponding to a CMQ subgroup of RL_{∞} along a weakly essential s.c.c..

(iv) Let Θ be a one edge splitting along an abelian subgroup A, RL_{∞} = D ∗_{A} E or RL_{∞} = D∗_{A} in which η(Γ) is elliptic, so that A is elliptic with respect to any other one edge abelian splitting of RL_{∞} in which η(Γ) is elliptic. Then Θ is obtained from the restricted JSJ decomposition of RL_{∞} by a sequence of collapsings, foldings, and conjugations.

(v) If JSJ_{1} is another restricted abelian JSJ decomposition of RL_{∞}, then JSJ_{1} is obtained from the restricted abelian JSJ decomposition by a sequence of slidings, conjugations and modifying boundary monomorphisms by conjuga-

tions (see section 1 of [Ri-Se2] for these notions)

From the canonical properties of the abelian JSJ decomposition of a limit group we were able to show in section 3 that a non-abelian, freely indecomposable limit group admits a principal cyclic splitting. The arguments used in proving theorem 3.2 naturally generalize to prove the existence of a (restricted) principal cyclic splitting of a restricted limit group.

Theorem 8.2. Let RL_{∞} be a restricted limit group which does not split to a nontrivial free product in which the subgroup η(Γ) is contained in one of the factors. Suppose that η(Γ) is a proper subgroup of RL_{∞}. Then there exists a principal cyclic splitting of RL_{∞} in which η(Γ) is elliptic.

The restricted abelian JSJ decomposition together with the existence of a restricted principal splitting, allow us to generalize the arguments of section 3

to construct the restricted cyclic JSJ decomposition of a restricted limit group.

Theorem 8.3 (cf. theorem 3.9). Let RL_{∞} be a restricted limit group which does not split to a non-trivial free product in which the subgroup η(Γ) is contained in one of the factors. Suppose that η(Γ) is a proper subgroup of RL_{∞}. Then there exists a reduced unfolded Z-splitting of RL_{∞}, which we call the restricted cyclic JSJ (Jaco-Shalen-Johannson) decomposition of RL_{∞} with the following properties:

(i) η(Γ) is elliptic in the restricted cyclic JSJ decomposition. (ii) Every (restricted) canonical maximal QH subgroup (CMQ) of RL_{∞} is con-

jugate to a vertex group in the restricted cyclic JSJ decomposition. Every restricted QH subgroup of RL_{∞} can be conjugated into one of the CMQ subgroups of RL_{∞}. Every vertex group in the restricted cyclic JSJ decomposition which is not a CMQ subgroup of RL_{∞} is elliptic in any Z-splitting of RL_{∞} in which η(Γ) is elliptic.

(iii) A one edge Z-splitting RL_{∞} = D ∗_{Z} E or RL_{∞} = D∗_{Z} in which η(Γ) is elliptic which is hyperbolic in another such elementary Z-splitting is obtained from the restricted cyclic JSJ decomposition of RL_{∞} by cutting a 2-orbifold corresponding to a (restricted) CMQ subgroup of RL_{∞} along a weakly essential s.c.c..

(iv) Let Θ be a one edge Z-splitting RL_{∞} = D ∗_{Z} E or RL_{∞} = D∗_{Z} in which η(Γ) is elliptic, so that Z is elliptic with respect to any other such one edge Z-splitting of RL_{∞}. Then Θ is obtained from the restricted cyclic JSJ decomposition of RL_{∞} by a sequence of collapsings, foldings, and conjugations.

(v) Let Λ be a general Z-splitting of RL_{∞} in which η(Γ) is elliptic. There exists a Z-splitting Λ_{1} obtained from the restricted cyclic JSJ decomposition by splitting the CMQ subgroups along weakly essential s.c.c. on their corresponding 2-orbifolds, so that there exists a RL_{∞}-equivariant simplicial map between a subdivision of the Bass-Serre tree T_{Λ_{1}} to T_{Λ}.

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

(vii) The restricted cyclic JSJ decomposition of RL_{∞} is non-trivial. Furthermore, the restricted cyclic JSJ decomposition can be collapsed to give a restricted principal cyclic splitting of RL_{∞}.

Since a restricted limit group is in particular a limit group, it is finitely presented (in fact, it is also possible to modify the construction of the analysis lattice to the restricted setup). Like in the case of limit groups, the finite presentability of restricted limit groups also shows that restricted limit groups are restricted ωresidually free groups. i.e., that for every finite set of elements in a restricted limit group RL_{∞} there exists a restricted homomorphism h : RL_{∞} → F_{k} that maps the elements in this finite set to distinct elements in F_{k}. In section 5 we have used the canonical cyclic JSJ decomposition of a limit group to construct its canonical Makanin-Razborov diagram. We continue by modifying the notions and arguments appear in section 5 to construct the restricted Makanin-Razborov diagram of a restricted limit group.

Definition 8.4. Let RL_{∞} be a restricted limit group which does not split to a nontrivial free product in which the subgroup η(Γ) is contained in one of the factors. Suppose that η(Γ) is a proper subgroup of RL_{∞}. We define the restricted modular group RMod(RL_{∞}) to be the subgroup of Aut(R) generated by the following families of automorphisms of R:

(i) Dehn twists along edges of the restricted cyclic JSJ decomposition of RL_{∞}. The Dehn twists are assumed to fix (elementwise) the vertex stabilized by η(Γ).

(ii) Dehn twists along essential s.c.c. in CMQ (canonical maximal quadratically hanging) vertex groups in the restricted cyclic JSJ decomposition of RL_{∞}. Again, these Dehn twists are assume to fix (elementwise) the vertex stabilized by η(Γ).

(iii) Let A be an abelian vertex group in the restricted cyclic JSJ decomposition of RL_{∞}. Let A_{1} < A be the subgroup generated by all edge groups connected to the vertex stabilized by A in the cyclic JSJ decomposition of R. Every automorphism of A that fixes A_{1} (elementwise) can be naturally extended to an automorphism of the ambient limit group RL_{∞} that fixes the vertex stabilized by η(Γ). We call these generalized Dehn twists and they form the third family of automorphisms that generate RMod(R).

Given a sequence of homomorphisms of a limit group into a free group, we used the modular group of automorphisms of that limit group to modify the sequence of homomorphisms and obtain a shortening quotient of the limit group we started with. Given a restricted limit group, and a sequence of homomorphisms of that restricted limit group into F_{k}, we may use the restricted modular group of automorphisms of that restricted limit group to modify the sequence of homomorphisms and obtain a restricted shortening quotient of a restricted limit group. By the same argument used to prove claim 5.3 a restricted shortening quotient of a restricted limit group is a proper quotient of it.

On the set of restricted shortening quotients of a restricted limit group we can naturally define a partial order and an equivalence relation, similar to the ones defined in section 5 for shortening quotients of limit groups. By the same argument used to prove lemma 5.4 the set of restricted shortening quotients of a restricted limit group contains maximal elements with respect to the partial order, and by the same argument used to prove lemma 5.5 there are only finitely many equivalence classes of maximal restricted shortening quotients of a restricted limit group. Like in proposition 5.6 and using an identical argument, for every restricted homomorphism RL_{∞} → F_{k} there exists some index 1 ≤ i ≤ k (not necessarily unique!) and a restricted modular automorphism φ_{h} ∈ RMod(R) so that h ∘ φ_{h} splits through the maximal restricted shortening quotient RM_{i}. i.e., h ∘ φ_{h} = h_{RM_{i}} ∘ η_{i} where h_{RM_{i}} : RM_{i} → F_{k} is a restricted homomorphism.

These basic facts concerning restricted limit groups and their restricted shortening quotients allow us to present the main goal of this section, the (canonical) restricted Makanin-Razborov diagram associated with a restricted limit group (restricted ω-residually free group). The restricted Makanin-Razborov diagram ”encodes” all possible restricted homomorphisms from a limit group into the (fixed) free group F_{k}, and like for limit groups some of its properties can be stated as a criteria for a general f.g. group to be a restricted limit group.

Let RL_{∞} be a restricted limit group (a restricted ω-residually free group). By definition in RL_{∞} there exists a (distinguished) finite set of elements < γ_{1}, …, γ_{k} > so that for any finite set U of elements in RL_{∞} there exists a (restricted) homomorphism h : RL_{∞} → F_{k} that sends γ_{i} to a_{i}, the i-th basis element of F_{k}, and sends the elements of U to distinct elements of F_{k}. Let Γ =< γ_{1}, …, γ_{k} >. Let RL_{∞} = RL_{1}∗… RL_{ℓ}∗F_{g_{1}} be a factorization of R, where Γ < RL_{1}, RL_{1} can not be written as a free product in which Γ is contained in one of the factors, each of the RL_{i}’s for 2 ≤ i ≤ ℓ is a freely-indecomposable non-cyclic subgroup of RL and F_{g_{1}} is a free group. It follows from Grushko’s theorem that such a free decomposition of RL_{∞} is canonical. By an analogue of lemma 5.4 to the restricted case, the set of restricted shortening quotients of the restricted limit group RL_{1} contain maximal elements (with respect to the partial order defined above) and by an analogue of lemma 5.5 to the restricted case there are only finitely many equivalence classes of maximal restricted shortening quotients of RL_{1}. Let RM_{1}, …, RM_{s} be a collection of representatives of equivalence classes of maximal restricted shortening quotients of RL_{1}, and let η_{j} : RL_{1} → M_{j} be the canonical projection maps.

We define the restricted Makanin-Razborov diagram of the restricted limit group RL_{∞} iteratively. We start by factoring RL_{∞} as above. From each of the factors RL_{2}, …, RL_{ℓ} we continue by adjoining its Makanin-Razborov diagram presented in section 5. From RL_{1} we continue along s edges going from RL_{1} to each of its maximal restricted quotients RM_{1}, …, RM_{s}. To each such directed edge we associate the canonical projection η_{j}. We proceed iteratively. Since a restricted shortening quotient of a restricted limit group is a proper quotient of it, the construction terminates. Each terminal vertex is either a free group (as in the Makanin-Razborov diagram presented in section 5) or it is the (image of the )”distinguished” free groups Γ =< γ_{1}, …, γ_{k} >. At least one of the terminal vertices in a restricted Makanin-Razborov diagram must be labeled with an image of the ”distinguished” subgroup Γ. By construction, up to the equivalence relation of restricted shortening quotients, the restricted Makanin-Razborov diagram of a restricted limit group is canonical. By an analogue of proposition 5.6 to the restricted case, all the restricted homomorphisms from a restricted limit group RL_{∞} into the free group F_{k} are encoded by the canonical restricted Makanin-Razborov diagram. i.e., they are all given by compositions of (restricted) modular automorphisms of the (restricted) limit groups in the diagram with the canonical maps from the (restricted) limit groups into their maximal (restricted) shortening quotients and finally with either the fixed map from (an image of) the distinguished subgroup Γ onto F_{k}, or general homomorphisms (”substitutions”) of the terminal (non-distinguished) free groups appear in the diagram into the target free group F_{k}.

The (canonical) restricted Makanin-Razborov diagram associated with a restricted limit group, encodes all the restricted homomorphsims from that restricted limit group into a free group F_{k}. Like in the non-restricted case (definitions 5.7 and 5.8) using the restricted Makanin-Razborov diagram we can define restricted Makanin-Razborov resolutions and restricted strict Makanin-Razborov resolutions of a restricted limit group. Like in the non-restricted case (theorem 5.11) the existence of a restricted strict MR resolution for a f.g. group G with a distinguished subgroup Γ =< γ_{1}, …, γ_{k} > is a criteria for G to be a restricted limit group (restricted ω-residually free group). The proofs are all direct modifications of the ones given in section 5 in the non-restricted case.

Like restricted limit groups (restricted ω-residually free groups) we may define in a similar way restricted residually free groups. The study of sets of solutions to equations with coefficients is naturally equivalent to study of all restricted homomorphisms from a f.g. restricted residually free group into the free group generated by the coefficients. For studying this collection of restricted homomorphisms we have an analogue of theorem 7.2. The proof is a direct modification.

Theorem 8.5. Let RF be a f.g. restricted residually free group. Then there exists a (canonical) finite collection of restricted ω-residually free quotients of RF: R_{1}, …, R_{ℓ} and for each i an epimorphism τ_{i} : RF → R_{i} with the following properties:

(i) for each restricted homomorphism h : R → F_{k} there exists some index i (not necessarily unique!) and a restricted homomorphism f : R_{i} → F_{k} so that h splits as: h = f ∘ τ_{i}.

(ii) if R is a restricted ω-residually free quotient of RF, and τ is an epimorphism τ : RF → R, then there exists some index i and an epimorphism λ : R_{i} → R so that τ = λ ∘ τ_{i}.

(iii) the couples {(R_{i}, τ_{i})} represent distinct equivalence classes, and if i ≠ j then the couple (R_{i}, τ_{i}) can not be compared with (R_{j}, τ_{j}) in the partial order defined on these couples.

(iv) if R̂_{1}, … R̂_{u} and {τ̂_{j} : RF → R̂_{j}} is another collection of restricted ωresidually free quotients of RF and epimorphisms from RF to the R̂_{i}’s that satisfy properties (i)-(iii) then u = ℓ and up to permutation the couple (R_{i}, τ_{i}) is equivalent to the couple (R̂_{i}, τ̂_{i}).

We have already modified the construction of the Makanin-Razborov diagram of a ω-residually free group to the restricted case. Having such diagram for restricted ω-residually free group, theorem 8.5 allows us to modify the construction of the Makanin-Razborov diagram associated with a residually free group presented in section 7 to the restricted case. This restricted Makanin-Razborov diagram of restricted residually free groups finally concludes our study of the structure of sets of solutions to systems of equations with coefficients.

§9. Configuration Limit Groups

The Makanin-Razborov resolutions associated with a limit group gives a complete description of all the homomorphisms from a limit group into a free group. However, a basic difficulty that arises in applying the structure given by the canonical set of Makanin-Razborov resolutions is the possibility of homomorphisms that factor through several resolutions and not through a unique one. In some cases the difficulties caused by this lack of uniqueness can be tackled using configuration limit groups. In particular, (graded) configuration limit groups are essential in analyzing parametric families of limit groups, which is an essential part in our approach to the analysis of elementary predicates defined over a free group. These applications of configuration limit groups will appear in the next papers in this sequence. For brevity, we call a homomorphism from a (restricted) limit group into a given free group F_{k}, a specialization of the (restricted) limit group.

Definition 9.1. Let Rlim(y, a) be a (restricted) limit group, and let Res(y, a) be a resolution of the limit group Rlim(y, a). We say that the set of specializations (y_{0}, a) of the (restricted) limit group Rlim(y, a) that factors through the resolution Res(y, a) is the modular block associated with the resolution Res(y, a). By the properties of the Makanin-Razborov diagram the entire set of specializations of the (restricted) limit group Rlim(y, a) is a (canonical) union of the modular blocks associated with the Makanin-Razborov resolutions Res_{1}(y, a), …, Res_{r}(y, a) of the (restricted) limit group Rlim(y, a).

To analyze the collection of specializations of a limit group that factor through a given set of resolutions, i.e., to analyze the intersection of given modular blocks, we define configuration limit groups.

Definition 9.2. Let Rlim(y, a) be a (restricted) limit group, and let Res_{1}(y, a), …, Res_{r}(y, a) be resolutions of Rlim(y, a). Suppose that for each index i, 1 ≤ i ≤ r, the chain of (restricted) limit groups associated with the resolution Res_{i}(y, a) is:

Rlim(y, a) → Rlim(z_{1}^{i}, a) → Rlim(z_{2}^{i}, a) → … → Rlim(z_{ℓ_{i}}^{i}, a).

To analyze the collection of all specializations (y_{0}, a) of the (restricted) limit group Rlim(y, a) that factor through all the resolutions Res_{1}(y, a), …, Res_{r}(y, a) we look at the set of specializations:

(y_{0}, z_{1}^{1}, …, z_{ℓ_{1}}^{1}, z_{1}^{2}, …, z_{ℓ_{2}}^{2}, …, z_{1}^{r}, …, z_{ℓ_{r}}^{r}, a)

where (y_{0}, a) factors through the resolutions Res_{1}(y, a), …, Res_{r}(y, a) and for each index i, 1 ≤ i ≤ r, z_{1}^{i}, …, z_{ℓ_{i}}^{i} are the specializations of the (restricted) limit groups Rlim(z_{1}^{i}, a), …, Rlim(z_{ℓ_{i}}^{i}) obtained by factoring (y_{0}, a) through the resolution Res_{i}(y, a).

By the same argument used to prove theorem 7.2, with the collection of specializations:

(y_{0}, z_{1}^{1}, …, z_{ℓ_{1}}^{1}, z_{1}^{2}, …, z_{ℓ_{2}}^{2}, …, z_{1}^{r}, …, z_{ℓ_{r}}^{r}, a)

defined above, we can naturally associate a canonical (finite) set of limit groups:

Conf_{1}(Rlim)(y, z_{1}^{1}, …, z_{ℓ_{r}}^{r}, a), …, Conf_{s}(Rlim)(y, z_{1}^{1}, …, z_{ℓ_{r}}^{r}, a)

which we call configuration limit groups.

The role of (graded) configuration limit groups in analyzing (graded) limit groups will become clearer in our next papers in this sequence.

§10. Graded Limit Groups

In the previous sections we have analyzed the structure of sets of solutions to systems of equations in a free group by studying the algebraic structure of limit groups which turned out to be ω-residually free groups. To solve the elementary theory of free groups, and, in particular, to study the structure of sets defined by elementary predicates (elementary sets), we will need to study the structure of sets of solutions to systems of equations with parameters, i.e., we will examine how the (restricted) Makanin-Razborov diagrams and resolutions vary with a change of the values of the defining parameters.

With a finite system of equations with parameters Φ over a free group F_{k} =< a_{1}, …, a_{k} > it is natural to associate a f.p. group G(Φ). If the system Φ is defined by the coefficients a_{1}, …, a_{k}, the parameters p_{1}, …, p_{u}, the unknowns x_{1}, …, x_{n} and the equations:

w_{1}(a_{1}, …, a_{k},p_{1}, …, p_{u}, x_{1}, …, x_{n}) = 1
⋮
w_{s}(a_{1}, …, a_{k},p_{1}, …, p_{u}, x_{1}, …, x_{n}) = 1

we set the associated f.p. group G(Φ) to be:

G(Φ) = < a_{1}, …, a_{k}, p_{1}, …, p_{u}, x_{1}, …, x_{n} | w_{1}, …, w_{s} >

Clearly, every solution of the system Φ corresponds to a homomorphism h : G(Φ) → F_{k} for which h(a_{i}) = a_{i}, and every such homomorphism corresponds to a solution of the system Φ. Therefore, the study of sets of solutions to systems of equations in a free group is equivalent to the study of all homomorphisms from a fixed f.p. group G into a free group F_{k} for which a given prescribed set of elements in G is mapped to a fixed basis of the free group F_{k}.

In the previous sections we studied the global set of (restricted) homomorphisms from a f.g. group G into a free group F_{k}, and later showed the existence of effective tools which enable an effective computation of the structure of this global set. In the first sections of this paper we will analyze the variation of this structure with a change of the defining parameters. Our whole study of the global set of restricted homomorphisms was based on understanding the algebraic structure of limit groups (ω-residually free groups). To analyze the variation in this structure with a change of the parameters we will need to look at a special class of limit groups which we call graded limit groups.

We set G =< x_{1}, …, x_{k}, p_{1}, …, p_{u}, a_{1}, …, a_{k} > to be a f.g. group. For brevity we will denote this (fixed) generating set by G =< g_{1}, …, g_{m} >, and F_{k} to be a free group with a fixed basis F_{k} =< a_{1}, …, a_{k} >. With this notation our goal is to get a structure theory for understanding the set of all homomorphisms:

Hom((G, {p_{j}}, {a_{i}}), (F_{k}, {a_{i}})) = { h | h : G → F_{k} , h(a_{i}) = a_{i} }

with a change in the values of the parameters {p_{j}}. We set X to be the Cayley graph of F_{k} with respect to its given basis a_{1}, …, a_{k}. Given any homomorphism h ∈ Hom(G, F_{k}), G admits a natural action λ_{h} on X given by λ_{h}(g, x) = h(g)(x) for every g ∈ G and x ∈ X.

Definition 10.1. Let G be a f.g. group and let h_{n} : G(x, p, a) → F_{k} be a sequence of homomorphisms. If {λ_{h_{n}}}, a sequence of actions of G on X, the Cayley graph of F_{k}, that corresponds to the sequence of homomorphisms {h_{n}}, converges in the Gromov-Haussdorff topology, we say that the sequence {h_{n}} converges. We call the obtained limit group, a graded limit group.

A graded limit group is in particular a limit group, so every f.g. graded limit group is f.p. and every f.g. graded limit group is ω-residually free by theorem 4.6. To construct the (canonical) graded Makanin-Razborov diagram of a graded limit group which is the fundamental tool in our analysis of the variation of sets of solutions to systems of equations with parameters, we need to study the algebraic structure of graded limit groups ”relative” to their grading. To do that we need to construct the graded abelian JSJ decomposition of a graded limit group, and the graded analysis lattice of a graded limit group. These constructions are all generalizations of their restricted analogues presented in section 8.

For the rest of this section let G(x, p, a) be a f.g. group, let {h_{m} : G(x, p, a) → F_{k}} be a convergent graded sequence of homomorphisms, and let Glim_{∞}(x, p, a) be the corresponding graded limit group. We set η : G(x, p, a) → Glim_{∞}(x, p, a) to be the canonical epimorphism and AP < Glim_{∞}(x, p, a) to be the subgroup: AP =< η(p_{1}), …, η(p_{u}), η(a_{1}), …, η(a_{k}) >. The abelian JSJ decomposition of a freely-indecomposable limit group ”encodes” all the possible splittings of such limit group with abelian edge groups. In studying graded limit groups we will be interested only in abelian splittings in which the subgroup AP is elliptic. The construction of the abelian JSJ decomposition of a limit group described in section 2, naturally generalizes to a graded abelian JSJ decomposition of a graded limit group.

Theorem 10.2 (cf. 8.1). Suppose Glim_{∞}(x, p, a) is a graded limit group which does not split to a non-trivial free decomposition in which the subgroup AP is contained in one of the factors. Then there exists a (relatively) reduced unfolded (perhaps trivial) splitting of Glim_{∞}(x, p, a) with abelian edge groups, which we call a graded abelian JSJ (Jaco-Shalen-Johannson) decomposition of Glim_{∞}(x, p, a) with the following properties:

(i) AP is elliptic in the graded abelian JSJ decomposition. (ii) Every (graded) canonical maximal QH subgroup (CMQ) of Glim_{∞}(x, p, a) is

conjugate to a vertex group in the graded JSJ decomposition. Every (graded) QH subgroup of Glim_{∞}(x, p, a) can be conjugated into one of the CMQ subgroups of Glim_{∞}(x, p, a). Every vertex group in the graded JSJ decomposition which is not a CMQ subgroup of Glim_{∞}(x, p, a) is elliptic in any abelian splitting of Glim_{∞}(x, p, a) under consideration (i.e., in one in which AP is elliptic).

(iii) A one edge (graded) abelian splitting Glim_{∞}(x, p, a) = D∗_{A}E or Glim_{∞}(x, p, a) = D∗_{A} in which AP is elliptic which is hyperbolic in another such elementary abelian splitting is obtained from the graded abelian JSJ decomposition of Glim_{∞}(x, p, a) by cutting a 2-orbifold corresponding to a (graded) CMQ subgroup of Glim_{∞}(x, p, a) along a weakly essential s.c.c..

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

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

§11. Graded Makanin-Razborov Resolutions and Diagram

In section 5 we have used the canonical cyclic JSJ decomposition of a limit group to construct its canonical Makanin-Razborov diagram. In section 8 we modified this construction to obtain the restricted Makanin-Razborov diagram for analyzing sets of solutions to equations with coefficients. To understand the variation of the restricted Makanin-Razborov diagram with a change of the defining parameters we need to further modify the construction of the Makanin-Razborov diagram to obtain the graded Makanin-Razborov diagram of a graded limit group.

Definition 11.1. Let Glim_{∞}(x, p, a) be a graded limit group which does not split to a non-trivial free product in which the subgroup AP =< p_{1}, …, p_{u}, a_{1}, …, a_{k} > is contained in one of the factors. Suppose that the principal graded abelian JSJ decomposition of Glim_{∞}(x, p, a) is non-trivial. We define the graded modular group GMod(Glim_{∞}(x, p, a)) to be the subgroup of Aut(Glim_{∞}(x, p, a)) generated by the following families of automorphisms of Glim_{∞}(x, p, a):

(i) Dehn twists along edges of the principal graded abelian JSJ decomposition of Glim_{∞}(x, p, a). The Dehn twists are assumed to fix (elementwise) the vertex stabilized by AP.

(ii) Dehn twists along essential s.c.c. in (graded) CMQ (canonical maximal quadratically hanging) vertex groups in the principal graded abelian JSJ decomposition of Glim_{∞}(x, p, a). Again, these Dehn twists are assume to fix (elementwise) the vertex stabilized by AP.

(iii) Let A be an abelian vertex group in the principal graded abelian JSJ decomposition of Glim_{∞}(x, p, a). Let A_{1} < A be the subgroup generated by all edge groups connected to the vertex stabilized by A in the principal graded abelian JSJ decomposition of Glim_{∞}(x, p, a). Every automorphism of A that fixes A_{1} (elementwise) can be naturally extended to an automorphism of the ambient limit group Glim_{∞}(x, p, a) that fixes the vertex stabilized by AP. We call these generalized Dehn twists and they form the third family of automorphisms that generate GMod(Glim_{∞}(x, p, a)).

We say that a homomorphism h : Glim(x, p, a) → F_{k} is in the graded modular class of the homomorphism ĥ : Glim(x, p, a) → F_{k} if ĥh ∘ φ, where φ is a graded modular automorphism of Glim(x, p, a), i.e., φ ∈ GMod(Glim(x, p, a)). Clearly, a graded modular class is an equivalence class of homomorphisms from the graded modular group Glim(x, p, a) to the free group F_{k}.

Let Glim(x, p, a) be a graded limit group that admits a non-trivial graded abelian JSJ decomposition. Once we fix a generating set for the graded limit group Glim(x, p, a), given a homomorphism h : Glim(x, p, a) → F_{k} we can choose the shortest homomorphisms in the graded modular class of h. A graded limit group obtained from a convergent sequence of homomorphisms h : Glim(x, p, a) → F_{k} which are the shortest in their graded modular class, is called a graded shortening quotient of the graded limit group Glim(x, p, a).

On the set of graded shortening quotients of a graded limit group we can naturally define a partial order and an equivalence relation, similar to the ones defined in section 5 for shortening quotients of limit groups. By the same argument used to prove lemma 5.4 the set of graded shortening quotients of a graded limit group contains maximal elements with respect to the partial order, and by the same argument used to prove lemma 5.5 there are only finitely many equivalence classes of maximal graded shortening quotients of a graded limit group.

So far we have modified the construction of maximal shortening quotients presented in section 5 to the graded setup. However, graded shortening quotients of a graded limit group need not be proper quotients of it. Furthermore, to get graded shortening quotients we naturally require that the graded abelian JSJ decomposition is non-trivial. Unlike (ungraded) limit groups, to understand the variation of the set of restricted homomorphisms from a graded limit group to F_{k} with a change of the defining parameters, we will need to study the structure of graded limit groups with a trivial principal graded abelian JSJ decomposition.

Definition 11.2. Let Glim(x, p, a) be a graded limit group that does not split into a free product in which AP can be conjugated into one of the factors. If Glim(x, p, a) has a trivial graded abelian JSJ decomposition it is called rigid graded limit group. If Glim(x, p, a) has a non-trivial graded abelian JSJ decomposition, and a (unique) maximal graded shortening quotient GMSQ(x, p, a) that is isomorphic to Glim(x, p, a), Glim(x, p, a) is called solid graded limit group.

To study rigid and solid graded limit groups we need to introduce the notion of flexible graded limit groups.

Definition 11.3. Let Glim(x, p, a) be either a rigid or a solid graded limit group. A sequence of homomorphisms {h_{m} : Glim(x, p, a) → F_{k}} is called flexible graded sequence if one of the following holds:

(i) each homomorphism h_{m} factors as h_{m} = ν_{m}∘τ_{m}, where τ_{m} : Glim(x, p, a) → F_{k}∗ < v > and τ_{m} is an epimorphism that maps the subgroup AP onto the factor F_{k}, and ν_{m} : F_{k}∗ < v >→ F_{k}. Furthermore, τ_{m} can not be shortened (in F_{k}∗ < v >) by an element from the graded modular group GMod(Glim(x, p, a)).

(ii) each homomorphism h_{m} does not factor through a free product in which the subgroup AP is mapped to a factor, and can not be shortened by an element from the graded modular group GMod(Glim_{∞}(x, p, a)). In addition, for each index m:

max_{g∈B_{m}} d_{X}(h_{m}(g), id.) > 2^{m} · (1 + max_{1≤j≤u} d_{X}(h_{m}(p_{j}), id.))

where B_{m} is the ball of radius m in the Cayley graph of Glim(x, p, a). A graded limit group which is the limit of a flexible graded sequence is called a

flexible graded quotient of the rigid or solid graded limit group Glim(x, p, a).

Lemma 11.4. Let F lxGlim(x, p, a) be a flexible graded quotient of the rigid or solid graded limit group Glim(x, p, a). Then:

(i) F lxGlim(x, p, a) is not a rigid graded limit group.

(ii) F lxGlim(x, p, a) is a proper quotient of Glim(x, p, a).

Proof: If F lxGlim(x, p, a) splits into a free product in which AP can be conjugated into one of the factors, then F lxGlim(x, p, a) is not rigid, and it can not be isomorphic to Glim(x, p, a). Hence, we may assume that F lxGlim(x, p, a) does not split into a free product in which AP can be conjugated into one of the factors. From the flexible graded sequence of homomorphisms F lxGlim(x, p, a) is obtained, one gets a stable action of F lxGlim(x, p, a) on a real tree Y (see section 1). Since the sequence of graded homomorphisms is flexible, AP fixes a point in Y. By (([Se3],3.1), see theorem 1.5) F lxGlim(x, p, a) admits a (non-trivial) graph of groups Λ from its action on the real tree Y. By that same theorem if the action of F lxGlim(x, p, a) on Y contains an IET component, then F lxGlim(x, p, a) admits a graded abelian splitting. If the action contains an axial component, F lxGlim(x, p, a) inherits a graded abelian splitting and if the stabilizer of some (non-degenerate) segment in Y is non-trivial, it is maximal abelian by lemma 1.3, so F lxGlim(x, p, a) splits over a maximal abelian subgroup, and by proposition 10.4 F lxGlim(x, p, a) admits a graded abelian splitting. Therefore, in all cases F lxGlim(x, p, a) admits a (non-trivial) graded abelian splitting, so the graded abelian JSJ decomposition of F lxGlim(x, p, a) is non-trivial, and we get part (i) of the lemma.

If Glim(x, p, a) is rigid it has a trivial graded abelian JSJ decomposition. Hence, by part (i) F lxGlim(x, p, a) is a proper quotient of it. If Glim(x, p, a) is solid and F lxGlim(x, p, a) is isomorphic to Glim(x, p, a), then for large enough m, it is possible to shorten the homomorphisms h_{m} : Glim(x, p, a) → F_{k} or the homomorphism τ_{m} : Glim(x, p, a) → F_{k}∗ < v > by pre-composing with elements of the graded modular group GMod(Glim(x, p, a)), which contradicts the properties of homomorphisms in a flexible sequence. Hence, a flexible graded quotient is a proper quotient of a graded limit group.

□

Let Glim(x, p, a) be a rigid or solid graded limit group. On the set of flexible graded quotients of Glim(x, p, a) we can naturally define a partial order and an equivalence relation, similar to the ones defined on graded limit groups. By the same argument used to prove lemma 5.4, the set of flexible graded quotients of Glim(x, p, a) contains maximal elements with respect to the partial order, and by the same argument used to prove lemma 5.5 there are only finitely many equivalence classes of maximal flexible graded quotients of Glim(x, p, a). For the sequel we will need the following definitions associated with rigid and solid graded limit groups and their associated maximal flexible limit quotients.

Definition 11.5. Let Rgd(x, p, a) be a rigid limit group and let F lx_{1}(x, p, a), …, F lx_{v}(x, p, a) be the maximal flexible graded quotients of it. A homomorphism h : Rgd(x, p, a) → F_{k} that does not factor through any of the maximal graded flexible quotients F lx_{1}(x, p, a), …, F lx_{v}(x, p, a) of Rgd(x, p, a) is called a rigid homomorphism (solution)of the rigid graded limit group Rgd(x, p, a). A homomorphism that does factor through one of the maximal flexible quotients is called a flexible homomorphism (solution).

Definition 11.6. Let Sld(x, p, a) be a solid graded limit group and let F lx_{1}(x, p, a), …, F lx_{v}(x, p, a) be the maximal flexible quotients of it. A homomorphism h : Sld(x, p, a) → F_{k} for which h = h′∘φ where h′ factors through one of the maximal graded flexible quotients of Sld(x, p, a), and φ is a graded modular automorphism of Sld(x, p, a), is called a flexible homomorphism (solution) of the solid graded limit group Sld(x, p, a). Note that every homomorphism h : Sld(x, p, a) → F_{k} that factors through a free product of the form F_{k}∗ < v > so that AP is mapped into F_{k}, is flexible. A non-flexible homomorphism h : Sld(x, p, a) → F_{k} is called a solid homomorphism (solution) of the solid graded limit group Sld(x, p, a).

Flexible quotients of rigid graded limit groups and flexible quotients of solid graded limit groups, contain all the ”generic infinite families” of specializations of these graded limit groups. Rigid solutions of rigid graded limit groups are the exceptional single solutions, and solid solutions of solid graded limit groups are the exceptional families of solutions.

Proposition 11.7. Let Rgd(x, p, a) be a rigid graded limit group, let Sld(x, p, a) be a solid graded limit group, and let p_{0} be a specialization of the defining parameters p. Then:

(i) there are at most finitely many rigid solutions: h : Rgd(x, p, a) → F_{k} for which h(p) = p_{0}.

(ii) up to pre-composing with a graded modular automorphism of the solid graded limit group Sld(x, p, a) there are at most finitely many solid homomorphisms: h : Sld(x, p, a) → F_{k} for which h(p) = p_{0}.

Proof: Suppose that for some specialization p_{0} of the defining parameters p there are infinitely many rigid homomorphisms of Rgd(x, p, a). From this infinite set of homomorphisms it is possible to extract a flexible subsequence, from which it is possible to extract a convergent flexible subsequence of homomorphisms. Now, this last flexible sequence converges into a flexible graded quotient of Rgd(x, p, a). Hence, all but at most finite of the rigid homomorphisms of the convergent subsequence factors through a flexible graded quotient of Rgd(x, p, a), a contradiction to their rigidity, and we get part (i) of the proposition. Part (ii) follows by the same argument starting with an infinite family of solid homomorphisms that are the shortest possible under the action of the graded modular group GMod(Sld(x, p, a)).

□

We will call the (ungraded) Makanin-Razborov diagram of a graded limit group obtained using the (ungraded) abelian JSJ decompositions of the various limit groups that appear along the various resolutions, the ungraded Makanin-Razborov diagram. We call each resolution of the ungraded Makanin-Razborov diagram of a graded limit group, an ungraded resolution. The above basic facts concerning graded limit groups and their graded shortening quotients and graded flexible quotients allow us to present the main goal of this section, the (canonical) graded Makanin-Razborov diagram associated with a graded limit group. The graded Makanin-Razborov diagram ”encodes” all possible homomorphisms from a graded limit group into the (fixed) free group F_{k} in a form ”compatible” with the parametric description of the set of solutions.

Let Glim(x, p, a) be a graded limit group. Let Glim(x, p, a) = Glim_{1}∗… Glim_{ℓ}∗ F_{g_{1}} be a factorization of Glim(x, p, a), where AP < Glim_{1}, Glim_{1} can not be written as a free product in which AP is contained in one of the factors, each of the Glim_{i}’s for 2 ≤ i ≤ ℓ is a freely-indecomposable non-cyclic subgroup of Glim(x, p, a) and F_{g_{1}} is a free group. It follows from Grushko’s theorem that such a free decomposition of Glim(x, p, a) is canonical.

Suppose first that Glim_{1} is not rigid or solid. By claim 10.2 the set of graded shortening quotients of the graded limit group Glim_{1} contains maximal elements (with respect to the partial order defined above) and by an analogue of lemma 5.5 to the graded case there are only finitely many equivalence classes of maximal graded shortening quotients of Glim_{1}. Since Glim_{1} is not a solid graded limit group each maximal graded shortening quotient of it is a proper quotient. Let GM_{1}, …, GM_{s} be a collection of representatives of equivalence classes of maximal graded shortening quotients of Glim_{1}, and let η_{j} : Glim_{1} → GM_{j} be the canonical projection maps. Now, suppose Glim_{1} is rigid or solid. In this case, Glim_{1} has finitely many equivalence classes of maximal flexible graded quotients. Let F lxGlim_{1}, …, F lxGlim_{v} be a collection of representatives of equivalence classes of maximal flexible graded quotients of Glim_{1}, and let ν_{j} : Glim_{1} → F lxGlim_{j} be the canonical projection maps.

We define the graded Makanin-Razborov diagram of the graded limit group Glim(x, p, a) iteratively. We start by factoring Glim(x, p, a) as above. From each of the factors Glim_{2}, …, Glim_{ℓ} we continue by adjoining its (ungraded) Makanin-Razborov diagram. If Glim_{1} is not rigid we continue along s edges going from Glim_{1} to each of its maximal graded shortening quotients GM_{1}, …, GM_{s}. To each such directed edge we associate the canonical projection η_{j}.

If Glim_{1} is rigid or solid we continue along v edges going from Glim_{1} to each of its maximal flexible graded quotients F lxGlim_{1}, …, F lxGlim_{v}. To each such directed edge we associate the canonical projection ν_{j}.

We proceed iteratively. Since a graded shortening quotient of a non-solid graded limit group, and a flexible shortening quotient of a solid or rigid graded limit groups are proper quotients of the graded limit group, the construction terminates by proposition 5.1. Each terminal vertex is either a free group (as in the Makanin-Razborov diagram presented in section 5), or it is a rigid graded limit group RgdGlim(x, p, a) for which for every value of the parameters p_{0}, there are at most finitely many possible homomorphisms h : RgdGlim(x, p, a) → F_{k} that satisfy h(p) = p_{0}, or a solid graded limit group Sld(x, p, a) with no flexible quotients. By construction, up to the equivalence relation of graded and restricted shortening quotients, and flexible graded quotients, the graded Makanin-Razborov diagram of a graded limit group is canonical.

As in the case of (ungraded) limit groups (definitions 5.7), We can use the graded Makanin-Razborov diagram to define graded Makanin-Razborov resolutions of a graded limit group. The main purpose of defining graded Makanin-Razborov diagrams and resolutions is the fact these ”encode” all the (ungraded) restricted resolutions for every specialization of the defining parameters of the graded limit group. A better understanding of this ”encoding” requires a better understanding of rigid and solid limit groups and will be obtained in the following sections of this paper and the following papers in the sequel.

As we pointed out in section 8, the study of sets of solutions to equations with coefficients is naturally equivalent to the study of all restricted homomorphisms from a f.g. restricted residually free group into the free group generated by the coefficients. For studying this collection of homomorphisms we have an analogue of theorems 7.2 and 8.5 in the graded case. The proof is a direct modification.

Theorem 11.8. Let RF (x, p, a) be a f.g. restricted residually free group. Then there exists a (canonical) finite collection of graded limit group quotients of RF (x, p, a): Glim_{1}(x, p, a), …, Glim_{ℓ}(x, p, a), and for each i an epimorphism τ_{i} : RF (x, p, a) → Glim_{i}(x, p, a) with the following properties:

(i) for each restricted homomorphism h : RF (x, p, a) → F_{k} there exists some index i (not necessarily unique!) and a restricted homomorphism f : Glim_{i}(x, p, a) → F_{k} so that h splits as: h = f ∘ τ_{i}.

(ii) if Glim(x, p, a) is a graded quotient of RF (x, p, a), and τ is an epimorphism τ : RF (x, p, a) → Glim(x, p, a), then there exists some index i and an epimorphism λ : Glim_{i}(x, p, a) → Glim(x, p, a) so that tau = λ ∘ τ_{i}.

(iii) the couples {(Glim_{i}(x, p, a), τ_{i})} represent distinct equivalence classes, and if i ≠ j then the couple (Glim_{i}(x, p, a), τ_{i}) can not be compared with (Glim_{j}(x, p, a), τ_{j}) in the partial order defined on these couples.

(iv) if Ĝlim_{1}(x, p, a), … Ĝlim_{u}(x, p, a) and {τ̂_{j} : RF (x, p, a) → Ĝlim_{j}(x, p, a)} is another collection of graded quotients of RF (x, p, a) and epimorphisms from RF (x, p, a) to the graded limit groups Ĝlim_{i}(x, p, a)’s that satisfy properties (i)-(iii) then u = ℓ and up to permutation, the couple (Glim_{i}(x, p, a), τ_{i}) is equivalent to the couple (Ĝlim_{i}(x, p, a), τ̂_{i}).

We have already modified the construction of the Makanin-Razborov diagram of a limit group to the graded case. Having such diagram for a graded limit group, theorem 11.9 allows us to modify the construction of the Makanin-Razborov diagram associated with a residually free group presented in section 8 to the graded case.

§12. The Singular Locus

The main purpose for modifying limit groups and their Makanin-Razborov diagrams and resolutions to the graded category is the ability to use the graded objects in order to understand the variation of sets of solutions with a change in the values of the defining parameters. Such analysis is crucial in studying the structure of elementary sets and elementary predicates as we will see later in the sequel.

Since the collection of graded resolutions of a graded limit group Glim(x,p,a) ”encodes” all the restricted homomorphisms of the group Glim(x, p_{0}, a) for any possible specialization p_{0} of the set of defining parameters p, to understand the variation in the set of solutions with a change of the defining parameters we need to look closely at all the possible degenerations in the graded resolutions of Glim(x, p, a) for all possible values of the defining parameters. Our aim in this section is to associate finitely many singular graded limit groups with each rigid and solid limit group in a graded resolution of the graded Makanin-Razborov diagram. The finite collection of singular limit groups associated with a rigid (or solid) limit group in a graded resolution describe all the possible degenerations in the part of the graded resolution that terminates at the rigid (or solid) graded limit group.

Let Glim(x, p, a) be a graded limit group, let GRes_{i} be a graded resolution in the graded Makanin-Razborov diagram of Glim(x, p, a) and let RgdGlim(y, p, a) be a rigid limit group in this resolution.

Definition 12.1. With the assumptions above, we say that the specialization (y_{0}, p_{0}, a) belongs to the singular locus of the tuple (RgdGlim(y, p, a), GRes_{i}) if for all homomorphisms h : Glim(x, p, a) → F_{k} that factor through the resolution GRes_{i} and the specialization (y_{0}, p_{0}, a) at least one of the graded abelian JSJ decompositions of the graded limit groups along the graded resolution GRes_{i} remains degenerate, i.e., at least one of the following possible degenerations in the graded abelian JSJ decompositions occurs:

(i) an edge group is always mapped to the trivial group in F_{k}.

(ii) a non-abelian vertex group is always mapped to a cyclic subgroup in F_{k}.

(iii) a QH vertex group is always mapped to a cyclic subgroup in F_{k}.

(note that (iii) can be viewed as a special case of (ii), but we prefer to list it as an additional separate case).

Clearly, there are only finitely many ways in which one of the graded abelian JSJ decompositions of the graded limit groups along the graded resolution GRes_{i} can get degenerate, so the singular locus of (RgdGlim(x, p, a), GRes_{i}) can be stratified according to the degenerate parts of these graded abelian JSJ decompositions.

Theorem 12.2. With the notation and assumptions above, there exist finitely many systems of equations Σ_{1}(y, p, a), …, Σ_{q}(y, p, a) so that a specialization (y_{0}, p_{0}, a) belongs to the singular locus of the tuple (RgdGlim(y, p, a), GRes_{i}) if and only if it satisfies one of the systems Σ_{1}, …, Σ_{q}.

Proof: Given the resolution GRes_{i} and elements in the graded modular groups of each of the graded limit groups in the resolution GRes_{i}, a degeneration in one of the graded abelian JSJ decomposition of one of the graded limit groups can be expressed as an equation in the variables (y, p). Hence, a specialization (y_{0}, p_{0}, a) belongs to the singular locus of the tuple (RgdGlim(y, p, a), GRes_{i}) if (y_{0}, p_{0}, a) satisfies an infinite system of equations parameterized by the product of the graded modular groups of the different graded limit groups in the graded resolution GRes_{i}. Since by Guba’s theorem [Gu] every infinite system of equations in a free group is equivalent to a finite one, the theorem follows.

□

Definition 12.3. With the notation above, we say that a graded limit group SngGlim(y, p, a) is a singular graded limit group of the tuple (RgdGlim(y, p, a), GRes_{i}) if it is a maximal graded limit group corresponding to one of the systems of equations Σ_{1}, … Σ_{q} constructed in theorem 12.2. Clearly, this associates canonically finitely many singular limit groups with every tuple (RgdGlim(x, p, a), GRes_{i}).

In a similar way we associate (canonically) finitely many singular limit groups with every tuple of a graded resolution and a solid graded limit group in it. Let Glim(x, p, a) be a graded limit group, let GRes_{i} be a graded resolution in the graded Makanin-Razborov diagram of Glim(x, p, a) and let SldGlim(y, p, a) be a rigid limit group in this resolution.

Definition 12.4. With the assumptions above, we say that the specialization (y_{0}, p_{0}, a) belongs to the singular locus of the tuple (SldGlim(y, p, a), GRes_{i}) if for all homomorphisms h : Glim(x, p, a) → F_{k} that factor through the resolution GRes_{i} and the specialization (y_{0}, p_{0}, a) at least one of the abelian graded JSJ decompositions of the graded limit groups along the graded resolution GRes_{i} remains degenerate (note that by all homomorphisms that factor through graded resolution GRes_{i} and the specialization (y_{0}, p_{0}, a) we allow a possible pre-composition with a graded modular automorphism of the solid graded limit group SldGlim(y, p, a) itself).

Like in the rigid case there exist finitely many systems of equations Σ_{1}(y, p, a), …, Σ_{q}(y, p, a) so that a specialization (y_{0}, p_{0}, a) belongs to the singular locus of the tuple (SldGlim(y, p, a), GRes_{i}) if and only if it satisfies one of the systems Σ_{1}, …, Σ_{q}. We say that a graded limit group SngGlim(y, p, a) is a singular graded limit group of the tuple (SldGlim(y, p, a), GRes_{i}) if it is a maximal graded limit group corresponding to one of the systems of equations Σ_{1}, … Σ_{q}. Clearly, this associates canonically finitely many singular limit groups with every tuple (SldGlim(x, p, a), GRes_{i}).

§13. Multi-graded Makanin-Razborov Diagrams

In the previous sections 10-12 we have analyzed the structure of parameterized sets of solutions to systems of equations in a free group, where the sets of solutions were parameterized by some subgroup of parameters P =< p_{1}, …, p_{u} >. The goal of this section is a generalization of the objects introduced in the previous sections to study sets of solutions to systems of equations parameterized by one subgroup, to the study of sets of solutions to systems of equations parameterized by finitely many subgroups.

With a finite system of equations with parameters Φ over a free group F_{k} =< a_{1}, …, a_{k} > it is natural to associate a f.p. group G(Φ). If the system Φ is defined by the coefficients a_{1}, …, a_{k}, the parameters p_{1}, …, p_{u}, and r_{1}^{1}, …, r_{m_{1}}^{1}, …, r_{1}^{ℓ}, …, r_{m_{ℓ}}^{ℓ}, the unknowns x_{1}, …, x_{n} and the equations:

w_{1}(a_{1}, …, a_{k},p_{1}, …, p_{u}, r_{1}^{1}, …, r_{m_{ℓ}}^{ℓ}, x_{1}, …, x_{n}) = 1
⋮
w_{s}(a_{1}, …, a_{k},p_{1}, …, p_{u}, r_{1}^{1}, …, r_{m_{ℓ}}^{ℓ}, x_{1}, …, x_{n}) = 1

we set the associated f.p. group G(Φ) to be:

G(Φ) = < a_{1}, …, a_{k}, p_{1}, …, p_{u}, r_{1}^{1}, …, r_{m_{ℓ}}^{ℓ}, x_{1}, …, x_{n} | w_{1}, …, w_{s} >

Clearly, every solution of the system Φ corresponds to a homomorphism h : G(Φ) → F_{k} for which h(a_{i}) = a_{i}, and every such homomorphism corresponds to a solution of the system Φ.

In sections 10-12 we studied the variation of the structure of the set of solutions with a change of the defining parameters. In this section we study the variation of the defining set of solutions with a change of the defining parameters and the conjugacy classes of the subgroups R_{1} =< r_{1}^{1}, …, r_{m_{1}}^{1} >, …, R_{ℓ} =< r_{1}^{ℓ}, …, r_{m_{ℓ}}^{ℓ}. To analyze the variation in this structure with a change of the defining parameters P and the conjugacy classes of the subgroups R_{1}, …, R_{ℓ} we will need to look at a special class of graded limit groups which we call multi-graded limit groups.

We set G =< x_{1}, …, x_{k}, p_{1}, …, p_{u}, r_{1}^{1}, …, r_{m_{ℓ}}^{ℓ}, a_{1}, …, a_{k} > to be a f.g. group. For brevity we will denote this (fixed) generating set by G =< g_{1}, …, g_{m} >, and F_{k} to be a free group with a fixed basis F_{k} =< a_{1}, …, a_{k} >. With this notation our goal is to get a structure theory for understanding the set of all homomorphisms:

Hom((G, {p_{j}}, {r_{q}}, {a_{i}}), (F_{k}, {a_{i}})) = { h | h : G → F_{k} , h(a_{i}) = a_{i} }

with a change in the values of the parameters {p_{j}} and the conjugacy class of the subgroups R_{1}, …, R_{ℓ}. We set X to be the Cayley graph of F_{k} with respect to its given basis a_{1}, …, a_{k}. Given any homomorphism h ∈ Hom(G, F_{k}), G admits a natural action λ_{h} on X given by λ_{h}(g, x) = h(g)(x) for every g ∈ G and x ∈ X.

Definition 13.1. Let G be a f.g. group and let h_{n} : G(x, r, p, a) → F_{k} be a sequence of homomorphisms. If {λ_{h_{n}}}, a sequence of actions of G on X, the Cayley graph of F_{k}, that corresponds to the sequence of homomorphisms {h_{n}}, converges in the Gromov-Haussdorff topology, we say that the sequence {h_{n}} converges. We call the obtained limit group, a multi-graded limit group.

A multi-graded limit group is in particular a limit group, so every f.g. multigraded limit group is f.p. and every f.g. graded limit group is ω-residually free by theorem 4.6. To construct the (canonical) multi-graded Makanin-Razborov diagram of a multi-graded limit group, which is the fundamental tool in our analysis of the variation of sets of solutions to systems of equations with a change in the parameters P and the conjugacy class of the subgroups R_{1}, …, R_{m}, we need to study the algebraic structure of multi-graded limit groups ”relative” to their multi-grading. To do that we need to construct the multi-graded abelian JSJ decomposition of a multi-graded limit group. These constructions are all generalizations of their graded analogues presented in section 10-12.

For the rest of this section let G(x, r, p, a) be a f.g. group, let {h_{m} : G(x, r, p, a) → F_{k}} be a convergent multi-graded sequence of homomorphisms, and let MGlim(x, r, p, a) be the corresponding graded limit group. We set η : G(x, r, p, a) → MGlim(x, r, p, a) to be the canonical epimorphism and AP < MGlim(x, r, p, a) to be the subgroup: AP =< η(p_{1}), …, η(p_{u}), η(a_{1}), …, η(a_{k}) >. The abelian JSJ decomposition of a freely-indecomposable limit group ”encodes” all the possible splittings of such limit group with abelian edge groups. In studying multi-graded limit groups we will be interested only in abelian splittings in which the subgroup AP and the subgroups R_{1}, …, R_{m} are elliptic. The construction of the abelian JSJ decomposition of a limit group described in section 2, naturally generalizes to a multi-graded abelian JSJ decomposition of a multi-graded limit group.

Theorem 13.2 (cf. 10.2). Suppose MGlim(x, r, p, a) = L_{0} ∗ … ∗ L_{v} is the most refined free decomposition in which AP < L_{0} and each of the subgroups R_{j} can be conjugated into one of the factors L_{i}. With each of the factors we associate a multigraded abelian JSJ decomposition. If non of the subgroups R_{j} can be conjugated into L_{i} we associate with it its cyclic JSJ decomposition. If L_{i} is L_{0} or it contains a conjugate of one of the subgroups R_{j} then there exists a (relatively) reduced unfolded (perhaps trivial) splitting of the factor L_{i} with abelian edge groups, which we call a multi − graded abelian JSJ (Jaco-Shalen-Johannson) decomposition of the factor L_{i} with the following properties:

(i) AP is elliptic in the multi-graded abelian JSJ decomposition of L_{0}. If a subgroup R_{j} can be conjugated into the factor L_{i}, then R_{j} is elliptic in the multi-graded abelian JSJ decomposition of L_{i}.

(ii) Every (multi-graded) canonical maximal QH subgroup (CMQ) of L_{i} is conjugate to a vertex group in the multi-graded JSJ decomposition. Every (multigraded) QH subgroup of MGlim(x, r, p, a) can be conjugated into one of the CMQ subgroups of L_{i}. Every vertex group in the multi-graded JSJ decomposition which is not a CMQ subgroup of L_{i} is elliptic in any abelian splitting of L_{i} under consideration (i.e., in one in which AP and the R_{j}’s are elliptic).

(iii) A one edge (multi-graded) abelian splitting MGlim(x, r, p, a) = D ∗_{A} E or L_{i} = D∗_{A} in which AP and the R_{j}’s are elliptic which is hyperbolic in another such elementary abelian splitting is obtained from the multi-graded abelian JSJ decomposition of L_{i} by cutting a 2-orbifold corresponding to a

(multi-graded) CMQ subgroup of L_{i} along a weakly essential s.c.c.. (iv) Let Θ be a one edge (multi-graded) splitting along an abelian subgroup L_{i} =

D ∗_{A} E or L_{i} = D∗_{A} in which AP and the R_{j}’s are elliptic, which is elliptic with respect to any other one edge (multi-graded) abelian splitting of L_{i} in which AP and the R_{j}’s are elliptic. Then Θ is obtained from the multi-graded abelian JSJ decomposition of L_{i} by a sequence of collapsings, foldings, and conjugations.

(v) If JSJ_{1} is another multi-graded abelian JSJ decomposition of L_{i}, then JSJ_{1} is obtained from the multi-graded abelian 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 5 we have used the canonical cyclic JSJ decomposition of a limit group to construct its canonical Makanin-Razborov diagram. In section 11 we modified this construction to obtain the graded Makanin-Razborov diagram for analyzing the variation of the restricted Makanin-Razborov diagram with a change of the defining parameters. To understand the variation of the Makanin-Razborov diagram with a change of the parameter subgroup P, and the conjugacy classes of the subgroups R_{j}, we need to further modify the construction of the graded Makanin-Razborov diagram to obtain the multi-graded Makanin-Razborov diagram of a multi-graded limit group.

Definition 13.3. Let MGlim(x, r, p, a) be a multi-graded limit group and let MGlim(x, r, p, a) = L_{0} ∗ … ∗ L_{v} be the most refined free decomposition in which AP < L_{0} and the subgroups R_{j} can be conjugated into the different factors L_{i}. Let L_{i} be one of those factors and suppose that the multi-graded abelian JSJ decomposition of L_{i} is non-trivial. We define the multi − graded modular group MGMod(L_{i}) to be the subgroup of Aut(L_{i}) generated by the following families of automorphisms of the factor L_{i}:

(i) Dehn twists along edges of the multi-graded abelian JSJ decomposition of L_{i}. The Dehn twists are assumed to fix (elementwise) the vertex stabilized by AP in case L_{i} is the factor L_{0}

(ii) Dehn twists along essential s.c.c. in (multi-graded) CMQ (canonical maximal quadratically hanging) vertex groups in the multi-graded abelian JSJ decomposition of L_{i}. Again, these Dehn twists are assume to fix (elementwise) the vertex stabilized by AP in case L_{i} is the factor L_{0}.

(iii) Let A be an abelian vertex group in the multi-graded abelian JSJ decomposition of L_{i}. Let A_{1} < A be the subgroup generated by all edge groups connected to the vertex stabilized by A in the multi-graded abelian JSJ decomposition of L_{i}. Every automorphism of A that fixes A_{1} (elementwise) can be naturally extended to an automorphism of the ambient factor L_{i} that fixes the vertex stabilized by AP and conjugates of the other subgroups R_{j}. We call these generalized Dehn twists and they form the third family of automorphisms that generate MGMod(L_{i}).

We say that a homomorphism h : MGlim(x, r, p, a) → F_{k} is the same multigraded modular class as the homomorphism ĥ : MGlim(x, r, p, a) → F_{k} if ĥ = h ∘ φ, and φ is a multi-graded modular automorphism of MGlim(x, r, p, a), i.e., φ ∈ MGlim(x, r, p, a).

Let L_{i} be a factor in the most refined free decomposition of the multi-graded limit group MGlim(x, r, p, a) in which the subgroups AP and R_{j}’s can be conjugated. Once we fix a generating set for the factor L_{i}, given a homomorphism h : L_{i} → F_{k} we can choose the shortest homomorphisms in the multi-graded modular class of h. A multi-graded limit group obtained from a convergent sequence of homomorphisms h : L_{i} → F_{k} which are the shortest in their multi-graded modular class, is called a multi-graded shortening quotient of the factor L_{i}.

On the set of multi-graded shortening quotients of the factor L_{i} we can naturally define a partial order and an equivalence relation, similar to the ones defined in section 5 for shortening quotients of limit groups. By the same argument used to prove lemma 5.4 the set of multi-graded shortening quotients of L_{i} contains maximal elements with respect to the partial order, and by the same argument used to prove lemma 5.5 there are only finitely many equivalence classes of maximal multi-graded shortening quotients of the factor L_{i}.

So far we have modified the construction of maximal shortening quotients presented in section 5 to the multi-graded setup. However, multi-graded shortening quotients of a multi-graded limit group need not be proper quotients of it. Furthermore, to get multi-graded shortening quotients we naturally require that the multigraded abelian JSJ decomposition of the factor L_{i} is non-trivial. Unlike (ungraded) limit groups, to understand the variation of the set of restricted homomorphisms from a graded limit group to F_{k} with a change of the defining parameters P and the conjugacy classes of the subgroups R_{j}, we will need to study the structure of multi-graded limit groups with a trivial principal graded abelian JSJ decomposition.

Definition 13.4. Let L_{i} be a factor in the most refined free decomposition of a multi-graded limit group MGlim(x, r, p, a). If the factor L_{i} has a trivial multigraded abelian JSJ decomposition it is called rigid multi-graded limit group. If L_{i} has a non-trivial multi-graded JSJ decomposition, and a (unique) maximal multigraded shortening quotient GMSQ(x, r, p, a) that is isomorphic to L_{i}, L_{i} is called solid multi-graded limit group.

To study rigid and solid graded limit groups we need to introduce the notion of flexible graded limit groups.

Definition 13.5. Let L_{i} be either a rigid or a solid factor of a multi-graded limit group MGlim(x, r, p, a). A sequence of homomorphisms {h_{m} : L_{i} → F_{k}} is called flexible multi-graded sequence if one of the following holds:

(i) each homomorphism h_{m} factors as h_{m} = ν_{m} ∘ τ_{m}, where τ_{m} : L_{i} → F_{k}∗ < v > and τ_{m} is an epimorphism that maps the subgroup AP onto the factor F_{k} and the subgroups R_{j} into a conjugate of F_{k} in F_{k}∗ < v >, and ν_{m} : F_{k}∗ < v >→ F_{k}. Furthermore, τ_{m} can not be shortened (in F_{k}∗ < v >) by an element from the graded modular group MGMod(L_{i}).

(ii) each homomorphism h_{m} does not factor through a free product in which the subgroups AP and R_{j}’s can be conjugated into various factors, and can not be shortened by an element from the multi-graded modular group MGMod(L_{i}). In addition, if L_{i} = L_{0} then for each index m:

max_{g∈B_{m}} d_{X}(h_{m}(g), id.) > 2^{m}·(1+ max_{1≤j≤u} d_{X}(h_{m}(p_{j}), id.)+ max_{1≤j≤ℓ} min_{f∈F_{k}} (d_{X}(fh_{m}(r_{1}^{j})f^{−1}, id.)+…+ (d_{X}(fh_{m}(r_{m_{ℓ}}^{ℓ})f^{−1}, id.))

where B_{m} is the ball of radius m in the Cayley graph of L_{i}. If L_{i} is not the factor L_{0}, i.e., if AP is not a subgroup of L_{i}, then for each index m:

min_{f∈F_{k}} max_{g∈B_{m}} d_{X}(fh_{m}(g)f^{−1}, id.) > 2^{m}·(1+ max_{1≤j≤ℓ} min_{f∈F_{k}} (d_{X}(fh_{m}(r_{1}^{j})f^{−1}, id.)+…+ (d_{X}(fh_{m}(r_{m_{ℓ}}^{ℓ})f^{−1}, id.)).

A multi-graded limit group which is the limit of a flexible multi-graded sequence is called a flexible multi-graded quotient of the rigid or solid multi-graded limit group L_{i}.

Lemma 13.6. Let F lx(x, r, p, a) be a flexible multi-graded quotient of the rigid or solid graded limit factor L_{i}. Then:

(i) F lxGlim(x, p, a) is not a rigid multi-graded limit group.

(ii) F lxGlim(x, p, a) is a proper quotient of L_{i}.

Proof: Identical with the proof of lemma 11.5.

□

Let MGlim(x, r, p, a) be a rigid or solid multi-graded limit group. On the set of flexible multi-graded quotients of MGlim(x, r, p, a) we can naturally define a partial order and an equivalence relation, similar to the ones defined on multi-graded limit groups. By the same argument used to prove lemma 5.4, the set of flexible graded quotients of MGlim(x, r, p, a) contains maximal elements with respect to the partial order, and by the same argument used to prove lemma 5.5 there are only finitely many equivalence classes of maximal flexible multi-graded quotients of MGlim(x, r, p, a). For the sequel we will need the following definitions associated with rigid and solid multi-graded limit groups and their associated maximal flexible limit quotients.

Definition 13.7. Let Rgd(x, r, p, a) be a rigid limit group and let F lx_{1}(x, r, p, a), …, F lx_{v}(x, r, p, a) be the maximal flexible multi-graded quotients of it. A homomorphism h : Rgd(x, r, p, a) → F_{k} that does not factor through any of the maximal multi-graded flexible quotients F lx_{1}(x, r, p, a), …, F lx_{v}(x, r, p, a) of Rgd(x, r, p, a) is called a rigid homomorphism (solution)of the rigid multi-graded limit group Rgd(x, r, p, a). A homomorphism that does factor through one of the maximal flexible quotients is called a flexible homomorphism (solution).

Definition 13.8. Let Sld(x, r, p, a) be a solid multi-graded limit group and let F lx_{1}(x, r, p, a), …, F lx_{v}(x, r, p, a) be the maximal flexible quotients of it. A homomorphism h : Sld(x, r, p, a) → F_{k} for which h = h′ ∘ φ where h′ factors through one of the maximal multi-graded flexible quotients of Sld(x, r, p, a), and φ is a multigraded modular automorphism of Sld(x, r, p, a), is called a flexible homomorphism (solution) of the solid multi-graded limit group Sld(x, r, p, a). Note that every homomorphism of Sld(x, r, p, a) → F_{k} that factors through a free product of the form F_{k}∗ < v > so that AP and the subgroups R_{j} are mapped into F_{k}, is flexible. A non-flexible homomorphism h : Sld(x, r, p, a) → F_{k} is called a solid homomorphism (solution) of the solid multi-graded limit group Sld(x, r, p, a).

Flexible quotients of rigid multi-graded limit groups and flexible quotients of solid multi-graded limit groups, contain all the ”generic infinite families” of specializations of these multi-graded limit groups. Rigid solutions of rigid multi-graded limit groups are the exceptional single solutions, and solid solutions of solid multi-graded limit groups are the exceptional families of solutions.

Proposition 13.9. Let Rgd(x, r, p, a) be a rigid multi-graded limit group, let Sld(x, r, p, a) be a solid multi-graded limit group, and let p_{0} be a specialization of the defining parameters p. Then:

(i) there are at most finitely many rigid solutions: h : Rgd(x, r, p, a) → F_{k} for which h(p) = p_{0} and each of the subgroups R_{j} are mapped to a conjugate of h(R_{j}) (elementwise).

(ii) up to pre-composing with a graded modular automorphism of the solid graded limit group Sld(x, r, p, a) there are at most finitely many solid homomorphisms: h : Sld(x, r, , p, a) → F_{k} for which h(p) = p_{0} and each of the subgroups R_{j} are mapped to a conjugate of h(R_{j}) (elementwise).

Proof: Identical with the proof of proposition 11.8.

□

The above basic facts concerning multi-graded limit groups and their multigraded shortening quotients and multi-graded flexible quotients allow us to present the main goal of this section, the (canonical) multi-graded Makanin-Razborov diagram associated with a multi-graded limit group. Let MGlim(x, r, p, a) be a multi-graded limit group. Let MGlim(x, r, p, a) = L_{0} ∗ …∗L_{v} be the most refined free decomposition of MGlim(x, r, p, a) so that AP < L_{0} and each of the subgroups R_{j} can be conjugated into one of the L_{i}’s. Suppose first that a factor L_{i} contains either the subgroup AP or a conjugate of one of the subgroups R_{j}. Suppose L_{i} is not rigid or solid. Then by claim 13.2 the set of multi-graded shortening quotients of the factor L_{i} contains maximal elements (with respect to the partial order defined above) and by an analogue of lemma 5.5 to the multi-graded case there are only finitely many equivalence classes of maximal multi-graded shortening quotients of L_{i}. Since L_{i} is not a solid multi-graded limit group each maximal multi-graded shortening quotient of it is a proper quotient. Let MGM_{1}, …, MGM_{s} be a collection of representatives of equivalence classes of maximal multi-graded shortening quotients of the factor L_{i}, and let η_{q} : L_{i} → MGM_{q} be the canonical projection maps. Note that MGM_{q} is a multi-graded limit group with respect to some subset of the subgroups P and R_{1}, …, R_{ℓ}. Now, suppose L_{i} is rigid or solid. In this case, L_{i} has finitely many equivalence classes of maximal flexible multi-graded quotients. Let F lx_{1}, …, F lx_{t} be a collection of representatives of equivalence classes of maximal flexible graded quotients of L_{i}, and let ν_{q} : L_{i} → F lx_{q} be the canonical projection maps.

We define the multi-graded Makanin-Razborov diagram of the multi-graded limit group MGlim(x, r, p, a) iteratively. We start by factoring MGlim(x, r, p, a) as above. From each of the factors L_{i} that does not contain the subgroup AP or a conjugate of one of the subgroups R_{j} we continue by adjoining its (ungraded) Makanin-Razborov diagram presented in section 5. If L_{i} contains the subgroup AP or a conjugate of one of the R_{j}’s, and L_{i} is not rigid or solid we continue along s edges going from L_{i} to each of its maximal multi-graded shortening quotients MGM_{1}, …, MGM_{s}. To each such directed edge we associate the canonical projection η_{q}.

If L_{i} is rigid or solid we continue along t edges going from L_{i} to each of its maximal multi-graded flexible quotients F lx_{1}, …, F lx_{t}. To each such directed edge we associate the canonical projection ν_{q}.

We proceed iteratively. Since a multi-graded shortening quotient of a non-solid multi-graded limit group, and a flexible shortening quotient of a solid or rigid multi-graded limit groups are proper quotients of the multi-graded limit group, the construction terminates by proposition 5.1. Each terminal vertex is either a free group (as in the Makanin-Razborov diagram presented in section 5), or it is a rigid multi-graded limit group Rgd(x, r, p, a) for which for every value of the parameters P and given conjugacy classes of the subgroups R_{j}, there are at most finitely many possible homomorphisms h : Rgd(x, r, p, a) → F_{k} that obtaining these values and conjugacy classes, or a solid multi-graded limit group Sld(x, r, p, a) with no flexible quotients. By construction, up to the equivalence relation of multi-graded and restricted shortening quotients, and multi-graded flexible quotients, the multigraded Makanin-Razborov diagram of a multi-graded limit group is canonical. As in the case of (ungraded) limit groups (definition 5.7), we can use the multi-graded Makanin-Razborov diagram to define multi-graded Makanin-Razborov resolutions of a multi-graded limit group.

References

[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.

[Kh-My] O. Kharlampovich and A. Myasnikov, Irreducible affine varieties over a free group II, Jour. of Algebra 200 (1998), 517-570.

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

[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-Se] E. Rips and Z. Sela, Cyclic splittings of finitely presented groups and the canonical JSJ decomposition, Annals of Mathematics 146 (1997), 53-104.

[Se1] Z. Sela, The Nielsen-Thurston classification and automorphisms of a free group I, Duke Math. Jour. 84 (1996), 379-397.

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

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

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