DIOPHANTINE GEOMETRY OVER GROUPS II:

COMPLETIONS, CLOSURES AND FORMAL SOLUTIONS

Z. Sela^{1,2}

posted April 19, 2001

This paper is the second 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 second paper we generalize Merzlyakov’s 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 first paper in this sequence on Diophantine geometry over groups we studied sets of solutions to systems of equations defined over a free group and parametric families of such sets. With a given system of equations we associated a canonical Makanin-Razborov diagram. This Makanin-Razborov diagram encodes the entire set of solutions to the system. Later on we studied systems of equations with parameters, and with each such system we associated 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 order to prove the correctness of a positive sentence defined over a free group, Merzlyakov has introduced ”formal solutions” [Me]. In the special case of AE sentences, Merzlyakov theorem implies that if the sentence:

∀y ∃x Σ(x, y, a) = 1

is a truth sentence, then there exists a formal solution x = x(y, a), so that if we replace the variables x with their corresponding formal solutions, then each equation in the obtained system Σ(x(y, a), y, a) represents the trivial word in the free group F (y, a), i.e., the free group generated by the variables y and the coefficients a.

To analyze general sentences and predicates, a generalized version of Merzlyakov theorem is required. First, we naturally need the sentences and predicates in question to include equalities and inequalities. Second, we need to study AE sentences and predicates in which the universal variables do not belong to an entire power set of the free group in question, but rather to some given variety. To analyze these general AE sentences we need to associate with the variety to which the universal variables belong, a canonical collection of completions of the variety, that are built from the (taut) Makanin-Razborov diagram associated with it. The union of the Diophantine sets defined by the completions associated with a variety is precisely the variety itself.

1Hebrew University, Jerusalem 91904, Israel.

2Partially supported by an Israel academy of sciences fellowship.

Once we define the completions of a variety, we are able to formulate the required generalization of Merzlyakov theorem. We show (theorem 1.18) that if a sentence of the form:

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

is a truth sentence, where V is a variety defined by a system of equations using the variables y and the coefficients a, then there exists a collection of closures of the completions of the variety V, and with each closure there is an associated formal solution x = x(s, z, y, a) defined over it, so that each of the words in the system of equations obtained by replacing the variables x with the formal solutions x = x(s, z, y, a) in the system Σ(x, y, a): Σ(x(s, z, y, a), y, a) represents the trivial element in the limit group associated with the corresponding closure of the variety V. Moreover, we prove that in a ”generic” point in that closure the inequalities hold as well.

As we will see in the sequel, to get a quantifier elimination procedure for predicates defined over a free group, we will need tools that encode the entire collection of formal solutions associated with a given sentence, and not only their existence. In the second section we present formal limit groups and their associated (canonical) formal Makanin-Razborov diagrams that are built precisely for that purpose. Indeed, given a truth sentence of the form given above, the formal limit groups and their associated formal Makanin-Razborov diagrams encode the entire collection of formal solutions associated with the given sentence.

In the first two sections we study general AE sentences. In the third one we generalize our constructions to study AE predicates. With an AE predicate we associate a finite collection of graded completions. Given a graded completion, we further associate with the given predicate a finite collection of graded formal limit groups, and with each of these limit groups we associate a (canonical) graded formal Makanin-Razborov diagram. As in our construction of the graded Makanin-Razborov diagram in the previous paper in this sequence, the formal graded diagram encodes the entire collection of formal Makanin-Razborov diagrams for all possible specializations of the defining parameters.

§1. Formal Solutions

To analyze the structure of elementary sets over a free group, we need to look at projections of sets that are in the Boolean algebra of AE sets. Our approach to study these projections is based on a finite ”trial and error” procedure, which uses extensively the existence of ”formal solutions” suggested by Merzlyakov theorem. However, unlike the original Merzlyakov theorem [Me], one can not define a ”formal solution” on a general variety in terms of its defining variables. As we will show in this section, general ”formal solutions” are associated with each of the resolutions that appear in the canonical Makanin-Razborov diagram associated with the variety, and they are defined not over the variety itself, but rather on closures of its canonical (finite) set of completions.

Our general approach to proving the existence of formal solutions associated with a given truth sentence, uses the theory of actions of groups on real trees and the shortening argument. We start this section with (a special case of) Merzlyakov original theorem, which we prove combinatorially, in a similar way to Merzlyakov’s original argument.

Theorem 1.1 [Me]. Let F_{k} =< a_{1}, …, a_{k} > be a free group, let y = (y_{1}, …, y_{ℓ}) and x = (x_{1}, …, x_{q}). Let w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 be a system of equations over F_{k}, and suppose that the sentence:

∀y ∃x w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1

is a truth sentence. Then there exists a formal solution x = x(y, a) so that each of the words w_{j}(x(y, a), y, a) is the trivial word in the free group F =< y, a >.

Proof: For a given set of tuples of integers {(α_{i}, β_{i})} we define:

y_{i}([α_{i}, β_{i}]) = a_{1}a_{2}^{α_{i}}a_{1}a_{2}^{α_{i}+1}a_{1} … a_{1}a_{2}^{β_{i}}a_{1}

for i = 1, …, ℓ.

Each specialization of y and x defines a tree of cancellations for each of the equations w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1. On each tree of cancellation we add notation for the placements of the x-segments, y-segments and a-segments (The a segments are the coefficients that appear in the equations w_{1}, …, w_{s}). Clearly, given the words w_{1}(x, y, a), …, w_{s}(x, y, a) the combinatorics of the trees of cancellations for any possible specialization is bounded. Setting the weight of a vertex v in a cancellation tree to be the total number of x, y and a segments passing through v, then the bounded combinatorics of the trees imply the existence of a global bound τ on the sum of the weights of the vertices in the cancellation trees corresponding to w_{1}(x, y, a), …, w_{s}(x, y, a) for all possible specializations of x and y.

Let α_{i}^{0} = 3(i + 1) · τ and β_{i}^{0} = 3(i + 2) · τ − 1, and let y_{i}^{0} = y_{i}([α_{i}^{0}, β_{i}^{0}]) for i = 1, …, ℓ. Let y^{0} = (y_{1}^{0}, …, y_{ℓ}^{0}). Since the sentence that appears in the formulation of the theorem is true, there exists some x^{0} = (x_{1}^{0}, …, x_{q}^{0}) so that w_{1}(x^{0}, y^{0}, a) = 1, …, w_{s}(x^{0}, y^{0}, a) = 1. Let T_{1}, …, T_{s} be the cancellation trees corresponding to these last equalities.

By a simple pigeon-hole argument for each y_{i}^{0} there exists some index pl_{i} so that the segment labeled by a_{1}a_{2}^{pl_{i}}a_{1} in y_{i}^{0} does not cut any of the vertices in all the cancellation trees T_{1}, …, T_{s}. At this stage for each i = 1, …, q we replace each of the segments a_{1}a_{2}^{pl_{i}}a_{1} in all the appearances of y_{i}^{0} on the cancellation trees T_{1}, …, T_{s} by a label z_{i}. This replacement allows us to write each of the variables y_{i} as: y_{i} = c_{i}^{1}z_{i}c_{i}^{2} for some constants c_{i}^{1} and c_{i}^{2}, and each of the variable x_{j} as a word x_{j} = x_{j}(z_{1}, …, z_{q}, a). By the way the segments a_{1}a_{2}^{pl_{i}}a_{1} are placed on the cancellation trees T_{1}, …, T_{s}, the words w_{1}(x(z, a), y(z, a), a), …, w_{s}(x(z, a), y(z, a), a) are the trivial words in the free group F =< z, a >. Since we can set z_{i} = (c_{1}^{i})^{−1}y_{i}(c_{2}^{i})^{−1} for i = 1, …, q the theorem follows.

□

As we have already indicated we will need a generalization of Merzlyakov theorem to a truth sentence defined over an arbitrary (given) variety. We start with a generalization of Merzlyakov theorem to a sentence containing inequalities, which basically follows from Merzlyakov proof of his theorem.

Theorem 1.2. Let F_{k} =< a_{1}, …, a_{k} > be a free group, let w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 be a system of equations over F_{k}, and let v_{1}(x, y, a), …, v_{r}(x, y, a) be a collection of words in the alphabet {x, y, a}. Suppose that the sentence:

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

is a truth sentence. Then there exists a formal solution x = x(y, a) so that each of the words w_{j}(x(y, a), y, a) is the trivial word in the free group F =< y, a >, and the sentence:

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

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

Proof: The first part of theorem 1.2 follows immediately from the argument used to prove theorem 1.1, by first choosing the y_{i}’s as in theorem 1.1, and then choosing the x_{j}’s to satisfy both the equalities w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 and the inequalities v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1 (such tuple of x_{j}’s exist by the assumption of theorem 1.2 for any possible y’s). The obtained formal solution satisfies the conclusion of the first part of the theorem.

Suppose that the words w_{1}, …, w_{s}, v_{1}, …, v_{r} are coefficient-free. Let F_{u} =< u_{1}, …, u_{k} > be a free group of rank k. Let x̃ = x̃(y, u) be words obtained from the formal solution x = x(y, a) by replacing the coefficients a_{1}, …, a_{k} with the new generators u_{1}, …, u_{k} in correspondence. Since the words w_{1}, …, w_{s}, v_{1}, …, v_{r} are coefficient-free, and the words w_{i}(x(y, a), y, a) are trivial in the free group F (y, a), the words w_{i}(x̃(y, u), y, a) are trivial in the free group F (y, a)∗F_{u}. Since there exists a specialization of the variables y, denoted y_{0}, for which: v_{j}(x(y_{0}, a), y_{0}, a) ≠ 1 in F_{k}, for all j, 1 ≤ j ≤ r, v_{j}(x̃(y_{0}, u), y_{0}, a) ≠ 1 in F_{k} ∗ F_{u}, for all j, 1 ≤ j ≤ r, which implies that: v_{j}(x̃(y, u), y, a) ≠ 1 in F (y, a) ∗ F_{u}, for all j, 1 ≤ j ≤ r. If for every substitution u = t(y), at least one of the words v_{j}(x̃(y, t(y)), y, a) = 1 in the free group F (y, a), then at least one of the words v_{j}(x̃(y, t(y)), y, a) = 1 in F (y, a) ∗ F_{u}, a contradiction. Hence, there must exist a substitution u = t(y), for which: v_{j}(x̃(y, t(y)), y, a) ≠ 1 in F (y, a), for all j, 1 ≤ j ≤ r, which implies that there exists some specialization of the variables y, ŷ ∈ F_{k}, for which: v_{j}(x̃(ŷ, t(ŷ)), ŷ, a) ≠ 1 in F_{k}, for all j, 1 ≤ j ≤ r. Clearly, since the words w_{i}(x̃(y, u), y, a) are trivial in F (y, a)∗F_{u}, the corresponding words w_{i}(x̃(y, t(y)), y, a) are trivial in F (y, a), so the coefficient-free formal solution x = x̃(y, t(y)) satisfies the conclusion of the second part of the theorem.

□

To generalize Merzlyakov theorem to arbitrary varieties, rather than the affine (free) varieties that appear in theorems 1.1 and 1.2, we need first to prove an analogous theorem for surface groups.

Theorem 1.3. Let F_{k} =< a_{1}, …, a_{k} > be a free group, and let u(y) = [y_{1}, y_{2}] … [y_{2g−1}, y_{2g}] for g > 1 or u(y) = y_{0}^{2} … y_{g}^{2} for g > 2 be given. Let the group Q =< y | u(y) > be the surface group corresponding to the equation u(y) = 1. Let w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 be a system of equations over F_{k}, and let v_{1}(x, y, a), …, v_{r}(x, y, a) be a collection of words in the alphabet {x, y, a}. Suppose that the sentence:

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

is a truth sentence. Then there exists a formal solution x = x(y, a) so that each of the words w_{j}(x(y, a), y, a) is the trivial word in the group Q ∗ F_{k} =< y, a >, and the sentence:

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

is a truth sentence in F_{k}. Furthermore, if the sentence is coefficient-free (i.e., the systems of equalities and inequalities contain no elements from the coefficient group F_{k}), then the formal solution can be taken to be coefficient-free as well, i.e., x = x(y, a) = x(y).

Proof: Let S be a surface with fundamental group Q =< y | u(y) >. Let μ : Q → F_{k} be a homomorphism with non-abelian image. By recursively applying lemma 5.13 of [Se1], we can find a finite set of non-homotopic, non-boundary parallel, disjoint s.c.c. on S, c_{1}, …, c_{m}, so that each connected component of the surface S obtained by cutting S 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 the F_{k} by the homomorphism μ.

Lemma 1.4. There exist two collections of essential, non-homotopic, non-boundary parallel disjoint s.c.c. on the surface S: b_{1}, …, b_{q} and d_{1}, …, d_{t}, and an automorphism ρ ∈ Aut(S) with the following properties:

(i) Each connected component S̃ obtained by cutting the surface S along the first collection of s.c.c. b_{1}, …, b_{q} has Euler charactersitic -1, and the homomorphism μ ∘ ρ : Q → F_{k} embeds the fundamental group of each of these connected components into F_{k}.

(ii) each of the curves d_{i} intersects non-trivially at least one of the curves b_{j}.

(iii) the entire collection of s.c.c. b_{1}, …, b_{q}, d_{1}, …, d_{t} fill the surface S, i.e., S \ ∪{b_{1}, …, b_{q}, d_{1}, …, d_{t}} is a disjoint collection of simply connected domains in S.

Proof: We can choose the collections of curves to be fixed collections of s.c.c. on the surface S. For orientable surface S we choose the collections:

For non-orientable surfaces S we choose the collections (we draw it for odd genus, for even genus the picture is similar):

The collections b_{1}, …, b_{q} and d_{1}, …, d_{t} clearly satisfy properties (ii) and (iii) of the lemma, each connected component obtained by cutting S along the curves b_{1}, …, b_{q} has Euler characteristic -1, and the fundamental group of each such connected component is isomorphic to F_{2}. To complete the proof of part (i), note that if w ∈ Q is a non-trivial element, and if we set ρ ∈ Aut(S) to be obtained from large enough powers of the Dehn twists along the curves c_{1}, …, c_{m}, then μ∘ρ maps w to a non-trivial element in F_{k}. Hence, for appropriately chosen large powers of the Dehn twists along c_{1}, …, c_{m}, μ ∘ ρ maps the fundamental group of each of the connected components obtained by cutting S along the collection of s.c.c. b_{1}, …, b_{q} isomorphically into F_{k}.

□

Let b_{1}, …, b_{q} and d_{1}, …, d_{t} be the collections of s.c.c. constructed in lemma 1.4, and let ρ ∈ Aut(S) be the automorphism chosen so that part (i) of the lemma holds. For the rest of the proof of theorem 1.3 we replace the homomorphism μ : Q → F_{k} by the composition μ ∘ ρ (and denote this composition μ). We further set φ_{1}, …, φ_{q} to be the automorphisms of Q that correspond to Dehn twists along the s.c.c. b_{1}, …, b_{q}, and ψ_{1}, …, ψ_{t} to be the automorphisms of Q that correspond to Dehn twists along the s.c.c. d_{1}, …, d_{t} in correspondence. In a similar way to the construction of the JSJ decomposition ([Ri-Se2],4), we define the following sequences of automorphisms of the surface group Q, {ν_{n}, τ_{n}}, iteratively. We set τ_{1} = id., and ν_{1} to be:

ν_{1} = ψ_{1}^{ℓ_{1}^{1}} ∘ ψ_{2}^{ℓ_{2}^{1}} ∘ … ∘ ψ_{t}^{ℓ_{t}^{1}}.

For every index n > 1 we define τ_{n} to be:

τ_{n} = φ_{1}^{m_{1}^{n}} ∘ φ_{2}^{m_{2}^{n}} ∘ … ∘ φ_{q}^{m_{q}^{n}} ∘ ν_{n−1}

and:

ν_{n} = ψ_{1}^{ℓ_{1}^{n}} ∘ ψ_{2}^{ℓ_{2}^{n}} ∘ … ∘ ψ_{t}^{ℓ_{t}^{n}} ∘ τ_{n}.

Given the sequence of automorphisms {ν_{n}, τ_{n}} of the surface group Q, we define the sequence of homomorphisms λ_{n} : Q → F_{k} to be a sequence of homomorphisms of the form:

λ_{n} = μ ∘ φ_{1}^{e_{n}} ∘ φ_{2}^{e_{n}} ∘ … ∘ φ_{q}^{e_{n}} ∘ ν_{n}.

Like in the construction of the JSJ decomposition, our aim in defining the sequence of automorphisms {ν_{n}, τ_{n}} and homomorphisms {λ_{n}}, is to guarantee that any action of the surface group Q obtained as a limit of a converging subsequence of homomorphisms λ_{n_{s}} : Q → F_{k} is a minimal IET action of the surface group Q on the limit real tree. To obtain that goal we need to restrict the sequences of powers {ℓ_{i}^{n}, m_{j}^{n}, e_{n}} used in the iterative definition of the sequences {ν_{n}, τ_{n}, λ_{n}} to satisfy certain combinatorial conditions, similar to the ones presented in section 4 of [Ri-Se2].

Let X be the Cayley graph of the free group F_{k} =< a_{1}, …, a_{k} >, let Y be the Cayley graph of the surface group Q (with respect to the generating set Q =< y_{1}, …, y_{s} >), let (T_{b}, t_{b}) be the Bass-Serre tree corresponding to the decomposition of the surface group Q along the collection of s.c.c. b_{1}, …, b_{q}, and let (T_{d}, t_{d}) be the Bass-Serre tree corresponding to the decomposition of the surface group Q along the collection of s.c.c. d_{1}, …, d_{t}. We denote by d_{X}, d_{Y}, d_{T_{b}}, and d_{T_{d}} the natural (simplicial) metrics on X, Y, T_{b}, and T_{d} in correspondence. For every element g ∈ Q we set ℓ_{b}(g) = d_{T_{b}}(g(t_{b}), t_{b}), ℓ_{d}(g) = d_{T_{d}}(g(t_{d}), t_{d}). If g acts hyperbolically on T_{b} we denote by tr_{b}(g) the trace of the action of g on T_{b}, and similarly if g acts hyperbolically on T_{d}, we denote its trace by tr_{d}(g). For an element f ∈ F_{k}, let tr_{X}(f) be the length of a cyclically reduced element that is conjugate to f in F_{k}, i.e., the ”length” of the conjugacy class of f in F_{k}.

Let Q =< y_{1}, …, y_{s} >, and suppose that each y_{i} can be written in a normal form y_{i} = a_{y_{i}}^{1}a_{y_{i}}^{2} … a_{y_{i}}^{ℓn(y_{i})} with respect to the graph of groups corresponding to the decomposition of the surface S by the curves d_{1}, …, d_{t}. Let P R^{ν_{1}} be the set of all prefixes of the words a_{y_{i}}^{1}a_{y_{i}}^{2} … a_{y_{i}}^{ℓn(y_{i})} for all i, 1 ≤ i ≤ s. We set R^{τ_{1}} = 1 and R^{ν_{1}} to satisfy:

R^{ν_{1}} ≥ 2 · max_{u∈P R^{ν_{1}}} d_{Y} (u, id.)

R^{ν_{1}} is the size of the ball whose elements are going to be ”controlled” by the automorphism ν_{1} of Q. Setting R^{ν_{1}} we define the set HY^{ν_{1}} to be:

HY^{ν_{1}} = {g ∈ Q | d_{Y} (g, id.) ≤ R^{ν_{1}} ∧ 0 < tr_{d}(g) }

and the set NF^{ν_{1}} to be:

NF^{ν_{1}} = {g ∈ Q | d_{Y} (g, id.) ≤ R^{ν_{1}} ∧ 0 < ℓ_{d}(g) }.

We define the constants R^{τ_{n}} and R^{ν_{n}} iteratively. For each g ∈ Q for which d_{Y} (g, id.) ≤ R^{ν_{n−1}} let:

ν_{n−1}(g) = a_{ν_{n−1}(g)}^{1}a_{ν_{n−1}(g)}^{2} … a_{ν_{n−1}(g)}^{ℓn(ν_{n−1}(g))}

be a normal form of ν_{n−1}(g) with respect to the graph of groups corresponding to the decomposition of the surface S by the curves b_{1}, …, b_{q}. Let P R^{τ_{n}} be the set of all prefixes of the words a_{ν_{n−1}(g)}^{1}a_{ν_{n−1}(g)}^{2} … a_{ν_{n−1}(g)}^{ℓn(ν_{n−1}(g))} for all g ∈ Q for which d_{Y} (g, id.) ≤ R^{ν_{n−1}}. We set R^{τ_{n}} to satisfy:

R^{τ_{n}} ≥ 2 · max_{u∈P R^{τn}} d_{Y} ((ν_{n−1})^{−1}(u), id.)

R^{τ_{n}} is the size of the ball whose elements are going to be ”controlled” by the automorphism τ_{n} of Q. Setting R^{τ_{n}} we define the set HY^{τ_{n}} to be:

HY^{τ_{n}} = {g ∈ Q | d_{Y} (g, id.) ≤ R^{τ_{n}} ∧ 0 < tr_{b}(ν_{n−1}(g)) }

and the set NF^{τ_{n}} to be:

NF^{τ_{n}} = {g ∈ Q | d_{Y} (g, id.) ≤ R^{τ_{n}} ∧ 0 < ℓ_{b}(ν_{n−1}(g)) }.

Similarly, for each g ∈ Q for which d_{Y} (g, id.) ≤ R^{τ_{n}} let:

τ_{n}(g) = a_{τ_{n}(g)}^{1}a_{τ_{n}(g)}^{2} … a_{τ_{n}(g)}^{ℓn(τ_{n}(g))}

be a normal form of τ_{n}(g) with respect to the graph of groups corresponding to the decomposition of the surface S by the curves d_{1}, …, d_{q}. Let P R^{ν_{n}} be the set of all prefixes of the words a_{τ_{n}(g)}^{1}a_{τ_{n}(g)}^{2} … a_{τ_{n}(g)}^{ℓn(τ_{n}(g))} for all g ∈ Q for which d_{Y} (g, id.) ≤ R^{τ_{n}}. We set R^{ν_{n}} to satisfy:

R^{ν_{n}} ≥ 2 · max_{u∈P R^{νn}} d_{Y} ((τ_{n})^{−1}(u), id.)

R^{ν_{n}} is the size of the ball whose elements are going to be ”controlled” by the automorphism ν_{n} of Q. Setting R^{ν_{n}} we define the set HY^{ν_{n}} to be:

HY^{ν_{n}} = {g ∈ Q | d_{Y} (g, id.) ≤ R^{ν_{n}} ∧ 0 < tr_{d}(τ_{n}(g)) }.

and the set NF^{ν_{n}} to be:

NF^{ν_{n}} = {g ∈ Q | d_{Y} (g, id.) ≤ R^{ν_{n}} ∧ 0 < ℓ_{d}(τ_{n}(g)) }.

Definition 1.5. For every index n and every g ∈ NF^{τ_{n}} let:

ν_{n−1}(g) = a_{ν_{n−1}(g)}^{1}a_{ν_{n−1}(g)}^{2} … a_{ν_{n−1}(g)}^{ℓn(ν_{n−1}(g))}

be the previously chosen normal form of ν_{n−1}(g) with respect to the decomposition of Q corresponding to the Bass-Serre tree T_{b}. For every h ∈ NF^{ν_{n}} let:

τ_{n}(h) = a_{τ_{n}(h)}^{1}a_{τ_{n}(h)}^{2} … a_{τ_{n}(h)}^{ℓn(τ_{n}(h))}

be the previously chosen normal form of τ_{n}(h) with respect to the decomposition of Q corresponding to the Bass-Serre tree T_{d}. We say that a sequence of automorphisms {ν_{n}, τ_{n}} of the surface group Q, and homomorphisms λ_{n} : Q → F_{k} of the form given above is a quadratic test sequence if the following conditions hold.

(i) for n > 1 and every b_{i}, 1 ≤ i ≤ q:

tr_{d}((b_{i})^{m_{i}^{n}}) > 100 · 2^{n} · max_{1≤i≤q} ℓ_{d}(b_{i}) · ∑_{d_{Y} (g,id.)≤R^{τn} ,j≤ℓn(g)} ℓ_{d}(a_{ν_{n−1}(g)}^{j})

(ii) for n ≥ 1 and every d_{i}, 1 ≤ i ≤ t:

tr_{b}((d_{i})^{ℓ_{i}^{n}}) > 100 · 2^{n} · max_{1≤i≤t} ℓ_{b}(d_{i}) · ∑_{d_{Y} (h,id.)≤R^{νn} ,j≤ℓn(h)} ℓ_{d}(a_{τ_{n}(h)}^{j})

(iii) for every n > 1 and every g, g′ ∈ NF^{τ_{n}}:

|\frac{ℓ_{d}(τ_{n}(g)) ℓ_{b}(ν_{n−1}(g′))}{ℓ_{d}(τ_{n}(g′)) ℓ_{b}(ν_{n−1}(g))} − 1| < \frac{1}{100 · q · 2^{n}}

(iv) for every n > 1 and every g ∈ HY^{τ_{n}}:

|\frac{tr_{d}(τ_{n}(g)) ℓ_{b}(ν_{n−1}(g))}{ℓ_{d}(τ_{n}(g)) tr_{b}(ν_{n−1}(g))} − 1| < \frac{1}{100 · q · 2^{n}}

(v) for every n ≥ 1 and every h, h′ ∈ NF^{ν_{n}}:

|\frac{ℓ_{b}(ν_{n}(h)) ℓ_{d}(τ_{n}(h′))}{ℓ_{b}(ν_{n}(h′)) ℓ_{d}(τ_{n}(h))} − 1| < \frac{1}{100 · q · 2^{n}}

(vi) for every n ≥ 1 and every h ∈ HY^{ν_{n}}:

|\frac{tr_{b}(ν_{n}(h)) ℓ_{d}(τ_{n}(h))}{ℓ_{b}(ν_{n}(h)) tr_{d}(τ_{n}(h))} − 1| < \frac{1}{100 · q · 2^{n}}

(vii) there exist constants c_{1}, c_{2} > 0 so that for every n ≥ 1 and every h, h′ ∈

NF^{ν_{n}}:

c_{1} < \frac{ℓ_{b}(ν_{n}(h)) d_{X}(λ_{n}(h′), id.)}{d_{X}(λ_{n}(h), id.) ℓ_{b}(ν_{n}(h′))} < c_{2}

(viii) there exist constants c_{3}, c_{4} > 0 so that for every n ≥ 1 and every h ∈ HY^{ν_{n}}:

c_{3} < \frac{tr_{b}(ν_{n}(h)) d_{X}(λ_{n}(h), id.)}{tr_{X}(λ_{n}(h)) ℓ_{b}(ν_{n}(h))} < c_{4}

(ix) for every index n, the homomorphism λ_{n} : Q → F_{k} can not be factored as λ_{n} = γ ∘ π, where π : Q → Q_{1} is an embedding of Q into the fundamental group of a surface S_{1} finitely covered by the surface S, and γ : Q_{1} → F_{k} is a homomorphism. i.e., the homomorphism λ_{n} : Q → F_{k} can not be extended to a surface covered by S.

Proposition 1.6. There exist quadratic test sequences associated with the surface group Q.

Proof: Inequalities (i)-(vi) are essentially identical to the inequalities that appear in claim 4.7 of [Ri-Se2]. Let Λ_{b}^{Q} be the graph of groups obtained by decomposing the surface group Q along the cyclic groups corresponding to the s.c.c. b_{1}, …, b_{q}. By construction, the homomorphism μ : Q → F_{k} maps every vertex group and every edge group in Λ_{b} monomorphically into F_{k}. The homomorphism λ_{n} : Q → F_{k} is defined to be:

λ_{n} = μ ∘ φ_{1}^{e_{n}} ∘ … ∘ φ_{q}^{e_{n}} ∘ ν_{n}.

Hence, given any finite set of elements M ⊂ Q, there exist some constant e, so that if the exponent e_{n} > e, then for every m_{1}, m_{2} ∈ M for which both ν_{n}(m_{1}) and ν_{n}(m_{2}) do not fix the point t_{b} ∈ T_{b}:

c_{1} < \frac{ℓ_{b}(ν_{n}(m_{1})) d_{X}(λ_{n}(m_{2}), id.)}{d_{X}(λ_{n}(m_{1}), id.) ℓ_{b}(ν_{n}(m_{2}))} < c_{2}

where the constants c_{1}, c_{2} are independent of the finite set M. Similarly, for every element m ∈ M for which tr_{b}(ν_{n}(m)) > 0:

c_{3} < \frac{tr_{b}(ν_{n}(m)) d_{X}(λ_{n}(m), id.)}{tr_{X}(λ_{n}(m)) ℓ_{b}(ν_{n}(m))} < c_{4}

where the constants c_{3}, c_{4} are independent of the finite set M, and the last two inequalities imply the inequalities (vii) and (viii) for high enough exponent e_{n} in the definition of the homomorphisms λ_{n}.

Fixing the index n, to construct a homomorphism λ_{n} that satisfy properties (i)-(viii) and does not factor through the fundamental group of any surface covered by the surface S (with fundamental group Q), we fix the automorphisms (μ_{n}, τ_{n}) of the surface group Q, and suppose that there exists an increasing sequence of exponents {e^{j}}_{j=1}^{∞} for which the homomorphisms:

λ^{j} = μ ∘ φ_{1}^{e^{j}} ∘ … ∘ φ_{q}^{e^{j}} ∘ ν_{n}

do factor through the fundamental group of surfaces covered by the surface S. Since up to isomorphism there are only finitely many possibilities for a couple (Q, Q_{1}), where Q < Q_{1} and Q_{1} is the fundamental group of a surface covered by the surface S, w.l.o.g. we may assume that all the homomorphisms {λ^{j}} factor through a (fixed) surface group Q_{1} which is the fundamental group of a surface S_{1} finitely covered by the surface S. So each homomorphism λ^{j} : Q → F_{k} factors as λ^{j} = γ^{j} ∘π where π : Q → Q_{1} is an embedding, and γ^{j} : Q_{1} → F_{k} is a homomorphism.

From the sequence of homomorphisms γ^{j} : Q_{1} → F_{k} we can extract a subsequence converging into a faithful action of the surface group Q_{1} on some real tree Y_{∞}. Since each homomorphism γ^{j} is an extension of the homomorphism λ^{j} : Q → F_{k}, and since by the structure of the homomorphisms {λ^{j} : Q → F_{k}}, the finite index subgroup Q < Q_{1} acts discretely on the limit tree Y_{∞}, the surface group Q_{1} acts discretely on the limit tree Y_{∞}. Furthermore, since every edge stabilizer in the action of Q on Y_{∞} is conjugate to a cyclic subgroups generated by one of the s.c.c. b_{i}, each edge stabilizer in the action of Q_{1} on Y_{∞} is conjugate to a maximal cyclic subgroup containing the element b_{i} in the surface group Q_{1}.

Let Λ_{b}^{Q} be the decomposition of the surface group Q along the s.c.c. b_{1}, …, b_{q}, and let Λ_{Y_{∞}}^{Q_{1}} be the graph of groups corresponding to the action of Q_{1} on the limit tree Y_{∞}. By the structure of the homomorphisms λ^{j} : Q → F_{k} every vertex group in Λ_{b}^{Q} fixes a point in Y_{∞}, so it is contained in a vertex group in the graph of groups Λ_{Y_{∞}}^{Q_{1}}. The map π : S → S_{1} corresponding to the embedding π : Q → Q_{1} is a covering map. Since Q_{1} is the fundamental group of a surface S_{1}, and since Λ_{Y_{∞}}^{Q_{1}} is a graph of groups with cyclic edge stabilizers, each vertex group in Λ_{Y_{∞}}^{Q_{1}} is a subsurface of S_{1}. Let Ŝ be a connected component of the set S \ ∪{b_{1}, …, b_{q}}. By construction χ(Ŝ) = −1, and Q̂ = π_{1}(Ŝ) is conjugate to a vertex stabilizer in Λ_{b}^{Q}. Q̂ fixes a point in Y_{∞} so it can be conjugated into a vertex group in Λ_{Y_{∞}}^{Q_{1}}. Let Q̂_{1} be that vertex stabilizer, and let Ŝ_{1} be the subsurface of S_{1} for which Q̂_{1} = π_{1}(Ŝ_{1}). The covering map π : S → S_{1} maps the subsurface Ŝ into the subsurface Ŝ_{1}, and the boundary of Ŝ is mapped to the boundary of Ŝ_{1}. Since in addition χ(Ŝ) = −1, then, necessarily, the covering map π maps the subsurface Ŝ homeomorphically onto the subsurface Ŝ_{1}. Since the restriction of the covering map π to each subsurface Ŝ is a homeomorphism, and since every edge stabilizer in Λ_{b}^{Q} is also contained in some edge stabilizer in Λ_{Y_{∞}}^{Q_{1}}, the closed surface S must be a subsurface of the closed surface S_{1}, which clearly implies that S = S_{1}. Hence, Q = Q_{1}, a contradiction to the construction of the sequence λ^{j}. Therefore, we can choose an exponent e_{n} as large as we like so that the homomorphism:

λ_{n} = μ ∘ φ_{1}^{e_{n}} ∘ … ∘ φ_{q}^{e_{n}} ∘ ν_{n}

does not factor through the fundamental group of any cover of the surface group S, and we get part (ix) in definition 1.5.

□

Proposition 1.7. Let the sequence of automorphisms of Q, {ν_{n}, τ_{n}} and homomorphisms {λ_{n} : Q → F_{k}} be a quadratic test sequence. Let g, g′ ∈ Q be non-trivial elements, and suppose max(d_{Y} (g, id.), d_{Y} (g′, id.)) ≤ R^{ν_{s}}. Then there exist constants const_{g,g′}^{1}, const_{g,g′}^{2}, const_{g}^{3}, const_{g}^{4} > 0 (depending on g and g′), so that for every index n > s + 1:

const_{g,g′}^{1} < \frac{d_{X}(λ_{n}(g), id.)}{d_{X}(λ_{n}(g′), id.)} < const_{g,g′}^{2}

const_{g}^{3} < \frac{tr_{X}(λ_{n}(g))}{d_{X}(λ_{n}(g), id.)} < const_{g}^{4}

and:

const_{g,g′}^{1} < \frac{tr_{X}(λ_{n}(g))}{tr_{X}(λ_{n}(g′))} < const_{g,g′}^{2}

Proof: If max(d_{Y} (g, id.), d_{Y} (g′, id.)) ≤ R^{ν_{s}} then max(d_{Y} (g, id.), d_{Y} (g′, id.)) ≤ min(R^{τ_{n}}, R^{ν_{n}}) for every n > s. Since the sequence {ν_{n}, τ_{n}, λ_{n}} is a quadratic test sequence, the last inequality implies that the inequalities listed in definition 1.5 apply to ν(g) and ν(g′) for every n > s. Let S be the surface with fundamental group Q. Since the curves b_{1}, …, b_{q}, d_{1}, …, d_{t} were chosen to fill the surface S, every element u ∈ Q, u ≠ 1, acts hyperbolically on either the Bass-Serre tree T_{b} or the Bass-Serre tree T_{d}. Since in addition max(d_{Y} (g, id.), d_{Y} (g′, id.)) ≤ min(R^{τ_{n}}, R^{ν_{n}}) for every n > s, each of the elements g, g′ belongs to either HY^{τ_{s+1}} or HY^{ν_{s+1}}. Therefore, inequalities (iii)-(viii) that appear in definition 1.5 hold for the couple (g, g′) for every n > s + 1. Now, from the combination of inequalities (iii), (iv), and (vii) of definition 1.5, we get the inequality that relates the lengths of the elements λ_{n}(g), λ_{n}(g′):

const_{g,g′}^{1} < \frac{d_{X}(λ_{n}(g), id.)}{d_{X}(λ_{n}(g′), id.)} < const_{g,g′}^{2}.

From the inequalities (v), (vi), and (viii) of proposition 1.5 we get the inequality that relates the trace and length of a single element g:

const_{g}^{3} < \frac{tr_{X}(λ_{n}(g))}{d_{X}(λ_{n}(g), id.)} < const_{g}^{4}

and the combination of the above two inequalities give us the third inequality on the ratio of the traces of two given elements g, g′:

const_{g,g′}^{1} < \frac{tr_{X}(λ_{n}(g))}{tr_{X}(λ_{n}(g′))} < const_{g,g′}^{2}

□

Once we have constructed quadratic test sequences we are ready to complete the proof of theorem 1.3. With the notation of the theorem 1.3, suppose that the sentence:

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

is a truth sentence. By proposition 1.6 there exists a quadratic test sequence associated with the surface group Q, so let {ν_{n}, τ_{n}, λ_{n}} be such a quadratic test sequence. Since by the assumptions of the theorem, for every possible specialization of the variables y obtained from a homomorphism from Q to the free group F_{k} there exists a specialization for the variables x, so that the given equalities w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 and inequalities v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1 are fulfilled, given the specializations λ_{n}(y) we can choose x_{n} to be the shortest possible elements, with respect to the metric on the Cayley graph of the coefficient free group F_{k}, for which:

w_{1}(x_{n}, λ_{n}(y), a) = 1, …, w_{s}(x_{n}, λ_{n}(y), a) = 1 ∧
∧ v_{1}(x_{n}, λ_{n}(y), a) ≠ 1, …, v_{r}(x_{n}, λ_{n}(y), a) ≠ 1.

By possibly passing to a subsequence (still denoted {(x_{n}, λ_{n}(y), a)}), we may assume that the sequence of specializations {(x_{n}, λ_{n}(y), a)} converges to an action of a limit group on some real tree Y_{∞}. We call the limit group into which the sequence converge, a quadratic test limit group and denote it QT L(x, y, a). Since the quadratic test limit group QT L(x, y, a) was constructed using a sequence of elements {(x_{n}, λ_{n}(y), a} for which the equalities w_{1}(x_{n}, λ_{n}(y), a) = 1, …, w_{s}(x_{n}, λ_{n}(y), a) = 1 are fulfilled, the words w_{1}(x, y, a), …, w_{s}(x, y, a) represent the trivial words in the quadratic test limit group QT L(x, y, a). Similarly, the words v_{1}(x, y, a), …, v_{r}(x, y, a) represent non-trivial elements in QT L(x, y, a).

Since the sequence {ν_{n}, τ_{n}, λ_{n}} is a quadratic test sequence, proposition 1.7 implies that the sequence of specializations {λ_{n}(y)} converges to the surface group Q, hence, Q < QT L(x, y, a). By the same proposition, either the subgroup Q fixes a point in the limit tree Y_{∞}, or it acts freely on Y_{∞}. Since Q is a surface group, if Q acts freely on Y_{∞} then Q acts freely on some IET component of the limit tree T_{∞}. Since by property (ix) of a quadratic test sequence (definition 1.5), the homomorphisms λ_{n} : Q → F_{k} do not factor through the fundamental group of a surface that is finitely covered by the surface S_{Q} corresponding to the subgroup Q, if Q is not elliptic in the real tree Y, then the subgroup (stabilizer) of the IET component of Y_{∞} on which Q acts in QT L(x, y, a) is Q itself.

Suppose that the surface subgroup Q fixes a point in the limit tree Y_{∞}. If the real tree Y_{∞} contains either an axial component, an IET component, or an edge with non-trivial (hence, abelian) stabilizer in its discrete part, then the shortening argument presented in [Se3], [Ri-Se1] and [Be] implies that there exists an automorphism τ of the limit group QT L(x, y, a) for which:

(i) τ fixes (elementwise) the subgroup Q and the coefficient group F_{k}.

(ii) for large enough n, w_{i}(τ(x_{n}), λ_{n}(y), a) = 1 for all i = 1, …, s and v_{j}(τ(x_{n}), λ_{n}(y), a) ≠

1 for all j = 1, …, r. (iii) τ(x_{n}) is strictly shorter than x_{n}.

which clearly contradicts our choice of the specializations x_{n} to be the shortest possible. Hence, the limit tree Y_{∞} contains no axial components, no IET components and all the edges in the discrete part of Y_{∞} have trivial stabilizers.

Let Λ_{Y_{∞}} be the graph of groups associated with the action of QT L on the limit tree Y_{∞}. By construction, in case the surface group Q fixes a point in the limit tree Y_{∞}, both subgroups Q and F_{k} fixes the same point in the real tree Y_{∞}, hence, they are contained in the same vertex stabilizer in the graph of groups Λ_{L_{∞}}. Since the limit group QT L acts non-trivially on the real tree Y_{∞}, and since Y_{∞} contains no axial components, no IET components, and all the edges in the discrete part of Y_{∞} have trivial stabilizers, the graph of groups Λ_{Y_{∞}} corresponds to a non-trivial free decomposition of the limit group QT L. Since both Q and F_{k} fixes the same vertex in Λ_{Y_{∞}}, both Q and F_{k} are contained in the same factor in the free decomposition of QT L associated with Λ_{Y_{∞}}.

Let QT L = H ∗ B_{1} ∗ … ∗ B_{t} ∗ F be the most refined (Grushko’s) free decomposition of the limit group QT L in which < Q, F_{k} > < H, the factor F is a free group, and the factors B_{1}, …, B_{t} are freely indecomposable and non-cyclic. By the argument presented above this free decomposition is non-trivial. Suppose that t ≥ 1, i.e., that there exists a factor in this free decomposition that is not free and does not contain the subgroup < Q, F_{k} >. In this case we modify the sequence of specializations {(x_{n}, λ_{n}(y), a)} so that it factors through a proper quotient of QT L. For each index i, 1 ≤ i ≤ t, let b_{i} be a set of generators of the factor B_{i}, let h_{1}, …, h_{m} be a set of generators of H, and let f be a free basis of the free factor F (if this factor is non-trivial). With each specialization (x_{n}, λ_{n}(y), a) from our given sequence, we associate the corresponding specialization of the generators h_{1}, …, h_{m}, which we denote h^{n}. With the specializations h^{n} and λ_{n}(y) we further associate specializations of the generating sets b^{1}, …, b^{t} in (new) free groups F_{1}, …, F_{t} in correspondence, where each such free group is isomorphic to the coefficient free group F_{k}. We denote these specializations b^{n}, and choose them to satisfy:

w_{1}(x(h^{n}, b^{n}, f), λ_{n}(y), a) = 1, …, w_{s}(x(h^{n}, b^{n}, f), λ_{n}(y), a) = 1 ∧
∧ v_{1}(x(h^{n}, b^{n}, f), λ_{n}(y), a) ≠ 1, …, v_{r}(x(h^{n}, b^{n}, f), λ_{n}(y), a) ≠ 1

in the free group F_{k} ∗ F_{1} ∗ …, F_{t} ∗ F, and among all such specializations of the generating set b^{1}, …, b^{t} we choose specializations for which the specialization of the generating set b^{t} is the shortest possible (with respect to the metric on the free group F_{t}). Note that since the words w_{i}(x, y, a) are trivial in QT L, and for every index n there exists a specialization (x_{n}, λ_{n}(y), a) in the original free group F_{k}, that factors through QT L and satisfies the inequalities v_{j}(x, y, a) ≠ 1, such specializations of the generating sets b^{1}, …, b^{t} in the limit group F_{k} ∗ F_{1} ∗ … ∗ F_{t} ∗ F do exist. By possibly passing to a subsequence, we may assume that the sequence of specializations of the generating sets b^{1}, …, b^{t} converges. In particular, the sequence of specializations of the generating set b^{t} of the factor B_{t} converges into either the trivial group or it converges into an action of a limit group B̃_{t} on some real tree T_{∞}, and since all the specializations of b^{t} are specializations of the factor B_{t}, B̃_{t} is a quotient of B_{t}. Furthermore, since the specializations of b^{t} were chosen to be shortest possible, the real tree T_{∞} contains no axial components, no IET components, and the stabilizer of all the edges in its discrete part are trivial. Hence, B̃_{t} is either trivial or cyclic or free or it inherits a non-trivial free decomposition from its action on T_{∞}. Therefore, if we set QT L_{1} to be the group D ∗ B_{1} ∗ … ∗ B̃_{t} ∗ F, then QT L_{1} is a proper quotient of QT L.

From the descending chain condition for limit groups ([Se1],5.1), after repeating this construction finitely many times, we may assume that the sequence of specializations {(x_{n}, λ_{n}(y), a)} converges into an action of a quadratic test limit group (still denoted) QT L on some real tree Y_{∞}, and either the surface group Q is not elliptic when acting on Y_{∞} or the Grushko’s free decomposition of QT L in which < Q, F_{k} > is elliptic, is of the form H ∗ F, where F is a free group.

Suppose the subgroup Q < QT L is still elliptic when acting on Y_{∞}. In this case we modify the sequence of specializations of QT L. Let h_{1}, …, h_{m} be a generating set of the factor H, and let f be a generating set of the free factor F. With each specialization (x_{n}, λ_{n}(y), a) from our given sequence, we associate a specialization of the generators h_{1}, …, h_{m}, which we denote h^{n}, which restricts to λ_{n}(y) on the subgroup Q < QT L, that satisfies:

w_{1}(x(h^{n}, f), λ_{n}(y), a) = 1, …, w_{s}(x(h^{n}, f), λ_{n}(y), a) = 1 ∧
∧ v_{1}(x(h^{n}, f), λ_{n}(y), a) ≠ 1, …, v_{r}(x(h^{n}, f), λ_{n}(y), a) ≠ 1

in the free group F_{k} ∗ F, and among all such specializations of the generating set h_{1}, …, h_{m} we choose specializations h^{n} which are the shortest possible with respect to the metric on the coefficient group F_{k}. By possibly passing to a subsequence, we may assume that the sequence of specializations {h^{n}} converges into an action of a limit group Ĥ on a real tree T_{∞}. By construction, F_{k} and Q are subgroups of Ĥ, and Ĥ is a quotient of H. If Q fixes a point when acting on T_{∞}, then by the argument used for the analysis of QT L on Y_{∞}, Ĥ admits a non-trivial free decomposition in which the subgroup < Q, F_{k} > is contained in a factor, so Ĥ is necessarily a proper quotient of H. Hence, if we set the limit group QT L_{1} = Ĥ ∗ F, then QT L_{1} is a proper quotient of QT L. Therefore, from the descending chain condition for limit groups ([Se1],5.1), after repeating this construction finitely many times, we may assume that the sequence of specializations {(x_{n}, λ_{n}(y), a)} converges into an action of a quadratic test limit group (still denoted) QT L on some real tree Y_{∞}, and either the action of the surface group Q is not elliptic when acting on Y_{∞}.

By proposition 1.7, if Q is not elliptic when acting on the limit tree Y_{∞}, then Q acts freely on Y_{∞}. Since Q is a surface group, and the homomorphisms λ_{n} : Q → F_{k} do not factor through the fundamental group of a surface finitely covered by Q, Q must be the stabilizer of an IET component in the limit tree Y_{∞}. Hence, the quadratic test limit group, QT L, admits a free decomposition of the form:

QT L = Q ∗ U ∗ B_{1} ∗ … ∗ B_{t} ∗ F

where F_{k} < U, the B_{i}’s are non-cyclic freely indecomposable, and F is a (possibly trivial) free group. By iteratively modifying the specializations of the subgroup U ∗ B_{1} ∗ … ∗ B_{t} ∗ F, precisely as we modified the specializations of QT L in case Q is elliptic when acting on Y_{∞}, we end up with a quadratic test limit group (still denoted) QT L of the form: QT L = Q ∗ F_{k} ∗ F.

By the construction of a quadratic test limit group, the words w_{i}(x, y, a) = 1 in QT L = Q ∗ F_{k} ∗ F for all i, 1 ≤ i ≤ s, and the words v_{j}(x, y, a) ≠ 1 in QT L = Q ∗ F_{k} ∗ F for all j, 1 ≤ j ≤ r. Hence, there must exist a retract: η : QT L → Q ∗ F_{k}, for which: w_{i}(η(x), y, a) = 1 and v_{j}(η(x), y, a) ≠ 1 in Q ∗ F_{k}, for all possible indices i and j. Hence, we have found a formal solution for our given sentence, η(x) = u(y, a), in the free product Q ∗ F_{k}, which proves the first part of theorem 1.3. Suppose the given sentence is coefficient-free. Repeating our modification of the quadratic test limit group QT L in the coefficient-free case, we end up with a quadratic test limit group of the form: QT L = Q ∗ F, where F is a free group. In this case there must exist a retract: ν : QT L → Q, for which: w_{i}(η(x), y, a) = 1 and v_{j}(η(x), y, a) ≠ 1 in Q, for all possible indices i and j. Hence, we have found a coefficient-free formal solution for our given coefficient-free sentence, ν(x) = u(y), in the surface group Q, and we finally conclude the proof of theorem 1.3.

□

Theorem 1.3 generalizes Merzlyakov theorem to quadratic equations. To get a general form of Merzlyakov theorem we will also need a generalization to a free abelian group.

Proposition 1.8. Let F_{k} =< a_{1}, …, a_{k} > be a free group, and for some n > 1 let u_{(i,j)}(y) = [y_{i}, y_{j}] for 1 ≤ i < j ≤ n. Let the group Y_{n} =< y | u(y) > be the corresponding free abelian group on n generators. Let w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 be a system of equations over F_{k}, and let v_{1}(x, y, a), …, v_{r}(x, y, a) be a collection of words in the alphabet {x, y, a}. Suppose that the sentence:

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

is a truth sentence.

Then there exist finitely many free abelian groups of rank n: Z_{n}^{1}, …, Z_{n}^{ℓ} where Z_{n}^{i} =< z_{1}^{i}, …, z_{n}^{i} > for i = 1, …, ℓ, together with ℓ monomorphisms: ν_{i} : Y_{n} → Z_{n}^{i}, for which ν_{i}(Y_{n}) is a finite index subgroup in Z_{n}^{i}, and ℓ formal solutions {x_{i} = x_{i}(z^{i}, a)} with the following properties:

(i) Each of the words w_{j}(x_{i}(z^{i}, a), y, a) is the trivial word in the group Z_{n}^{i} ∗ F_{k}, and the sentence:

∃z^{i} ([z_{j}^{i}, z_{j′}^{i}] = 1, 0 ≤ j < j′ ≤ n) ∧ v_{1}(x(z^{i}, a), y, a) ≠ 1, …, v_{r}(x(z^{i}, a), y, a) ≠ 1

is a truth sentence in F_{k}. (ii) With each monomorphism ν_{i} : Y_{n} → Z_{n+1}^{i} one can naturally associate a

Diophantine system Σ_{i} of n equations in n variables, setting each of the y_{j}’s to be equal to a linear combination of the elements (z_{1}^{i}, …, z_{n}^{i}) corresponding to ν_{i}(y_{j}), where we view z_{1}^{i}, …, z_{n}^{i} as variables. With each system Σ_{i} we can associate the set of (integer) tuples (y_{1}, …, y_{n}) that are obtained as combinations of tuples of integers z_{1}^{i}, …, z_{n}^{i}. Since the homomorphisms ν_{i} map the group Y_{n} into a finite index subgroup of Z_{n}^{i}, the determinants of the systems Σ_{i} are non-zero, hence, for each system Σ_{i} this collection of the obtained (integer) tuples (y_{1}, …, y_{n}) is a finite index subgroup of the free abelian group of rank n, Z^{n}. We denote the corresponding subgroup C_{i}. Then the union of these subgroups C_{1}, …, C_{ℓ} covers the entire free abelian group of rank n, Z^{n}.

Proof: As in the proof of theorem 1.1, for each couple of positive integers (α, β) let:

λ([α, β]) = a_{1}a_{2}^{α}a_{1}a_{2}^{α+1} … a_{1}a_{2}^{β}.

For each positive integer m, we set γ_{m} to be: γ_{m} = λ([1, m]).

We say that a sequence of n+1-tuples of positive integers: {(q_{0}(j), q_{1}(j), …, q_{n}(j))}_{j=1}^{∞} is an abelian test sequence, if the sequence {q_{0}(j)}_{j=1}^{∞} is a strictly increasing sequence, and for every index j:

j · q_{0}(j) < q_{1}(j), j · q_{1}(j) < q_{2}(j), …, j · q_{n−1}(j) < q_{n}(j).

Given an abelian test sequence we set:

y_{1}(j) = γ_{q_{0}(j)}^{q_{1}(m_{j})}, …, y_{n}(j) = γ_{q_{0}(j)}^{q_{n}(j)}.

Since by the assumptions of the proposition, for every possible specialization of commuting y’s there exist specialization for the variables x, so that the given equalities w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 and inequalities v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1 are fulfilled, given the specializations y_{1}(j), …, y_{n}(j) we can choose x(j) to be the shortest possible element for which:

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

If the sequence of specializations {(x(j), y(j), a)} corresponding to an abelian test sequence converges, we call the obtained limit group an abelian test limit group. On the collection of abelian test limit group we define a natural partial order. We say that an abelian test limit group AT L_{1}(x, y, a) is bigger than an abelian test limit group AT L_{2}(x, y, a), if there exists a proper epimorphism η : AT L_{1}(x, y, a) → AT L_{2}(x, y, a) that maps the generators {x, y, a} of AT L_{1} to the corresponding generators of AT L_{2}. By the arguments used in constructing the Makanin-Razborov diagram of a limit group in (see lemmas 5.4 and 5.5 in [Se1]) there exist maximal abelian test limit groups with respect to the collection of all possible abelian test sequences, and in fact there is a canonical finite collection of maximal abelian test limit groups with respect to the entire collection of all possible abelian test sequences, which we denote: MAT L_{1}(x, y, a), …, MAT L_{ℓ}(x, y, a).

Since the maximal abelian test limit groups MAT L_{1}(x, y, a), …, MAT L_{ℓ}(x, y, a) were constructed using sequences of elements {(x(j), y_{1}(j), …, y_{n}(j))} for which the equalities w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 are fulfilled, the words:

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

represent the trivial words in the maximal abelian test limit groups:

MAT L_{1}(x, y, a), …, MAT L_{ℓ}(x, y, a)

and similarly the words v_{1}(x, y, a), …, v_{r}(x, y, a) represent non-trivial elements in the maximal abelian test limit groups. Since the sequences {y(j)} are abelian test sequences, for each maximal abelian test limit group, < y > < MAT L_{i} is a free abelian group of rank n. We continue by looking at a sequence of specializations {(x(j), y(j), a)} that converges into an action of one of a maximal abelian test limit group, which we denote MAT L(x, y, a), on some real tree T_{∞}. Suppose that the subgroup < y > < MAT L(x, y, a) fixes a point in the limit tree T_{∞}. If the real tree T_{∞} contains either an axial component, an IET component, or an edge with non-trivial (hence, abelian) stabilizer in its discrete part, then the shortening argument presented in [Se3], [Ri-Se1] and [Be] implies that there exists an automorphism τ of the limit group MAT L(x, y, a) for which:

(i) τ fixes (elementwise) the subgroup < y > and the coefficient group F_{k}.

(ii) for large enough j, w_{i}(τ(x(j)), y(j), a) = 1 for all i = 1, …, s and v_{j}(τ(x(j)), y(j), a) ≠

1 for all j = 1, …, r. (iii) τ(x(j)) is strictly shorter than x(j).

which clearly contradicts our choice of the specializations x(j) to be the shortest possible. Hence, the limit tree T_{∞} contains no axial components, no IET components and all the edges in the discrete part of T_{∞} have trivial stabilizers, which implies that the maximal abelian test limit group MAT L(x, y, a) admits a nontrivial free decomposition in which the subgroup < y, a > is contained in one of the factors.

In this case we continue as in the proof of theorem 1.3. Let MAT L = H ∗ B_{1} ∗ … ∗ B_{t} ∗ F be the most refined (Grushko’s) free decomposition of the limit group MAT L in which < y, a > < H, the factor F is a free group, and the factors B_{1}, …, B_{t} are freely indecomposable and non-cyclic. Suppose that t ≥ 1, i.e., that there exists a factor in this free decomposition that is not free and does not contain the subgroup < y, a >. In this case we modify the sequences of specializations {(x(j), y(j), a)} that factor through MAT L(x, y, a) so that they all factor through a finite collection of proper quotients of MAT L(x, y, a). For each index i, 1 ≤ i ≤ t, let b_{i} be a set of generators of the factor B_{i}, let h_{1}, …, h_{m} be a set of generators of H, and let f be a free basis of the free factor F (if this factor is non-trivial). Given a sequence {(x(j), y(j), a)} that factors through MAT L(x, y, a), with each specialization (x(j), y(j), a) from the given sequence, we associate the corresponding specialization of the generators h_{1}, …, h_{m}, which we denote h^{j}. With the specializations h^{j} we further associate specializations of the generating sets b^{1}, …, b^{t} in (new) free groups F_{1}, …, F_{t} in correspondence, where each such free group is isomorphic to the coefficient free group F_{k}. We denote these specializations b^{j}, and choose them to satisfy:

w_{1}(x(h^{j}, b^{j}, f), y(j), a) = 1, …, w_{s}(x(h^{j}, b^{j}, f), y(j), a) = 1 ∧
∧ v_{1}(x(h^{j}, b^{j}, f), y(j), a) ≠ 1, …, v_{r}(x(h^{j}, b^{j}, f), y(j), a) ≠ 1

in the free group F_{k} ∗ F_{1} ∗ …, F_{t} ∗ F, and among all such specializations of the generating set b^{1}, …, b^{t} we choose specializations for which the specialization of the generating set b^{t} is the shortest possible (with respect to the metric on the free group F_{t}).

By our standard arguments (lemmas 5.4 and 5.5 in [Se1]), the collection of all convergent sequences of these modified specializations {(x(h^{j}, b^{j}, f), y(j), a)} factor through a finite collection of maximal limit groups which we (still) denote MAT L_{1}(x, y, a), …, MAT L_{q}(x, y, a). Let {(x(h^{j}, b^{j}, f), y(j), a)} be a sequence that converges into one of these maximal limit groups MAT L_{i}(x, y, a). In particular, the sequence of specializations of the generating set b^{t} of the factor B_{t} converges into either the trivial group or it converges into an action of a limit group B̃_{t} on some real tree R_{∞}, and since all the specializations of b^{t} are specializations of the factor B_{t}, B̃_{t} is a quotient of B_{t}. Furthermore, since the specializations of b^{t} were chosen to be shortest possible, the real tree R_{∞} contains no axial components, no IET components, and the stabilizer of all the edges in its discrete part are trivial. Hence, B̃_{t} is either trivial or cyclic or free or it inherits a non-trivial free decomposition from its action on R_{∞}. Therefore, each of the limit groups MAT L_{i}(x, y, a) is a proper quotient of the original maximal abelian test limit group MAT L(x, y, a).

From the descending chain condition for limit groups ([Se1],5.1), after repeating this construction finitely many times, we may assume that the sequences of specializations {(x(j), y(j), a)} factor through a finite collection of maximal abelian test limit groups (still denoted) MAT L_{1}(x, y, a), …, MAT L_{ℓ}(x, y, a), and the Grushko’s free decomposition of each of these limit groups in which the subgroup < y, a > is elliptic is either trivial, or it is of the form: H ∗ F, where F is a free group, and < y, a > < H.

We continue by modifying the sequences of specializations that factor through the maximal abelian test limit groups MAT L_{1}(x, y, a), …, MAT L_{ℓ}(x, y, a). Let h_{1}, …, h_{m} be a set of generators of H, and let f be a free basis of the free factor F (if this factor is non-trivial). Given a sequence {(x(j), y(j), a)} that factors through MAT L_{i}(x, y, a), with each specialization (x(j), y(j), a) from the given sequence, we associate the corresponding specialization of the generators h_{1}, …, h_{m}, which satisfies:

w_{1}(x(h^{j}, f), y(j), a) = 1, …, w_{s}(x(h^{j}, f), y(j), a) = 1 ∧
∧ v_{1}(x(h^{j}, f), y(j), a) ≠ 1, …, v_{r}(x(h^{j}, f), y(j), a) ≠ 1

in the free group F_{k} ∗F, and among all such specializations of h_{1}, …, h_{m} we choose specializations that are the shortest possible (with respect to the metric on the free group F_{k}), which we denote h^{j}. The collection of all convergent sequences of these modified specializations factor through a finite collection of maximal abelian test limit groups that are quotients of MAT L_{i}(x, y, a). If they are proper quotients we continue with these modifications. By the descending chain condition for limit groups ([Se1],5.1), after finitely many steps we obtain finitely many maximal abelian test limit groups (still denoted) MAT L_{1}(x, y, a), …, MAT L_{ℓ}(x, y, a), each of the form MAT L_{i}(x, y, a) = H_{i} ∗ F_{i}, where F_{i} is a (possibly trivial) free group, < y, a > < H_{i} and H_{i} admits no (nontrivial) free decomposition in which the subgroup < y, a > is contained in a factor. Furthermore, for each sequence of specializations {(x(h^{j}, f), y(j), a)} that factor through a maximal test limit group MAT L_{i}(x, y, a), the specializations h^{j} of the generators of the factor H_{i} are the shortest possible among the specializations that satisfy the equalities and inequalities:

w_{1}(x(h^{j}, f), y(j), a) = 1, …, w_{s}(x(h^{j}, f), y(j), a) = 1 ∧
∧ v_{1}(x(h^{j}, f), y(j), a) ≠ 1, …, v_{r}(x(h^{j}, f), y(j), a) ≠ 1.

At this point we look at a sequence of specializations {(x(j), y(j), a)} that converges into a faithful action of a maximal test abelian limit groups MAT L_{i}(x, y, a) = H_{i} ∗ F_{i} on a (pointed) real tree (T_{∞}, t_{0}). Since the factor H_{i} is assumed to have no (non-trivial) free decomposition in which the subgroup < y, a > is elliptic, and for every index j, the specialization h^{j} of a (fixed) generating set of the factor H_{i} was chosen to be shortest possible, the subgroup < y, a > does not fix a point when acting on the limit tree T_{∞}. Furthermore, by the structure of an abelian test sequence, this implies that the subgroup < y_{1}, …, y_{n−1}, a > fixes the base point t_{0} ∈ T_{∞} when acting on the real tree T_{∞}, y_{n} acts hyperbolically on the real tree T_{∞}, and the (free abelian) subgroup < y_{1}, …, y_{n−1} > fixes the segment [t_{0}, y_{n}(t_{0})] ⊂ T_{∞}, where t_{0} is the base point of the limit tree T_{∞}.

Since the stabilizer of the segment [t_{0}, y_{n}(t_{0})] ⊂ T_{∞} is non-trivial, the segment [t_{0}, y_{n}(t_{0})] is either contained in an axial component of the tree T_{∞} or it is contained in the discrete part of T_{∞}, and all the edges that are contained in the segment [t_{0}, y_{n}(t_{0})] have a non-trivial stabilizer that contains the free abelian subgroup < y_{1}, …, y_{n−1} >, and these edge stabilizers stabilize (pointwise) the entire axis of y_{n} in T_{∞}.

In case the segment [t_{0}, y_{n}(t_{0})] is contained in an axial component of T_{∞}, the factor H_{i} < MAT L_{i} admits the amalgamated product H_{i} = V ∗_{Ab_{1}} Ab, where < y_{1}, …, y_{n−1} > < Ab_{1}, and y_{n} ∈ Ab but y_{n} ∉ Ab_{1}. In case the segment t_{0}, y_{n}(t_{0})] is contained in the discrete part of T_{∞}, the graph of groups associated with the action of H_{i} on the real tree T_{∞} contains a circle in which all the edge groups are some abelian subgroup Ab_{1}, < y_{1}, …, y_{n−1} > < Ab_{1}, and all the edges in the segment [t_{0}, y_{n}(t_{0})] are in the orbit of edges contained in this circle. Since y_{n} acts hyperbolically on T_{∞}, y_{n} ∉ Ab_{1}. In this case, the Bass-Serre generator, bs, associated with the circle in the graph of groups associated with the action of H_{i} on T_{∞} can be chosen to commute with the subgroup Ab_{1}, y_{n} ∈< Ab_{1}, bs >= Ab, and H_{i} admits an amalgamated product of the form: H_{i} = V ∗_{Ab_{1}} Ab.

Therefore, in both cases H_{i} = V ∗_{Ab_{1}} Ab, y_{1}, …, y_{n−1} ∈ Ab_{1}, y_{n} ∉ Ab_{1}, and the abelian group Ab is the direct sum: Ab = Ab_{1} + U for some abelian subgroup U < Ab. We continue by fixing a generating set for V, v_{1}, …, v_{m}. We further modify the sequences of specializations that factor through the maximal abelian test limit groups MAT L_{i}(x, y, a). Recall that MAT L_{i} = H_{i} ∗ F_{i}. Let f be a free basis of the free factor F_{i} (if this factor is non-trivial). Given a sequence {(x(j), y(j), a)} that factors through MAT L_{i}(x, y, a), with each specialization (x(j), y(j), a) from the given sequence, we associate the corresponding specialization of the generators v_{1}, …, v_{m}, which we denote v^{j}, and a specialization of the element z_{n}, denoted z_{n}^{j}, which satisfies:

w_{1}(x(v^{j}, z_{n}^{j}, f), y(j), a) = 1, …, w_{s}(x(h^{j}, z_{n}^{j}, f), y(j), a) = 1 ∧
∧ v_{1}(x(h^{j}, z_{n}^{j}, f), y(j), a) ≠ 1, …, v_{r}(x(h^{j}, z_{n}^{j}, f), y(j), a) ≠ 1

in the free group F_{k} ∗F_{i}, and among all such specializations of v_{1}, …, v_{m} we choose specializations that are the shortest possible (with respect to the metric on the free group F_{k}), which we denote v^{j}.

The collection of all convergent sequences of these modified specializations factor through a finite collection of maximal abelian test limit groups that are quotients of MAT L_{i}(x, y, a). By the descending chain condition for limit groups ([Se1],5.1), after finitely many steps of this ”uncovering” procedure, we obtain finitely many maximal abelian test limit groups (still denoted) MAT L_{1}(x, y, a), …, MAT L_{ℓ}(x, y, a), each of the form

MAT L_{i}(x, y, a) = F_{k} ∗ Ab_{i} ∗ F_{i}

where F_{i} is a (possibly trivial) free group, and < y_{1}, …, y_{n} > is a subgroup (of rank n) of the free abelian group Ab_{i}. By basic properties of f.g. free abelian groups, since for every index i, the subgroup < y_{1}, …, y_{n} > is a subgroup of rank n of the abelian group Ab_{i}, Ab_{i} can be written as a (possibly trivial) direct sum:

Ab_{i} = < z_{1}^{i}, …, z_{n}^{i} > + < u_{1}^{i}, …, u_{s_{i}}^{i} >

where < y_{1}, …, y_{n} > is a finite index subgroup in < z_{1}^{i}, …, z_{n}^{i} >, and the (possibly trivial) subgroup < u_{1}^{i}, …, u_{s_{i}}^{i} > is a direct summand of rank s.

By the construction of the maximal test abelian groups, MAT L_{i}(x, y, a), the words w_{1}(x, y, a), …, w_{s}(x, y, a) represent trivial words in MAT L_{i}(x, y, a), and each of the words v_{1}(x, y, a), …, v_{r}(x, y, a) represent a non-trivial element in MAT L_{i}(x, y, a). Hence, if for each index i, we denote the direct summand < z_{1}^{i}, …, z_{n}^{i} >, by rAb_{i}, then for each i, there must exist a retract:

η_{i} : MAT L_{i}(x, y, a) = F_{k} ∗ Ab_{i} ∗ F_{i} → F_{k} ∗ rAb_{i} ∗ F_{i}

obtained by mapping each of the basis elements u_{1}^{i}, …, u_{s}^{i} into multiples of the element y_{1}, for which the elements η_{i}(v_{1}(x, y, a)), …, η_{i}(v_{r}(x, y, a)) are non-trivial elements in η_{i}(MT L_{i}). We continue by replacing each of the maximal abelian test limit groups MAT L_{i}(x, y, a), by its retract η_{i}(MT L_{i}(x, y, a), and for brevity we (still) denote each of the obtained retracts MAT L_{i}(x, y, a).

Since the maximal abelian test limit groups MAT L_{1}(x, y, a), …, MAT L_{ℓ}(x, y, a) were constructed using sequences of elements {(x(j), y_{1}(j), …, y_{n}(j), a)} for which the inequalities:

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

are fulfilled, for each i, 1 ≤ i ≤ ℓ, there exists a specialization of the elements f_{1}, …, f_{d_{i}} for which there exists a specialization of the generators of the free abelian group < z_{1}^{i}, …, z_{n}^{i} > so that all the inequalities:

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

are fulfilled. Therefore, setting Z_{n}^{i} = rAb_{i}, we have found epimorphisms:

τ_{i} : MAT L_{i}(x, y, a) → F_{k} ∗ Z_{n}^{i}

for which:

(1) τ_{i} embeds the subgroup Y_{n} into a finite index subgroup of Z_{n}^{i}.

(2) the words w_{1}(x, y, a), …, w_{s}(x, y, a) are trivial in MAT L_{i}(x, y, a) for every i, hence, these words are mapped by τ_{i} to the trivial element in F_{k} ∗ Z_{n}^{i}.

(3) for each i there exists some specialization of z^{i} so that the inequalities v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1 are fulfilled.

The properties of the rank n abelian groups Z_{n}^{i} stated above prove part (i) of the proposition. With each monomorphism ν_{i} : Y_{n} → Z_{n}^{i} one can naturally associate a Diophantine system Σ_{i} of n equations in n variables, setting each of the y_{j}’s to be equal to a linear combination of the elements (z_{1}^{i}, …, z_{n}^{i}) corresponding to ν_{i}(y_{j}), where we view z_{1}^{i}, …, z_{n}^{i} as variables. With each system Σ_{i} we associate the set of (integer) tuples (y_{1}, …, y_{n}) that are obtained as combinations of tuples of integers z_{1}^{i}, …, z_{n}^{i}, which is a finite index subgroup of the free abelian group of rank n, that we denote C_{i}. Suppose that the union of the subgroups C_{i} does not cover the whole free abelian group of rank n, Z^{n}. Under this last assumption there must exist an element ŷ ∈ Z^{n}, so that ŷ ∉ C_{i} for i = 1, …, ℓ. If for each index i, the subgroup C_{i} is a subgroup of index ind_{i} of Z^{n}, then for every element v ∈ Z^{n}, the element:

ind_{1} · ind_{2} · . . . · ind_{ℓ} · v + ŷ ∉ C_{i}

for every index i, 1 ≤ i ≤ ℓ. Therefore, there exists an abelian test sequence of integers {(q_{0}(j), q_{1}(j), …, q_{n}(j))} for which there is no convergent subsequence of corresponding elements {(x(j), y(j), a)} that factors through any of the maximal abelian test limit groups MAT L_{1}(x, y, a), …, MAT L_{ℓ}(x, y, a), which contradicts their universal property.

□

For completeness we bring a formulation of proposition 1.8 for free abelian groups with constants, i.e., when the free abelian group Y_{n} is assumed to commute with a fixed element c_{1} ∈ F_{k}. The proof is essentially identical to the proof of proposition 1.8.

Proposition 1.9. Let F_{k} =< a_{1}, …, a_{k} > be a free group, and let u_{1}(y) = [c_{1}, y_{1}] … u_{n}(y) = [c_{1}, y_{n}] for some n > 1, c_{1} ∈ F_{k}, c_{1} ≠ 1, and u_{(i,j)} = [y_{i}, y_{j}] for 1 ≤ i < j ≤ n. W.l.o.g. we may assume that c_{1} has no non-trivial roots in F_{k}. Let the group CY_{n+1} =< c_{1}, y | u(y) > be the corresponding free abelian group on n + 1 generators. Let w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 be a system of equations over F_{k}, and let v_{1}(x, y, a), …, v_{r}(x, y, a) be a collection of words in the alphabet {x, y, a}. Suppose that the sentence:

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

is a truth sentence.

Then there exist finitely many free abelian groups of rank n+1: CZ_{n+1}^{1}, …, CZ_{n+1}^{ℓ} where CZ_{n+1}^{i} =< c_{1}, z_{1}^{i}, …, z_{n}^{i} > for i = 1, …, ℓ, together with ℓ monomorphisms ν_{i} : CY_{n+1} → CZ_{n+1}^{i} so that ν_{i}(c_{1}) = c_{1}, and ℓ formal solutions {x_{i} = x_{i}(z^{i}, a)} with the following properties:

(i) Each of the words w_{j}(x_{i}(z^{i}, a), y, a) is the trivial word in the group CZ_{n+1}^{i}∗_{<c_{1}>} F_{k}, and the sentence:

∃z^{i} u(z^{i}) = 1 ∧ v_{1}(x(z^{i}, a), y, a) ≠ 1, …, v_{r}(x(z^{i}, a), y, a) ≠ 1

is a truth sentence in F_{k}.

(ii) With each monomorphism ν_{i} : CY_{n+1} → CZ_{n+1}^{i} one can naturally associate a Diophantine system of equations, setting each of the y_{j}’s to be equal to a linear combination of the elements (c_{1}, z_{1}^{i}, …, z_{n}^{i}). Since the determinant of this system is non-zero, there exists a (finite index) subgroup U_{n}^{i} < Y_{n} =< y_{1}, …, y_{n} > and a constant vector a_{i} ∈ Y_{n} for which the solutions of the corresponding Diophantine system are all integers if and only if y = u + a_{i} where u ∈ U_{n}^{i}. Then the union of the cosets a_{1} + U_{n}^{1}, …, a_{ℓ} + U_{n}^{ℓ} cover the entire abelian group Y_{n}.

In the above theorems the sentences considered are defined over a free group (theorems 1.1,1.2), a surface group (theorem 1.3), and a free abelian group (propositions 1.8,1.9). To state a similar theorem for a general limit group we need to present the completion of a limit group associated with a given resolution of it. To define the completion of a limit group associated with a resolution, we first replace the canonical Makanin-Razborov diagram by the canonical strict Makanin-Razborov diagram.

Let Rlim(y, a) be a restricted limit group. The (canonical) Makanin-Razborov diagram of Rlim(y, a) gives a canonical collection of (Makanin-Razborov) resolutions, so that any specialization of the restricted limit group Rlim(y, a) factors through (at least) one of the Makanin-Razborov resolutions. Our first step in constructing the completion of a restricted limit group is to replace the canonical collection of Makanin-Razborov resolutions associated with a restricted limit group with a canonical collection of strict MR resolutions (strict MR resolutions are defined in ([Se1],5.11)).

Proposition 1.10. Let Rlim(y, a) be a restricted limit group. There exists a (canonical) collection of strict MR resolutions Res_{1}(y, a), …, Res_{s}(y, a) for which every specialization of Rlim(y, a) factors through (at least) one of the resolutions Res_{i}(y, a).

Proof: To get such a (canonical) collection of strict MR resolutions, we start with the canonical collection of Makanin-Razborov resolutions (the ones that appear in the Makanin-Razborov diagram of the restricted limit group Rlim(y, a)). We take each of the strict Makanin-Razborov resolutions from the Makanin-Razborov diagram of Rlim(y, a) to be one of the resolutions in our new collection, and replace those resolutions in the Makanin-Razborov diagram that are not strict MR resolutions. Let Res(y, a) be a resolution in the Makanin-Razborov diagram of Rlim(y, a) that is not a strict MR resolution. Let {Rlim_{j}(y, a)} be the restricted limit groups that appear along the resolution Res(y, a). For each level j, let ARlim_{j}(y, a) be the restricted limit group obtained from the collection of specializations of Rlim_{j}(y, a) that factor through (the relevant part of) the resolution Res(y, a). Since Res(y, a) is not a strict MR resolution, at least for some level j, ARlim_{j}(y, a) is a proper quotient of Rlim_{j}(y, a). Let j_{h} be the highest level for which ARlim_{j}(y, a) is a proper quotient of Rlim_{j}(y, a). We replace the resolution Res(y, a), by finitely many resolutions obtained in the following way:

(i) the top part of the obtained resolutions is identical with the top part of the resolution Res(y, a) starting at level j_{h} − 1 and above.

(ii) each of the new resolutions is obtained by starting with the top part of Res(y, a) and continuing along one of the resolutions that appear in the Makanin-Razborov diagram of the restricted limit group ARlim_{j_{h}}(y, a).

Clearly, every specialization that factors through the resolution Res(y, a) factors through (at least) one of the obtained resolutions.

We continue the construction of the strict Makanin-Razborov diagram with the obtained resolutions. Any resolution from the obtained collection which is a strict resolution, is taken to be a resolution in our collection of strict resolutions. If an obtained resolution is not strict, we replace it by finitely many resolutions obtained by the same procedure applied before for the resolution Res(y, a). Since a restricted limit group that appears along a resolution obtained by this procedure is a proper quotient of the previous limit group that appears along the same resolution, and since the procedure replaces a restricted limit group along a resolution by its proper quotient, the ascending chain condition for (restricted) limit groups ([Se1],5.1) implies that the procedure described above terminates in a finite time. By construction, every resolution obtained after the termination of the procedure is a strict resolution, and every specialization that factors through the restricted limit group Rlim(y, a) factors through at least one of the collection of strict resolutions we end up with.

□

We call the canonical collection of strict MR resolutions constructed in proposition 1.10, the (canonical) strict Makanin-Razborov diagram of the restricted limit group Rlim(y, a). For the purposes of our ”trail and error” procedure for quantifier elimination we need to construct completion of resolutions which are strict MR resolutions ([Se1],5.11), and are more general than the resolutions that appear in the strict Makanin-Razborov diagram of a limit group. To allow ”economical” construction of the completion, we need to restrict the construction of the completion to wellstructured resolutions.

Definition 1.11. Let F_{k} =< a_{1}, …, a_{k} > be a free group, let Rlim(y, a) be a restricted limit group defined over F_{k}, and let Res(y, a) be a strict MR resolution of Rlim(y, a) ([Se1],5.11). Suppose that the resolution Res(y, a) is given by a decreasing sequence of restricted limit groups:

Rlim(y, a) = Rlim_{0}(y, a) → Rlim_{1}(y, a) → … Rlim_{i}(y, a) → … →
… → Rlim_{ℓ}(y, a) =< f, a > ∗H^{ℓ}

where < f, a > is a free group generated by < f, a >, and H^{ℓ} is a free group. Let η_{i} : Rlim_{i}(y, a) → Rlim_{i+1}(y, a) be the canonical quotient maps. With each restricted limit group Rlim_{i}(y, a) that appears along the given restricted resolution Res(y, a), there is an associated (restricted) free decomposition:

Rlim_{i}(y, a) = R_{1}^{i} ∗ … ∗ R_{q(i)}^{i} ∗ F_{rk(i)}^{i} ∗ H^{i}

where F_{rk(i)}^{i} is a (possibly trivial) free group of rank rk(i), H^{i} is a (possibly trivial) free group, and the coefficient group F_{k} is contained in one of the factors R_{j}^{i}. With each factor R_{j}^{i} there is an associated (restricted, possibly trivial) abelian decomposition (graph of groups), and a corresponding restricted modular group. The associated restricted modular groups of each of the factors R_{j}^{i} is generated by the following families of automorphisms of R_{j}^{i} (cf. [Se1],8.4):

(i) Dehn twists along edges of the restricted abelian decomposition of R_{j}^{i}. If the coefficient group F_{k} is a subgroup of a factor R_{j}^{i}, then the Dehn twists are assumed to fix (elementwise) the vertex stabilized by the coefficient group F_{k} in the graph of groups associated with the factor R_{j}^{i}.

(ii) Dehn twists along essential s.c.c. in QH (quadratically hanging) vertex groups in the restricted abelian decomposition of R_{j}^{i}. Again, these Dehn twists are assume to fix (elementwise) the vertex stabilized by the coefficient group F_{k} if it is contained in a factor R_{j}^{i}.

(iii) Let A be an abelian vertex group in the restricted abelian decomposition of R_{j}^{i}. Let A_{1} < A be the subgroup generated by all edge groups connected to the vertex stabilized by A in the abelian decomposition of R_{j}^{i}. Every automorphism of A that fixes A_{1} (elementwise) can be naturally extended to an automorphism of the ambient limit group R_{j}^{i}, and this automorphism of the factor R_{j}^{i} can be assumed to fix the coefficient group F_{k} if it is contained in the factor R_{j}^{i}.

We say that the strict MR resolution Res(y, a) is a well-structured resolution if the following conditions hold:

(1) the quotient map η_{i} : Rlim_{i}(y, a) → Rlim_{i+1}(y, a) maps F_{rk(i)}^{i} monomorphically onto a free factor of F_{rk(i+1)}^{i+1} and H^{i} onto a free factor of H^{i+1}.

(2) If the factor R_{j}^{i} is not a closed surface group nor a free abelian group, then η_{i}(R_{j}^{i}) is a free product of (possibly) some non-free factors in the free decomposition of Rlim_{i+1}(y, a), and (possibly trivial) factors in some free decomposition of the free groups F_{rk(i+1)}^{i+1} and H^{i+1}. In the free decompositions of Rlim_{i+1}(y, a), F_{rk(i+1)}^{i+1} and H^{i+1}, the factors onto which a non-abelian, non-surface factor R_{j}^{i} is mapped are distinct from the factors onto which R_{j′}^{i} is mapped for j ≠ j′, and distinct from the factors η_{i}(H^{i}) and η_{i}(F_{rk(i)}^{i}.

(3) since we assume that the resolution Res(y, a) is a strict MR resolution, the quotient map η_{i} maps every non-abelian, non-QH vertex group and every (abelian) edge group in the abelian decompositions associated with a factor R_{i}^{j} monomorphically into Rlim_{i+1}(y, a), for all possible tuples (i, j). The image of a QH vertex group under a quotient map is non-abelian.

(4) Let Ab_{1}^{i}, …, Ab_{q(i)}^{i} be the (non-cyclic) abelian factors among the factors R_{j}^{i}. Then η_{i}(Ab_{u}^{i}) = C_{u}^{i}, C_{u}^{i} is a cyclic subgroup of H^{i+1}, and C_{1}^{i} ∗ … ∗ C_{q(i)}^{i} ∗ η_{i}(H^{i}) is a free factor in some free decomposition of the free group H^{i+1}.

(5) Let R_{j_{1}}^{i}, …, R_{j_{d(i)}}^{i} be the subset of the factors R_{j}^{i} that are isomorphic to (non-abelian) closed surface groups. Then the image of such factor, η_{i}(R_{j_{v}}^{i}) = H_{v}^{i}, H_{v}^{i} is a subgroup of H^{i+1}, and:

H_{1}^{i} ∗ … ∗ H_{d(i)}^{i} ∗ C_{1}^{i} ∗ … ∗ C_{q(i)}^{i} ∗ η_{i}(H^{i})

is a free factor in some free decomposition of the free group H^{i+1}.

(6) Let Q_{1}^{i}, …, Q_{s(i)}^{i} be the QH vertex groups in the abelian decompositions of the factors R_{j}^{i} that are non-abelian and not isomorphic to a closed surface group. For each QH subgroup Q_{t}^{i} let Λ_{Q_{t}^{i}} be the cyclic decomposition obtained from the abelian decomposition associated with the factor R_{j}^{i} containing the QH subgroup Q_{t}^{i}, by collapsing all the edges that are not connected to the QH subgroup Q_{t}^{i}. We say that the circumference of the QH subgroup Q_{t}^{i}, denoted Circum(Q_{t}^{i}), is the subgroup generated by Q_{t}^{i} and all the Bass-Serre generators connecting (some of) its boundary components to vertex groups in Λ_{Q_{t}^{i}}. For each QH subgroup Q_{t}^{i} let bd_{t,1}, …, bd_{t,c(t)} be its boundary components. Let η_{i}(Circum(Q_{t}^{i})) = V_{1} ∗…∗V_{m(t)} ∗H_{t}^{i} be the maximal (most refined) free decomposition inherited by η(Circum(Q_{t}^{i})) from the given free decomposition of Rlim_{i}(y, a) in which each of the images of the boundary elements η_{i}(bd_{t,n}) can be conjugated into one of the free factors V_{r}, and for each factor V_{r} there exists at least one image of a boundary element η_{i}(bd_{t,n}) that can be conjugated into it. Then H_{t}^{i} is a free group and:

H^{i+1} = H_{1}^{i} ∗ … ∗ H_{s(i)}^{i} ∗ C_{1}^{i} ∗ … ∗ C_{q(i)}^{i} ∗ η_{i}(H^{i})

and:

V_{1} ∗ … ∗ V_{m}(t) < R_{1}^{i+1} ∗ … ∗ R_{q(i+1)}^{i+1} ∗ F_{rk(i+1)}^{i+1}.

Note that every strict Makanin-Razborov resolution, i.e., a resolution in the strict Makanin-Razborov diagram constructed in proposition 1.10, is a well-structured resolution. Hence, proposition 1.10 allows us to restrict the construction of the completion to well-structured resolutions.

Definition 1.12. Let Res(y, a) be a well-structured resolution of a limit group Rlim(y, a). We construct the completion of the resolution Res(y, a), denoted Comp(Res)(z, y, a), iteratively from bottom to top. Keeping the notation of definition 1.11, suppose that the resolution Res(y, a) is given by a decreasing sequence of restricted limit groups:

Rlim(y, a) = Rlim_{0}(y, a) → Rlim_{1}(y, a) → … Rlim_{i}(y, a) → … →

… → Rlim_{ℓ}(y, a) =< f, a > ∗H^{ℓ}

where < f, a > is a free group generated by < f, a >, and H^{ℓ} is a free group. Let η_{i} : Rlim_{i}(y, a) → Rlim_{i+1}(y, a) be the canonical quotient maps. Res(y, a) is a wellstructured resolution, so with each restricted limit group Rlim_{i}(y, a) that appears along the given restricted resolution Res(y, a), there is an associated (restricted) free decomposition:

Rlim_{i}(y, a) = R_{1}^{i} ∗ … ∗ R_{q(i)}^{i} ∗ F_{rk(i)}^{i} ∗ H^{i}

where F_{rk(i)}^{i} is a (possibly trivial) free group of rank rk(i), H^{i} is a (possibly trivial) free group, and the coefficient group F_{k} is contained in one of the factors R_{j}^{i}. With each factor R_{j}^{i} there is an associated (restricted, possibly trivial) abelian decomposition (graph of groups), and a corresponding restricted modular group.

For presentation purposes we start by describing the construction of the completion assuming the resolution Res(y, a) is a minimal rank well-structured resolution, i.e., assuming that the terminal free group Rlim_{ℓ} = F_{rk(ℓ)}^{ℓ} ∗ H^{ℓ} is the coefficient group F_{k} (i.e., that F_{rk(ℓ)}^{ℓ} = F_{k} and H^{ℓ} is trivial), and then generalize the construction for arbitrary well-structured resolutions.

Suppose that Res(y, a) is a minimal rank well-structured resolution. Since Res(y, a) is of minimal rank, the free products associated with the various levels are trivial, i.e., Rlim_{i}(y, a) = R_{1}^{i} for 0 ≤ i ≤ ℓ − 1, none of these limit groups are abelian nor a closed surface group, and with Rlim_{i}(y, a) there is an associated graph of groups with (non-trivial) abelian edge groups. We construct the completion of Res(y, a) iteratively from bottom to top. We start by changing the ℓ−1-th limit group, Rlim_{ℓ−1}(y, a), to a limit group Comp(Rlim)_{ℓ−1} by modifying the abelian decomposition associated with Rlim_{ℓ−1}.

Let Λ^{ℓ−1} be the abelian decomposition associated with the ℓ − 1-th limit group Rlim_{ℓ−1}(y, a). To modify the limit group Rlim_{ℓ−1}(y, a) and its abelian decomposition, we start with the terminal (coefficient) free group Rlim_{ℓ}(y, a) = F_{k}. With each edge e in the graph of groups Λ^{ℓ−1} that connects two non-abelian, non-QH vertex groups we associate a generator g_{e}. Let G_{e} be the edge group associated with such an edge in Λ^{ℓ−1}. We set the group G_{1} to be the group generated by the terminal group Rlim_{ℓ}(y, a) together with the additional elements {g_{e}}. To define G_{1} we add relations that force each of the additional generators g_{e} to commute with the maximal cyclic subgroup in F_{k} that contain the image of G_{e} under η_{ℓ−1}, η_{ℓ−1}(G_{e}). For any pair of edges e_{1}, e_{2}, for which η_{ℓ−1}(G_{e_{1}}) commutes with η_{ℓ−1}(G_{e_{2}}), we further add the relation [g_{e_{1}}, g_{e_{2}}] = 1. Hence, G_{1} is obtained from Rlim_{ℓ} = F_{k} by adding some free abelian groups amalgamated along (maximal) cyclic edge groups.

We continue by modifying G_{1} by adding new generators associated with (noncyclic) abelian vertex groups in Λ^{ℓ−1}. With each non-cyclic abelian vertex group Ab_{n} of rank n in the cyclic decomposition Λ^{ℓ−1} that is connected to some nonabelian vertex group by an edge with (maximal) cyclic stabilizer G_{Ab_{n}}, we associate new generators ab_{1}, …, ab_{n}. We modify G_{1} by adding all the new generators to it, together with relations that force ab_{1} to be equal to the corresponding generator of η_{ℓ−1}(Ab_{n}) < F_{k} < G_{1}, and commutant relations that force the other new generators to commute with the centralizer in G_{1} of the image of Ab_{n} in F_{k}. Therefore, we ended this second modification with a group G_{2}, that admits a canonical graph of groups composed of one vertex stabilized by the coefficient group F_{k}, and (possibly) several additional vertices, each stabilized by a non-cyclic free abelian group and connected to the vertex stabilized by F_{k} with a single edge with (maximal) cyclic stabilizer.

We continue by adding QH vertex groups corresponding to the QH vertex groups in Λ^{ℓ−1} to the group G_{2}. Let Q_{1}, …, Q_{u} be the QH vertex groups in Λ^{ℓ−1}. Let Q′_{1}, …, Q′_{u} be QH vertex group isomorphic to Q_{1}, …, Q_{u} in correspondence. With G_{2} and the QH subgroups Q′_{1}, …, Q′_{u} we associate a graph of groups, starting with the graph of groups associated with the group G_{2}, and adding new vertices for each of the vertex groups Q′_{1}, …, Q′_{u}. For each boundary component bd′ of a QH vertex group Q′_{j}, we add an edge connecting the vertex stabilized by Q′_{j} to the vertex stabilized by Rlim_{ℓ}(y, a) = F_{k}, and identifying the cyclic subgroup generating by bd′ to the image in F_{k} of the corresponding boundary component bd of the QH vertex group Q_{j} in Λ^{ℓ−1}, η_{ℓ−1}(bd).

Performing all these operations, we end up with one graph of groups with cyclic edge stabilizers, one vertex stabilized by Rlim_{ℓ}(y, a) = F_{k}, (possibly) few vertices with free abelian vertex groups connected to the (distinguished) vertex stabilized by F_{k} with an edge with (maximal) cyclic stabilizer, and (possibly) few vertices with QH vertex groups, whose boundary components are all connected to the vertex stabilized by F_{k}. We call the fundamental group of this graph of groups, the completion of Rlim_{ℓ−1}(y, a), and denote it Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a). We call the graph of groups, the completed decomposition of Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a), and with it we naturally associate the completed modular group (inherited from the modular group of Rlim_{ℓ−1}(y, a).

Lemma 1.13. The ℓ − 1-th limit group Rlim_{ℓ−1}(y, a) (canonically) embeds into the completed limit group Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a):

ν_{ℓ−1} : Rlim_{ℓ−1}(y, a) → Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a).

Furthermore, the quotient map η_{ℓ−1} : Rlim_{ℓ−1}(y, a) → Rlim_{ℓ}(y, a) naturally extends to a quotient map:

Comp(η)_{ℓ−1} : Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a) → Rlim_{ℓ}(y, a) = F_{k}.

Proof: The extension of the quotient map η_{ℓ−1} : Rlim_{ℓ−1}(y, a) → Rlim_{ℓ}(y, a) to a quotient map:

Comp(η)_{ℓ−1} : Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a) → Rlim_{ℓ}(y, a) = F_{k}

is natural from the construction of the completion. To construct the natural embedding of Rlim_{ℓ−1} into the completion, Comp(Rlim)_{ℓ−1}, we look at the following example. Let Rlim_{ℓ} = F_{k}, and let the abelian decomposition of Rlim_{ℓ−1} be Rlim_{ℓ−1} = A ∗_{C} B, where C is cyclic, and A and B are some free groups. In this case the quotient map η_{ℓ−1} maps A, B and C isomorphically into F_{k}. Let < c_{1} > < F_{k} be the maximal cyclic subgroup in F_{k} that contains η_{ℓ−1}(C). In this case the completion has the form:

Comp(Rlim)_{ℓ−1} = F_{k}∗_{<c_{1}>} < c_{1}, t >

and the natural embedding ν_{ℓ−1} maps Rlim_{ℓ−1} isomorphically onto the subgroup:

η_{ℓ−1}(A) ∗_{<c_{1}>} tη_{ℓ−1}(B)t^{−1}

of the completion, Comp(Rlim)_{ℓ−1}. The generalization of the natural embedding ν_{ℓ−1} to an arbitrary ℓ − 1 limit group is rather straightforward.

□

. Although the image of Rlim_{ℓ−1}(y, a) in the completion Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a) under the canonical embedding ν_{ℓ−1}, can be expressed as words in the generators (z_{ℓ−1}, a) we prefer to specifically note this image by changing the notation of the completion to Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, y, a).

We continue the construction of the completed resolution iteratively (bottom to top). At each step, i, we start with the completed limit group constructed at the lower level, Comp(Rlim)_{i+1}(z_{i+1}, y, a), and its associated completed abelian decomposition, and construct Comp(Rlim)_{i}(z_{i}, y, a), its associated completed decomposition and completed modular groups, the natural embedding:

ν_{i} : Rlim_{i}(y, a) → Comp(Rlim)_{i}(z_{i}, y, a)

and the completed quotient map: Comp(η)_{i} : Comp(Rlim)_{i} → Comp(Rlim)_{i+1}. We start the construction of the completed limit group Comp(Rlim)_{i}(z_{i}, y, a) with the completed limit group Comp(Rlim)_{i+1}(z_{i+1}, y, a). Let Λ^{i} be the abelian decomposition associated with the i-th limit group Rlim_{i}(y, a) in the well-structured resolution Res(y, a). With each edge with abelian stabilizer that connects two nonabelian, non-QH vertex groups in the abelian decomposition Λ_{i} we associate a new generator g_{e}. We set G_{1} to be a group generated by Comp(Rlim)_{i+1}(z_{i+1}, y, a), and all the new generators {g_{e}} corresponding to these edges in Λ^{i}. To define G_{1} we further add commutant relations that force each of the new variables g_{e} to commute with the centralizer of the image under ν_{i+1} ∘ η_{i} of the abelian stabilizer of the edge it is associated with in Comp(Rlim)_{i+1}(z_{i+1}, y, a), and with other generators g_{e′} for which the image of the edge group associated with them in Comp(Rlim)_{i+1}(z_{i+1}, y, a) can be conjugated to commute with the image of the edge group associated with g_{e} in Comp(Rlim)_{i+1}(z_{i+1}, y, a). Hence, G_{1} is the fundamental group of a graph of groups having one (distinguished) vertex stabilized by Comp(Rlim)_{i+1}(z_{i+1}, y, a), and (possibly) few other vertices with free abelian stabilizers, each connected to the distinguished vertex with a unique edge, and the stabilizer of that edge is the centralizer of the image of the corresponding edge group in Λ^{i} in Comp(Rlim)_{i+1}(z_{i+1}, y, a).

We continue by modifying G_{1} by adding new generators associated with (noncyclic) abelian vertex groups in Λ^{i}. With each non-cyclic abelian vertex group Ab_{n} of rank n in the cyclic decomposition Λ^{i}, we associate new generators ab_{1}, …, ab_{n}. We modify G_{1} by adding all the new generators to it, together with relations that force the subgroup of Ab_{n} generated by the edge groups connected to Ab_{n} in Λ^{i}, to be equal to its image under ν_{i+1} ∘ η_{i} in Comp(Rlim)_{i+1}(z_{i+1}, y, a), and relations that force ab_{1}, …, ab_{n} to commute and to commute with the centralizer of the image of the subgroup of Ab_{n} generated by the edge groups connected to Ab_{n} in Λ^{i} in G_{1}. Therefore, we ended this second modification with a group G_{2}, that admits a canonical graph of groups composed of one vertex stabilized by Comp(Rlim)_{i+1}(z_{i+1}, y, a), and (possibly) several additional vertices, each stabilized by a non-cyclic free abelian group and connected to the vertex stabilized by Comp(Rlim)_{i+1}(z_{i+1}, y, a) by a single edge with abelian stabilizer.

We continue by adding QH vertex groups corresponding to the QH vertex groups in Λ^{i} to the group G_{2}. Let Q_{1}, …, Q_{u} be the QH vertex groups in Λ^{i}. Let Q′_{1}, …, Q′_{u} be QH vertex group isomorphic to Q_{1}, …, Q_{u} in correspondence. With G_{2} and the QH subgroups Q′_{1}, …, Q′_{u} we associate a graph of groups, starting with the graph of groups associated with the group G_{2}, and adding new vertices for each of the vertex groups Q′_{1}, …, Q′_{u}. For each boundary component bd′ of a QH vertex group Q′_{j}, we add an edge connecting the vertex stabilized by Q′_{j} to the vertex stabilized by Comp(Rlim)_{i+1}(z_{i+1}y, a), and identifying the cyclic subgroup generated by bd′ to the image in Comp(Rlim)_{i+1}(z_{i+1}, y, a) under ν_{i+1} ∘ η_{i}, of the corresponding boundary component bd of the QH vertex group Q_{j} in Λ^{i}.

Performing all these operations, we end up with one graph of groups with abelian edge stabilizers, one (distinguished) vertex stabilized by Comp(Rlim)_{i+1}(z_{i+1}y, a), (possibly) few vertices with free abelian vertex groups connected to the (distinguished) vertex with an edge with (maximal) cyclic stabilizer, and (possibly) few vertices with QH vertex groups, whose boundary components are all connected to the distinguished vertex. We call the fundamental group of this graph of groups, the completion of Rlim_{i}(y, a), and denote it Comp(Rlim)_{i}(z_{i}, a). We call the graph of groups, the completed decomposition of Comp(Rlim)_{i}(z_{i}, a), and with it we naturally associate the completed modular group (inherited from the modular group of Rlim_{i}(y, a). In a similar way to lemma 1.13, with the completion of Rlim_{i}(y, a) we associate two natural maps, a canonical embedding:

ν_{i} : Rlim_{i}(y, a) → Comp(Rlim)_{i}(z_{i}, a)

and a quotient map:

Comp(η)_{i} : Comp(Rlim)_{i}(z_{i}, a) → Comp(Rlim)_{i+1}(z_{i+1}y, a).

Although the image of Rlim_{i}(y, a) in the completion Comp(Rlim)_{i}(z_{i}, a) under the canonical embedding ν_{i}, can be expressed as words in the generators (z_{i}, a) we prefer to specifically note this image by changing the notation of the completion to Comp(Rlim)_{i}(z_{i}, y, a).

Finally, we say that Comp(Rlim)_{0}(z_{0}, y, a) is the completed limit group of the minimal rank well-structured resolution Res(y, a), and the sequence of completed limit groups Comp(Rlim)_{i}(z_{i}, y, a), 1 ≤ i ≤ ℓ, together with their associated completed decompositions is the completed resolution of Res(y, a), which we denote Comp(Res)(z_{0}, y, a).

So far we have presented the construction of the completion for minimal rank well-structured resolutions Res(y, a). At this point we generalize the construction to an arbitrary well-structured resolution. The terminal limit group of the well-structured resolution Res(y, a) is Rlim_{ℓ}(y, a) = F_{rk(ℓ)}^{ℓ} ∗ H^{ℓ}. We start the construction of the completion of Res(y, a) by setting Comp(Rlim)_{ℓ}(z_{ℓ}, a) to be: Comp(Rlim)_{ℓ}(z_{ℓ}, a) = F_{rk(ℓ)}^{ℓ}. We set G_{1} to be the free product of Comp(Rlim)_{ℓ}(z_{ℓ}, a) with those factors among the factors R_{j}^{ℓ−1} in the given free decomposition of Rlim_{ℓ−1}(y, a) that are isomorphic to either nonabelian closed surface groups: S_{1}^{ell−1}, …, S_{d(ℓ−1)}^{ℓ−1} or non-cyclic free abelian groups: Ab_{1}^{ℓ−1}, …, AB_{q(ℓ−1)}^{ℓ−1}.

We continue the construction of the completion by considering the abelian decompositions associated with the various factors R_{j}^{ℓ−1} that are not abelian nor closed surface groups. Let Λ_{j}^{ℓ−1} be the abelian decomposition associated with such factor R_{j}^{ℓ−1}. With each edge e in one of the graph of groups Λ_{j}^{ℓ−1} that connects two nonabelian, non-QH vertex groups we associate a generator g_{e}. Let G_{e} be the edge group associated with such an edge in Λ_{j}^{ℓ−1}. We set the group G_{2} to be the group generated by G_{1} together with the additional elements {g_{e}}. To define G_{2} we add relations that force each of the additional generators g_{e} to commute with the maximal cyclic subgroup in Comp(Rlim)_{ℓ}(z_{ℓ}, a) that contain the image of G_{e} under η_{ℓ−1}, η_{ℓ−1}(G_{e}). For any pair of edges e_{1}, e_{2}, for which η_{ℓ−1}(G_{e_{1}}) commutes with η_{ℓ−1}(G_{e_{2}}), we further add the relation [g_{e_{1}}, g_{e_{2}}] = 1. Hence, G_{2} is obtained from G_{1} by adding some free abelian groups amalgamated along (maximal) cyclic edge groups. We continue by modifying G_{2} by adding new generators associated with (non-cyclic) abelian vertex groups in the decompositions Λ_{j}^{ℓ−1}. With each non-cyclic abelian vertex group Ab_{n} of rank n in a cyclic decomposition Λ_{j}^{ℓ−1} that is connected to some non-abelian vertex group by an edge with (maximal) cyclic stabilizer G_{Ab_{n}}, we associate new generators ab_{1}, …, ab_{n}. We modify G_{2} by adding all the new generators to it, together with relations that force ab_{1} to be equal to the corresponding generator of η_{ℓ−1}(Ab_{n}) < Comp(Rlim)_{ℓ}(z_{ℓ}, a) < G_{2}, and commutant relations that force the other new generators to commute with the centralizer in G_{2} of the image of Ab_{n} in Comp(Rlim)_{ℓ}(z_{ℓ}, a). Therefore, we ended this second modification with a group G_{3}, that admits a canonical free decomposition in which with a single factor we associate a graph of groups composed of one vertex stabilized by a factor of Comp(Rlim)_{ℓ}(z_{ℓ}, a), and (possibly) several additional vertices, each stabilized by a non-cyclic free abelian group and connected to the vertex stabilized by the factor of Comp(Rlim)_{ℓ}(z_{ℓ}, a) by a single edge with (maximal) cyclic stabilizer.

We continue by adding QH vertex groups corresponding to the QH vertex groups in the decompositions Λ_{j}^{ℓ−1} to the group G_{3}. Let U_{1} ∗ … ∗ U_{b} be the most refined free decomposition of G_{3} in which the images under η_{ℓ−1} of all the edge groups and all the non-QH vertex groups in the abelian decompositions Λ_{j}^{ℓ−1} are elliptic. Let Q_{1}, …, Q_{u} be the QH vertex groups in the various graph of groups Λ_{j}^{ℓ−1}. Let Q′_{1}, …, Q′_{u} be QH vertex group isomorphic to Q_{1}, …, Q_{u} in correspondence. With G_{3} and the QH subgroups Q′_{1}, …, Q′_{u} we associate a graph of groups, starting with the free decomposition U_{1} ∗ … ∗ U_{b} of G_{3}, and adding new vertices for each of the vertex groups Q′_{1}, …, Q′_{u}. For each boundary component bd′ of a QH vertex group Q′_{t}, we add an edge connecting the vertex stabilized by Q′_{t} to the vertex stabilized by the vertex stabilized by the factor U_{s} into which the corresponding boundary component bd of Q_{t} is mapped by η_{ℓ−1}. We further identify the cyclic subgroup generated by bd′ with the image in U_{b} of the corresponding boundary component bd under η_{i}.

We call the fundamental group of this graph of groups, the completion of Rlim_{ℓ−1}(y, a), and denote it Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a). We call the graph of groups, the completed decomposition of Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a), and with it we naturally associate the completed modular group (inherited from the modular group of Rlim_{ℓ−1}(y, a). In a similar way to lemma 1.13, the ℓ − 1-th limit group Rlim_{ℓ−1}(y, a) (canonically) embeds into the completed limit group Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a):

ν_{ℓ−1} : Rlim_{ℓ−1}(y, a) → Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a).

Furthermore, the quotient map η_{ℓ−1} : Rlim_{ℓ−1}(y, a) → Rlim_{ℓ}(y, a) naturally extends to a quotient map:

Comp(η)_{ℓ−1} : Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a) → Rlim_{ℓ}(y, a) = F_{k}.

Also, we prefer to note the image of Rlim_{ℓ−1}(y, a) in the completion Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, a) under the canonical embedding ν_{ℓ−1}, so we change the notation of the completion to Comp(Rlim)_{ℓ−1}(z_{ℓ−1}, y, a).

As in the minimal rank case, we continue the construction of the completed resolution iteratively (bottom to top). At each step, i, we start with the completed limit group constructed at the lower level, Comp(Rlim)_{i+1}(z_{i+1}, y, a), and its associated completed abelian decomposition, and construct Comp(Rlim)_{i}(z_{i}, y, a), its associated completed decomposition and completed modular groups, the natural embedding: ν_{i} : Rlim_{i}(y, a) → Comp(Rlim)_{i}(z_{i}, y, a), and the completed quotient map: Comp(η)_{i} : Comp(Rlim)_{i} → Comp(Rlim)_{i+1}. We start the construction of the completed limit group Comp(Rlim)_{i}(z_{i}, y, a) with the completed limit group Comp(Rlim)_{i+1}(z_{i+1}, y, a). We set G_{1} to be the free product of Comp(Rlim)_{i+1}(z_{i+1}, a) with those factors among the factors R_{j}^{i} in the given free decomposition of Rlim_{i}(y, a) that are isomorphic to either non-abelian closed surface groups: S_{1}^{i}, …, S_{d(i)}^{i}, or to abelian groups: Ab_{1}^{i}, …, Ab_{q(i)}^{i}.

We continue the construction of the completion by considering the abelian decompositions associated with the various factors R_{j}^{i} that are not abelian nor closed surface groups. Let Λ_{j}^{i} be the abelian decomposition associated with such factor R_{j}^{i}. With each edge e in one of the graph of groups Λ_{j}^{i} that connects two non-abelian, non-QH vertex groups we associate a generator g_{e}. Let G_{e} be the edge group associated with such an edge in Λ_{j}^{i}. We set the group G_{2} to be the group generated by G_{1} together with the additional elements {g_{e}}. To define G_{2} we add relations that force each of the additional generators g_{e} to commute with the centralizer of the image (under ν_{i+1} ∘ η_{i}) of the associated edge group G_{e} in Comp(Rlim)_{+1i}(z_{i+1}, y, a), ν_{i+1} ∘ η_{i}(G_{e}). For any pair of edges e_{1}, e_{2}, for which ν_{i+1} ∘ η_{i}(G_{e_{1}}) (can be conjugated to) commute with ν_{⊂+1} ∘ η_{i}(G_{e_{2}}), we further add the relation [g_{e_{1}}, g_{e_{2}}] = 1. Hence, G_{2} is obtained from G_{1} by adding some free abelian groups amalgamated along (non-trivial) subgroups of smaller rank.

We continue by modifying G_{2} by adding new generators associated with (noncyclic) abelian vertex groups in the various abelian decompositions Λ_{j}^{i}. With each non-cyclic abelian vertex group Ab_{n} of rank n in one of the abelian decompositions Λ^{i_{j}}, that is connected to some non-abelian vertex group, we associate new generators ab_{1}, …, ab_{n}. We modify G_{2} by adding all the new generators to it, together with relations that force the subgroup of Ab_{n} generated by the edge groups connected to Ab_{n} in Λ_{j}^{i}, to be equal to its image under ν_{i+1}∘η_{i} in Comp(Rlim)_{i+1}(z_{i+1}, y, a), and relations that force ab_{1}, …, ab_{n} to commute and to commute with the centralizer of the image of the subgroup of Ab_{n} generated by the edge groups connected to Ab_{n} in Λ_{j}^{i} in G_{2}. Therefore, we ended this part with a group G_{3}, that admits a canonical free decomposition in which with a single factor we associate a graph of groups composed of one vertex stabilized by a factor of Comp(Rlim)_{i+1}(z_{i+1}, y, a), and (possibly) several additional vertices, each stabilized by a non-cyclic free abelian group and connected to the vertex stabilized by the factor of Comp(Rlim)_{i+1}(z_{i+1}, y, a) by a single edge with (non-trivial) abelian stabilizer.

We continue by adding QH vertex groups corresponding to the QH vertex groups in the decompositions Λ_{j}^{i} to the group G_{3}. Let U_{1} ∗ … ∗ U_{b} be the most refined free decomposition of G_{3} in which the images under ν_{i+1} ∘ η_{i} of all the edge groups and all the non-QH vertex groups in the abelian decompositions Λ_{j}^{i} are elliptic. Let Q_{1}, …, Q_{u} be the QH vertex groups in the various graph of groups Λ_{j}^{i}. Let Q′_{1}, …, Q′_{u} be QH vertex group isomorphic to Q_{1}, …, Q_{u} in correspondence. With G_{3} and the QH subgroups Q′_{1}, …, Q′_{u} we associate a graph of groups, starting with the free decomposition U_{1} ∗ … ∗ U_{b} of G_{3}, and adding new vertices for each of the vertex groups Q′_{1}, …, Q′_{u}. For each boundary component bd′ of a QH vertex group Q′_{t}, we add an edge connecting the vertex stabilized by Q′_{t} to the vertex stabilized by the vertex stabilized by the factor U_{s} into which the corresponding boundary component bd of Q_{t} is mapped by ν_{i+1} ∘ η_{i}. We further identify the cyclic subgroup generated by bd′ with the image in U_{b} of the corresponding boundary component bd under ν_{i+1} ∘ η_{i}.

We call the fundamental group of this graph of groups, the completion of Rlim_{i}(y, a), and denote it Comp(Rlim)_{i}(z_{i}, a). We call the graph of groups, the completed decomposition of Comp(Rlim)_{i}(z_{i}, a), and with it we naturally associate the completed modular group (inherited from the modular group of Rlim_{i}(y, a). In a similar way to lemma 1.13, the i-th limit group Rlim_{i}(y, a) (canonically) embeds into the completed limit group Comp(Rlim)_{i}(z_{i}, a):

ν_{i} : Rlim_{i}(y, a) → Comp(Rlim)_{i}(z_{i}, a).

Furthermore, the quotient map η_{i} : Rlim_{i}(y, a) → Rlim_{i+1}(y, a) naturally extends to a quotient map:

Comp(η)_{i} : Comp(Rlim)_{i}(z_{i}, a) → Comp(Rlim)_{i+1}(z_{i+1}, y, a).

Also, we prefer to note the image of Rlim_{i}(y, a) in the completion Comp(Rlim)_{i}(z_{i}, a) under the canonical embedding ν_{i}, so we change the notation of the completion to Comp(Rlim)_{i}(z_{i}, y, a). Finally, we say that Comp(Rlim)_{0}(z_{0}, y, a) is the completed limit group of the minimal rank well-structured resolution Res(y, a), and the sequence of completed limit groups Comp(Rlim)_{i}(z_{i}, y, a), 1 ≤ i ≤ ℓ, together with their associated completed decompositions is the completed resolution of Res(y, a), which we denote Comp(Res)(z_{0}, y, a).

The following are some basic properties of the completion of a well-structured resolution. All follow in a rather straightforward way from the construction of the completion, so we omit their proof. Still they are crucial in obtaining formal solutions defined over the completion of a well-structured resolution of a restricted limit group.

Lemma 1.14. Let Res(y, a) be a well-structured resolution of a restricted limit group Rlim(y, a), and let Comp(Res)(z, y, a) be its completed resolution. Then:

(i) If we replace each of the completed limit groups Comp(Rlim)_{i}(z, y, a) with the group Comp(Rlim)_{i}(z, y, a) ∗ H^{i}, and change the completed quotient map Comp(η)_{i} accordingly (i.e., Comp(η)_{i} will map the additional free factor H^{i} isomorphically onto a factor of H^{i+1}, and the additional surface and abelian factors onto factors of H^{i+1}), then the completed resolution Comp(Res)(z, y, a) is a well-structured resolution.

(ii) a generator of a cyclic edge group connecting two non-QH vertex groups in the completed decomposition of one of the factors of the completed limit group Comp(Rlim)_{i}(z, y, a) for some i, is projected by some composition of maps:

Comp(η)_{i} ∘ … ∘ Comp(η)_{i′} : Comp(Rlim)_{i}(z, y, a) → Comp(Rlim)_{i′−1}(z, y, a)

to either an element with no root that is not contained in one of the factors of Comp(Rlim)_{i′}(z, y, a), a hyperbolic element with no root in the completed decomposition of Comp(Rlim)_{i′}(z, y, a) or to a non-boundary element with no root in a QH vertex in a completed decomposition.

(iii) The subgroup < y, a > < Comp(Rlim)(z, y, a) is mapped onto Comp(Rlim)_{ℓ} = F_{rk(ℓ)}^{ℓ} by the composition of the quotient maps. The rank of the completed resolution, Comp(Res(z, y, a)), is at most the rank of the well-structured resolution Res(y, a).

(iv) For any specialization (y_{0}, a) of the restricted limit group Rlim(y, a) that factors through the resolution Res(y, a), there exists some specialization z_{0} so that (z_{0}, y_{0}, a) is a specialization of the completed limit group Comp(Rlim)(z, y, a) that factors through the completed resolution Comp(Res)(z, y, a).

Completed resolutions are defined in order to enable one to construct formal solutions. If all the decompositions associated with the various levels of a wellstructured resolution contains no (non-cyclic) abelian vertex groups, then it is indeed possible to construct formal solutions defined over the completed resolution.

However, in the presence of (non-cyclic) abelian vertex groups we still need to define a closure of a resolution, and a finite collection of such closures which forms a covering closure.

Definition 1.15. Let Res(y, a) be a well-structured resolution and let Comp(Res)(z, y, a) be its completion. Let Ab_{1}, …, Ab_{d} be the non-conjugate, non-cyclic, maximal abelian subgroups that appear along the completion, Comp(Res)(z, y, a) and are mapped onto a non-cyclic abelian factor in a free decomposition associated with one of the levels of the completion. Let P Ab_{1}, …, P Ab_{pd} be the non-conjugate, non-cyclic, maximal pegged abelian groups that appear along the completed resolution, i.e., maximal non-cyclic abelian subgroups in Comp(Rlim)(z, y, a), that are mapped onto a non-cyclic abelian vertex group in some abelian decomposition associated with some level of the completed resolution Comp(Res)(z, y, a), and this abelian vertex is connected to the other vertices of the completed decomposition of that level by an edge with (maximal) cyclic stabilizer. We call the maximal cyclic subgroup of a pegged abelian group connecting it to the other vertices of the corresponding completed decomposition, the peg of the pegged abelian group P Ab.

Let S_{1}, …, S_{d} be free abelian groups so that Ab_{1} < S_{1}, …, Ab_{d} < S_{d} are subgroups of finite index. Let P S_{1}, …, P S_{pd} be free abelian groups so that P Ab_{1} < P S_{1}, …, P Ab_{pd} < P S_{pd} are subgroups of finite index, and the pegs peg_{1}, …, peg_{pd} are primitive elements in the ambient free abelian groups P S_{1}, …, P S_{pd}. A closure of the completed resolution Comp(Res)(z, y, a) is obtained by replacing the free abelian groups Ab_{1}, …, Ab_{d} by the free abelian groups S_{1}, …, S_{d}, and the pegged abelian groups P Ab_{1}, …, P Ab_{pd} by the free abelian groups P S_{1}, …, P S_{pd} in correspondence, along the entire completed resolution, i.e., from the top level through the bottom level in which a subgroup of the pegged abelian group appears along the completed resolution. We say that the free abelian groups S_{1}, …, S_{d} and P S_{1}, …, P S_{pd} are the extension of the pegged abelian groups P Ab_{1}, …, P Ab_{pd} in correspondence. We denote a closure of the completed resolution by Cl(Res)(s, z, y, a), and the corresponding limit group by Cl(Rlim)(s, z, y, a). Naturally, Comp(Rlim)(z, y, a) is embedded in Cl(Rlim)(s, z, y, a).

By construction, properties (i)-(iii) of lemma 1.14 which are valid for the completion, remain valid for a closure. However, in general only a subset of the specializations that factor through a resolution can be extended to specializations that factor through a closure of it. Therefore, we need to generalize what we did in propositions 1.8,1.9 for free abelian groups and define a covering closure.

Definition 1.16. We will keep the notation of definition 1.15. Let Res(y, a) be a well-structured resolution, and let Comp(Res)(z, y, a) be its completion. With each closure, Cl(Res)(s, z, y, a), there are associated embeddings of abelian and pegged abelian groups into their extensions:

Ab_{1} < S_{1}, …, Ab_{d} < S_{d}, P Ab_{1} < P S_{1}, …, P Ab_{pd} < P S_{pd}.

Like in propositions 1.8 with each embedding Ab_{j} < S_{j} we can associate a subgroup C_{j} of the free abelian group of rank rk(Ab_{j}), and like in proposition 1.9, with each embedding P AB_{j} < P S_{j} we can associate a Diophantine system of rk(P AB_{j}) − 1 equations in rk(P AB_{j}) − 1 variables (with coefficient), with non-zero determinant. With this system we can associate a coset Co_{j} of a finite index subgroup U_{j} of the free abelian group Z^{rk(P AB_{j})−1} (see propositions 1.8,1.9). Therefore, with each closure Cl(Res)(s, z, y, a) we can associate a tuple: (C_{1}, …, C_{d}, Co_{1}, …, Co_{pd}) of cosets of finite index subgroups in the corresponding free abelian groups. We call this collection of cosets, the closure domain, and denote it by Dom(Cl(Res)).

We say that a collection of closures of a resolution Res(y, a), {Cl(Res)_{1}, …, Cl(Res)_{q}} is a covering closure if the union of the closures domains:

Dom(Cl(Res)_{1}), …, Dom(Cl(Res)_{q})

covers the entire cross product of the abelian and pegged abelian groups:

Ab_{1}, …, Ab_{d}, P Ab_{1}, …, P Ab_{pd}.

The main importance of a covering closure is the following simple observation.

Lemma 1.17. Let Cl(Res)_{1}(s, z, y, a), …, Cl(Res)_{q}(s, z, y, a) be a covering closure of a well-structured resolution Res(y, a). For any specialization (y_{0}, a) that factors through the resolution Res(y, a) there exists an index i and elements s_{0}, z_{0}, so that (s_{0}, z_{0}, y_{0}, a) is a specialization of (at least) one of the closures Cl(Res)_{i}(s, z, y, a).

Proof: By lemma 1.14 for any specialization (y_{0}, a) that factors through the resolution Res(y, a) there exists some element z_{0} so that (z_{0}, y_{0}, a) is a specialization that factors through the completed resolution Comp(Res)(z, y, a). By definition, every specialization (z_{0}, y_{0}, a) that factors through the completion, can be extended to a specialization (s_{0}, z_{0}, y_{0}, a) that factors through one of the closures: Cl(Res)_{1}(s, z, y, a)_{1}, …, Cl(Res)_{q}(s, z, y, a), and the lemma follows.

□

The completion of a resolution Comp(Res)(z, y, a), its closures Cl(Res)(s, y, a), and the notion of a covering closure, finally allow us to generalize Merzlyakov theorem for free groups and propositions 1.3,1.8-1.9 for surface and free abelian groups, to present formal solutions associated with a well-structured resolution of a restricted limit group.

Theorem 1.18. Let F_{k} =< a_{1}, …, a_{k} > be a free group, and let u_{1}(y, a), …, u_{m}(y, a) be a collection of words in the alphabet {y, a} for which the group Rlim(y, a) =< y, a | u_{1}(y, a), …, u_{m}(y, a) > is a restricted limit group. Let Res(y, a) be a wellstructured resolution of the restricted limit group Rlim(y, a), and let Comp(Res)(z, y, a) be the completion of the resolution Res(y, a) with a corresponding completed limit group Comp(Rlim)(z, y, a).

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

∀y (u_{1}(y, a) = 1, …, u_{m}(y, a) = 1) ∃x w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1∧

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

is a truth sentence.

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

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

Furthermore, if the limit group Rlim(y, a) is not abelian, and the words:

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

are coefficient-free, then the formal solutions x = x_{i}(s, z, y, a) can be taken to be coefficient-free, i.e., x = x_{i}(s, z, y).

Proof: Our approach to proving the existence of formal solutions defined over a closure of a well-structured resolution of a general limit group is basically a combination of our approach to proving the existence of formal solutions for free groups (theorems 1.1-1.2), surface groups (theorem 1.3) and free abelian groups (propositions 1.8-1.9). Like in these theorems we start with defining test sequences associated with the completion Comp(Res)(z, y, a) of the given resolution Res(y, a). We start the construction of test sequences with a generalization of lemma 1.4 to punctured surfaces (rather than closed ones).

Lemma 1.19. Let S be a punctured surface with fundamental group Q, suppose that χ(S) ≤ −2 or S is a punctured torus, and let br_{1}, …, br_{w} be its boundary components. Let μ : Q → F_{k} be a homomorphism with non-abelian image, and suppose that for each i, 1 ≤ i ≤ w, μ(br_{i}) ≠ 1. There exist two collections of essential, non-homotopic, non-boundary parallel disjoint s.c.c. on the surface S: b_{1}, …, b_{q} and d_{1}, …, d_{t}, and an automorphism ρ ∈ Aut(S) with the following properties:

(i) Each connected component S̃ obtained by cutting the surface S along the first collection of s.c.c. b_{1}, …, b_{q} has Euler charactersitic -1, and the homomorphism μ ∘ ρ : Q → F_{k} embeds the fundamental group of each of these connected components into F_{k}.

(ii) each of the curves d_{i} intersects non-trivially at least one of the curves b_{j}. (iii) the entire collection of s.c.c. b_{1}, …, b_{q}, d_{1}, …, d_{t} fill the punctured surface

S, i.e., S\∪{b_{1}, …, b_{q}, d_{1}, …, d_{t}} is a disjoint collection of connected components, where each connected component is either homeomorphic to a disk or to an annulus. If such a component is homeomorphic to an annulus, then one of its boundary components is one of the boundary components of the surface S, br_{i}.

Proof: Similar to the proof of lemma 1.4.

□

Suppose that the completed resolution Comp(Res)(z, y, a) is given by the sequence of epimorphisms:

Comp(Rlim)(z, y, a) = Comp(Rlim)_{0}(z, y, a) → Comp(Rlim)_{1}(z, y, a) → …

… → Comp(Rlim)_{ℓ}(z, y, a) = F =< f, a >

where η_{i} : Comp(Rlim)_{i}(z, y, a) → Comp(Rlim)_{i+1}(z, y, a), 1 ≤ i ≤ ℓ, are the associated quotient maps, and suppose that the terminal free group in the completed resolution Comp(Res)(z, y, a) is F =< a_{1}, …, a_{k}, f_{1}, …, f_{c} >.

To construct test sequences associated with the completed resolution Comp(Res)(z, y, a) we fix a (bottom to top) order of the (punctured and closed) QH subgroups that appear in the completed abelian decompositions associated with the various levels of the completed resolution Comp(Res)(z, y, a), and a (bottom to top) order of the non-cyclic abelian factors and pegged abelian vertex groups that appear in these abelian decompositions. For each QH-vertex group QH_{i} in the completed abelian decomposition of one of the completed limit groups Comp(Rlim)_{i}(z, y, a), we fix a finite set of essential, non-boundary parallel s.c.c. b_{1}^{i}, …, b_{q_{i}}^{i}, d_{1}^{i}, …, d_{t_{i}}^{i} that satisfy the topological properties of lemma 1.19. With each of the completed restricted limit groups Comp(Rlim)_{i}(z, y, a) we associate a preferred system of generators, the one inherited from a fixed system of generators of the completed limit group, Comp(Rlim)(z, y, a). We further fix a set of generators for each of the (pegged) abelian groups and each of the QH vertex groups that appear in the completed abelian splittings associated with the various levels of the completed restricted resolution Comp(Res)(z, y, a).

For each QH subgroup QH_{i} that appear in one of the abelian decompositions along the completed resolution Comp(Res)(z, y, a), let φ_{1}^{i}, …, φ_{q_{i}}^{i} be the automorphisms of QH_{i} that correspond to Dehn twists along the (pre-chosen) s.c.c. b_{1}^{i}, …, b_{q_{i}}^{i}, and let ψ_{1}^{i}, …, ψ_{t_{i}}^{i} be the automorphisms of QH_{i} that correspond to Dehn twists along the (pre-chosen) s.c.c. d_{1}^{i}, …, d_{t_{i}}^{i} in correspondence. In a similar way to the construction of quadratic test sequences (definition 1.5), we define the following sequences of automorphisms of the surface group QH_{i}, {ν_{n}^{i}, τ_{n}^{i}}, iteratively. We set τ_{1}^{i} = id., and ν_{1}^{i} to be:

ν_{1}^{i} = (ψ_{1}^{i})^{ℓ_{1}^{i,1}} ∘ (ψ_{2}^{i})^{ℓ_{2}^{i,1}} ∘ … ∘ (ψ_{t_{i}}^{i})^{ℓ_{t_{i}}^{i,1}}.

For every index n > 1 we define τ_{n}^{i} to be:

τ_{n}^{i} = (φ_{1}^{i})^{m_{1}^{i,n}} ∘ (φ_{2}^{i})^{m_{2}^{i,n}} ∘ … ∘ (φ_{q_{i}}^{i})^{m_{q_{i}}^{i,n}} ∘ ν_{n−1}^{i}

and:

ν_{n}^{i} = (ψ_{1}^{i})^{ℓ_{1}^{i,n}} ∘ (ψ_{2}^{i})^{ℓ_{2}^{i,n}} ∘ … ∘ (ψ_{t_{i}}^{i})^{ℓ_{t_{i}}^{i,n}} ∘ τ_{n}^{i}.

Like in the case of a quadratic limit group (theorem 1.3), our aim in defining the sequence of automorphisms {ν_{n}^{i}, τ_{n}^{i}}, is to guarantee that any action of the QH subgroup QH_{i}, obtained as a limit of a converging subsequence of a test sequence of the ambient completed limit group Comp(Rlim)(z, y, a), is a minimal IET action of the subgroup QH_{i} on the limit real tree. To obtain that goal we need to restrict the sequences of powers {ℓ_{j}^{i,n}, m_{j}^{i,n}} used in the iterative definition of the sequences {ν_{n}^{i}, τ_{n}^{i}} to satisfy certain combinatorial conditions.

Let X be the Cayley graph of the free group F_{k} =< a_{1}, …, a_{k} >, let Y be the Cayley graph of the Completed limit group Comp(Rlim)(z, y, a), let (T_{b}^{i}, t_{b}^{i}) be the Bass-Serre tree corresponding to the decomposition of the QH subgroup QH_{i} along the collection of s.c.c. b_{1}^{i}, …, b_{q_{i}}^{i}, and let (T_{d}^{i}, t_{d}^{i}) be the Bass-Serre tree corresponding to the decomposition of the QH subgroup QH_{i} along the collection of s.c.c. d_{1}^{i}, …, d_{t_{i}}^{i}. We denote by d_{X}, d_{Y}, d_{T_{b}^{i}}, and d_{T_{d_{i}}^{i}} the natural (simplicial) metrics on X, Y, T_{b}^{i}, and T_{d}^{i} in correspondence. For every element g ∈ QH_{i} we set ℓ_{b}^{i}(g) = d_{T_{b}^{i}}(g(t_{b}^{i}), t_{b}^{i}), ℓ_{d}^{i}(g) = d_{T_{d}^{i}}(g(t_{d}^{i}), t_{d}^{i}). If g acts hyperbolically on T_{b}^{i} we denote by tr_{b}^{i}(g) the trace of the action of g on T_{b}^{i}, and similarly if g acts hyperbolically on T_{d}^{i}, we denote its trace by tr_{d}^{i}(g). For an element f ∈ F_{k}, let tr_{X}(f) be the length of a cyclically reduced element that is conjugate to f in F_{k}, i.e., the ”length” of the conjugacy class of f in F_{k}.

Let QH_{i} =< y_{1}^{i}, …, y_{s_{i}}^{i} >, and suppose that each y_{j} can be written in a normal

form y_{j} = a_{y_{j}^{i}}^{1}a_{y_{j}^{i}}^{2} … a_{y_{j}^{i}}^{ℓn(y_{j}^{i})} with respect to the graph of groups corresponding to

the decomposition of the (punctured or closed) surface S_{i} (with fundamental group QH_{i}) associated with the curves d_{1}^{i}, …, d_{t_{i}}^{i}. Let P R^{ν_{1}^{i}} be the set of all prefixes of

the words a_{y_{j}^{i}}^{1}a_{y_{j}^{i}}^{2} … a_{y_{j}^{i}}^{ℓn(y_{j}^{i})} for all j, 1 ≤ j ≤ s_{i}. We set R^{τ_{1}^{i}} = 1 and R^{ν_{1}^{i}} to satisfy:

R^{ν_{1}^{i}} ≥ 2 · max_{u∈P R^{ν^{i}_{1}}} d_{Y} (u, id.)

R^{ν_{1}^{i}} is the size of the ball whose elements are going to be ”controlled” by the automorphism ν_{1}^{i} of QH_{i}. Setting R^{ν_{1}^{i}} we define the set HY^{ν_{1}^{i}} to be:

HY^{ν_{1}^{i}} = {g ∈ QH_{i} | d_{Y} (g, id.) ≤ R^{ν_{1}^{i}} ∧ 0 < tr_{d}^{i}(g) }

and the set NF^{ν_{1}^{i}} to be:

NF^{ν_{1}^{i}} = {g ∈ QH_{i} | d_{Y} (g, id.) ≤ R^{ν_{1}^{i}} ∧ 0 < ℓ_{d}^{i}(g) }.

We define the constants R^{τ_{n}^{i}} and R^{ν_{n}^{i}} iteratively. For each g ∈ QH_{i} for which d_{Y} (g, id.) ≤ R^{ν_{n−1}^{i}} let:

ν_{n−1}^{i}(g) = a_{ν_{n−1}^{i}(g)}^{1}a_{ν_{n−1}^{i}(g)}^{2} … a_{ν_{n−1}^{i}(g)}^{ℓn(ν_{n−1}^{i}(g))}

be a normal form of ν_{n−1}^{i}(g) with respect to the graph of groups corresponding to the decomposition of the surface S_{i} by the curves b_{1}^{i}, …, b_{q}^{i}. Let P R^{τ_{n}^{i}} be the set

of all prefixes of the words a_{ν_{n−1}^{i}(g)}^{1}a_{ν_{n−1}^{i}(g)}^{2} … a_{ν_{n−1}^{i}(g)}^{ℓn(ν_{n−1}^{i}(g))} for all g ∈ QH_{i} for which

d_{Y} (g, id.) ≤ R^{ν_{n−1}^{i}}. We set R^{τ_{n}^{i}} to satisfy:

R^{τ_{n}^{i}} ≥ 2 · max_{u∈P R^{τ^{i}_{n}}} d_{Y} ((ν_{n−1}^{i})^{−1}(u), id.)

R^{τ_{n}^{i}} is the size of the ball whose elements are going to be ”controlled” by the automorphism τ_{n}^{i} of QH_{i}. Setting R^{τ_{n}^{i}} we define the set HY^{τ_{n}^{i}} to be:

HY^{τ_{n}^{i}} = {g ∈ QH_{i} | d_{Y} (g, id.) ≤ R^{τ_{n}^{i}} ∧ 0 < tr_{b}^{i}(ν_{n−1}^{i}(g)) }

and the set NF^{τ_{n}^{i}} to be:

NF^{τ_{n}^{i}} = {g ∈ QH_{i} | d_{Y} (g, id.) ≤ R^{τ_{n}^{i}} ∧ 0 < ℓ_{b}^{i}(ν_{n−1}^{i}(g)) }.

Similarly, for each g ∈ QH_{i} for which d_{Y} (g, id.) ≤ R^{τ_{n}^{i}} let:

τ_{n}^{i}(g) = a_{τ_{n}^{i}(g)}^{1}a_{τ_{n}^{i}(g)}^{2} … a_{τ_{n}^{i}(g)}^{ℓn(τ_{n}^{i}(g))}

be a normal form of τ_{n}^{i}(g) with respect to the graph of groups corresponding to the decomposition of the surface S_{i} by the curves d_{1}^{i}, …, d_{q}^{i}. Let P R^{ν_{n}^{i}} be the

set of all prefixes of the words a_{τ_{n}^{i}(g)}^{1}a_{τ_{n}^{i}(g)}^{2} … a_{τ_{n}^{i}(g)}^{ℓn(τ_{n}^{i}(g))} for all g ∈ QH_{i} for which

d_{Y} (g, id.) ≤ R^{τ_{n}^{i}}. We set R^{ν_{n}^{i}} to satisfy:

R^{ν_{n}^{i}} ≥ 2 · max_{u∈P R^{ν^{i}_{n}}} d_{Y} ((τ_{n}^{i})^{−1}(u), id.)

R^{ν_{n}^{i}} is the size of the ball whose elements are going to be ”controlled” by the automorphism ν_{n}^{i} of QH_{i}. Setting R^{ν_{n}^{i}} we define the set HY^{ν_{n}^{i}} to be:

HY^{ν_{n}^{i}} = {g ∈ QH_{i} | d_{Y} (g, id.) ≤ R^{ν_{n}^{i}} ∧ 0 < tr_{d}^{i}(τ_{n}^{i}(g)) }.

and the set NF^{ν_{n}^{i}} to be:

NF^{ν_{n}^{i}} = {g ∈ QH_{i} | d_{Y} (g, id.) ≤ R^{ν_{n}^{i}} ∧ 0 < ℓ_{d}^{i}(τ_{n}^{i}(g)) }.

Definition 1.20. Let {ν_{n}^{i}, τ_{n}^{i}} be sequences of automorphisms of each of the QH subgroups QH_{i} that appear in the abelian decompositions associated with the various levels of the completed resolution Comp(Res)(z, y, a). Let λ_{n} : Comp(Rlim)(z, y, a) → F_{k} be a sequence of homomorphisms that factor through the completed resolution Comp(Res)(z, y, a). Let F =< a_{1}, …, a_{k}, f_{1}, …, f_{c} > be the terminal free group of the completed resolution Comp(Res)(z, y, a). For every QH vertex group QH_{i}, every index n and every g ∈ NF^{τ_{n}^{i}} let:

ν_{n−1}^{i}(g) = a_{ν_{n−1}^{i}(g)}^{1}a_{ν_{n−1}^{i}(g)}^{2} … a_{ν_{n−1}^{i}(g)}^{ℓn(ν_{n−1}^{i}(g))}

be the previously chosen normal form of ν_{n−1}^{i}(g) with respect to the decomposition of QH_{i} corresponding to the Bass-Serre tree T_{b}. For every h ∈ NF^{ν_{n}^{i}} let:

τ_{n}^{i}(h) = a_{τ_{n}^{i}(h)}^{1}a_{τ_{n}^{i}(h)}^{2} … a_{τ_{n}^{i}(h)}^{ℓn(τ_{n}^{i}(h))}

be the previously chosen normal form of τ_{n}^{i}(h) with respect to the decomposition of QH_{i} corresponding to the Bass-Serre tree T_{d}^{i}. For each positive integer m we set:

f_{1}(m) = a_{1}a_{2}a_{1}a_{2}^{b+1}a_{1}a_{1}^{2b+1}a_{1} … a_{1}a_{2}^{mb+1}a_{1}, …, f_{b}(m) = a_{1}a_{2}^{b}a_{1}a_{2}^{2b}a_{1} … a_{1}a_{2}^{(m+1)b}a_{1}.

We say that a sequence of automorphisms {ν_{n}^{i}, τ_{n}^{i}} of the QH vertex groups QH_{i} together with the sequence of homomorphisms λ_{n} : Comp(Rlim)(z, y, a) → F_{k}, is a test sequence for the completed resolution Comp(Res)(z, y, a) if the following conditions hold. In a similar way to quadratic test sequences (definition 1.5), for every QH subgroup QH_{i} that appear in one of the abelian decompositions associated with the completed resolution Comp(Res)(z, y, a):

(i) for n > 1 and every b_{j}^{i}, 1 ≤ j ≤ q_{i}:

tr_{d}^{i}((b_{j}^{i})^{m_{j}^{i,n}}) > 100 · 2^{n} · max_{1≤j≤q_{i}} ℓ_{d}^{i}(b_{j}^{i}) · ∑_{d_{Y} (g,id.)≤R^{τ^{i}_{n}} ,p≤ℓn(g)} ℓ_{d}^{i}(a_{ν_{n−1}^{i}(g)}^{p})

(ii) for n ≥ 1 and every d_{j}^{i}, 1 ≤ j ≤ t_{i}:

tr_{b}^{i}((d_{j}^{i})^{ℓ_{j}^{i,n}}) > 100 · 2^{n} · max_{1≤j≤t_{i}} ℓ_{b}^{i}(d_{j}^{i}) · ∑_{d_{Y} (h,id.)≤R^{ν^{i}_{n}} ,j≤ℓn(h)} ℓ_{d}(a_{τ_{n}^{i}(h)}^{p})

(iii) for every n > 1 and every g, g′ ∈ NF^{τ_{n}^{i}}:

|\frac{ℓ_{d}^{i}(τ_{n}^{i}(g)) ℓ_{b}^{i}(ν_{n−1}^{i}(g′))}{ℓ_{d}^{i}(τ_{n}^{i}(g′)) ℓ_{b}^{i}(ν_{n−1}^{i}(g))} − 1| < \frac{1}{100 · q_{i} · 2^{n}}

(iv) for every n > 1 and every g ∈ HY^{τ_{n}^{i}}:

|\frac{tr_{d}^{i}(τ_{n}^{i}(g)) ℓ_{b}^{i}(ν_{n−1}^{i}(g))}{ℓ_{d}^{i}(τ_{n}^{i}(g)) tr_{b}^{i}(ν_{n−1}^{i}(g))} − 1| < \frac{1}{100 · q_{i} · 2^{n}}

(v) for every n ≥ 1 and every h, h′ ∈ NF^{ν_{n}^{i}}:

|\frac{ℓ_{b}^{i}(ν_{n}^{i}(h)) ℓ_{d}^{i}(τ_{n}^{i}(h′))}{ℓ_{b}^{i}(ν_{n}^{i}(h′)) ℓ_{d}^{i}(τ_{n}^{i}(h))} − 1| < \frac{1}{100 · q_{i} · 2^{n}}

(vi) for every n ≥ 1 and every h ∈ HY^{ν_{n}^{i}}:

|\frac{tr_{b}^{i}(ν_{n}^{i}(h)) ℓ_{d}^{i}(τ_{n}^{i}(h))}{ℓ_{b}^{i}(ν_{n}^{i}(h)) tr_{d}(τ_{n}^{i}(h))} − 1| < \frac{1}{100 · q_{i} · 2^{n}}

(vii) there exist constants c_{1}, c_{2} > 0 so that for every n ≥ 1 and every h, h′ ∈ NF^{ν_{n}^{i}}:

c_{1} < \frac{ℓ_{b}^{i}(ν_{n}^{i}(h)) d_{X}(λ_{n}(h′), id.)}{d_{X}(λ_{n}(h), id.) ℓ_{b}^{i}(ν_{n}^{i}(h′))} < c_{2}

(viii) there exist constants c_{3}, c_{4} > 0 so that for every n ≥ 1 and every h ∈ HY^{ν_{n}^{i}}:

c_{3} < \frac{tr_{b}^{i}(ν_{n}^{i}(h)) d_{X}(λ_{n}(h), id.)}{tr_{X}(λ_{n}(h)) ℓ_{b}^{i}(ν_{n}^{i}(h))} < c_{4}

(ix) for every index n, the restriction of the homomorphism λ_{n} to the QH subgroup QH_{i}, λ_{n} : QH_{i} → F_{k}, can not be factored as λ_{n} = γ ∘ π, where π : QH_{i} → Q is an embedding of QH_{i} into the fundamental group of a surface S finitely covered by the surface S_{i} (with fundamental group QH_{i}), and γ : Q → F_{k} is a homomorphism. i.e., the homomorphism λ_{n} : Q → F_{k} can not be extended to a surface covered by S.

In addition to properties (i)-(ix) we need to restrict the images of the generators {f_{1}, …, f_{b}} of the terminal free group F under the homomorphisms λ_{n}, and to further restrict the ratios of the sizes of elements from different QH and abelian vertex groups to be in accordance with the (fixed) order previously defined on these vertex groups.

(x) for each index n, λ_{n}(f_{1}) = f_{1}(m_{n}), …, λ_{n}(f_{b}) = f_{b}(m_{n}) where n < m_{n} < m_{n+1}.

(xi) We have already fixed an order on the non-cyclic abelian factors and pegged abelian vertex groups in the completed abelian splittings, so let Ab_{1}, …, Ab_{d} be the non-cyclic abelian factors that appear in the free decompositions associated with the various levels of the completion, Comp(Res), and P Ab_{1}, …, P Ab_{pd} be the pegged abelian groups that appear in the completed abelian splittings associated with the various levels of the completed resolution Comp(Res)(z, y, a). Let ℓ(i) be the level of the completed resolution Comp(Res)(z, y, a) in which an abelian factor Ab_{i} appears, or a a pegged abelian group P Ab_{i} appears as a vertex group. Let B_{i}(n) be the set of all elements g ∈ Comp(Rlim)(z, y, a), so that d_{Y} (g, id.) ≤ n, and either g ∈ Comp(Rlim)_{ℓ(i)+1}(z, y, a), or g ∈ Ab_{j} or g ∈ P Ab_{j} for some abelian or pegged abelian groups, Ab_{j} or P Ab_{j}, which are lower in the order defined on the abelian and pegged abelian groups in the completed resolution Comp(Res)(z, y, a). We have also fixed bases for the non-cyclic abelian factors and pegged abelian groups that appear in the completed abelian splittings, so let q_{1}^{i}, …, q_{d_{i}}^{i} be a pre-chosen basis of the abelian factor Ab_{i}, or q_{0}^{i}, q_{1}^{i}, …, q_{d_{i}}^{i} be the pre-chosen basis of P Ab_{i}, where q_{0}^{i} is the peg of the pegged abelian group P Ab_{i}. Let dist_{i}(n) be: dist_{i}(n) = max{d_{X}(λ_{n}(g), id.) | g ∈ B_{i}(n)}. In case the abelian group in question is a pegged abelian group P Ab_{i}, we choose λ_{n}(q_{j}^{i}) to commute with λ_{n}(q_{0}^{i}) and:

n · dist_{i}(n) < d_{X}(λ_{n}(q_{1}^{i}), id.), n · d_{X}(λ_{n}(q_{1}^{i}), id.) < d_{X}(λ_{n}(q_{2}^{i}), id.), …

…, n · d_{X}(λ_{n}(q_{d_{i}−1}^{i}), id.) < d_{X}(λ_{n}(q_{d_{i}}^{i}), id.).

If the abelian group in question is a non-cyclic abelian factor Ab_{i}, we set h_{i}(n) = f_{1}(n·dist_{i}(n)). We further set each of the elements λ_{n}(q_{1}^{i}), …, λ_{n}(q_{d_{i}}^{i}) to commute with h_{i}(n), and:

n · |h_{i}(n)| < d_{X}(λ_{n}(q_{1}^{i}), id.), n · d_{X}(λ_{n}(q_{1}^{i}), id.) < d_{X}(λ_{n}(q_{2}^{i}), id.), …

…, n · d_{X}(λ_{n}(q_{d_{i}−1}^{i}), id.) < d_{X}(λ_{n}(q_{d_{i}}^{i}), id.).

(xii) Let QH_{i} be a QH vertex group in the completed abelian splitting of

Comp(Rlim)_{ℓ(i)}(z, y, a).

We have already fixed an order of the QH vertex groups in the completed abelian splittings of Comp(Rlim)_{ℓ(i)}(z, y, a). Let QB_{i}(n) be the set of all elements g ∈ Comp(Rlim)(z, y, a), so that d_{Y} (g, id.) ≤ n, and either g ∈ Comp(Rlim)_{ℓ(i)+1}(z, y, a), or g ∈ Ab_{j} or g ∈ P Ab_{j} for some non-cyclic abelian factor Ab_{j}, or a pegged abelian group P Ab_{j} in the abelian decomposition associated with Comp(Rlim)_{ℓ(i)}(z, y, a), or g ∈ QH_{j} for some QH subgroup QH_{j} which is lower in the order defined on QH vertex groups in the completed resolution Comp(Res)(z, y, a). Let Qdist_{i}(n) be: Qdist_{i}(n) = max{d_{X}(λ_{n}(g), id.) | g ∈ QB_{i}(n)}. Then for each element c ∈ QH_{i} so that d_{Y} (c, id.) ≤ n and c corresponds to a non-boundary parallel curve on S_{QH_{i}}, the (punctured) surface corresponding to QH_{i}:

n · Qdist_{i}(n) < d_{X}(λ_{n}(c), id.).

(xiii) Let c ∈ QH_{i} and suppose d_{Y} (c, id.) ≤ n. If c corresponds to a non-boundary parallel curve in S_{QH_{i}}, the (punctured) surface corresponding to QH_{i}, and c has no roots in QH_{i}, then λ_{n}(c) generates a maximal cyclic subgroup in F_{k}.

(xiv) For every index n and every peg q_{0}^{i} of a pegged abelian group P Ab_{i} in one of the levels of the completed resolution, Comp(Res)(z, y, a), λ_{n}(q_{0}^{i}) is a primitive element in F_{k}.

Lemma 1.21. There exist test sequences for every given completed resolution Comp(Res)(z, y, a). Furthermore, given any two integers s_{1} < s_{2} we can choose the n-th specialization of a basis element of some (pegged) abelian group Ab_{t} or P Ab_{t} that appears in one of the the completed abelian decompositions associated with the various levels of the completed resolution Comp(Res)(z, y, a), λ_{n}(q_{r}^{t}), for some r ≥ 1, to be of the form λ_{n}(q_{r}^{t}(n)) = u^{ms_{2}+s_{1}} for some integer m, where u has no non-trivial roots in F_{k}.

Proof: The construction of a test sequence for a general completed resolution is a combination of the constructions of free, quadratic, and abelian test sequences presented in the proofs of theorems 1.1, 1.3 and 1.8 in correspondence. We start by applying lemma 1.6 to construct a sequence of automorphisms {(ν_{n}^{i}, τ_{n}^{i})} that satisfy properties (i)-(vi) for each of the QH subgroups QH_{i} that appear in the abelian decompositions associated with the various levels of the completed resolutions Comp(Res)(z, y, a).

We construct the homomorphisms λ_{n} : Comp(Rlim)(z, y, a) → F_{k} iteratively from bottom to top. First we set λ_{n}(f_{1}) = f_{1}(m_{n}), …, λ_{n}(f_{b}) = f_{b}(m_{n}), for some m_{n} > m_{n−1} that will be specified in the sequel. Hence, property (x) is fulfilled. If Comp(Rlim)_{ℓ−1}(z, y, a) is the completed limit group that lies above the bottom one, then if we choose m_{n} to be large enough, then the image under the (completed) map Comp(η)_{ℓ−1} : Comp(Rlim)_{ℓ−1}(z, y, a) → F_{k} of all the edge groups that appear in the abelian decomposition associated with Comp(Rlim)_{ℓ−1}(z, y, a) is non-trivial and primitive, and the image of all the QH vertex groups that appear in this abelian decomposition is non-abelian. We set λ_{n} : Comp(Rlim)_{ℓ−1}(z, y, a) → F_{k} as follows. On Comp(Rlim)_{ℓ}(z, y, a) =< f_{1}, …, f_{b} > we have already defined the homomorphism λ_{n}, and we denote this restriction of λ_{n} as λ_{n}^{F}. we continue by defining λ_{n} iteratively on each of the abelian vertex groups that appear in the abelian decomposition associated with Comp(Rlim)_{ℓ−1}(z, y, a), in accordance with their given order, to satisfy condition (xi). Clearly, if q_{r}^{t}, r ≥ 1, is a basis element of any of the abelian or pegged abelian groups that appear in this abelian decomposition and s_{1} < s_{2} are given integers, we can choose λ_{n}(q_{r}^{t}) = u^{ms_{2}+s_{1}} where m is an integer, and u has no roots in F_{k}.

Next, we define the homomorphism λ_{n} iteratively on each of the QH subgroups QH_{i} that appear in the abelian decomposition associated with Comp(Rlim)_{ℓ−1}(z, y, a) in accordance with their given order. On each subgroup QH_{i} we set the homomorphism λ_{n} to be of the form: λ_{n}^{QH_{i}} = λ_{n}^{F} ∘ Comp(η)_{ℓ−1} ∘ α_{n}^{i} ∘ ν_{n}^{i} where α_{n}^{i} is an automorphism of the subgroup QH_{i} of the form:

α_{n}^{i} = ρ_{n}^{i} ∘ (φ_{1}^{i})^{e_{n}^{i}} ∘ (φ_{2}^{i})^{e_{n}^{i}} ∘ … ∘ (φ_{q_{i}}^{i})^{e_{n}^{i}}

and ρ_{n}^{i} is a (modular) automorphism of QH_{i} chosen according to lemma 1.19. We have chosen the homomorphism λ_{n}^{F} :< f_{1}, …, f_{b} >→ F_{k} to guarantee that λ_{n}^{F} ∘ Comp(η)_{ℓ−1} : QH_{i} → F_{k} has a non-abelian image. Hence, by lemma 1.19 and the same argument used to prove the existence of a quadratic test sequence (lemma 1.6), we choose the exponents e_{n}^{i} to be large enough, properties (vii)-(ix), and properties (xii) and (xiii) hold for the homomorphisms λ_{n} : Comp(Rlim)_{ℓ−1}(z, y, a) → F_{k}. By possibly further increasing the integer m_{n} used to define the homomorphism λ_{n}^{F} :< f_{1}, …, f_{b} >→ F_{k}, and further increasing the exponents e_{n}^{i} used to define the homomorphisms λ_{n}^{QH_{i}}, and the exponents used in setting the image of basis elements of the abelian vertex groups, we get property (xiv) to hold as well. So far we have defined the homomorphism λ_{n} only on the ℓ − 1-th completed limit group Comp(Rlim)_{ℓ−1}(z, y, a). Repeating the construction of the homomorphism λ_{n} for each of the abelian vertex groups and each of the QH vertex groups that appear in the abelian decompositions associated with each of the upper levels iteratively and according to the pre-fixed order, we obtain a homomorphism λ_{n} : Comp(Rlim)(z, y, a) → F_{k} that satisfies properties (i)-(xiv) of the lemma.

□

Having constructed test sequences, we continue the proof of theorem 1.18 by essentially combining the arguments used to prove theorems 1.1, 1.3 and 1.8,1.9. Also, we may assume that our given completed limit group Comp(Rlim)(z, y, a) is not the free group < f, a >, since in that case theorem 1.18 follows from theorem 1.2. By the assumptions of theorem 1.18, for every possible specialization of (y, a) that factors through the restricted limit group Rlim(y, a), there exists a specialization for the variables x, so that the given equalities w_{1}(x, y, a) = 1, …, w_{s}(x, y, a) = 1 and inequalities v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1 are fulfilled. Given a well-structured resolution Res(y, a) of Rlim(y, a), its completion Comp(Res)(z, y, a), and a test sequence {(ν_{n}^{i}, τ_{n}^{i}, λ_{n})} associated with the completed resolution Comp(Res)(z, y, a), for each index n, we can choose a specialization x_{n} to be a shortest possible specialization (in the word metric on F_{k}) for which:

w_{1}(x_{n}, λ_{n}(y), a) = 1, …, w_{s}(x_{n}, λ_{n}(y), a) = 1 ∧
∧ v_{1}(x_{n}, λ_{n}(y), a) ≠ 1, …, v_{r}(x_{n}, λ_{n}(y), a) ≠ 1.

If the sequence of specializations {(x_{n}, λ_{n}(z), λ_{n}(y), a)}, corresponding to a test sequence and some shortest possible specializations {x_{n}} converges, we call the obtained limit group a test limit group. On the set of test limit groups we define a natural partial order, by setting T L_{1}(x, z, y, a) ≥ T L_{2}(x, z, y, a) if T L_{2}(x, z, y, a) is a quotient of T L_{1}(x, z, y, a). By the arguments used in constructing the Makanin-Razborov diagram of a limit group (lemmas 5.4 and 5.5 in [Se1]), there exist maximal test limit groups and in fact there are finitely many equivalence classes of maximal test limit groups that we denote:

MT L_{1}(x, z, y, a), …, MT L_{m}(x, z, y, a).

Since the maximal test limit groups MT L_{1}(x, z, y, a), …, MT L_{m}(x, z, y, a) were constructed using sequences of specializations {(x_{n}, λ_{n}(z), λ(y), a)} for which the equalities w_{1}(x_{n}, λ_{n}(y), a) = 1, …, w_{s}(x_{n}, λ_{n}(y), a) = 1 are fulfilled, the words w_{1}(x, y, a), …, w_{s}(x, y, a) represent the trivial words in the maximal test limit groups

MT L_{1}(x, z, y, a), …, MT L_{m}(x, z, y, a).

Similarly, the words v_{1}(x, y, a), …, v_{r}(x, y, a) represent non-trivial words in these maximal test limit groups.

By repeating the iterative modifications of the specializations {x_{n}}, applied in the proofs of theorems 1.3 and 1.8, we may further replace the maximal test limit groups: MT L_{1}(x, z, y, a), …, MT L_{m}(x, z, y, a), by quotients of them (still denoted MT L_{j}(x, z, y, a)), so that each of the maximal test limit groups MT L_{j}(x, z, y, a) admits a free decomposition:

MT L_{j}(x, z, y, a) = G_{j}(g, z, y, a) ∗ < e_{1}, …, e_{d_{j}} >

where < e_{1}, …, e_{d_{j}} > is a (possibly trivial) free group on the set e_{1}, …, e_{d_{j}}, Comp(Rlim)(z, y, a) < G_{j}(g, z, y, a), and G_{j}(g, z, y, a) admits no free decomposition in which Comp(Rlim)(z, y, a) is contained in one of the factors.

At this point we continue with each of the maximal test limit groups MT L_{j}(x, z, y, a) in parallel, by combining the arguments used to prove theorems 1.3 and 1.8. Let MT L(x, z, y, a) be one of the maximal test limit groups. We fix a generating system of the factor G(g, z, y, a) of MT L(x, z, y, a), G(g, z, y, a) =< g_{1}, …, g_{c} >. We continue with all the sequences {(x_{n}, λ_{n}(z), λ_{n}(y), a)} for which the corresponding sequence {(λ_{n}(z), a)} is a test sequence, and for every index n:

(1) the specializations x_{n} is in the free group F_{k} ∗ F_{d}, where:

MT L(x, y, z, a) = G(g, z, y, a) ∗ F_{d}.

(2) the tuple (x_{n}, λ_{n}(z), λ_{n}(y), a) factors through the maximal test limit group MT L(x, z, y, a).

(3) v_{1}(x_{n}, λ_{n}(y), a) ≠ 1, …, v_{r}(x_{n}, λ_{n}(y), a) ≠ 1.

(4) the specializations g_{1}(n), …, g_{c}(n) ∈ F_{k} obtained from the specialization x_{n}, have the shortest length (in the simplicial metric on the Cayley graph of F_{k}) among all possible specializations x_{n} that satisfy properties (1)-(3).

We look at such a sequence, that convergence to a faithful action of MT L(x, z, y, a) on a real tree Y_{1}. By the shortening argument used in the proofs of theorems 1.3 and 1.8, since the specializations g_{1}(n), …, g_{c}(n) were chosen to be shortest possible, and since the factor G(g, z, y, a) admits no free decomposition in which the completion Comp(z, y, a) is elliptic, the factor G(g, z, y, a) does not fix a point in the real tree Y_{1}. Furthermore, the action of MT L(x, z, y, a) on the real tree Y_{1} must be of one of the following types:

(1) MT L(x, z, y, a) (and G(g, z, y, a)) inherits from its action on the real tree Y_{1}, a graph of groups with one QH subgroup Q < Comp(Rlim)(z, y, a) which is the highest order QH subgroup in the completed resolution Comp(Res)(z, y, a), and several vertex groups V_{j}(v, a), corresponding to the various orbits of point stabilizers in the action of MT L(x, z, y, a) on Y_{1}. The decomposition Comp(Rlim)(z, y, a) inherits from this decomposition of MT L(x, z, y, a) is exactly of the same form, and is compatible with the (top level of the) completed resolution Comp(Res)(z, y, a).

(2) MT L(x, z, y, a) (and the factor G(g, z, y, a)) acts discretely on Y_{1}, and it inherits a graph of groups with several vertex groups located on a loop with abelian stabilizer, where the Bass-Serre generator bs corresponding to the loop can be chosen to commute with the (abelian) loop stabilizer. Hence, the maximal test limit group MT L admits an amalgamated product of the form: MT L = V ∗_{Ab_{1}} Ab, where the subgroup Ab is abelian, and contains the (pegged) abelian subgroup of highest order in Comp(Res)(z, y, a). Furthermore, the (pegged) abelian group of highest order in Comp(Res)(z, y, a) is not elliptic in this amalgamated product. The decomposition Comp(Rlim)(z, y, a) inherits from this decomposition of MT L is exactly of the same form, and is compatible with the (top level of the) completed resolution Comp(Res)(z, y, a).

(3) The action of the maximal test limit group MT L(x, z, y, a) (and the factor G(g, z, y, a)) on the real tree Y_{1} corresponds to a unique axial component and several point stabilizers located on that axial component. In this case MT L (and the factor G(g, z, y, a)) admits an amalgamated product of the form: MT L = V ∗_{Ab_{1}} Ab, where the subgroup Ab is abelian, and contains the (pegged) abelian subgroup of highest order in Comp(Res)(z, y, a). Furthermore, the (pegged) abelian group of highest order in Comp(Res)(z, y, a) is not elliptic in this amalgamated product. The decomposition Comp(Rlim)(z, y, a) inherits from this decomposition of MT L is exactly of the same form, and is compatible with the (top level of the) completed resolution Comp(Res)(z, y, a).

If the action of the maximal test limit group MT L(x, z, y, a) satisfies the properties of case (1) we continue the analysis of MT L(x, z, y, a) by analyzing each of the vertex groups V_{j}(v, a) in parallel. If the action of MT L satisfies the properties of cases (2) or (3), we continue with the vertex group V, where MT L inherits the amalgamated product MT L = V ∗_{Ab_{1}} Ab from its action on the real tree Y_{1}. By iteratively repeating this ”uncovering” process (as we did in the proof of theorem 1.8), we are finally able to replace each of the maximal test limit groups, MT L(x, z, y, a), with finitely many quotients (still denoted MT L_{j}(x, z, y, a)) of the form:

MT L_{j}(x, z, y, a) = Cl_{j}(s, z, y, a) ∗ E_{j}(e_{1}, …, e_{d_{j}})

where E_{j}(e_{1}, …, e_{d_{j}}) is a free group, freely generated by < e_{1}, …, e_{d_{j}} >, and Cl_{j}(s, z, y, a) is a closure of the resolution Res(y, a).

The maximal test limit groups MT L_{j}(x, z, y, a) were obtained as the limit of sequences of the form {(x_{n}, λ_{n}(z), λ_{n}(y), a)}, where for every index n, the tuple (x_{n}, λ_{n}(z), λ_{n}(y), a) factors through MT L_{j}(x, z, y, a), and in addition: v_{1}(x_{n}, λ_{n}(y), a) ≠ 1, …, v_{r}(x_{n}, λ_{n}(y), a) ≠ 1. Hence, there must exist a retract:

η : MT L_{j}(x, z, y, a) → Cl_{j}(s, z, y, a)

so that the words η(v_{1}(x, y, a)), …, η(v_{r}(x, y, a)) are all non-trivial in the closure Cl_{j}(s, z, y, a). Therefore, each of the generator x of η(MT L_{j}(x, z, y, a) can be naturally presented as a word in the closure Cl_{i}(Res)(s, z, y, a), i.e., x = η(x)(s, z, y, a), each of the words: w_{1}(x(s, z, y, a), y, a), …, w_{s}(x(s, z, y, a), y, a) represent the trivial word in the closure Cl_{j}(Res)(s, z, y, a), and there exists some specialization (s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, a) for which:

v_{1}(x(s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, a), y_{0}^{i}, a) ≠ 1, …, v_{r}(x(s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, a), y_{0}^{i}, a) ≠ 1.

Since every test sequence associated with the completed resolution Comp(Res)(z, y, a) can be adjoined by a sequence {x_{n}} to form a sequence that factors through at least one of the maximal test limit groups MT L_{j}(x, z, y, a), the same argument used in proving proposition 1.8 shows that the collection of closures Cl_{j}(Res)(s, y, a) associated with the maximal test limit groups MT L_{j}(x, z, y, a), has to be a covering closure.

If the graded resolution Res(y, a) is not abelian, and the words: w_{1}(x, y, a), …, w_{s}(x, y, a), and: v_{1}(x, y, a), …, v_{r}(x, y, a) are coefficient-free, then each of the maximal test limit groups constructed by our iterative procedure has the form:

MT L_{j}(x, z, y, a) = F_{k} ∗ Cl_{j}(s, z, y) ∗ E_{j}(e_{1}, …, e_{d_{j}})

where F_{k} is the coefficient group, and E_{j}(e_{1}, …, e_{d_{j}}) is a (possibly trivial) free group. In this coefficient-free case, there must exist a retract:

η : MT L_{j}(x, z, y, a) → Cl_{j}(s, z, y)

for which the elements η(v_{1}(x, y)), …, η(v_{r}(x, y)) are mapped to non-trivial elements in Cl_{j}(s, z, y), so that the formal solutions can be taken to be coefficient-free, i.e., x = η(x)(s, z, y).

□

For the purposes of our ”trial and error” procedure for quantifier elimination, a slight generalization of theorem 1.18 is required. The proof of the more general form that appears below is identical to the proof of theorem 1.18.

Theorem 1.22. Let F_{k} =< a_{1}, …, a_{k} > be a free group, and let u_{1}(y, a), …, u_{m}(y, a) be a collection of words in the alphabet {y, a} for which the group Rlim(y, a) =< y, a | u_{1}(y, a), …, u_{m}(y, a) > is a restricted limit group. Let Res(y, a) be a wellstructured resolution of the restricted limit group Rlim(y, a), and let Comp(Res)(z, y, a) be the completion of the resolution Res(y, a) with a corresponding completed limit group Comp(Rlim)(z, y, a).

Let Σ_{1}(x, y, a) = 1, …, Σ_{r}(x, y, a) = 1 be a collection of systems of equations over F_{k}, and let Ψ_{1}(x, y, a), …, Ψ_{r}(x, y, a) be a collection of words in the alphabet {x, y, a}. Suppose that the sentence:

∀y (u_{1}(y, a) = 1, …, u_{m}(y, a) = 1) ∃x

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

is a truth sentence.

Then there exists a covering closure: Cl(Res)_{1}(s, z, y, a)_{1}, …, Cl(Res)_{q}(s, z, y, a), and for each index i, 1 ≤ i ≤ q, there exists a formal solution x_{i}(s, z, y, a) and an index j(i), 1 ≤ j(i) ≤ r, with the following properties:

(i) for each index i, 1 ≤ i ≤ q, all the words in the system Σ_{j(i)}(x_{i}(s, z, y, a), y, a) represent the trivial word in the restricted limit group corresponding to the i-th closure Cl(Rlim)_{i}(s, y, a).

(ii) for each index i, 1 ≤ i ≤ q, there exists a specialization (s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, a) that factors through the i-th closure Cl(Res)_{i}(s, z, y, a), so that all the words in the collection Ψ_{j(i)}(x_{i}(s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, a), y_{0}^{i}, a) are not the trivial element in F_{k}.

Furthermore, if the limit group Rlim(y, a) is not abelian, and the words w_{1}(x, y, a), …, w_{s}(x, y, a), v_{1}(x, y, a), …, v_{r}(x, y, a) are coefficient-free, then the formal solutions x = x_{i}(s, z, y, a) can be taken to be coefficient-free, i.e., x = x_{i}(s, z, y).

§2. Formal Limit Groups

Theorems 1.18 and 1.22 show that given a restricted limit group and a wellstructured resolution of that limit group, the validity of an AE sentence over the given limit group, implies the existence of a finite collection of formal solutions defined over a covering closure of the resolution of that limit group. The finite collection of formal solutions constructed in theorems 1.18 and 1.22 are guaranteed to satisfy the equalities specified in the sentence, and at the same time to admit some particular specialization for which all the inequalities specified in the sentence are valid. Our approach to quantifier elimination of predicates is based on the existence of formal solutions satisfying the properties listed in theorems 1.18 and 1.22. However, instead of distinguishing formal solutions that admit specializations that satisfy the inequalities specified in the sentence, our strategy is to analyze the entire family of formal solutions that satisfy only the equalities specified in the sentence, so that if the sentence is indeed a truth sentence, theorems 1.18 and 1.22 guarantee that the entire family contains a finite collection of formal solutions defined over a covering closure of the given (well-structured) resolution and admitting specializations that satisfy also the inequalities specified in the sentence.

Given a restricted limit group Rlim(y, a) and a well-structured resolution Res(y, a) of it, to analyze the family of all formal solutions of a given system of equations Σ(x, y, a) = 1, defined over some closure of the completion of our given resolution, we need to present formal limit groups and their canonically associated formal Makanin-Razborov diagrams. We start by defining formal limit groups.

Definition 2.1. Let Res(y, a) be a well-structured resolution of a restricted limit group Rlim(y, a), let Comp(Res)(z, y, a) be the completed resolution of Res(y, a), and let Σ(x, y, a) = 1 be a system of equations. Let the sequence of automorphisms {(ν_{n}^{i}, τ_{n}^{i})} of the QH subgroups QH_{i} that appear in the abelian decompositions associated with the various levels in the completed resolution Comp(Res)(z, y, a), together with the homomorphisms {λ_{n} : Comp(Rlim) → F_{k}}, be a test sequence associated with the completed resolution Comp(Res)(z, y, a). For each index n suppose that there exists some specialization x_{n} for which: Σ(x_{n}, λ_{n}(y), a) =

1. For each index n, the homomorphism λ_{n} : Comp(Rlim)(z, y, a) → F_{k} together with the specialization x_{n} defines a homomorphism from the free group with generating set < x, z, y, a >, denoted F (x, z, y, a), to the coefficient group F_{k}: α_{n} : F (x, z, y, a) → F_{k}. We say that the test sequence {ν_{n}^{i}, τ_{n}^{i}, λ_{n}} together with the sequence of specializations {x_{n}} is a convergent formal sequence, if the sequence of corresponding homomorphisms {α_{n} : F (x, z, y, a) → F_{k}} is convergent (in the Gromov-Haussdorff topology, after appropriate rescaling). We call the obtained limit group, a formal limit group and denote it F L(x, z, y, a).

Note that by construction Comp(Rlim)(z, y, a) < F L(x, z, y, a). Since every abelian subgroup of a limit group is contained in a unique maximal abelian subgroup, every abelian subgroup of a limit group is contained in a unique maximal abelian subgroup of the same rank. By replacing the (pegged) abelian groups in Comp(Rlim)(z, y, a) by the maximal abelian groups of the same rank containing them in F L(x, z, y, a), we obtain a (canonical) closure of Comp(Rlim)(z, y, a) in F L(x, z, y, a), which we call the formal closure of Comp(Rlim)(z, y, a) in the formal limit group F L(x, z, y, a). We denote the formal closure, F Cl(s, z, y, a).

To analyze formal limit groups we need to construct their associated (canonical) formal Makanin-Razborov diagrams. To do that we need to study the algebraic structure of formal limit groups, F L(x, z, y, a), relative to their subgroup, the completed restricted limit group Comp(Rlim)(z, y, a). To do that we start by defining the formal JSJ decomposition of a formal limit group. In the sequel below let Res(y, a) be a well-structured resolution of a restricted limit group Rlim(y, a), and let Comp(Rlim)(z, y, a) be the limit group associated with its completion. Let Σ(x, y, a) = 1 be a system of equations and let F L(x, z, y, a) be a formal limit group corresponding to the system Σ(x, y, a) = 1. Let F Cl(s, z, y, a) be the formal closure of Comp(Rlim)(z, y, a) in the formal limit group F L(x, z, y, a).

Definition 2.2. Suppose that the formal limit group F L(x, z, y, a) does not split as a non-trivial free product in which Comp(Rlim)(z, y, a) is contained in one of the factors. An essential one edge abelian splitting, F L(x, z, y, a) = D ∗_{A} E or F L(x, z, y, a) = D∗_{A}, in which Comp(Rlim)(z, y, a) is elliptic, is called a formal abelian splitting.

The arguments used in section 2 of [Se1], naturally generalize to construct the formal JSJ decomposition of a formal limit group.

Theorem 2.3 (cf. ([Se1],9.2)). Let F L(x, z, y, a) be a formal limit group which does not split as a non-trivial free product in which the completed limit group Comp(Rlim)(z, y, a) is contained in one of the factors. There exists an essential (perhaps trivial) abelian splitting of F L(x, z, y, a), which we call the formal JSJ decomposition of F L(x, z, y, a), with the following properties:

(i) Comp(Rlim)(z, y, a) is elliptic in the formal JSJ decomposition. If the formal JSJ decomposition of F L(x, z, y, a) is not trivial, then any one edge abelian splitting obtained by collapsing all edges but one in the formal JSJ decomposition is a formal splitting of F L(x, z, y, a).

(ii) Every (formal) canonical maximal QH subgroup (CMQ) of F L(x, z, y, a) is conjugate to a vertex group in the formal JSJ decomposition. Every formal QH subgroup of F L(x, z, y, a) can be conjugated into one of the formal CMQ subgroups of F L(x, z, y, a). Every vertex group in the formal JSJ decomposition which is not a CMQ subgroup of F L(x, z, y, a) is elliptic in any formal splitting of F L(x, z, y, a).

(iii) A one edge formal splitting F L(x, z, y, a) = D ∗_{A} E or F L(x, z, y, a) = D∗_{A} which is hyperbolic in another such elementary formal splitting is obtained from the formal JSJ decomposition of F L(x, z, y, a) by cutting a surface corresponding to a formal CMQ subgroup of F L(x, z, y, a) along an essential s.c.c..

(iv) Let Θ be a one edge formal abelian splitting F L(x, z, y, a) = D ∗_{A} E or F L(x, z, y, a) = D∗_{A}, which is elliptic with respect to any other such one edge formal splitting of F L(x, z, y, a). Then Θ is obtained from the formal JSJ decomposition of F L(x, z, y, a) by a sequence of collapsings, conjugations, and modifying boundary monomorphisms by conjugations.

(v) Let Λ be a general formal abelian splitting of F L(x, z, y, a). There exists a formal splitting Λ_{1} obtained from the formal JSJ decomposition by splitting the formal CMQ subgroups along weakly essential s.c.c. on their corresponding surfaces, so that there exists a F L(x, z, y, a)-equivariant simplicial map between a subdivision of the Bass-Serre tree T_{Λ_{1}} to T_{Λ}.

(vi) If JSJ_{1} is another formal JSJ decomposition of F L(x, z, y, a), then JSJ_{1} is obtained from the formal JSJ decomposition by a sequence of slidings, conjugations and modifying boundary monomorphisms by conjugations (see section 1 of [Ri-Se2] for these notions)

(vii) If F L(x, z, y, a) admits a formal abelian splitting, then the formal JSJ decomposition of F L(x, z, y, a) is non-trivial.

In case the formal JSJ decomposition is non-trivial, it allows one to ”further simplify” formal limit groups. In order to construct formal Makanin-Razborov diagrams we still need to study the structure of formal limit groups with trivial formal JSJ decomposition.

Proposition 2.4. Let F L(x, z, y, a) be a formal limit group which does not split as a non-trivial free product in which the completed limit group Comp(Rlim)(z, y, a) is contained in one of the factors. If the formal JSJ decomposition of F L(x, z, y, a) is trivial, then F L(x, z, y, a) is a formal closure of Comp(Rlim)(z, y, a) < F L(x, z, y, a). i.e., F L(x, z, y, a) = F Cl(s, z, y, a).

Proof: Suppose that F L(x, z, y, a) does not split as a non-trivial free product in which Comp(Rlim)(z, y, a) is contained in one of the factors, and the formal JSJ decomposition of F L(x, z, y, a) is trivial. The formal limit group F L(x, z, y, a) was constructed from a sequence of homomorphisms: α_{n} : F (x, z, y, a) → F_{k}, that are composed from a test sequence {ν_{n}^{i}, τ_{n}^{i}, λ_{n}} and specializations {x_{n}}, for which Σ(x_{n}, λ_{n}(y), a) = 1. From the convergence of the sequence of homomorphisms {α_{n}}_{n=1}^{∞}, we get a (non-trivial) stable action of the formal limit group F L(x, z, y, a) on some real tree Y_{1}, in which the stabilizer of every non-degenerate segment is either trivial or abelian. By the classification of stable actions of groups on real trees (see theorem 1.5 in [Se1]), there is a graph of groups Λ_{1} with abelian edge stabilizers and fundamental group F L(x, z, y, a), corresponding to the action of F L(x, z, y, a) on the real tree Y_{1}. If the completed limit group Comp(Rlim)(z, y, a) is contained in a vertex group of Λ_{1}, or more generally if Comp(Rlim)(z, y, a) is contained in a fundamental group of a proper subgraph of Λ_{1}, the formal limit group F L(x, z, y, a) admits a formal abelian or a free decomposition in which the completed limit group Comp(Res)(z, y, a) is elliptic, a contradiction to our assumptions.

Hence, by the properties of a test sequence, if Comp(Res)(z, y, a) is equal to its terminal free group F =< a, f >, then necessarily F L(x, z, y, a) = F, and the theorem follows. Otherwise, note that by the properties of test sequences, the action of Comp(Res)(z, y, a) on the real tree Y_{1} either contains a unique IET orbit and finitely many orbits of point stabilizers, or the action is discrete with a unique orbit of non-abelian point stabilizer and a unique edge stabilized by some abelian subgroup of Comp(Res)(z, y, a). Since F L(x, z, y, a) inherits from its action on Y_{1} a graph of groups of the same form as the one Comp(Res)(z, y, a) inherits from its action on Y_{1}, the action of F L(x, z, y, a) on Y_{1} must contain also either a unique orbit of an IET component and finitely many orbits of point stabilizers, or its action is discrete with one orbit of non-abelian point stabilizers and one orbit of edges stabilized by some abelian subgroup of F L(x, z, y, a).

In both types of the dynamics of the action of the formal limit group F L(x, z, y, a) on the limit tree Y_{1}, the generators x of the formal limit group F L(x, z, y, a) can be written as words in elements from the vertex stabilizers V_{i} and elements from the formal closure F Cl(s, z, y, a). Now, if we restrict the specializations of the subgroup < x, z, y, a > to each of the vertex groups V_{i} in the graph of groups associated with the action of F L(x, z, y, a) on the real tree Y_{1}, with each vertex group V_{i} we associate an action of V_{i} on some real tree V_{2}^{i}. Repeating this argument for the action of the vertex stabilizers V_{i} on a real tree Y_{2}^{i}, if V_{i} is not the free group F =< f, a >, the action of V_{i} on Y_{2}^{i} must be one of two types. Either it contains a unique orbit of an IET component and finitely many orbits of point stabilizers, or the action is discrete with one orbit of non-abelian point stabilizers and one orbit of edges stabilized by some abelian subgroup of the closure F Cl(s, z, y, a). Hence, the generators x of the formal limit group F L(x, z, y, a) can be written as words in elements from the vertex stabilizers W_{i} and elements from the formal closure F Cl(s, z, y, a). A finite induction argument clearly finishes the proof of the proposition.

□

Defining formal limit groups and their formal JSJ decompositions, and showing that a (relatively) freely indecomposable formal limit group with trivial formal JSJ decomposition is a formal closure F Cl(s, z, y, a) of the completed limit group Comp(Rlim)(z, y, a), we are able to present formal Makanin-Razborov diagrams.

Let Res(y, a) be a well-structured resolution of a restricted limit group Rlim(y, a), let Comp(Res)(z, y, a) be the completed resolution of Res(y, a), and let Σ(x, y, a) = 1 be a system of equations. Recall that a formal limit group F L(x, z, y, a) of the system Σ(x, y, a) = 1 with respect to the resolution Res(y, a) was constructed from a convergent sequence of homomorphisms: {α_{n} : F (x, z, y, a) → F_{k}} composed from a test sequence {ν_{n}^{i}, τ_{n}^{i}, λ_{n}}, and a sequence of specializations {x_{n}} for which: Σ(x_{n}, λ_{n}(y), a) = 1. On the set of formal limit groups we can naturally define a partial order, by setting F L_{1}(x, z, y, a) ≥ F L_{2}(x, z, y, a) if there exists an epimorphism:

η : F L_{1}(x, z, y, a) → F L_{2}(x, z, y, a).

By the arguments used in the construction of the Makanin-Razborov diagram of a limit group (see lemmas 5.4 and 5.5 in [Se1]), given the system of equations Σ(x, y, a) = 1, and the (well-structured) resolution Res(y, a), there exist maximal formal limit groups (with respect to the natural partial order), and up to the natural equivalence relation on formal limit groups there are only finitely many equivalence classes of formal limit groups which we denote: MF L_{1}(x, z, y, a), …, MF L_{t}(x, z, y, a).

To construct the formal Makanin-Razborov of the system Σ(x, y, a) = 1 with respect to the restricted well-structured resolution Res(y, a), we proceed as in the construction of the graded Makanin-Razborov diagrams (section 10 in [Se1]). We first decompose each of the maximal formal limit groups into the maximal (Grushko’s) free decomposition in which the completed limit group Comp(Rlim)(z, y, a) is contained in a factor. We associate the formal JSJ decomposition with the factor containing Comp(Rlim)(z, y, a), and the (standard) abelian JSJ decomposition with each of the other factors. These associated JSJ decompositions naturally define the formal modular groups of each of the maximal formal limit groups MF L_{i}(x, z, y, a). Having these modular groups, and assuming they are not trivial, we are able to define formal shortening quotients of each of the maximal formal limit groups. By the argument used to prove claim 5.3 in [Se1], every formal shortening quotient of a formal limit group is a proper quotient of it. Now, by the arguments used to prove lemmas 5.4 and 5.5 in [Se1], there are maximal formal shortening quotients, and up to the natural equivalence classes of formal limit groups there are only finitely many equivalence classes of maximal shortening quotients of each of the maximal formal limit groups: MF L_{1}(x, z, y, a), …, MF L_{t}(x, z, y, a).

Since a formal limit group is in particular a limit group, any properly decreasing sequence of formal limit groups terminates. Therefore, if we continue the above construction of maximal formal free decompositions, formal JSJ decompositions and formal modular groups for each of the factors, and then collecting the (canonical) family of maximal formal shortening quotients, we are guaranteed that this iterative construction terminates. We call the obtained diagram the formal Makanin-Razborov diagram of the system of equations Σ(x, y, a) = 1 with respect to the (well-structured) resolution Res(y, a). We call each path in this (directed) diagram a formal resolution and denote it F Res(x, z, y, a). Note that by proposition 2.4, every formal resolution terminates with a formal limit group of the form F Cl(s, z, y, a) ∗ F̂, where F Cl(s, z, y, a) is a closure of the resolution Res(y, a) and F̂ is some (possibly trivial) free group. In particular, every formal resolution in the formal Makanin-Razborov diagram is defined over some closure of the completed limit group Comp(Rlim)(z, y, a).

Theorems 1.18 and 1.22 prove that if an AE sentence defined over some limit group is a truth sentence, then there exist formal solutions that may serve as ”witnesses” for the correctness of the sentence in a ”generic” point of the variety associated with the given limit group. Along our ”trial and error” procedure for quantifier elimination we are not going to look for specific formal solutions that satisfy the conclusions of theorems 1.18 and 1.22, but rather study the entire collection of formal solutions by studying the maximal formal limit groups associated with systems of equations with respect to some given resolutions, and then use the conclusions of theorems 1.18 and 1.22 that guarantee that these entire collections of formal solutions contain formal solutions with the properties listed in these theorems. Since this point of view is used extensively in our quantifier elimination procedure, we prefer to state it specifically as a corollary.

Corollary 2.5. Let F_{k} =< a_{1}, …, a_{k} > be a free group, and let u_{1}(y, a), …, u_{m}(y, a) be a collection of words in the alphabet {y, a}, for which the group Rlim(y, a) =< y, a | u_{1}(y, a), …, u_{m}(y, a) > is a restricted limit group. Let Res(y, a) be a wellstructured resolution of the restricted limit group Rlim(y, a), and let Comp(Res)(z, y, a) be the completion of the resolution Res(y, a) with a corresponding completed limit group Comp(Rlim)(z, y, a).

Let Σ(x, y, a) = 1 be a system of equations over F_{k}, and let v_{1}(x, y, a), …, v_{r}(x, y, a) be a collection of words in the alphabet {x, y, a}. Suppose that the sentence: ∀y (u_{1}(y, a) = 1, …, u_{m}(y, a) = 1) ∃x Σ(x, y, a) = 1 ∧ v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1 is a truth sentence.

Then there exists a covering closure: Cl(Res)_{1}(s, z, y, a), …, Cl(Res)_{q}(s, z, y, a), and formal resolutions F Res(x, z, y, a)_{1}, …, F Res_{q}(x, z, y, a) in the formal Makanin-Razborov diagram associated with the system of equations Σ(x, y, a) = 1 and the well-structured resolution Res(y, a), with the following properties:

(i) for each index i, 1 ≤ i ≤ q, the formal resolution F Res_{i}(s, z, y, a) terminates with a formal limit group of the form Cl_{i}(s, z, y, a) ∗ F_{i} for some (possibly trivial) free group F_{i}.

(ii) for each index i, 1 ≤ i ≤ q, there exists a formal solution x_{i}(s, z, y, a) that factors through the resolution F Res_{i}(x, z, y, a), and a specialization (s_{0}^{i}, y_{0}^{i}, f_{0}^{i}, a) that factors through the i-th closure Cl(Res)_{i}(s, z, y, a), so that for every index j:

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

. In particular, in case the above sentence is a truth sentence, the set of closures

that appear in the terminal points of the formal resolutions in the formal Makanin-Razborov diagrams of the system Σ(x, y, a) = 1 and the resolution Res(y, a), contains a covering closure of the restricted resolution Res(y, a).

In a similar way, we get the following corollary from theorem 1.22.

Corollary 2.6. Let F_{k} =< a_{1}, …, a_{k} > be a free group, and let u_{1}(y, a), …, u_{m}(y, a) be a collection of words in the alphabet {y, a}, for which the group Rlim(y, a) =< y, a | u_{1}(y, a), …, u_{m}(y, a) > is a restricted limit group. Let Res(y, a) be a wellstructured resolution of the restricted limit group Rlim(y, a), and let Comp(Res)(z, y, a) be the completion of the resolution Res(y, a), with a corresponding completed limit group Comp(Rlim)(z, y, a).

Let Σ_{1}(x, y, a) = 1, …, Σ_{r}(x, y, a) = 1 be a collection of systems of equations over F_{k}, and let Ψ_{1}(x, y, a), …, Ψ_{r}(x, y, a) be a set of collections of words in the alphabet {x, y, a}. Suppose that the sentence:

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

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

is a truth sentence.

Then there exists a covering closure: Cl(Res)_{1}(s, z, y, a)_{1}, …, Cl(Res)_{q}(s, z, y, a), and formal resolutions F Res(x, z, y, a)_{1}, …, F Res_{q}(x, z, y, a), where for each index i, 1 ≤ i ≤ q, there exists some index j(i), 1 ≤ j(i) ≤ r, for which F Res_{i}(x, z, y, a) is a formal resolution in the formal Makanin-Razborov diagram of the system of equations Σ_{j(i)}(x, y, a) = 1 and the well-structured resolution Res(y, a), with the following properties:

(i) for each index i, 1 ≤ i ≤ q, the formal resolution F Res_{i}(s, z, y, a) terminates with a formal limit group of the form Cl_{i}(s, z, y, a) ∗ F_{i} for some (possibly trivial) free group F_{i}.

(ii) for each index i, 1 ≤ i ≤ q, there exists a formal solution x_{i}(s, z, y, a) that factors through the formal resolution F Res_{i}(x, z, y, a), so that there exists a specialization (s_{0}^{i}, y_{0}^{i}, f_{0}^{i}, a) that factors through the i-th closure Cl(Res)_{i}(s, z, y, a) so that all the words in the collection Ψ_{j(i)}(x_{i}(s_{0}^{i}, y_{0}^{i}, f_{0}^{i}, a), y_{0}^{i}, f_{0}^{i}, a) are not the trivial element in F_{k}.

In particular, in case the above sentence is a truth sentence, the set of closures that appear as the terminal points of the formal resolutions in the collection of formal Makanin-Razborov diagrams of the systems Σ_{j}(x, y, a) = 1 and the resolution Res(y, a) contains a covering closure of the restricted resolution Res(y, a).

§3. Graded Formal Limit Groups

Theorems 1.18 and 1.22 show that given a restricted limit group and a wellstructured resolution of that limit group, the validity of an AE sentence defined over the given restricted limit group implies the existence of a finite collection of formal solutions defined over a covering closure of the given well-structured resolution of that limit group. In the previous section we studied the entire family of formal solutions of a system of equations Σ(x, y, a) = 1 with respect to a given well-structured resolution Res(y, a). For the purpose of our quantifier elimination procedure, an understanding of the structure of such families of formal solutions is not sufficient. Our quantifier elimination procedure requires a careful analysis of parametric families of formal solutions. i.e., given a graded limit group Glim(y, p, a), a (well-structured) graded resolution of it, GRes(y, p, a), and a parametric system of equations Σ(x, y, p, a) = 1, we need to study how the family of formal solutions of the system Σ(x, y, p, a) and the graded resolution GRes(y, p, a), varies with a change of the defining parameters p. To analyze the variation of the set of formal solutions, we combine the techniques used in the previous section with the ones used in the construction of the graded Makanin-Razborov diagram of a graded limit group presented in sections 9-10 in [Se1].

Let Glim(y, p, a) be a graded limit group, and let GRes(y, p, a) be a wellstructured graded resolution of it. The graded resolution GRes(y, p, a) terminates in either a rigid graded limit group, Rgd(y, p, a), or a solid graded limit group, Sld(y, p, a). By section 10 in [Se1], for any given specialization p_{0} of the defining parameters p, the graded resolution GRes(y, p, a) ”covers” at most finitely many ungraded resolutions of the form Res(y, p_{0}, a), where each of the resolutions Res(y, p, a) terminates in either a rigid specialization of Rgd(y, p, a), in case the graded resolution GRes(y, p, a) terminates in the rigid graded limit group Rgd(y, p, a), or a solid family of specializations of Sld(y, p, a), in case the graded resolution GRes(y, p, a) terminates in the solid graded limit group Sld(y, p, a). Since the graded resolution GRes(y, p, a) is well-structured, so are all the non-degenerate ungraded resolutions Res(y, p_{0}, a) covered by it.

In analyzing the entire collection of formal solutions of the system Σ(x, y, p_{0}, a) = 1 and an ungraded resolution of the form Res(y, p_{0}, a), that is ”covered” by the graded resolution GRes(y, p, a), we will assume that the ungraded resolution Res(y, p_{0}, a) is non-degenerate. According to section 11 of [Se1], there are finitely many ways for the ”covered” ungraded resolution Res(y, p_{0}, a) to be degenerate, and the collection of all formal solutions defined over ungraded resolutions that are degenerated in a particular way (one of the finitely many possibilities), can be analyzed using precisely the same procedure used to analyze the collection of formal solutions defined over non-degenerate ungraded resolutions.

In section 1 of this paper we defined the completion of a well-structured ungraded resolution. Hence, with each of the (non-degenerate, well-structured) ungraded resolutions Res(y, p_{0}, a), that is covered by the graded resolution GRes(y, p, a), we can associate its completion Comp(Res)(z, y, p_{0}, a). Since all the (non-degenerate) ungraded resolutions Res(y, p_{0}, a) are covered by the graded resolution GRes(y, p, a), they all terminate in the same free group which we denote by < a, f >, and the variables z added at the various levels in each of the completions Comp(Res)(z, y, p_{0}, a), associated with the ungraded resolutions Res(y, p_{0}, a), are added in a compatible way in accordance with the structure of the graded resolution GRes(y, p, a). Also, the decompositions associated with the different levels of the completed resolutions Comp(Res)(y, p_{0}, a) are compatible, which implies the compatibility of the QH subgroups appear in the different levels, as well as the abelian vertex and edge groups that appear in the various levels of those completions.

As in the ungraded setup, given a graded limit group, Glim(y, p, a), and a graded well-structured resolution of it, GRes(y, p, a), to analyze the family of all formal solutions of a given system of parametric equations Σ(x, y, p, a) = 1 and a (nondegenerate) ungraded resolutions Res(y, p_{0}, a) that is covered by the given graded resolution GRes(y, p, a), we need to present graded formal limit groups and their canonically associated graded formal Makanin-Razborov diagrams. As we did in the first two sections of this paper, to construct graded formal limit groups we start by defining graded test sequences associated with the graded resolution GRes(y, p, a). The structure of all the non-degenerate ungraded resolutions GRes(y, p_{0}, a) covered by the graded resolution GRes(y, p, a) is compatible. Hence, as we did in the ungraded case, to define graded test sequences we fix a (bottom to top) order of the QH and abelian vertex groups that appear in the completion of the nondegenerate ungraded resolutions GRes(y, p_{0}, a) covered by GRes(y, p, a). We also fix an (ordered) bases for the abelian and pegged abelian groups that appear in such (non-degenerate) completed resolutions Comp(GRes)(z, y, a).

Definition 3.1. Let Glim(y, p, a) be a graded limit group, and let GRes(y, p, a) be a well-structured graded resolution of Glim(y, p, a) that terminates in either a rigid graded limit group Rgd(y, p, a), or a solid graded limit group Sld(y, p, a). Let X be the Cayley graph of F_{k} =< a_{1}, …, a_{k} >, and let Y be the Cayley graph of Comp(Glim)(z, y, p, a). Let d_{X} and d_{Y} be the corresponding (simplicial) metrics.

Let {(y_{n}, p_{n}, a)} be a sequence of either rigid or solid specializations of the terminal rigid or solid graded limit groups of the graded resolution GRes(y, p, a), Rgd(y, p, a) or Sld(y, p, a) in correspondence, and let {GRes(y, p_{n}, a)} be the ungraded resolutions covered by GRes(y, p, a) corresponding to these specializations. We say that the sequence {(y_{n}, p_{n}, a)}, together with a sequence of automorphisms {(ν_{n}^{i}, τ_{n}^{i})} of the QH subgroups that appear in the graded abelian decompositions associated with the various levels in the completed resolutions Comp(GRes)(z, y, p_{n}, a), and a sequence of homomorphisms {λ_{n} : Comp(Glim)(z, y, p_{n}, a) → F_{k}}, is a graded test sequence if the following conditions hold. For every index n:

(i) the ungraded resolutions GRes(y, p_{n}, a) are non-degenerate.

(ii) conditions (i)-(xiv) of definition 1.20 (defining an ungraded test sequence) hold for the completed ungraded resolution Comp(GRes)(z, y, p_{n}, a), the automorphisms {(ν_{n}^{i}, τ_{n}^{i})} and the homomorphism λ_{n} : Comp(GRes)(z, y, p_{n}, a) → F_{k}.

(iii) if g ∈ Comp(Glim)(z, y, p, a), d_{Y} (g, id.) ≤ n, and g is not elliptic in at least one of the abelian decomposition associated with the various levels of the (ungraded) completed resolution Comp(Res)(z, y, p_{n}, a), then:

n · max d_{X}(p_{n}, id.) < d_{X}(λ_{n}(g), id.).

Lemma 3.2. Let GRes(y, p, a) be a well-structured graded resolution of the graded limit group Glim(y, p, a). Let {(y_{n}, p_{n}, a)} be a sequence of either rigid or solid specializations of the terminal rigid or solid limit group, Rgd(y, p, a) or Sld(y, p, a), for which the corresponding ungraded resolutions GRes(y, p_{n}, a) covered by the graded resolution GRes(y, p, a) are non-degenerate. Then there exists a sequence of automorphisms {(ν_{n}^{i}, τ_{n}^{i})} of the QH subgroups that appear in the abelian decompositions associated with the various levels of the completed resolutions {Comp(GRes)(z, y, p_{n}, a)} and homomorphisms {λ_{n} : Comp(Glim)(z, y, p_{n}, a) → F_{k}, so that these sequences together with the given sequence of specializations {(y_{n}, p_{n}, a)} is a graded test sequence. Furthermore, given any two integers s_{1} < s_{2} we can choose the n-th specialization of a basis element q_{r}^{t} of some of the (pegged) abelian groups that appear in an abelian decomposition associated with some level of the completed resolution Comp(GRes)(y, p_{n}, a), to be of the form λ_{n}(q_{i}^{t}) = h_{n}^{ms_{2}+s_{1}} for some integer m, and so that the element h_{n} has no non-trivial roots in F_{k}.

Proof: Since for every index n, the ungraded resolution GRes(y, p_{n}, a) is assumed to be non-degenerate, the proof of the lemma is identical to the proof of lemma 1.21.

□

Constructing graded test sequences, we are finally able to start analyzing the family of formal solutions of a given system of equations with respect to a given (well-structured) graded resolution. We start this analysis by defining graded formal limit groups.

Definition 3.3. Let Σ(x, y, p, a) = 1 be a system of equations, and let GRes(y, p, a) be a well-structured graded resolution of a graded limit group Glim(y, p, a). Let {(y_{n}, p_{n}, a)} be a sequence of either rigid or solid specializations of the terminal rigid or solid limit group of the graded resolution GRes(y, p, a), Rgd(y, p, a) or Sld(y, p, a) in correspondence. Let the sequence of specializations {(y_{n}, p_{n}, a)} together with a sequence of automorphisms {(ν_{n}^{i}, τ_{n}^{i})} of the QH subgroups QH_{i} that appear in the abelian decompositions associated with the various levels of the completed resolutions {Comp(GRes)(z, y, p_{n}, a)}, and the sequence of homomorphisms: {λ_{n} : Comp(GRes)(z, y, p_{n}, a) → F_{k}} be a graded test sequence. Suppose that for every index n there exists some specialization x_{n}, for which: Σ(x_{n}, λ_{n}(y), p_{n}, a) = 1. For each index n, the homomorphism λ_{n} : Comp(GRes)(z, y, p_{n}, a) → F_{k} together with the specialization x_{n}, define a homomorphism from the free group F (x, z, y, p, a) to F_{k}, β_{n} : F (x, z, y, p, a) → F_{k}.

We say that the given test sequence together with the sequence of specializations {x_{n}} is a convergent graded formal sequence, if the corresponding sequence of homomorphisms: {β_{n} : F (x, z, y, p, a) → F_{k}} is convergent (in the Gromov-Haussdorff topology, after appropriate rescaling). We call the obtained limit group, a graded formal limit group, and denote it GF L(x, z, y, p, a).

As in analyzing (ungraded) formal limit groups, with a graded formal limit group we can naturally associate a graded formal closure.

Definition 3.4. Let GF L(x, z, y, p, a) be a graded formal limit group, and let:

C(z, y, p, a) = < z, y, p, a > < GF L(x, z, y, p, a).

Since every abelian subgroup of a limit group is contained in a unique maximal abelian subgroup, every abelian subgroup of a limit group is contained in a unique maximal abelian subgroup of the same rank. By replacing the (pegged) abelian groups that appear in the abelian decompositions associated with the various levels in the graded completion, C(z, y, p, a), by the maximal abelian groups of the same rank containing them in GF L(x, z, y, p, a), we obtain a (canonical) subgroup (graded closure) in GF L(x, z, y, p, a), which we call the graded formal closure of C(z, y, p, a) in the graded formal limit group GF L(x, z, y, p, a). We denote the graded formal closure, GF Cl(s, z, y, p, a).

To analyze graded formal limit groups we need to construct their associated (canonical) graded formal Makanin-Razborov diagrams. To do that we need to study the algebraic structure of graded formal limit groups GF L(x, z, y, p, a), relative to the subgroup < z, y, p, a >. To do that we start by defining the graded formal JSJ decomposition of a graded formal limit group.

In the sequel below let GRes(y, p, a) be a well-structured graded Makanin-Razborov resolution of a graded limit group Glim(y, p, a), and let Σ(x, y, p, a) = 1 be a system of equations. Let GF L(x, z, y, p, a) be a graded formal limit group with respect to the system of equations Σ(x, y, p, a) = 1 relative to the well-structured graded resolution GRes(y, p, a). We further use the notation:

C(z, y, p, a) =< z, y, p, a > < GF L(x, z, y, p, a) AP =< a, p > < GF L(x, z, y, p, a).

Definition 3.5. Suppose the graded formal limit group GF L(x, z, y, p, a) does not split into a non-trivial free product in which C(z, y, p, a) is contained in one of the factors. A one edge essential abelian splitting, GF L(x, z, y, p, a) = D ∗_{A} E or GF L(x, z, y, p, a) = D∗_{A}, in which C(z, y, p, a) is elliptic, is called a graded formal abelian splitting.

The arguments used in section 2 of [Se1] to construct the abelian JSJ decomposition of a limit group, naturally generalize to construct the graded formal JSJ decomposition of a graded formal limit group.

Theorem 3.6 (cf. ([Se1],9.2)). Let GF L(x, z, y, p, a) be a graded formal limit group which does not split to a non-trivial free product in which the subgroup C(z, y, p, a) is contained in one of the factors. There exists an essential (perhaps trivial) abelian splitting of GF L(x, z, y, p, a), which we call the graded formal JSJ decomposition of GF L(x, z, y, p, a), with the following properties:

(i) C(z, y, p, a) is elliptic in the graded formal JSJ decomposition. If the graded formal JSJ decomposition of GF L(x, z, y, p, a) is non-trivial, then any one edge abelian splitting obtained by collapsing all edges but one in the graded formal JSJ decomposition is a graded formal splitting of GF L(x, z, y, p, a).

(ii) Every graded (formal) canonical maximal QH subgroup (CMQ) of GF L(x, z, y, p, a) is conjugate to a vertex group in the graded formal JSJ decomposition. Every graded formal QH subgroup of GF L(x, z, y, p, a) can be conjugated into one of the graded formal CMQ subgroups of GF L(x, z, y, p, a). Every vertex group in the graded formal JSJ decomposition which is not a CMQ subgroup of GF L(x, z, y, p, a) is elliptic in any graded formal splitting of GF L(x, z, y, p, a).

(iii) A one edge graded formal splitting GF L(x, z, y, p, a) = D∗_{A}E or GF L(x, z, y, p, a) = D∗_{A}, which is hyperbolic in another such elementary graded formal splitting, is obtained from the graded formal JSJ decomposition of GF L(x, z, y, p, a) by cutting a surface corresponding to a graded (formal) CMQ subgroup of GF L(x, z, y, p, a) along an essential s.c.c..

(iv) Let Θ be a one edge graded formal splitting GF L(x, z, y, p, a) = D ∗_{A} E or GF L(x, z, y, p, a) = D∗_{A}, which is elliptic with respect to any other such one edge graded formal splitting of GF L(x, z, y, p, a). Then Θ is obtained from the graded formal JSJ decomposition of GF L(x, z, y, p, a) by a sequence of collapsings, conjugations, and modifying boundary monomorphisms by conjugations.

(v) Let Λ be a general graded formal abelian splitting of GF L(x, z, y, p, a). There exists a graded formal splitting Λ_{1} obtained from the graded formal JSJ decomposition by splitting the graded (formal) CMQ subgroups along essential s.c.c. on their corresponding surfaces, so that there exists a GF L(x, z, y, p, a)-equivariant simplicial map between a subdivision of the Bass-Serre tree T_{Λ_{1}} to T_{Λ}.

(vi) If JSJ_{1} is another graded formal JSJ decomposition of GF L(x, z, y, p, a), then JSJ_{1} is obtained from the graded formal JSJ decomposition by a sequence of slidings, conjugations and modifying boundary monomorphisms by conjugations (see section 1 of [Ri-Se2] for these notions)

(vii) If GF L(x, z, y, p, a) admits a formal abelian splitting then the graded formal JSJ decomposition of GF L(x, z, y, p, f, a) is non-trivial.

As in analyzing graded limit groups, the graded formal JSJ decomposition allows one to ”further simplify” graded formal limit groups in case it is not trivial. In order to construct graded formal Makanin-Razborov diagrams we still need to study the structure of rigid graded formal limit groups (i.e., graded formal limit groups with trivial graded formal JSJ decomposition), as well as solid graded formal limit groups. In both cases we divide our study into two parts. First we assume that the graded resolution we have started with, GRes(y, a), terminates in a rigid limit group, and then we analyze the case in which the graded resolution GRes(y, a) terminates in a solid limit group.

Theorem 3.7. Let GF L(x, z, y, p, a) be a graded formal limit group that does not split as a non-trivial free product in which the subgroup C(z, y, p, a) is contained in one of the factors, and suppose that the graded formal JSJ decomposition of GF L(x, z, y, p, a) is trivial.

(i) Suppose that the graded resolution we have started with, GRes(y, a), terminates in a rigid limit group. Then there exists a rigid graded (not formal!) limit group Rgd(b, p, a), so that GF L(x, z, y, p, a) can be written as an amalgamated product:

GF L(x, z, y, p, a) = Rgd(b, p, a) ∗_{T erm(ŝ,z,p,a)} GF Cl(s, z, y, p, a).

(ii) Suppose that the graded resolution we have started with, GRes(y, a), terminates in a solid limit group. Then there exists a graded (not formal!) limit group Glim_{t}(b, p, a), so that GF L(x, z, y, p, a) can be written as an amalgamated product:

GF L(x, z, y, p, a) = Glim_{t}(b, p, a) ∗_{T erm(ŝ,z,p,a)} GF Cl(s, z, y, p, a)

where in both cases, GF Cl(s, z, y, p, a) is the graded formal closure associated with GF L(x, z, y, p, a), and the elements {ŝ} are primitive roots of some of the pegs of pegged abelian groups that appear in the various levels of the graded formal closure GF Cl(s, z, y, p, a). T erm(ŝ, z, p, a) is the terminal subgroup of the graded formal closure GF Cl(s, z, y, p, a).

Proof: Suppose that the graded resolution GRes(y, a) terminates in a rigid limit group, and the graded formal limit group GF L(x, z, y, p, a) does not split as a nontrivial free product in which C(z, y, p, a) is contained in one of the factors, and the graded formal JSJ decomposition of GF L(x, z, y, p, a) is trivial. The graded formal limit group GF L(x, z, y, p, a) was constructed from a convergent graded formal sequence, obtained from a test sequence composed of specializations {(y_{n}, p_{n}, a)}, of the terminal rigid graded limit group of the graded resolution GRes(y, p, a), automorphisms {(ν_{n}^{i}, τ_{n}^{i})} of the QH subgroups that appear in the various levels in the completed resolutions Comp(GRes)(z, y, p_{n}, a), and homomorphisms {λ_{n} : Comp(GRes)(z, y, p_{n}, a) → F_{k}}, and a sequence of specializations {x_{n}}, for which: Σ(x_{n}, λ_{n}(y), p_{n}, a) = 1, so that the sequence of homomorphisms α_{n} : F (x, z, y, p, a) → F_{k} converges.

From the convergence of the sequence of homomorphisms {α_{n} : F (x, z, y, p, a) → F_{k}}, we get a (non-trivial) stable action of the graded formal limit group GF L(x, z, y, p, a) on a real tree Y_{1}. By the classification of stable actions of f.g. groups on real trees (see theorem 1.5 in [Se1]), with the action of GF L(x, z, y, p, a) on the real tree Y_{1}, there is an associated (non-trivial) graph of groups Λ_{1} with abelian edge stabilizers. If the subgroup C(z, y, p, a) is contained in a vertex group of Λ_{1}, or more generally if C(z, y, p, a) is contained in the fundamental group of a proper subgraph of Λ_{1}, the graded formal limit group GF L(x, z, y, p, a) admits a non-trivial graded formal decomposition, a contradiction to our assumptions.

Suppose that the graded limit group Glim(y, p, a), associated with the graded resolution GRes(y, p, a), is of the form: Glim(y, p, a) = Rgd(w, p, a)∗ < f > where F =< f_{1}, …, f_{c} > is a free group, and Rgd(w, p, a) is a rigid graded (not formal!) limit group, and the graded resolution GRes(y, p, a) terminates in the rigid graded limit group Rgd(w, p, a). In this case, since GF L(x, z, y, p, a) admits no free decomposition in which C(z, y, p, a) is contained in one of the factors, since the graded formal JSJ decomposition of GF L(x, z, y, p, a) is trivial, and since GF L(x, z, y, p, a) admits a non-trivial action on a real tree, necessarily: GF L(x, z, y, p, a) = Rgd(b, p, a) ∗ F, so GF L(x, z, y, p, a) = Rgd(b, p, a) ∗_{Rgd(w,p,a)} (Rgd(w, p, a)∗F), which proves the statement of the theorem in case Glim(x, z, y, p, a) = Rgd(w, p, a) ∗ F.

Hence, we may assume that Glim(y, p, a) is not of the form Rgd(w, p, a) ∗ F for Rgd(w, p, a) rigid, F free, and GRes(y, p, a) terminates in Rgd(w, p, a). By the properties of a graded formal test sequence (definition 3.1), the action of C(z, y, p, a) on the real tree Y_{1} either contains a unique IET orbit and finitely many orbits of point stabilizers, or the action is discrete with a unique orbit of non-abelian point stabilizer and a unique edge stabilized by some abelian subgroup of C(z, y, p, a). Since GF L(x, z, y, p, a) inherits from its action on Y_{1} a graph of groups of the same form as the one C(z, y, p, f, a) inherits from its action on Y_{1}, the action of GF L(x, z, y, p, a) on Y_{1} must contain either a unique orbit of an IET component and finitely many orbits of point stabilizers, or its action is discrete with one orbit of non-abelian point stabilizers and one orbit of edges stabilized by some abelian subgroup of GF L(x, z, y, p, a). In both types of the dynamics of the action of GF L(x, z, y, p, a) on the limit tree Y_{1}, the generators x of the graded formal limit group GF L(x, z, y, p, a) can be written as words in elements from the vertex stabilizers V_{1}^{i} and elements from the graded formal closure GF Cl(s, z, y, p, a). ”Uncovering” the top level, we continue with each of the non-abelian, non-QH vertex stabilizers V_{1}^{i} in the graph of groups Λ_{1}, and the actions these vertex stabilizers obtain on corresponding real trees Y_{2}^{i}. Repeating the argument used for analyzing the action of GF L(x, y, z, p, a) on the real tree Y_{1}, for the actions of the groups V_{1}^{i} on the real trees Y_{2}^{i}, if C(z, y, p, a)∩V_{1}^{i} is not of the form T erm(w, p, a) ∗ F where F =< f_{1}, …, f_{c} > is free, and T erm(w, p, a) is the terminal subgroup of the completion C(z, y, p, a), i.e., if we did not yet ”finished” with all the levels of the graded resolution GRes(y, p, a), the action of V_{1}^{i} on Y_{2}^{i} must have the same dynamics as one of the two possibilities described above. i.e., either it contains a unique orbit of an IET component and finitely many orbits of point stabilizers, or the action is discrete with one orbit of non-abelian point stabilizers and one orbit of edges stabilized by some abelian subgroup of the graded formal closure GF Cl(s, z, y, p, a). Hence, the generators x of the formal limit group GF L(x, z, y, p, a) can again be written as words in elements from vertex stabilizers W_{2}^{i} and elements from the graded formal closure GF Cl(s, z, y, p, a).

This process continues until at some stage ℓ, C(z, y, p, a) ∩ V_{ℓ}^{i} is of the form T erm(w, p, a) ∗ F, where F is free, and T erm(w, p, a) is the terminal group in the graded completion C(z, y, p, a). Therefore, a finite induction argument implies that every element in the graded formal limit group GF L(x, z, y, p, a) can be written as a word in elements from the graded formal closure GF Cl(s, z, y, p, a), and elements from the terminal vertex V_{ℓ}, which is necessarily rigid. We denote this terminal vertex group V_{ℓ}, Rgd(b, p, a). Clearly, the terminal group of the graded formal closure GF Cl(s, z, p, a), which we denote T erm(ŝ, z, p, a), is a subgroup of Rgd(b, p, a), and part (i) of the theorem follows. The proof of the theorem in case the graded resolution GRes(y, p, a) terminates in a solid limit group (part (ii)) is identical.

□

Defining graded formal limit groups and their graded formal JSJ decompositions, and showing that a (relatively) freely indecomposable graded formal limit group with trivial formal JSJ decomposition has the ”same structure” as a graded formal closure GF Cl(s, z, y, p, a), we are able to present graded formal Makanin-Razborov diagrams.

Let GRes(y, p, a) be a graded well-structured resolution of a graded limit group Glim(y, p, a), and let Σ(x, y, p, a) = 1 be a system of equations. Recall that a graded formal limit group GF L(x, z, y, p, a) of the system Σ(x, y, p, a) = 1 with respect to the graded resolution GRes(y, p, a), was constructed from a graded formal test sequence. On the set of graded formal limit groups GF L(x, z, y, p, a) associated with the system Σ(x, z, y, p, a) = 1, and the graded formal resolution GRes(y, p, a), we can naturally define a partial order. We say that GF L_{1}(x, z, y, p, a) ≥ GF L_{2}(x, z, y, p, a), if there exists an epimorphism:

η : GF L_{1}(x, z, y, p, a) → GF L_{2}(x, z, y, p, a).

By the arguments used in the construction of the Makanin-Razborov diagram of a limit group (lemma 5.4 and 5.5 in [Se1]), given the system of equations Σ(x, y, p, a) = 1 and the graded resolution GRes(y, p, a), there exist maximal graded formal limit groups, and up to the natural equivalence relation on graded formal limit groups, there are only finitely many equivalence classes of maximal graded formal limit groups which we denote: MGF L_{1}(x, z, y, p, a), …, MGF L_{n}(x, z, y, p, a).

To construct the graded formal Makanin-Razborov diagram of the system Σ(x, y, p, a) = 1 with respect to the graded resolution GRes(y, p, a), we proceed as in the construction of the graded Makanin-Razborov diagrams (see sections 9-10 in [Se1]). We first decompose each of the maximal graded formal limit groups into the maximal (canonical) free decomposition in which the subgroup:

C(z, y, p, a) =< z, y, p, a > < MGF L_{i}(x, z, y, p, a)

is contained in a factor. We associate the graded formal JSJ decomposition with the factor containing C(z, y, p, a), and the (standard) abelian JSJ decomposition with each of the other factors. These associated JSJ decompositions naturally define the graded formal modular groups of each of the maximal graded formal limit groups MGF L_{i}(x, z, y, p, a). Having these modular groups, we are able to define graded formal shortening quotients of each of the maximal graded formal limit groups. Theorem 3.7 analyzes graded formal limit groups with trivial graded formal JSJ decomposition. In a similar way, one can analyze graded formal limit groups with non-trivial graded formal JSJ decomposition, which are isomorphic to one of their graded formal shortening quotients, which we call solid formal limit groups. As in analyzing rigid formal limit groups, we divide our study of solid limit groups into two parts, depending on whether the terminal limit group of the graded resolution GRes(y, a) is rigid or solid.

Theorem 3.8. Let GF L(x, z, y, p, a) be a graded formal limit group which does not split as a non-trivial free product in which the subgroup C(z, y, p, a) is contained in one of the factors. Suppose that the graded formal JSJ decomposition of GF L(x, z, y, p, a) is non-trivial, and there exists a graded formal shortening quotient of GF L(x, z, y, p, a) that is isomorphic to GF L(x, z, y, p, a).

(i) Suppose that the terminal limit group of the graded resolution, GRes(y, a), is rigid. Then there exists a solid graded (not formal!) limit group Sld(b, p, a), so that the graded formal limit group GF L(x, z, y, p, a) can be written in the form:

GF L(x, z, y, p, a) = Sld(b, p, a) ∗_{T erm(ŝ,z,p,a)} GF Cl(s, z, y, p, a).

(ii) Suppose that the terminal limit group of the graded resolution, GRes(y, a), is solid. Then there exists a graded (not formal!) limit group Glim_{t}(b, p, a), so that the graded formal limit group GF L(x, z, y, p, a) can be written in the form:

GF L(x, z, y, p, a) = Glim_{t}(b, p, a) ∗_{T erm(ŝ,z,p,a)} GF Cl(s, z, y, p, a)

where in both cases, GF Cl(s, z, y, p, a) is the graded formal closure associated with GF L(x, z, y, p, a), and the elements {ŝ} are primitive roots of some of the pegs of pegged abelian groups that appear in the various levels of the graded formal closure GF Cl(s, z, y, p, a). T erm(ŝ, z, p, a) is the terminal subgroup of the graded formal closure GF Cl(s, z, y, p, a).

Proof: Identical with the proof of theorem 3.7.

□

The combinations of theorems 3.7 and 3.8 allow us to complete the construction of the graded formal Makanin-Razborov diagram. Suppose that the graded formal limit group GF L(x, z, y, p, a) admits a non-trivial graded formal JSJ decomposition, and every graded formal shortening quotient of it is a proper quotient. By the arguments used to prove lemmas 5.4 and 5.5 in [Se1], there are maximal graded formal shortening quotients, and up to the natural equivalence classes of graded formal limit groups, there are only finitely many equivalence classes of maximal graded formal shortening quotients of each of the maximal graded formal limit groups: MGF SQ_{1}(x, z, y, p, a), …, MGF SQ_{n}(x, z, y, p, a).

Since a graded formal limit group is in particular a limit group, any properly decreasing sequence of graded formal limit groups terminates. Therefore, if we continue the above construction of maximal graded formal free decompositions, graded formal JSJ decompositions and graded formal modular groups for each of the factors, and then collecting the (canonical) family of maximal graded formal shortening quotients, and assuming each graded formal shortening quotient is indeed a proper quotient, we are guaranteed that this iterative construction terminates. When the process of collecting maximal graded formal shortening quotients which are proper quotients terminates, we are left with either rigid or solid formal limit groups. By theorems 3.7 and , a rigid or solid formal limit group has the form:

GF L(x, z, y, p, a) = Glim_{t}(b, p, a) ∗_{T erm(ŝ,z,p,a)} GF Cl(s, z, y, p, a)

for some graded (not formal!) limit group Glim_{t}(b, p, a). We continue the diagram with the graded (not formal!) Makanin-Razborov diagrams of the graded limit group Glim_{t}(b, p, a).

We call the obtained diagram the graded formal Makanin-Razborov diagram of the system of equations Σ(x, y, p, a) = 1 with respect to the graded resolution GRes(y, p, a). We call each path in this (directed) diagram a graded formal (Makanin-Razborov) resolution and denote it GF Res(x, z, y, p, a). Note that with every such graded formal resolution one can naturally associate a graded formal closure GF Cl(s, z, y, p, a) of the original graded resolution Gres(y, p, a). Also, note that every non-QH, non-abelian vertex group and every edge group in the abelian decomposition associated with the terminal rigid or solid limit group of the graded resolution GRes(y, a) we have started with, remains elliptic along all the graded formal resolutions of the formal limit group GF L(x, z, y, p, a).

Theorems 1.18 and 1.22 prove that if an AE sentence is a truth sentence over the set of specializations of some (ungraded) limit group group, then there exist formal solutions that may serve as ”witnesses” for the correctness of the sentence in a ”generic” point. Corollaries 2.5 and 2.6 state the existence of these ”witnesses” in terms of the formal Makanin-Razborov diagram associated with a system of equations Σ(x, y, a) = 1 with respect to a given well-structured resolution Res(y, a). Since our ”trial and error” procedure for quantifier elimination is based on finding ”witnesses” in stratas of the parameter set, i.e., graded formal solutions that satisfy the properties of theorems 1.18 and 1.22 on ”nice” subsets of the ambient set of defining parameters, we present generalizations of corollaries 2.5 and 2.6 in the graded framework.

Corollary 3.9. Let F_{k} =< a_{1}, …, a_{k} > be a free group, let Glim(y, p, a) be a graded limit group defined by the set of relations: u_{1}(y, p, a) = 1, …, u_{m}(y, p, a) = 1, and let GRes(y, p, a) be a well-structured graded resolution of the graded limit group Glim(y, p, a).

Let Σ(x, y, p, a) = 1 be a system of equations over F_{k}, and let v_{1}(x, y, p, a), …, v_{r}(x, y, p, a) be a collection of words in the alphabet {x, y, p, a}. Let T (p) be defined by the predicate:

T (p) = ∀y (u_{1}(y, p, a) = 1, …, u_{m}(y, p, a) = 1) ∃x Σ(x, y, p, a) = 1 ∧

∧ v_{1}(x, y, p, a) ≠ 1, …, v_{r}(x, y, p, a) ≠ 1.

If a specialization p_{0} ∈ T (p), and (y_{0}, p_{0}, a) is a specialization of the terminal rigid or solid graded limit group of the graded resolution GRes(y, p, a), then there exists a collection of formal resolutions:

F Res_{1}(x, z, y, p_{0}, a), …, F Res_{q}(x, z, y, p_{0}, a)

covered by graded formal resolutions:

GF Res_{i_{1}}(x, z, y, p, a), …, GF Res_{i_{q}}(x, z, y, p, a)

from the graded formal Makanin-Razborov diagram of the system Σ(x, y, p, a) = 1 with respect to the graded resolution GRes(y, p, a), for which:

(i) the collection of formal closures:

F Cl_{1}(s, z, y, p_{0}, a), …, F Cl_{q}(s, z, y, p_{0}, a)

associated with the formal resolutions:

F Res_{1}(x, z, y, p_{0}, a), …, F Res_{q}(x, z, y, p_{0}, a)

is a covering closure of the (ungraded) resolution GRes(y, p_{0}, a) corresponding to the specialization (y_{0}, p_{0}, a).

(ii) for each index i, 1 ≤ i ≤ q, there exists a formal solution x_{i}(s, z, y, p_{0}, a) that factors through the formal resolution F Res_{i}(x, z, y, p_{0}, a), and a specialization (s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, p_{0}, a), so that for every index j:

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

.

In particular, in case the above predicate is truth at p_{0}, then for any specialization (y_{0}, p_{0}, a) of the terminal rigid or solid limit group of the graded resolution GRes(y, p, a), the set of formal closures associated with formal resolutions covered by the graded formal resolutions in the graded formal Makanin-Razborov diagram of the system Σ(x, y, p, a) = 1 with respect to the graded resolution GRes(y, p, a), contains a covering closure of the (ungraded) resolution GRes(y, p_{0}, a) corresponding to the specialization (y_{0}, p_{0}, a).

In a similar way, we get the following corollary from theorem 2.6.

Corollary 3.10. Let F_{k} =< a_{1}, …, a_{k} > be a free group, let Glim(y, p, a) be a graded limit group defined by the set of relations: u_{1}(y, p, a) = 1, …, u_{m}(y, p, a) = 1, and let GRes(y, p, a) be a well-structured graded resolution of the graded limit group Glim(y, p, a).

Let Σ_{1}(x, y, p, a) = 1, …, Σ_{r}(x, y, p, a) = 1 be a collection of systems of equations over F_{k}, and let Ψ_{1}(x, y, p, a), …, Ψ_{r}(x, y, p, a) be a set of collections of words in the alphabet {x, y, p, a}. Let T (p) be defined by the predicate:

T (p) = ∀y (u_{1}(y, p, a) = 1, …, u_{m}(y, p, a) = 1) ∃x

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

If a specialization p_{0} ∈ T (p), and (y_{0}, p_{0}, a) is a specialization of the terminal rigid or solid graded limit group of the graded resolution GRes(y, p, a), then there exists a collection of formal resolutions:

F Res_{1}(x, z, y, p_{0}, a), …, F Res_{q}(x, z, y, p_{0}, a)

covered by graded formal resolutions:

GF Res_{i_{1}}(x, z, y, p, a), …, GF Res_{i_{q}}(x, z, y, p, a)

from the graded formal Makanin-Razborov diagrams of the systems:

Σj(i_{1})(x, y, p, a), …, Σj(i_{q})(x, y, p, a)

in correspondence, with respect to the graded resolution GRes(y, p, a), for which: (i) the collection of formal closures:

F Cl_{1}(s, z, y, p_{0}, a), …, F Cl_{q}(s, z, y, p_{0}, a)

associated with the formal resolutions:

F Res_{1}(x, z, y, p_{0}, a), …, F Res_{q}(x, z, y, p_{0}, a)

is a covering closure of the (ungraded) resolution GRes(y, p_{0}, a) corresponding to the specialization (y_{0}, p_{0}, a).

(ii) for each index i, 1 ≤ i ≤ q, there exists a formal solution x_{i}(s, z, y, p_{0}, a) that factors through the formal resolution F Res_{i}(x, z, y, p_{0}, a), and a specialization (s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, p_{0}, a), for which:

Ψ_{j(i)}(x_{i}(s_{0}^{i}, z_{0}^{i}, y_{0}^{i}, p_{0}, a), y_{0}^{i}, p_{0}, a) ≠ 1.

In particular, in case the above predicate is truth at p_{0}, then for any specialization (y_{0}, p_{0}, a) of the terminal rigid or solid limit group of the graded resolution GRes(y, p, a), the set of formal closures associated with formal resolutions covered by the graded formal resolutions in the graded formal Makanin-Razborov diagrams of the systems:

Σ_{1}(x, y, p, a) = 1, …, Σ_{r}(x, y, p, a) = 1

with respect to the graded resolution GRes(y, p, a), contains a covering closure of the (ungraded) resolution GRes(y, p_{0}, a) corresponding to the specialization (y_{0}, p_{0}, a).

References

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

[Ma] G. S. Makanin, 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.

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

[Ri-Se2] , Cyclic splittings of finitely presented groups and the canonical JSJ decomposition, Annals of Mathematics 146 (1997), 53-104.

[Se] Z. Sela, Diophantine geometry over groups I: Makanin-Razborov diagrams, Publications Mathematiques de l’IHES, to appear.