DIOPHANTINE GEOMETRY OVER GROUPS II:

COMPLETIONS, CLOSURES AND FORMAL SOLUTIONS

Z. Sela^{1,2}

posted Nov. 26, 2000

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 of 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.17) 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 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. We start this section with (a special case of) Merzlyakov original theorem.

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 predicate:

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

is a truth predicate. 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 notations for the placements of the x-segments, y-segments and a-segments. 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 and y 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 predicate 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 predicate defined over an arbitrary (given) variety. We start with a generalization of Merzlyakov theorem to a predicate 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 predicate:

∀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 predicate. 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 predicate:

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

is a truth predicate in F_{k}.

Proof: 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 satisfy the conclusion of the theorem.

□

To generalize Merzlyakov theorem to arbitrary varieties, rather than the ”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 predicate:

∀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 predicate. 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}, and the predicate:

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

is a truth predicate in F_{k}.

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 Lemma 5.13 of [Se1] there exists a collection of disjoint non-homotopic essential simple closed curves (s.c.c.) c_{1}, …, c_{m} on the surface S with the following properties:

(1) S \ ∪{c_{1}, …, c_{m}} is collection of surfaces (with boundary) S_{1}, …, S_{r} and χ(S_{j}) = −1.

(2) the homomorphism μ maps π_{1}(S_{j}) monomorphically into F_{k}. Every subsurface S_{j} is of Euler characteristic χ(S_{j}) = −1 so it has to be either a three-punctured sphere, a once-punctured Mobius band or a once-punctured Klein bottle. If S_{j} is a once-punctured Klein bottle, then there exists a non-boundary parallel essential s.c.c. ν on S_{j}, so that S_{j} \ ν is a three-punctured sphere:

Hence, if for every subsurface S_{j} which is a once-punctured Klein bottle, we add the corresponding essential s.c.c. ν to the collection c_{1}, …, c_{m}, we get a new finite collection of essential s.c.c. on the surface S that satisfy properties (1) and (2) above, for which the complementary regions are either three-punctured spheres or once-punctured Mobius bands. We will denote the obtained collection of essential s.c.c. on S, b_{1}, …, b_{q}. To the collection b_{1}, …, b_{q} we add an additional finite collection of curves d_{1}, …, d_{t} so that the entire collection b_{1}, …, b_{q}, d_{1}, …, d_{t} fill the surface S.

Lemma 1.4. Let b_{1}, …, b_{q} be the above collection of essential s.c.c. on the surface S. Then there exists a finite collection of essential s.c.c. d_{1}, …, d_{t} on S with the following properties:

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

(ii) 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: The surface S \ ∪{b_{1}, …, b_{q}} is a finite union of three-punctured spheres and once-punctured Mobius bands {S_{j}}. On each of the three-punctured spheres and the once-punctured Mobius bands we add the following essential arcs:

Clearly, the union of the essential arcs on the subsurfaces {S_{j}} is a collection of s.c.c. d_{1}, …, d_{t} on the surface S. By construction, the surface S\∪{b_{1}, …, b_{q}, d_{1}, …, d_{t}} is a disjoint union of simply-connected domains. By a simple ”innermost circle” argument, each of the s.c.c. d_{1}, …, d_{t} is essential, and intersects non-trivially at least one of the curves b_{1}, …, b_{q}.

□

Let φ_{1}, …, φ_{q} be the automorphisms of Q that correspond to Dehn twists along the s.c.c. b_{1}, …, b_{q}, and let ψ_{1}, …, ψ_{t} 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 {ν_{m}, τ_{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 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} > 0 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,g′}^{1} < \frac{tr_{X}(λ_{n}(g))}{d_{X}(λ_{n}(g), id.)} < const_{g,g′}^{2}

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,g′}^{1} < \frac{tr_{X}(λ_{n}(g))}{d_{X}(λ_{n}(g), id.)} < const_{g,g′}^{2}

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 suppose that the predicate:

∀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 predicate. 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 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.

Clearly, by possibly passing to a subsequence, we may assume that the sequence of specializations {(x_{n}, λ_{n}(y), a)} converges. We call the obtained limit group a quadratic test limit group, and denote it QT L(x, y, a). Let T_{∞} be the obtained limit tree. Since the sequence {ν_{n}, τ_{n}, λ_{n}} is a quadratic test sequence, the sequence of specializations {λ_{n}(y)} converges to the surface group Q, hence, Q < QT L(x, y, a). By proposition 1.7 either the subgroup Q fixes a point in the limit tree T_{∞}, or it acts freely on T_{∞}. Since Q is a surface group, if Q acts freely on T_{∞} then Q acts freely on some IET component of the limit tree T_{∞}. 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). Furthermore, since the elements x_{n} were chosen to be the shortest possible among those that satisfy both the equalities w_{1}(x_{n}, λ_{n}(y), a) = 1, …, w_{s}(x_{n}, λ_{n}(y), a) = 1 and inequalities v_{1}(x_{n}, λ_{n}(y), a) ≠ 1, …, v_{r}(x_{n}, λ_{n}(y), a) ≠ 1, the shortening argument used in constructing the Makanin-Razborov diagrams in section 5 of

[Se1] (which can be applied in the presence of inequalities just as well!), implies that:

QT L(x, y, a) = F_{k} ∗ Q̂ ∗ < f_{1}, …, f_{d} >

where < f_{1}, …, f_{d_{t}} > is a free group on the set f_{1}, …, f_{d}, and Q̂ is a surface group in which the surface group Q is a subgroup of finite index.

Let S be a surface with fundamental group Q. Since the homomorphisms λ_{n} : Q → F_{k} do not factor through the fundamental group of any surface covered by the surface S, Q̂ = Q. Since the quadratic test limit group QT L(x, y, a) was constructed using sequences of elements {(x_{n}, λ_{n}(y), a)} for which the inequalities v_{1}(x_{n}, λ_{n}(y), a) ≠ 1, …, v_{r}(x_{n}, λ_{n}(y), a) ≠ 1 are fulfilled, there exists a specialization of the elements f_{1}, …, f_{d} for which there exists a specialization of the generators y of the surface group Q so that all the inequalities: v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1 are fulfilled. This finally concludes 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 predicate:

∀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 predicate.

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}, 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 predicate:

∃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 predicate in F_{k}. (ii) With each monomorphism ν_{i} : Y_{n} → Z_{n}^{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 (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} for which the solutions of the corresponding Diophantine system are all integers. Then the union of the subgroups U_{n}^{1}, …, U_{n}^{ℓ} cover the entire abelian group Y_{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-tuples {(q_{1}(m_{j}), …, q_{n}(m_{j}))}_{j=1}^{∞} is an abelian test sequence, if for the sequence {m_{j}}_{j=1}^{∞} is an increasing sequence and for every m_{j} in this increasing sequence:

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

Given an abelian test sequence we set δ_{m_{j}} = λ([1, 2^{m_{j}}q_{n}(m_{j})]) and:

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

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}(m_{j}), …, y_{n}(m_{j}) we can choose x(m_{j}) to be the shortest possible element for which:

w_{1}(x(m_{j}), y(m_{j}), a) = 1, …, w_{s}(x(m_{j}), y(m_{j}), a) = 1 ∧
∧ v_{1}(x(m_{j}), y(m_{j}), a) ≠ 1, …, v_{r}(x(m_{j}), y(m_{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. By the arguments used in constructing the Makanin-Razborov diagram of a limit group in ([Se1],5) 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: Mab_{1}(x, y, a), …, Mab_{ℓ}(x, y, a).

Since the maximal abelian test limit groups Mab_{1}(x, y, a), …, Mab_{ℓ}(x, y, a) were constructed using sequences of elements {(x(m_{j}), y_{1}(m_{j}), …, y_{n}(m_{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 Mab_{1}(x, y, a), …, Mab_{ℓ}(x, y, a). Furthermore, since the elements x(m_{j}) were chosen to be the shortest possible among those that satisfy both the equalities w_{1}(x, y(m_{j}), a) = 1, …, w_{s}(x, y(m_{j}), a) = 1 and inequalities v_{1}(x, y(m_{j}), a) ≠ 1, …, v_{r}(x, y(m_{j}), a) ≠ 1, the shortening argument used in constructing the Makanin-Razborov diagrams in section 5 of [Se1] (which can be applied in the presence of inequalities just as well!), implies that for each 1 ≤ i ≤ ℓ:

Mab_{i}(x, y, a) = F_{k} ∗ Ab_{i} ∗ < f_{1}, …, f_{d_{t_{i}}} >

where < f_{1}, …, f_{d_{t}} > is a free group on the set f_{1}, …, f_{d_{t}}, and Ab_{i} is a free abelian group in which Y_{n} is a subgroup of finite index.

Since the maximal test limit groups Mab_{1}(x, y, a), …, Mab_{ℓ}(x, y, a) were constructed using sequences of elements {(x(m_{j}), y_{1}(m_{j}), …, y_{n}(m_{j}))} for which the inequalities v_{1}(x(m_{j}), y(m_{j}), a) ≠ 1, …, v_{r}(x(m_{j}), y(m_{j}), a) ≠ 1 are fulfilled, for each 1 ≤ i ≤ ℓ there exists a specialization of the elements f_{1}, …, f_{d_{t_{i}}} for which there exists a specialization of the generators of the abelian group Ab_{i} so that all the inequalities v_{1}(x, y, a) ≠ 1, …, v_{r}(x, y, a) ≠ 1 are fulfilled. Therefore, we have found maps τ_{i} : Mab_{i}(x, y, a) → F_{k} ∗ Z_{n}^{i} for which:

(1) τ_{i} embeds 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 MAb_{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 exist 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. To prove part (ii) let U_{n}^{i} < Y_{n} be the subgroups as defined in the formulation of the proposition (i.e., the subgroups of Y_{n} for which the corresponding Diophantine systems of equations in z_{n}^{i}’s have integer solutions), and suppose the union of the subgroups U_{n}^{i} does not cover the whole group Y_{n}. Under this last assumption there must exist an element y_{0} ∈ Y_{n} so that y_{0} ∉ U_{n}^{i} for i = 1, …, ℓ. If the index of the subgroup U_{n}^{i} in Y_{n} is ind_{i}, then also the elements (m · ind_{1} · ind_{2} … ind_{ℓ} + 1) · y_{0} ∉ U_{n}^{i} for every integer m. Therefore, there exist an abelian test sequence of integers {(q_{1}(m_{j}), …, q_{n}(m_{j}))} for which every convergent subsequence of the corresponding elements {(x(m_{j}), y(m_{j})} does not factor through any of the maximal abelian test limit groups Mab_{1}(x, y, a), …, Mab_{ℓ}(x, y, a), which contradicts their canonical properties.

□

For completeness we bring a formulation of proposition 1.8 for free abelian groups with constants, i.e., when y_{0} = c_{1} ∈ F_{k}. The proof is essentially identical to the proof of proposition 1.4.

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 predicate:

∀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 predicate.

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 predicate:

∃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 predicate 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 predicates 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.

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 one of the resolutions Res_{i}(y, a).

Proof: To get the strict MR resolutions with the properties listed above, we start with the canonical collection of Makanin-Razborov resolutions (the ones that appear in the Makanin-Razborov diagram). We take each of the strict Makanin-Razborov resolutions from the Makanin-Razborov diagram to be one of the resolutions in our new collection. Let Res(y, a) be a Makanin-Razborov resolution which is not strict. 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 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 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 by its proper quotient, the ascending chain condition for restricted limit groups ([Se1],5) 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), and H^{i} is a (possibly trivial) free group. 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}. The Dehn twists are assumed to fix (elementwise) the vertex stabilized by the subgroup F_{k} < 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 F_{k} < 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} that fixes the vertex stabilized by F_{k} < 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}. η_{i}(H^{i}) is trivial.

(2) If the factor R_{j}^{i} is not a free abelian group and not a closed surface 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}. The factors in the free decompositions of Rlim_{i+1}(y, a), F_{rk(i+1)}^{i+1} and H^{i+1} onto which 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′.

(3) since we assume the resolution Res(y, a) is a strict MR resolution, the canonical quotient map η_{i} maps every non-abelian, non-QH vertex group and every (abelian) edge group in the canonical decompositions in 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} is a free factor in some free decomposition of the free group H^{i+1}.

(5) Let Q_{1}^{i}, …, Q_{s(i)}^{i} be the QH vertex groups in the abelian decompositions of the factors R_{j}^{i}, and let Ab_{1}^{i}, …, Ab_{q(i)}^{i} be the abelian factors among the factors R_{j}^{i}. Recall that η_{i}(Ab_{u}^{i}) = C_{u}^{i}. For each QH subgroup Q_{h}^{i} let Λ_{Q_{h}^{i}} be the cyclic decomposition obtained from the abelian decomposition associated with the factor R_{j}^{i} containing the QH subgroup Q_{h}^{i}, by collapsing all the edges that are not connected to the QH subgroup Q_{h}^{i}. We say that the circumference of the QH subgroup Q_{h}^{i}, denoted Circum(Q_{h}^{i}) is the subgroup generated by Q_{h}^{i} and all the Bass-Serre generators connecting (some of) its boundary components to vertex groups in Λ_{QH_{h}^{i}}.

For each QH subgroup Q_{h}^{i} let bd_{h,1}, …, bd_{h,c(h)} be its boundary components. Let η_{i}(Circum(Q_{h}^{i})) = V_{1} ∗ … ∗ V_{m(h)} ∗ H_{h}^{i} be the maximal (most refined) free decomposition inherited by η(Circum(Q_{h}^{i})) from the given free decomposition of Rlim_{i}(y, a) in which each of the images of the boundary elements η_{i}(bd_{h,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_{h,n}) that can be conjugated into it. Then H_{h}^{i} is a free group and:

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

and:

V_{1} ∗ … ∗ V_{m}(h) < 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 completion construction to well-structured resolutions.

Definition 1.12. With the above notation and assumptions we construct the completed resolution, denoted Comp(Res)(z, y, a), of a given (restricted) well-structured resolution Res(y, a) from bottom to top. We change Rlim_{ℓ−1} to a limit group Comp(Rlim)_{ℓ−1} by modifying the abelian decompositions of each of the non-abelian, non-surface factors R_{j}^{ℓ−1} of Comp(Rlim)_{ℓ−1}.

Let Ab_{1}^{ℓ−1}, …, Ab_{q(ℓ−1)}^{ℓ−1} be the (non-cyclic) abelian factors among the factors R_{j}^{ℓ−1}, and let S_{1}^{ell−1}, …, S_{d(ℓ−1)}^{ℓ−1} be the closed surface factors among the factors R_{j}^{i}. We set G_{1} to be the group which is the free product of the free group < f, a > (which is a free factor of Rlim_{ℓ}(y, a)) with the factors Ab_{1}^{ℓ−1}, …, Ab_{q(ℓ−1)}^{ℓ−1} and S_{1}^{ell−1}, …, S_{d(ℓ−1)}^{ℓ−1}.

We start modifying G_{1} by modifying the free group < a, f > which is a free factor of the group G_{1}. For each non-abelian, non-surface factors R_{j}^{ℓ−1} that appears in the free decomposition associated with the restricted limit group Rlim_{ℓ−1}(y, a) in the well-structured resolution Res(y, a) we do the following. Let B_{j}^{ℓ−1} = < a, f > ∩η_{ℓ−1}(R_{j}^{ℓ−1}). Since Res(y, a) is a well-structured resolution (definition 1.11), B_{j}^{ℓ−1} is a free factor of the free group < a, f >. Let Λ_{j}^{ℓ−1} be the abelian decomposition associated with the factor R_{j}^{ℓ−1}, and let B_{j}^{ℓ−1} = V_{1} ∗ … ∗ V_{μ_{j}^{ℓ−1}} be the most refined

free decomposition of the free group B_{j}^{ℓ−1} in which the image under the map η_{ℓ−1} : Rlim_{ℓ−1} →< a, f > of every non-QH vertex group and every edge group in Λ_{j}^{ℓ−1} is contained in one of the factors V_{t}. With each edge with cyclic stabilizer that connects two non-abelian, non-QH vertex groups in the abelian decomposition Λ_{ℓ−1}^{j} of the (non-abelian, non-surface) factor R_{j}^{ℓ−1} we associate a new generator g_{e}. We add all the new generators {g_{e}} corresponding to these edges to the different groups V_{1}, …, V_{μ_{j}^{ℓ−1}}, and add commutant relations that force each of the new variables g_{e} to commute with the centralizer of the cyclic stabilizer of the edge it is associated with. Hence, we start this first modification with the group G_{1}, and add to it some free abelian groups amalgamated along (maximal) cyclic edge groups. We call the obtained group G_{2}.

To each non-cyclic abelian vertex group Ab_{n} of rank n in the cyclic decomposition of one of the non-abelian factors R_{j}^{ℓ−1} that is connected to some non-abelian, non-QH vertex group by an edge with (maximal) cyclic stabilizer, we associate new generators ab_{1}, …, ab_{n}. We modify G_{2} by adding all the new generators to it, together with relations that forces ab_{1} to be equal to the corresponding element in the corresponding factor V_{t} < < f, a > < G_{2} (the generator of the image of Ab_{n} in V_{t} < < f, a >), and commutant relations that force the other new generators to commute with the centralizer in G_{2} of the image of Ab_{n} in G_{2}. Therefore, we ended this second modification with a group G_{3}, in which to every non-abelian nonsurface factor R_{j}^{ℓ−1} correspond finitely many factors W_{1}, …, W_{μ_{j}^{ℓ−1}} corresponding to the factors of its image in < a, f >: V_{1}, …, V_{μ_{j}^{ℓ−1}}, where each factor W_{t} admits a canonical graph of groups composed of one vertex stabilized by a free factor V_{t} of the initial free group < a, f >, and (possibly) several additional vertices, each stabilized by a non-cyclic free abelian group and connected to the vertex stabilized by the factor of < f, a > by a single edge with (maximal) cyclic stabilizer.

We continue with the group G_{3}, and its factors W_{1}, …, W_{μ_{j}^{ℓ−1}} as follows. We

start with Λ_{j}^{ℓ−1}, the graph of groups associated with the non-abelian non-surface factor R_{j}^{ℓ−1} in the resolution Res(y, a), and collapse all the edges in Λ_{j}^{ℓ−1} that connect two non-abelian non-QH vertex groups. We are left with a quotient graph of groups Δ_{j}^{ℓ−1} containing non-QH and QH vertex groups, in which every non-QH vertex group is connected to only Q vertex groups, and by construction, each of the non-QH vertex groups and each edge group is mapped by η_{ℓ−1} to one of the factors V_{1}, …, V_{μ_{j}^{ℓ−1}}. We associate with the graph of groups Δ_{j}^{ℓ−1} a graph of groups Θ_{j}^{ℓ−1}

as follows. For each index t, 1 ≤ t ≤ μ_{j}^{ℓ−1}, we place a vertex stabilized by the factor W_{t} on one of the vertices that is mapped by η_{ℓ−1} to the corresponding factor V_{t}. We connect this vertex to all boundary components of QH subgroups in which vertices that are mapped by η_{ℓ−1} to the factor V_{t} are connected. We further erase all the non-QH vertices on which we didn’t place any factor W_{t}, and all the edges connected to them.

Performing all these operations, we end up with one graph of groups with cyclic edge stabilizers corresponding to each of the non-abelian, non-surface factors R_{j}^{ℓ−1}, and possibly few (closed) surface and few abelian factors. We call the obtained group which is the free product of the fundamental groups of these graphs of groups and the surface and abelian factors, the completion of Rlim_{ℓ−1}(y, a), and denote it Comp(Rlim)_{ℓ−1}(z, a). We call its associated (free and cyclic) decomposition, the completed decomposition of Comp(Rlim)_{ℓ−1}(z, a), and with it we naturally associate the completed modular group (inherited from the modular group of Rlim_{ℓ−1}(y, a). Since the subgroup

R_{1}^{ℓ−1} ∗ … ∗ R_{q(ℓ−1)}^{ℓ−1} ∗ F_{rk(ℓ−1)}^{ℓ−1} < Rlim_{ℓ−1}(y, a)

canonically embeds into Comp(Rlim)_{ℓ−1}(z, a), and η_{ℓ−1}(H^{i}) is trivial, we set ν_{ℓ−1} : Rlim_{ℓ−1}(y, a) → Comp(Rlim)_{ℓ−1}(z, a) to be the map that sends H^{ℓ−1} to the trivial group and the subgroup which is the free product of the other factors into their canonical image in Comp(Rlim)_{ℓ−1}(z, a). We denote the canonical quotient inherited from η_{ℓ−1} by Comp(η)_{ℓ−1}(z, a) : Comp(Rlim)_{ℓ−1}(z, a) → Comp(Rlim)_{ℓ}(y, a) =< f, a >. Although the y’s as elements in the completion Comp(Rlim)_{ℓ−1}(z, a) can be expressed as words in the generators (z, a) we prefer to specifically note them by changing the notation of the completion to Comp(Rlim)_{ℓ−1}(z, y, a).

We continue the construction of the completed resolution recursively (bottom to top). At each step we start with Comp(Rlim)_{i+1}(z, y, a) and its associated free decomposition, and construct Comp(Rlim)_{i}(z, y, a), its associated completed decomposition and completed modular groups, the natural maps ν_{i} : Rlim_{i}(y, a) → Comp(Rlim)_{i}(z, y, a), and the completed quotient Comp(η)_{i} : Comp(Rlim)_{i} → Comp(Rlim)_{i+1}. Let R_{j}^{i} be a factor in the free decomposition of Rlim_{i}(y, a) Let B_{j}^{i} = Rlim_{i+1}(y, a)∩ η_{i}(R_{j}^{i}). Since Res(y, a) is a well-structured resolution (definition 1.11), B_{j}^{i} is a free factor of the free group Rlim_{i+1}(y, a). Let Λ_{j}^{i} be the abelian decomposition associated with the factor R_{j}^{i}, and let B_{j}^{i} = V_{1} ∗ … ∗ V_{μ_{j}^{i}} be the most refined free decomposition of the free group B_{j}^{i} in which the image under the map η_{i} : Rlim_{i} → Rlim_{i+1}(y, a) of every non-QH vertex group and every edge group in Λ_{j}^{ℓ−1} is contained in one of the factors V_{t}. By the construction of the lower levels of the completed resolution, and since Res(y, a) is a well-structured resolution, with each factor V_{t} of Rlim_{i+1}(y, a) we can naturally associate a factor U_{t} of the completed limit group Comp(Rlim)_{i+1}(z, y, a), so that V_{t} < U_{t}. With each edge with abelian stabilizer that connects two non-abelian, non-QH vertex groups in the abelian decomposition Λ_{i}^{j} of the (non-abelian, non-surface) factor R_{j}^{i} we associate a new generator g_{e}. We add all the new generators {g_{e}} corresponding to these edges to the different factors U_{1}, …, U_{μ_{j}^{i}}, and add commutant relations that force each of the new variables g_{e} to commute with the centralizer of the abelian stabilizer of the edge it is associated with. Hence, we start this first modification with the factors U_{1}, …, U_{μ_{j}^{i}} and add to it some free abelian groups amalgamated along abelian edge groups.

To each non-cyclic abelian vertex group Ab_{n} of rank n in the abelian decomposition of one of the non-abelian factors R_{j}^{i} that is connected to some non-abelian, non-QH vertex group by an edge with abelian stabilizer, we associate new generators ab_{1}, …, ab_{n}, add all the new generators to the previously obtained factors, together with relations that forces the edge group to be equal to the corresponding subgroup in the corresponding factor U_{t} < Comp(Rlim)_{i+1}(z, y, a), and add commutant relations that force the other new generators to commute with the centralizer in U_{t} of the image of Ab_{n} in U_{t}. Therefore, we ended this second modification with a group in which to every non-abelian non-surface factor R_{j}^{i} correspond finitely many factors W_{1}, …, W_{μ_{j}^{i}} corresponding to the factors of its image in Rlim_{i+1}(y, a): V_{1}, …, V_{μ_{j}^{i}}, where each factor W_{t} admits a canonical graph of groups composed of one vertex stabilized by a free factor U_{t} of the completed limit group Comp(Rlim)_{i+1}(z, y, a), and (possibly) several additional vertices, each stabilized by a non-cyclic free abelian group and connected to the vertex stabilized by U_{t} with a single edge with abelian stabilizer.

We continue with the factors W_{1}, …, W_{μ_{j}^{i}} as follows. We start with Λ_{j}^{i}, the graph of groups associated with the non-abelian non-surface factor R_{j}^{i} in the resolution Res(y, a), and collapse all the edges in Λ_{j}^{i} that connect two non-abelian non-QH vertex groups. We are left with a quotient graph of groups Δ_{j}^{i} containing non-QH and QH vertex groups, in which every non-QH vertex group is connected to only Q vertex groups, and by construction, each of the non-QH vertex groups and each edge group is mapped by η_{i} to one of the factors V_{1}, …, V_{μ_{j}^{i}}. We associate with the graph of groups Δ_{j}^{i} a graph of groups Θ_{j}^{i} as follows. For each index t, 1 ≤ t ≤ μ_{j}^{i}, we place a vertex stabilized by the factor W_{t} on one of the vertices that is mapped by η_{i} to the corresponding factor V_{t}. We connect this vertex to all boundary components of QH subgroups in which vertices that are mapped by η_{i} to the factor V_{t} are connected. We further erase all the non-QH vertices on which we didn’t place any factor W_{t}, and all the edges connected to them.

Performing all these operations, we end up with one graph of groups with abelian edge stabilizers corresponding to each of the non-abelian, non-surface factors R_{j}^{i}, and possibly few (closed) surface and few abelian factors. We call the obtained group which is the free product of the fundamental groups of these graphs of groups and the surface and abelian factors, the completion of Rlim_{i}(y, a), and denote it Comp(Rlim)_{i}(z, a). We call its associated (free and cyclic) decomposition, the completed decomposition of Comp(Rlim)_{i}(z, a), and with it we naturally associate the completed modular group (inherited from the modular group of Rlim_{i}(y, a). Since the subgroup

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

canonically embeds into Comp(Rlim)_{i}(z, a), and η_{i}(H^{i}) is trivial, we set ν_{i} : Rlim_{i}(y, a) → Comp(Rlim)_{i}(z, a) to be the map that sends H^{i} to the trivial group and the subgroup which is the free product of the other factors into their canonical image in Comp(Rlim)_{i}(z, a). We denote the canonical quotient inherited from η_{i} by Comp(η)_{i}(z, a) : Comp(Rlim)_{i}(z, a) → Comp(Rlim)_{i+1}(z, y, a). Although the y’s as elements in the completion Comp(Rlim)_{i}(z, a) can be expressed as words in the generators (z, a) we prefer to specifically note them by changing the notation of the completion to Comp(Rlim)_{i}(z, 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.13. 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} to the trivial group), 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 Rlim_{ℓ} =< f, a > 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 restricted limit group Comp(Rlim)(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.14. 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 (maximal) non-conjugate abelian groups that appear along the completed resolution Comp(Res)(z, y, a) that are mapped to an abelian factor in some level of the completed resolution Comp(Res)(z, y, a). Let P Ab_{1}, …, P Ab_{pd} be the non-conjugate (maximal) pegged abelian groups that appear along the completed resolution, i.e., maximal abelian subgroups in Comp(Rlim)(z, y, a), that are mapped onto an 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, in the entire construction of the completed resolution, i.e., from the bottom level an image of the (pegged) abelian group appears through all the upper levels. 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 Ab_{1}, …, Ab_{d} and P Ab_{1}, …, P Ab_{pd} in correspondence. Since the completion of a resolution is canonical, we denote a closure of the completed resolution by Cl(Res)(s, y, a), and the corresponding limit group by Cl(Rlim)(s, y, a). Naturally, Comp(Rlim)(z, y, a) is embedded in Cl(Rlim)(z, y, a).

By construction, all the properties of the completion listed in lemma 1.13 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.15. We will keep the notation of definition 1.10. 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 proposition 1.8, for each of the abelian groups Ab_{j}, and each embedding (extension) Ab_{j} < S_{j} we associate a finite index subgroup U_{j} for which the corresponding Diophantine system of equations (with variables s) has integer solutions. For each pegged abelian group P Ab_{j} we fix a (co-dimension 1) subgroup P K_{j} < P AB_{j} which is the kernel of the corresponding completed quotient map restricted to the pegged abelian group P AB_{j} (with image isomorphic to < peg_{j} >). Clearly, rank(P K_{j}) + 1 = rank(P Ab_{j}) and P Ab_{j} =< P K_{j}, peg_{j} >. Like in proposition 1.5 with each pegged embedding (extension) P Ab_{j} < P S_{j} we associate a coset P U_{j} + c_{j} of a finite index subgroup P U_{j} < P K_{j} and c_{j} < P K_{j} for which the corresponding Diophantine system of equations (with variables s) has integer solutions. Therefore, with each closure Cl(Res)(s, y, a) we can associate a tuple:

(U_{1}, …, U_{d}, P U_{1} + c_{1}, …, P U_{pd} + c_{pd})

which corresponds to some subset of the cross product of the abelian groups Ab_{1}, …, Ab_{d}, P K_{1}, …, P K_{pd} which we call 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 groups Ab_{1}, …, Ab_{d}, P K_{1}, …, P K_{pd}.

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

Lemma 1.16. Let Cl(Res)_{1}(s, y, a), …, Cl(Res)_{q}(s, 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 an element s_{0}, so that (s_{0}, y_{0}, a) is a specialization of one of the closures Cl(Res)_{i}(s, y, a).

Proof: By lemma 1.12 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}, y_{0}, a) that factors through one of the closures: Cl(Res)_{1}(s, y, a)_{1}, …, Cl(Res)_{q}(s, 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.17. 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 predicate:

∀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 predicate.

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

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

.

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

Let S be a punctured surface with fundamental group Q, 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. By Lemma 5.13 of [Se1] there exists a collection of disjoint non-homotopic, non-boundary parallel essential s.c.c. c_{1}, …, c_{m} on the surface S with the following properties:

(1) S \ ∪{c_{1}, …, c_{m}} is collection of surfaces (with boundary) S_{1}, …, S_{r} and χ(S_{j}) = −1.

(2) the homomorphism μ maps π_{1}(S_{j}) monomorphically into F_{k}.

Every subsurface S_{j} is of Euler characteristic χ(S_{j}) = −1 so it has to be either a three-punctured sphere, a once-punctured Mobius band or a once-punctured Klein bottle. If S_{j} is a once-punctured Klein bottle, then there exists a non-boundary parallel essential s.c.c. ν on S_{j}, so that S_{j} \ ν is a three-punctured sphere, hence, if for every subsurface S_{j} which is a once-punctured Klein bottle, we add the corresponding essential s.c.c. ν to the collection c_{1}, …, c_{m}, we get a new finite collection of essential s.c.c. on the surface S that satisfy properties (1) and (2) above, for which the complementary regions are either three-punctured spheres or once-punctured Mobius bands. We will denote the obtained collection of essential s.c.c. on S, b_{1}, …, b_{q}. As in lemma 1.4, to the collection b_{1}, …, b_{q} we add an additional finite collection of curves d_{1}, …, d_{t} so that the entire collection b_{1}, …, b_{q}, d_{1}, …, d_{t} fill the surface S.

Lemma 1.18. Let b_{1}, …, b_{q} be the above collection of essential s.c.c. on the punctured surface S. Then there exists a finite collection of essential, non-boundary parallel s.c.c. d_{1}, …, d_{t} on S with the following properties:

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

(ii) 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 domains in S, where each component is either homeomorphic to a disk or to an annulus. If it is homeomorphic to an annulus, than one of its boundary components is one of the boundary components of the surface S, br_{i}.

Proof: The surface S \ ∪{b_{1}, …, b_{q}} is a finite union of three-punctured spheres and once-punctured Mobius bands {S_{j}}. If no boundary component of such three punctured sphere, or once-punctured Mobius band is a boundary component of the punctured surface S then we add the same arcs as we added in the proof of lemma 1.4:

If certain boundary components of such three punctured sphere or once-punctured Mobius band is a boundary component of the surface S then we add the following arcs:

Clearly, the union of the essential arcs on the subsurfaces {S_{j}} is a collection of s.c.c. d_{1}, …, d_{t} on the surface S. By construction, the surface S\∪{b_{1}, …, b_{q}, d_{1}, …, d_{t}} is a disjoint union of simply-connected domains and domains homeomorphic to annuli. By a simple ”innermost circle” argument, each of the s.c.c. d_{1}, …, d_{t} is essential, and intersects non-trivially at least one of the curves b_{1}, …, b_{q}.

□

Suppose 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 >

and suppose 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 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 abelian and pegged abelian vertex groups that appear in these abelian decompositions. For each QHvertex group QH_{i} in the completed abelian splitting of one of the completed restricted limit groups Comp(Rlim)_{i}(z, y, a), we fix a finite set of essential, nonboundary parallel s.c.c. b_{1}^{i}, …, b_{q_{i}}^{i}, d_{1}^{i}, …, d_{t_{i}}^{i} that satisfy properties (i) and (ii) of lemma 1.18. 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 the fixed system of generators of Comp(Rlim)(z, y, a). We fix a set of generators for each of the abelian and pegged abelian groups that appear in the completed abelian splittings associated with the various levels of completed restricted resolution Comp(Res)(z, y, a).

For each QH subgroup QH_{i} that appear in one of the abelian decomposition 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 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 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) surface S_{i} (with fundamental group QH_{i}) by 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.19. 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 sequences 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 abelian and pegged abelian vertex groups in the completed abelian splittings, so let Ab_{1}, …, Ab_{d} be the abelian groups, and let 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 either Ab_{i} or P Ab_{i} appear 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 group 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 abelian and pegged abelian groups that appear in the completed abelian splittings, so in case Ab_{i} is a (peg-free) abelian group let q_{1}^{i}, …, q_{d_{i}}^{i} be its pre-chosen basis, and in case P Ab_{i} is a pegged abelian group let q_{1}^{i}, …, q_{d_{i}}^{i} be the pre-chosen basis for the kernel of the map Comp(η)_{ℓ(i)} : P Ab_{i} → Comp(Rlim)_{ℓ(i)+1}(z, y, a) (sending the pegged abelian group P Ab_{i} to the centralizer of its peg in Comp(Rlim)_{ℓ(i)+1}(z, y, a)). Let dist_{i}(n) be: dist_{i}(n) = max{d_{X}(λ_{n}(g), id.) | g ∈ B_{i}(n)}. Then:

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

(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 abelian or pegged abelian group Ab_{j} or 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) Let E be a cyclic edge group in one of the abelian decompositions associated with one of the levels of the completed resolution Comp(Res)(z, y, a). Then λ_{n}(E) is a maximal cyclic subgroup of F_{k}.

Lemma 1.20. 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 q_{r}^{t} of some of the (pegged) abelian groups that appear in the completed abelian splittings of Comp(Res)_{i}(z, y, a) to be of the form q_{r}^{t}(n) = h^{ms_{2}+s_{1}} for some integer s and so that the element h has no 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 and 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 not trivial, 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 λ_{n} as λ_{n}^{F}. Next we define λ_{n} sequentially 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} 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}) = h^{ms_{1}+s_{2}} where m is an integer and h is an element in F_{k} with no non-trivial roots.

Next, we define the homomorphism λ_{n} sequentially 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}. 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, and the image of every boundary element of QH_{i} is non-trivial. Hence, by lemma 5.13 there exists a modular automorphism α_{n}^{i} of QH_{i} for which the homomorphism: λ_{n}^{F} ∘Comp(η)_{ℓ−1} ∘α_{n}^{i} :

QH_{i} → F_{k} maps the elements b_{1}^{i}, …, b_{q_{i}}^{i} associated with QH_{i} to non-trivial elements in F_{k}, and the fundamental groups of the (Euler characteristic -1) subsurfaces, obtained by cutting the surface S_{i} along the curves b_{1}^{i}, …, b_{q_{i}}^{i}, monomorphically into F_{k}. Setting the automorphisms α_{n}^{i}, we may apply the same argument used to prove the existence of a quadratic test sequence (lemma 1.6), and choose the exponents e_{n}^{i} to be large enough,so that properties (vii)-(ix), and properties (xii) and (xiii) hold. By possibly further increasing the integer m_{n} used to define the homomorphism λ_{n}^{F} :< f_{1}, …, f_{b} >→ F_{k}, further increasing the exponents e_{n}^{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 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 previously 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.17 by essentially combining the arguments used to prove theorems 1.1, 1.3 and 1.8. 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.17 follows from theorem 1.2. By the assumptions of theorem 1.17 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. By the arguments used in constructing the Makanin-Razborov diagram of a limit group in ([Se4],5), there exist maximal test limit groups and in fact there is a canonical finite collection of maximal test limit groups which we denote: MT_{1}(x, z, y, a), …, MT_{m}(x, z, y, a).

Since the maximal test limit groups MT_{1}(x, z, y, a), …, MT_{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_{1}(x, z, y, a), …, MT_{m}(x, z, y, a). Furthermore, since the elements {x_{n}} were chosen to be the shortest possible among those that satisfy both the equalities w_{1}(x_{n}, λ_{n}(y), a) = 1, …, w_{s}(x_{n}, λ_{n}(y), a) = 1 and inequalities v_{1}(x_{n}, λ_{n}(y), a) ≠ 1, …, v_{r}(x_{n}, λ_{n}(y), a) ≠ 1, the shortening argument used in constructing the Makanin-Razborov diagrams in section 5 of [Se4] (which can be applied in the presence of inequalities just as well!), implies that for each 1 ≤ j ≤ m:

MT_{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 our argument with each of the maximal test limit groups in parallel, so we denote the maximal test group treated by: MT (x, z, y, a) = G(g, z, y, a) ∗ < e_{1}, …, e_{d} > (without an index). We fix a generating system G(g, z, y, a) =< g_{1}, …, g_{c} > for the group G(g, z, y, a). For each test sequence that satisfy the conditions above, and for each index n, we pick specializations x_{n} for the variables x, so that the following hold:

(1) the tuple (x_{n}, λ_{n}(z), λ_{n}(y), a) factors through MT (x, z, y, a).

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

(3) the specializations g_{1}(n), …, g_{c}(n) obtained from the specialization x_{n}, have the shortest length among all possible specializations x_{n} that satisfy properties (1) and (2).

We call a limit group obtained from a convergent sequence of tuples {g(n), λ_{n}(z), λ_{n}(y), a)}, for which the corresponding sequence of tuples {(x_{n}, λ_{n}(z), λ_{n}(y), a)} satisfy the properties listed above, a test nuclei of the maximal test limit group MT (x, z, y, a). By our standard argument, there are maximal test nuclei limit groups, and there are only finitely many equivalence classes of maximal test nucleus. We denote them MT N_{1}(g, z, y, a), …, MT N_{r}(g, z, y, a). Clearly, each maximal test nuclei is a quotient of the group G(g, z, y, a) and the completed limit group Comp(Rlim)(z, y, a) is a subgroup of each of the maximal test nuclei MT N_{i}(g, z, y, a). If maximal test nuclei MT N_{i}(g, z, y, a) admits a free decomposition of the form: MT N_{i} = H(h, z, y, a)∗F for which Comp(Rlim)(z, y, a) < H(h, z, y, a) and F is a free group, we construct the (canonical) finite set of maximal test nuclei of MT N_{i}(g, z, y, a) and replace MT N_{i}(g, z, y, a) by its finite maximal nuclei. Hence, we assume that none of the groups MT N_{i}(g, z, y, a) admits a free decomposition of the form: MT N_{i} = H(h, z, y, a) ∗ F for which Comp(Rlim)(z, y, a) < H(h, z, y, a) and F is a free group.

Each maximal test nuclei is obtained from a convergent sequence of tuples {(g_{j}, λ_{n}(z), λ_{n}(y), a)}, hence, each maximal test nuclei MT N_{i}(g, z, y, a) admits a (non-trivial) action on some real tree Y_{i}. Since the elements g_{1}(n), …, g_{c}(n) were chosen to be the shortest possible, since MT N_{i} admits no free decomposition in which Comp(Rlim)(z, y, a) is elliptic, and by the way we have chosen our test sequences, MT N_{i}(g, z, y, a) admits one of the following decompositions from its action on the real tree Y_{i}:

(1) MT N_{i} admits 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 H_{j}(h, a), corresponding to the various orbits of point stabilizers in the action of MT N_{i} on Y_{i}. The decomposition Comp(Rlim)(z, y, a) inherits from this decomposition of MT N_{i} is exactly of the same form, and is compatible with the (top level of the) completed resolution Comp(Res)(z, y, a).

(2) MT N_{i} acts discretely on Y_{i}, and it inherits a graph of groups with one vertex stabilized by H(h, a) and a loop based on it. The stabilizer of that loop together with its corresponding Bass-Serre generator centralize the (pegged) abelian subgroup of highest order in Comp(Res)(z, y, a), and the (pegged) abelian group of highest order in Comp(Res)(z, y, a) is not elliptic in this graph of groups. The decomposition Comp(Rlim)(z, y, a) inherits from this decomposition of MT N_{i} 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 MT N_{i} satisfies the properties of case (1) we continue the analysis of MT N_{i} with each of the vertex groups H_{j}(h, a) in parallel, and if the action satisfies the properties of case (2) we continue with the vertex group H(h, a). For brevity, we will denote the vertex group in question H(h, a), omitting the relevant index. Now, the vertex group H(h, a) being a subgroup of the maximal test nuclei MT N_{i}(g, z, y, a) admits an action on a real tree Y_{2}, and since the elements g_{1}(n), …, g_{c}(n) were chosen to be the shortest possible, since MT N_{i}(g, z, y, a) admits no free decomposition in which Comp(Rlim)(z, y, a) is elliptic, and by the way we have chosen our test sequences, either H(h, a) is a factor in the terminal free group in the completed resolution Comp(Res)(z, y, a), < a, f >, or the action of H(h, a) on the real tree Y_{2} satisfies properties (1) or (2) above. Repeating this ”unraveling” process iteratively, we get that each of the maximal test nuclei is a closure of the resolution Res(y, a), i.e., MT N_{i}(g, z, y, a) = Cl_{i}(s, y, a). Hence, each of the maximal test limit groups, MT_{i}(x, z, y, a) is of the form:

MT_{i}(x, z, y, a) = Cl_{i}(s, y, a) ∗ E_{i}(e_{1}, …, e_{d_{i}})

where E_{i}(e_{1}, …, e_{d_{i}}) is a free group, freely generated by < e_{1}, …, e_{d_{i}} >, each of the elements z is in the subgroup < s, y, a >, and each element x can be expressed as a word in the elements {s, y, e_{1}, …, e_{d_{i}}, a}.

The maximal test limit groups MT_{i}(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_{i}(x, z, y, a) and in addition: v_{1}(x_{n}, λ_{n}(y), a) ≠ 1, …, v_{r}(x_{n}, λ_{n}(y), a) ≠ 1. By further replacing the free group E_{i}(e_{1}, …, e_{d_{i}}) with the specialization it inherits from the specialization (x_{n}, λ_{n}(y), a) for some index n, we get a quotient of MT_{i}(x, z, y, a), which we denote: M̂T_{i}(x, z, y, a), so that M̂T_{i}(x, z, y, a) is naturally isomorphic to MT N_{i}(g, z, y, a) = Cl_{i}(Res)(s, y, a). Hence, each of the generator x of M̂T_{i}(x, z, y, a) can be naturally presented as a word in the closure Cl_{i}(Res)(s, y, a), i.e., x = x(s, y, a), each of the words: w_{1}(x(s, y, a), y, a), …, w_{s}(x(s, y, a), y, a) represent the trivial word in the closure Cl_{i}(Res)(s, y, a), and there exists some specialization (s_{0}^{i}, y_{0}^{i}, a) for which: v_{1}(x(s_{0}^{i}, y_{0}^{i}, a), y_{0}^{i}, a) ≠ 1, …, v_{r}(x(s_{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_{i}(x, z, y, a), the same argument used in proving proposition 1.8 shows that the collection of closures Cl_{i}(Res)(s, y, a) associated with the quotients of the maximal test limit groups M̂T_{i}(x, z, y, a) has to be a covering closure. This finally concludes the proof of theorem 1.17.

□

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

Theorem 1.21. 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 collections of words in the alphabet {x, y, a}. Suppose that the predicate:

∀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 predicate.

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

(i) for each index i, 1 ≤ i ≤ q, all the words in the system Σ_{j(i)}(x_{i}(s, 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}, y_{0}^{i}, a) that factors through the i-th closure Cl(Rlim)_{i}(s, y, a), so that all the words in the collection Ψ_{j(i)}(x_{i}(s_{0}^{i}, y_{0}^{i}, a), y_{0}^{i}, a) are not the trivial element in F_{k}.

§2. Formal Limit Groups

Theorems 1.17 and 1.21 show that given a restricted limit group and a wellstructured resolution of that limit group, the validity of certain predicates imply 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.17 and 121. are guaranteed to satisfy both the equalities given by the predicate and at the same time to have some particular specializations that satisfy all the inequalities defined by the predicate. Our approach to quantifier elimination of predicates is based on the existence of formal solutions satisfying the properties listed in theorems 1.17 and 1.21. However, instead of spotting formal solutions that admit particular specializations that satisfy the inequalities given by a predicate, our strategy is to analyze the entire family of formal solutions that satisfy only the equalities of the predicate, so that if the predicate is indeed a truth predicate, theorems 1.17 and 1.21 guarantee that the entire family contains a finite collection of formal solutions defined over a covering closure of our given (well-structured) resolution and admitting specializations that satisfy also the inequalities defined by the predicate.

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) 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) be a system of equations.

Let the sequence of automorphisms {(ν_{n}^{i}, τ_{n}^{i})} of the QH subgroups QH_{i} that appear in the various abelian decompositions associated with the completed resolution Comp(Res)(z, y, a), and 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} so that: Σ(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} define a homomorphism from the free group with generating set < x, z, y, a >, denoted F (x, z, y, a), to 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). 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 of 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 closure of Comp(Rlim)(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 by F Cl(Rlim)(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 resolution of a restricted limit group Rlim(y, a), and let Comp(Rlim)(z, y, a) be its completion. Let Σ(x, y, a) be a system of equations and let F L(x, y, a) be a formal limit group corresponding to Σ(x, y, a). 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, y, a).

Definition 2.2. Suppose the formal limit group F L(x, z, y, a) does not split into a non-trivial free product in which Comp(Rlim)(z, y, a) is contained in one of the factors. A one edge (formal) 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 of section 3 of [Se1] naturally generalize to construct the formal JSJ decomposition of a formal limit group.

Theorem 2.3 (cf. ([Se1],10.5)). Let F L(x, z, y, a) be a formal limit group which does not split to a non-trivial free product in which the completed limit group Comp(Rlim)(z, y, a) is contained in one of the factors. Then there exists a reduced unfolded (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 a weakly 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.

The formal JSJ decomposition allows one to ”further simplify” formal limit groups in case it is not trivial. 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 to 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 the formal closure of Comp(Rlim)(z, y, a) < F L(x, z, y, a), i.e., F L(x, z, y, a) = F Cl(Rlim)(s, z, y, a).

Proof: Suppose F L(x, z, y, a) does not split to 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 corresponds to 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) action of the formal limit group F L(x, z, y, a) on a real tree Y_{1}. By ([Be-Fe],[Ri]) there is a graph of groups Λ_{1} with abelian edge stabilizers 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 trivial decomposition in which the completed limit group Comp(Res)(z, y, a) is elliptic, a contradiction to our assumptions.

Hence, 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 nonabelian 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 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(Res)(s, z, y, a). Now, we may repeat this argument for the action of the vertex stabilizers V_{i} on a real tree Y_{2}^{i}. Again, by exactly the same reasons listed above, 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(Res)(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 the a closure Cl(Res)(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) be a system of equations. Recall that a formal limit group F L(x, z, y, a) of the system Σ(x, y, a) with respect to the resolution Res(y, a) was constructed from a convergent sequence of homomorphisms: {α_{n} : F (x, z, y, a) → F_{k}} associated with a test sequence {ν_{n}^{i}, τ_{n}^{i}, λ_{n}} and a sequence of specializations {x_{n}} for which: Σ(x_{n}, λ_{n}(y), a) = 1. By the arguments presented in section 5 of [Se1] (the construction of Makanin-Razborov diagrams of limit groups), given the system of equations Σ(x, y, a) and the resolution Res(y, a) there exist maximal formal limit groups, and up to the natural equivalence relation on formal limit groups (cf. ([Se1],5)), there are only finitely many equivalence classes of formal limit groups which we denote:

MF L_{1}(x, z, y, a), …, MF L_{n}(x, z, y, a).

To construct the formal Makanin-Razborov of the system Σ(x, y, a) with respect to the restricted well-structured resolution Res(y, a) we proceed as in the construction of the graded Makanin-Razborov diagrams. We first decompose each of the maximal formal limit groups into the maximal (canonical) 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, we are able to define formal shortening quotients of each of the maximal formal limit groups, and 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_{s}(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 recursive construction terminates. We call the obtained diagram the formal Makanin-Razborov diagram of the system of equations Σ(x, y, a) with respect to the 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 Cl(Res)(s, z, y, a) ∗ F̂, where 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.17 and 1.21 prove that if a predicate of certain form is a truth predicate then there exist formal solutions that may serve as ”witnesses” for the correctness of the predicate. Through 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.17 and 1.21, 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.17 and 1.21 that guarantee that these entire collections of formal solutions include 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.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 Σ(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 predicate:

∀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 predicate.

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) of the system of equations Σ(x, y, a) with respect to the restricted resolution Res(y, a) with the following properties:

(i) for each index 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 1 ≤ i ≤ q there exists a formal solution x_{i}(s, 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, 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 predicate is a truth predicate, 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) with respect to the resolution Res(y, a) contains a covering closure of the restricted resolution.

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

Corollary 2.7. 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 predicate:

∀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 predicate.

Then there exists a covering closure: Cl(Res)_{1}(s, y, a)_{1}, …, Cl(Res)_{q}(s, y, a), and formal resolutions F Res(x, z, y, a)_{1}, …, F Res_{q}(x, z, y, a), where for some 1 ≤ j(i) ≤ r, F Res_{i}(x, z, y, a) is a formal resolution of the system of equations Σ_{j(i)}(x, y, a) with respect to the restricted resolution Res(y, a) with the following properties:

(i) for each index 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 1 ≤ i ≤ q there exists a formal solution x_{i}(s, 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, 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 predicate is a truth predicate, the set of closures that appear as the terminal points of the formal resolutions in the formal Makanin-Razborov diagrams of the systems Σ_{j}(x, y, a) with respect to the resolution Res(y, a) contains a covering closure of the restricted resolution.

§3. Graded Formal Limit Groups

Theorems 1.17 and 1.21 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). However, 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), associated with 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 [Se1] in the construction of graded Makanin-Razborov diagrams of graded limit groups.

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) of the graded limit group Glim(y, p, a). By section 11 of [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 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) with respect to an ungraded resolution of the form Res(y, p_{0}, a) that are ”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 12 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 have 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) 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 to 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 of the various levels.

As in the ungraded setup, given a graded limit group Glim(y, p, a) and a graded well-structured resolution GRes(y, p, a) of it, to analyze the family of all formal solutions of a given system of parametric equations Σ(x, y, p, a) = 1 with respect to (non-degenerate) ungraded resolutions Res(y, p_{0}, a) that are 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 non-degenerate ungraded resolutions GRes(y, p_{0}, a) covered by GRes(y, p, a). We also fix a basis 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 it 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 Y be the Cayley graph of Glim(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 resolution GRes(y, p_{n}, a) is non-degenerate.

(ii) conditions (i)-(xiv) of definition 1.19 (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_{n}, a), d_{Y} (g, id.) ≤ n and g ∉ F_{k}, 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 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 abelian or (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 roots in the free group F_{k}.

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

□

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 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 specializations (p_{n}, 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). We call the obtained limit group, a graded formal limit group, and denote it GF L(x, 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) 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) relative to the well-structured graded resolution GRes(y, p, a), let C(z, y, p, a) =< z, y, p, a > < GF L(x, z, y, p, a) and let AP =< a, p > < GF L(x, z, y, p, a).

Definition 3.4. 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 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 of section 3 of [Se1] naturally generalize to construct the graded formal JSJ decomposition of a graded formal limit group.

Theorem 3.5 (cf. ([Se1],10.5)). 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. Then there exists a reduced unfolded (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 a weakly 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 weakly 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 an abelian splitting in which C(z, y, p, a) is elliptic then the graded formal JSJ decomposition of GF L(x, z, y, p, f, a) is non-trivial.

In general, 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., ones with trivial graded formal JSJ decomposition) as well as solid graded formal limit groups.

Theorem 3.6. 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. If the graded formal JSJ decomposition of GF L(x, z, y, p, a) is trivial, then for some rigid graded (not formal!) limit group RgdGL(b, p, a), GF L(x, z, y, p, a) can be written in the form:

GF L(x, z, y, p, a) = RgdGL(b, p, a) ∗_{<MAb_{1},... ,MAb_{pd′} ,Nuc(w,p,a)>} GF Cl(r, s, c, z, y, p, a)

where GF Cl(r, s, c, z, y, p, a) is generated by a closure of the resolution GRes(y, p, a) and the subgroups MAb_{1}, …, MAb_{pd′}, the subgroups MAb_{1}, …, MAb_{pd′} are the maximal abelian subgroups of the rigid limit group RgdGL(b, p, a) containing pegs of pegged abelian groups that appear in the abelian decompositions associated with the graded completed resolution Comp(GRes)(z, y, p, a) in case the terminal graded limit group of the resolution GRes(y, p, a) is rigid, and in case the terminal graded limit group of the graded resolution GRes(y, p, a) is solid to generate GF Cl(r, s, c, z, y, p, a) additional variables c can be added to the non-QH, non-abelian vertex groups in the graded JSJ abelian decomposition of the terminal solid limit group of GRes(y, p, a). Nuc(w, p, a) is either a quotient 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 quotient of the vertex group stabilized by the subgroup AP =< a, p > in the graded abelian decomposition of Sld(y, p, a) in case GRes(y, p, a) terminates in the solid graded limit group Sld(y, p, a). The elements {r} are generators of the subgroups {MAb_{1}, …, MAb_{pd′}}, and the elements s are roots added to abelian and pegged abelian vertex groups associated with the completed resolution Comp(GRes)(z, y, p, a), precisely in the same way they were added to the closure of a resolution in the ungraded case (see definition 1.14)).

Proof: Suppose GF L(x, z, y, p, a) does not split to a non-trivial 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 consisting of a test sequence of specializations {(y_{n}, p_{n}, a)}, of the terminal rigid or solid 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), 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) action of the graded formal limit group GF L(x, z, y, p, a) on a real tree Y_{1}. By ([Be-Fe],[Ri]) there is a graph of groups Λ_{1} with abelian edge stabilizers corresponding to the action of GF L(x, z, y, p, a) on the real tree Y_{1}. 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.

First, suppose that the graded limit group Glim(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 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 GF Cl(r, s, c, z, y, p, a). ”Unraveling” the top level, we may repeat this argument for the action of the vertex stabilizers V_{1}^{i} on corresponding real trees Y_{2}^{i}. Again, by exactly the same reasons listed above, if C(z, y, p, a) ∩ V_{1}^{i} is not of the form Nuc(w, p, a) ∗ F where F =< f_{1}, …, f − c > is free, and Nuc(w, p, a) is either rigid or it is the vertex stabilized by the subgroup AP =< a, p > in the graded abelian decomposition associated with the terminal solid graded limit group of the graded resolution GRes(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 GF Cl(r, s, c, 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 the vertex stabilizers W_{2}^{i} and elements from GF Cl(r, s, c, z, y, p, a).

This process continues until at some stage ℓ, C(z, y, p, a) ∩ V_{ℓ}^{i} is of the form Nuc(w, p, a) ∗ F, where F is free, and Nuc(w, p, a) is either rigid or corresponds to the vertex stabilized by AP in the graded abelian decomposition associated with the terminal solid graded limit group of the graded resolution GRes(y, p, a). Hence, by a finite induction every element in the graded formal limit group GF L(x, z, y, p, a) can be written as a word in elements from V_{ℓ} and GF Cl(r, s, c, z, y, p, a). By the argument given above, for the case in which the entire graded limit group Glim(y, p, a) is of the form Nuc(w, p, a) ∗ F, the group V_{ℓ}^{i} containing the subgroup AP =< a, p > can be decomposed as: V_{ℓ}^{i} = RgdGL(b, p, a) ∗_{Nuc(w,p,a)} (Nuc(w, p, a) ∗ F), for some graded (not formal!) rigid limit group RgdGL(b, p, a). Now, the original graded formal limit group GF L(x, z, y, p, a) can be obtained from V_{ℓ}^{i} by successive amalgamated products and HNN extensions along abelian subgroups. By construction, if instead of V_{ℓ}^{i} we start with its subgroup < MAb_{1}, …, MAb_{pd′}, Nuc(w, p, a) > ∗F and perform these successive amalgamated products and HNN extensions (along abelian subgroups), we obtain the graded formal closure GF Cl(r, s, c, z, y, p, a). When we start with the entire group V_{ℓ}^{i} and perform these successive amalgamated products and HNN extensions, we obtain:

GF L(x, z, y, p, a) = RgdGL(b, p, a) ∗_{<MAb_{1},... ,MAb_{ℓ},Nuc(w,p,a)>} GF Cl(r, s, c, z, y, p, a)

and the theorem follows.

□

We call the subgroup GF Cl(r, s, c, z, y, p, a) that appears in the formulation of theorem 3.6, a graded formal closure of the graded resolution GRes(y, p, a). 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 is the amalgamated product of a graded formal closure GF Cl(r, s, c, z, y, p, a) with a rigid graded limit group RgdGL(b, p, a) along the amalgamated subgroup < MAb_{1}, …, MAb_{pd′}, Nuc(w, 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) 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) with respect to the graded resolution GRes(y, p, a) was constructed from a graded formal test sequence. By the arguments presented in section 5 of [Se1] (the construction of Makanin-Razborov diagrams of limit groups), given the system of equations Σ(x, y, p, a) 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 (cf. ([Se1],5)), 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) with respect to the graded resolution GRes(y, p, a), we proceed as in the construction of the graded Makanin-Razborov diagrams. 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) principal cyclic 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.6 analyzes graded formal limit groups with trivial graded formal JSJ decomposition. Similarly, one can analyze graded formal limit groups with nontrivial graded formal JSJ decomposition, which are isomorphic to one of their graded formal shortening quotients.

Theorem 3.7. 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. Suppose the graded formal JSJ decomposition of GF L(x, z, y, p, a) is non-trivial. If a graded formal shortening quotient of GF L(x, z, y, p, a) is not a proper quotient of GF L(x, z, y, p, a) then for some solid graded (not formal!) limit group SldGL(b, p, a), GF L(x, z, y, p, a) can be written in the form:

GF L(x, z, y, p, a) = SldGL(b, p, a) ∗_{<MAB_{1},... ,MAb_{pd′} ,Nuc(w,p,a)>} GF Cl(r, s, c, z, y, p, a)

where GF Cl(r, s, c, z, y, p, a) is generated by a closure of the resolution GRes(y, p, a) and the subgroups MAb_{1}, …, MAb_{pd′}, the subgroups MAb_{1}, …, MAb_{pd′} are the maximal abelian subgroups of the solid limit group SldGL(b, p, a) containing pegs of pegged abelian groups that appear in the abelian decompositions associated with the graded completed resolution Comp(GRes)(z, y, p, a) in case GRes(y, p, a) is rigid, and in case the terminal graded limit group of the graded resolution GRes(y, p, a) is solid to generate GF Cl(r, s, c, z, y, p, a) additional variables c can be added to the non-QH, non-abelian vertex groups in the graded JSJ abelian decomposition of the terminal solid limit group of GRes(y, p, a). Nuc(w, p, a) is either a quotient 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 quotient of the terminal graded limit group in GF Cl(r, s, c, z, y, p, a) in case the terminal graded limit group of GRes(y, p, a) is solid. The elements {r} are generators of the subgroups {MAb_{1}, …, MAb_{pd′}}, and the elements s are roots added to abelian and pegged abelian vertex groups associated with the completed resolution Comp(GRes)(z, y, p, a), precisely in the same way they were added to the closure of a resolution in the ungraded case (see definition 1.14)).

Proof: identical with the proof of theorem 3.6.

□

The combinations of theorems 3.6 and 3.7 allow us to complete the construction of the graded formal Makanin-Razborov diagram. Suppose 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 recursive construction terminates. When the process of collecting maximal graded formal shortening quotients which are proper quotients terminates, we have either a graded formal limit group with trivial graded JSJ decomposition, or a graded formal limit group with some isomorphic maximal graded formal shortening quotient. By theorem 3.6 a graded formal limit group with trivial graded JSJ decomposition is of the form:

GF L(x, z, y, p, a) = RgdGL(b, p, a) ∗_{<MAb_{1},... ,MAb_{pd′} ,Nuc(w,p,a)>} GF Cl(r, s, c, z, y, p, a)

and by theorem 3.7, a graded formal limit group with an isomorphic graded formal shortening quotient is of the form:

GF L(x, z, y, p, a) = SldGL(b, p, a) ∗_{<MAb_{1},... ,MAb_{pd′} ,Nuc(w,p,a)>} GF Cl(r, s, c, z, y, p, a).

In both cases we continue the diagram by the graded (not formal!) Makanin-Razborov diagrams of RgdGL(b, p, a) or SldGL(b, p, a) in correspondence, viewing the subgroup Nuc(w, p, a) as the subgroup of parameters. We call the obtained diagram the graded formal Makanin-Razborov diagram of the system of equations Σ(x, y, p, a) 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(r, s, c, z, y, p, a) of the original graded resolution Gres(y, p, a).

Theorems 1.17 and 1.21 prove that if a predicate of certain form is a truth predicate, then there exist formal solutions that may serve as ”witnesses” for the correctness of the predicate. Corollaries 2.6 and 2.7 state the existence of these ”witnesses” in terms of the formal Makanin-Razborov diagram associated with a system of equations Σ(x, y, a) 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.17 and 1.21 on ”nice” subsets of the ambient set of defining parameters, we present generalizations of corollaries 2.6 and 2.7 in the graded framework. To generalize corollaries 2.6 and 2.7 we need to generalize the notions of covering closure to the graded category.

Definition 3.8. Let F_{k} =< a_{1}, …, a_{k} > be a free group, 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) be a system of equations defined over F_{k}. Let GF L(x, z, y, p, a) be a graded formal limit group of the system Σ(x, y, p, a) with respect to the graded resolution Comp(GRes)(z, y, p, a), and let GF Res(x, z, y, p, a) be a graded formal resolution in the graded formal Makanin-Razborov diagram of GF L(x, z, y, p, a). By the construction of the graded formal Makanin-Razborov diagram, with each graded formal resolution we can associate a graded formal closure GF Cl(r, s, c, z, y, p, a).

Following definition 1.15, we say that a collection of graded formal closures GF Cl_{1}(r, s, c, z, y, p, a), …, GF Cl_{q}(r, s, c, z, y, p, a), associated with the graded formal resolutions GF Res_{1}(x, z, y, p, a), …, GF Res(x, z, y, p, a) in correspondence, is a covering closure at some specialization (y_{0}, p_{0}, a) of the terminal rigid or solid graded limit group, of the graded resolution GRes(y, p, a), Rgd(y, p, a) or Sld(y, p, a) in correspondence, if the union of closure domains (see definition 1.14) Dom(GF Cl_{1}(r, s, c, z, y, p_{0}, a)), …, Dom(GF Cl_{q}(r, s, c, z, y, p_{0}, a)) covers the entire cross product of the abelian and pegged abelian groups Ab_{1}, …, Ab_{d}, P K_{1}, …, P K_{pd} in the (ungraded) completed resolution Comp(GRes)(z, y, p_{0}, a) corresponding to the specialization (y_{0}, p_{0}, a).

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 graded formal closures: GF Cl_{1}(r, s, c, z, y, p, a), …, GF Cl_{q}(r, s, c, z, y, p, a), associated with the graded formal resolutions GF Res_{1}(x, z, y, p, a), …, GF Res_{q}(x, z, y, p, a) of the system of equations Σ(x, y, p, a) with respect to the graded resolution GRes(y, p, a), so that the collection of graded formal closures is a covering closure of the (ungraded) resolution GRes(y, p_{0}, a) corresponding to the specialization (y_{0}, p_{0}, a), and for each index i, 1 ≤ i ≤ q, there exists a graded formal solution x_{i}(s, z, y, p_{0}, a) that factors through the graded formal resolution GF 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 a truth predicate 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 graded formal closures associated with the graded formal resolutions in the graded formal Makanin-Razborov diagram of the system Σ(x, y, p, a) 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.7.

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 graded formal closures: GF Cl_{1}(r, s, c, z, y, p, a), …, GF Cl_{q}(r, s, c, z, y, p, a), associated with the graded formal resolutions GF Res_{1}(x, z, y, p, a), …, GF Res_{q}(x, z, y, p, a), where for each index i, 1 ≤ i ≤ q, GF Res_{i}(x, z, y, p, a) is a graded formal resolution of the system of equations Σ_{j(i)}(x, y, p, a) with respect to the graded resolution GRes(y, p, a), so that the collection of graded formal closures is a covering closure of the (ungraded) resolution GRes(y, p_{0}, a) corresponding to the specialization (y_{0}, p_{0}, a), and for each index i, 1 ≤ i ≤ q, there exists a graded formal solution x_{i}(s, z, y, p, a) that factors through the graded formal resolution GF Res_{i}(x, z, y, p, 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 a truth predicate 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 graded formal closures associated with the graded formal resolutions in the graded formal Makanin-Razborov diagrams of the systems Σ_{1}(x, y, p, a), …, Σ_{r}(x, y, p, a) 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-Fe1] M. Bestvina and M. Feighn, Stable actions of groups on real trees, Inventiones Math. 121 (1995), 287-321.

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

[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-Se] E. Rips and Z. Sela, 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, preprint.