ON SOME NON-TERMINATING PROCEDURES

IN THE ELEMENTARY THEORY OF A FREE GROUP II

Z. Sela^{1,2}

We present some non-terminating iterative procedures that naturally arise in studying the first order theory over a free group. These procedures, that agree with the notions of [Kh-My], demonstrate some of the inherent difficulties in tackling Tarski’s problems on the elementary theory of a free group.

In any approach towards Tarski’s problems on the elementary theory of a free group that uses formal solutions (i.e., generalizations of Merzlyakov’s theorem [Me]), which include all the current approaches, the main conceptual and technical difficulties involve the ability to construct terminating procedures for the analysis of first order sentences and predicates. These inherent difficulties, to which the main part of our work is devoted ([Se4] and [Se5]), require the study of the structure of projections of varieties defined over a free group, which is far more involved than the structure of varieties defined over a free group.

In a previous note [Se], we have demonstrated the difficulties in constructing (terminating) procedures for analyzing AE sentences (which are still considerably easier than general first order sentences), by presenting a natural non-terminating procedure ([Se],2.1). Although the phenomenas demonstrated by the procedure presented in [Se] are conceptual, the objects we used did not agree with the notions and constructions of [Kh-My], as was pointed out, in justice, by O. Khralampovich [Kh].

In this note we modify the non-terminating procedure presented in [Se], so that it will agree with the notions and constructions of [Kh-My]. The modified nonterminating procedure we construct (theorem 2.1) is a counter-example to theorem 5 in [Kh-My]:

Theorem 5 ([Kh-My], page 10). Any sequence of the following type terminates.

F_{R(u_{1}(x_{1},... ,x_{n_{1}} ))} →_{τ_{1}} F_{R(s_{1}(x_{1},... ,x_{n_{2}} ))} →_{θ_{1}} F_{R(u_{2}(x_{1},... ,x_{n_{2}} ))} →_{τ_{2}} …
→_{τ_{k−1}} F_{R(s_{k−1}(x_{1},... ,x_{n_{k}}))} →_{θ_{k−1}} F_{R(u_{k}(x_{1},... ,x_{n_{k}}))} …

where n_{1} ≤ n_{2} ≤ … n_{k}, u_{1} = 1, …, u_{k} = 1 are irreducible systems, each τ_{i} is a canonical homomorphism from F_{R(u_{i})} in the NTQ group F_{R(s_{i})} (s_{i} = 1 is NTQ not in the variables x_{1}, …, x_{n_{i+1}}), each θ_{i} is a proper surjective homomorphism.

We should note that the terminating questions involved in analyzing general first order sentences (e.g. sentences with 4 quantifiers) are far more delicate.

1Hebrew University, Jerusalem 91904, Israel.

2Partially supported by an Israel academy of sciences fellowship.

Before we present such a non-terminating iterative procedure, we modify the example presented in the first section of [Se], to demonstrate the ”increase of rank” phenomena using the notions of [Kh-My]. To understand why this phenomena may cause (conceptual) difficulties in constructing terminating procedures, an interested reader may want to look at the argument used to prove theorem 5 in [Kh-My].

§1. The increase of the rank

Before modifying our construction of a non-terminating procedure associated with the validation of an AE sentence, we modify the example presented in the first section of [Se], so that it will agree with the notions and constructions given in [Kh-My], and demonstrate the natural phenomena which we call the increase of the rank.

Recall that the rank of a limit group L, rk(L), is the maximal rank of a free group F_{u} for which there exists an epimorphism h : L → F_{u}. Thus the rank of a free abelian group is 1, and the rank of an orientable surface group of genus g is g.

Let L(y) be a limit group. In section 5 of [Se1] we have associated a (canonical) Makanin-Razborov diagram with the limit group L, and in section 1 of [Se2] we modified this construction and associated a (canonical) strict Makanin-Razborov diagram with a limit group L (see definition 1.10 in [Se2]). With each resolution Res(y) in the strict Makanin-Razborov diagram of the limit group L(y), we have associated the completed resolution Comp(Res)(z, y), and the corresponding completed limit group Comp(Rlim)(z, y) (definition 1.11 in [Se2]). In Proposition 1.2 of [Se], we have shown that the rank of a proper quotient of a completion of a limit group L may be larger than the rank of L. O. Kharlampovich has pointed out to us that, in general, a completion of a limit group L may not be one of the minimal (canonical) NTQ groups associated with L discussed in theorems 4 and 5 in [Kh-My]. The next proposition demonstrates the ”increase of rank” phenomena for a minimal (canonical) NTQ group associated with a limit group.

Proposition 1.1. There exists a limit group L(y), a resolution Res(y) in the strict Makanin-Razborov diagram of L(y), and a proper (limit) quotient G(z, y) of the completion of Res(z, y), Comp(Rlim)(z, y),for which:

(i) The completion Comp(Rlim)(z, y) is one of the minimal (canonical) NTQ groups associated with the limit group L(y) according to theorems 4 and 5 of [Kh-My].

(ii) the rank of G(z, y) is strictly bigger than the rank of L(y):

rk(L(y)) < rk(G(z, y)) ≤ rk(Comp(Rlim)(z, y)).

Proof: Let F_{2} =< x_{1}, x_{2} > be a free group of rank 2, and let:

w_{1} = x_{1}[x_{1}^{3}, x_{2}^{3}] , w_{2} = x_{1}[x_{1}^{4}, x_{2}^{4}].

Lemma 1.2. F_{2} admits no (non-trivial) free decomposition in which w_{1} or w_{2} is contained in one of the factors, and no essential cyclic decomposition in which either w_{1} or w_{2} are elliptic.

Proof: By [Os-Zi], since w_{1}, w_{2} and x_{1} are mapped to the same element in the abelianization of F_{2}, if w_{1} or w_{2} are elements in a free basis of F_{2}, then they must be conjugates of x_{1}. Since both w_{1} and w_{2} are not conjugates of x_{1}, F_{2} admits no non-trivial free decomposition in which either w_{1} or w_{2} is contained in one of the factors.

Every essential cyclic splitting of F_{2} is an HNN of the form F_{2} = B∗_{C}, where C is cyclic and generated by a s.c.c. on the corresponding punctured torus. Since w_{1} w_{2} and x_{1} are mapped to the same element in the abelianization of F_{2}, if w_{1} or w_{2} are elliptic in such a splitting then the edge group C must be (conjugate to) < x_{1} >. Clearly, both w_{1} and w_{2} are not elliptic in a splitting of F_{2} along < x_{1} >, hence, w_{1} and w_{2} can not be elliptic in any essential cyclic splitting of F_{2}.

□

Let Q_{1,g} be a free group of rank 2g, which we view as the fundamental group of a once-punctured (orientable) surface of genus g. We set b to be a generator of the cyclic boundary subgroup of Q_{1,g}. Let U_{1} and U_{2} be isomorphic to Q_{1,g} and let b_{1} and b_{2} be their corresponding boundary elements. We further set the groups H_{1}, H_{2} to be:

H_{1} = F_{2} ∗_{<w_{1}>=<b_{1}>} U_{1} H_{2} = F_{2} ∗_{<w_{2}>=<b_{2}>} U_{2}

and:

L = U_{1} ∗_{<b_{1}>=<w_{1}>} F_{2} ∗_{<w_{2}>=<b_{2}>} U_{2}.

Lemma 1.3.

(1) H_{1}, H_{2} and L are freely indecomposable. Their essential abelian (cyclic) JSJ decompositions are given by the cyclic decompositions presented above.

(2) L (and hence, so are H_{1} and H_{2}) are limit groups.

(3) rk(L) ≤ 2g + 4.

Proof: To prove (1) we first observe that H_{1} is not a free group. Indeed, if H_{1} was free, then the element w_{1} = b_{1} must be an element in a free basis of either F_{2} or U_{1}. By lemma 1.2 it is not an element in a free basis of F_{2}, and since U_{1} is a once-punctured surface, it’s boundary element b_{1} is not an element in a free basis.

Suppose that H_{1} is freely decomposable. If the element w_{1} = b_{1} can be conjugated into one of the factors, then both F_{2} and U_{1} can be conjugated into that factor, a contradiction. Hence, we may assume that H_{1} = A ∗ B, and w_{1} = b_{1} can not be conjugated into the factors. Now, since both F_{2} and U_{1} are free, any non-trivial subgroup of H_{1} that does not intersect any conjugate of the subgroup < b_{1} >=< w_{1} > is either cyclic or free. Therefore, both A and B are free groups, which implies that H_{1} is free, a contradiction. The same argument implies that H_{2} is freely indecomposable, and since both H_{1} and H_{2} are freely indecomposable, and L is generated by H_{1} and H_{2}, L must be freely indecomposable as well.

H_{1} is freely-indecomposable and it admits the free decomposition: H_{1} = F_{2}∗_{<w_{1}>=<b_{1}>} U_{1}. If the subgroup < w_{1} >=< b_{1} > is not an edge group in the essential abelian JSJ of H_{1}, then it must correspond to a s.c.c. in a CMQ subgroup M in the JSJ of of H_{1}, and that CMQ subgroup M must contain the QH subgroup U_{1}. Since F_{2} admits no essential cyclic splitting in which w_{1} is elliptic, the CMQ subgroup M must contain F_{2} as well, hence, the entire group H_{1} is contained in M, a contradiction. Therefore, < w_{1} >=< b_{1} > is an edge group in the abelian (cyclic) JSJ decomposition of H_{1}. Since F_{2} admits no cyclic splitting in which w_{1} is elliptic, F_{2} is elliptic in the essential JSJ of H_{1}, hence, the essential JSJ of H_{1} is given by the decomposition: H_{1} = F_{2} ∗_{<w_{1}>=<b_{1}>} U_{1}. The JSJ of H_{2} is obtained in exactly the same way, and since both H_{1} and H_{2} are subgroups of L, they generate L, and their intersection in L is the subgroup F_{2}, the essential JSJ of L is given by:

L = U_{1} ∗_{<b_{1}>=<w_{1}>} F_{2} ∗_{<w_{2}>=<b_{2}>} U_{2}

which finally proves part (1) of the lemma.

Let Q_{1,g−1} be a free group of rank 2g − 2, which we view as the fundamental group as a once-punctured surface of genus g −1. Let b̂ be a generator of its (cyclic) boundary subgroup. We set V to be the group obtained as the amalgamated free product:

V = F_{2} ∗_{<x_{1}>=<b̂>} Q_{1,g−1}.

Since F_{2} =< x_{1}, x_{2} >, V is a free group of rank 2g − 1. Clearly, there exists a natural epimorphism: η : L → V, that maps the subgroup F_{2} < L isomorphically onto the subgroup F_{2} < V. Hence, by theorem 5.12 of [Se1], L is a limit group and we get part (2).

Let Q_{2g+2} be the fundamental group of an oriented surface of genus 2g+2. By the construction of the limit group L, there exists an epimorphism: ν : Q_{2g+2} ∗F_{2} → L. Therefore:

rk(L) ≤ rk(Q_{2g+2} ∗ F_{2}) = 2g + 4

which gives part (3) of the lemma.

□

We are now ready to prove proposition 1.1. We set Q_{1,g−1} to be the fundamental group of a once-punctured surface of genus g − 1, and b̂ to be the generator of its (cyclic) boundary subgroup. We set:

V = F_{2} ∗_{<x_{1}>=<b̂>} Q_{1,g−1} Comp = L ∗_{<x_{1}>=<b̂>} Q_{1,g−1}.

Note that V is a free group of rank 2g − 1.

Lemma 1.4.

(1) L is naturally embedded in Comp.

(2) Comp is freely indecomposable, and its essential JSJ decomposition contains 4 vertices stabilized by U_{1}, U_{2}, Q_{2g−1}, F_{2}, where the vertices stabilized by U_{1}, U_{2}, Q_{g−1} are connected to the vertex stabilized by F_{2} with edges stabilized by < b_{1} >, < b_{2} > and < x_{1} > in correspondence.

(3) Comp is a completion of L.

(4) Comp is one of the minimal (canonical) NTQ groups associated with L according to theorems 4 and 5 in [Kh-My].

(5) Comp has a free quotient G of rank 3g − 1. In particular, for every g ≥ 6:

rk(L) ≤ 2g + 4 < 3g − 1 ≤ rk(G) ≤ rk(Comp).

Proof: Comp is the amalgamated product: Comp = L ∗_{<x_{1}>=<b̂_{1}>} Q_{1,g−1}, so L is naturally embedded in Comp. Since L is freely indecomposable, and Q_{1,g−1} admits no free decomposition in which b̂_{1} is contained in a factor, Comp is freely indecomposable as well. Since F_{2} is elliptic in the essential JSJ decomposition of L, the structure of the essential JSJ decomposition of Comp presented in part (1) of the lemma, follows from the structure of the essential JSJ decomposition of L presented in part (2) of lemma 1.3.

One of the resolutions in the strict Makanin-Razborov diagram of L is the (two level) resolution Res: L → V. By definition ([Se2],1.11), the completion corresponding to this resolution, is Comp.

Since Comp is a completion, it is, in particular, a NTQ subgroup in the sense of [Kh-My]. The element x_{1} ∈ Comp is not in the commutator subgroup when viewed as an element x_{1} ∈ F_{2}, is an element of genus g + 1 as an element in L, and is an element of genus g − 1 in Comp. Since every specialization that factor through the limit group L, can be completed to a specialization of at least one of the the minimal (canonical) NTQ groups associated with L according to theorems 4 and 5 of [Kh-My], the element x_{1} has to be of genus g − 1 in at least one of those minimal (canonical) NTQ groups. Since all the specializations of L that can be completed to specializations that factor through the completion Comp must factor through at least one of the minimal (canonical) NTQ groups, and in particular a test sequence that factors through the completion Comp (see definition 1.19 in [Se2]), the completion Comp must be one of the minimal (canonical) NTQ groups associated with L according to [Kh-My].

rk(L) ≤ 2g+4 by part (3) of lemma 1.3. By mapping F_{2} < Comp to the identity element, we get an epimorphism of Comp onto the free product Q_{g} ∗ Q_{g} ∗ Q_{g−1}. Therefore, there exists an epimorphism from Comp onto a free group G of rank 3g − 1 and part (4) of the lemma follows.

□

The limit group L and its associated minimal (canonical) NTQ group Comp used in lemma 1.4, clearly proves proposition 1.1 and demonstrate the ”increase of rank” phenomena using the notions and construction of [Kh-My].

□

§2. A non-terminating iterative procedure

In any approach towards Tarski’s problems on the elementary theory of a free group that uses formal solutions, which include all the current approaches, the main conceptual and technical difficulties involve the ability to present terminating procedures for the analysis of first order sentences and predicates. In our previous note [Se], we demonstrated the difficulties in constructing such procedures for analyzing AE sentences (which are still considerably easier than general first order sentences), by presenting a natural non-terminating procedure. The phenomenas we demonstrated in [Se] are conceptual, still O. Kharlampovich pointed out [Kh], in justice, that our non-terminating procedure does not agree with the notions of [Kh-My]. In this section, we modify the procedure presented in the second section of [Se], and present a natural non-terminating procedure that agrees with the notions and and constructions of [Kh-My]. Hence, this nonterminating procedure (theorem 2.1) is a counter-example to theorem 5 of [Kh-My]. We should note that the terminating questions involved in analyzing general first order sentences (e.g. sentences with 4 quantifiers) are far more delicate.

Theorem 2.1 (cf. [Kh-My], theorem 5). There exists a non-terminating iterative procedure of the form:

L_{1} → Comp_{1} → L_{2} → Comp_{2} → … →
… → L_{i} → Comp_{i} → Ł_{i+1} → Comp_{i+1} → …

for which for every index i:

(1) L_{i} is a limit group.

(2) Comp_{i} is the completion of a resolution in the strict Makanin-Razborov diagram of the limit group L_{i}, and L_{i} naturally embeds in Comp_{i}.

(3) Comp_{i} is one of the minimal (canonical) NTQ groups associated with the limit group L according to theorems 4 and 5 in [Kh-My].

(4) L_{i+1} is a proper quotient of Comp_{i}.

Proof: As in the second section of [Se], the procedure we construct is based on the ”increasing rank” phenomena presented in section 1. We start by presenting a general construction of a limit group with an (integer) parameter g, and then use this construction to define the L_{i}’s and Comp_{i}’s in a non-terminating procedure.

Let U be a free group of rank 2g which we view as the fundamental group of a once-punctured surface of genus g. Let b be a generator of its (cyclic) boundary group. Let F_{2} =< x_{1}, x_{2} > be a free group of rank 2, and let w ∈ F_{2} be the element: w = x_{1}[x_{1}^{3}, x_{2}^{3}]. Let V be a free group of rank 3, which we view as the fundamental group of a twicepunctured torus. Let c_{1}, c_{2} be the generators of its (cyclic) boundary subgroups, so that V admits a presentation of the form:

V = < c_{1}, f_{1}, f_{2}, c_{2} | c_{1} = c_{2}[f_{1}, f_{2}] >

Let r ∈ V be the element: r = c_{1}[c_{1}^{4}, (f_{1}[f_{1}^{3}, f_{2}^{3}])^{4}]. Finally, we set L_{g} to be the group obtained by the amalgamated product:

L_{g} = F_{2} ∗_{<w>=<c_{2}>} V ∗_{<r>=<b>} U.

Lemma 2.2.

(1) V admits no (non-trivial) free decomposition in which r is contained in one of the factors, and no essential cyclic decomposition in which the element r is elliptic.

(2) L_{g} is freely indecomposable. The essential abelian (cyclic) JSJ decomposition of L_{g} is given by the amalgamated product:

L_{g} = F_{2} ∗_{<w>=<c_{2}>} V ∗_{<r>=<b>} U.

(3) L_{g} is a limit group.

(4) deg(L_{g}) ≤ 2g + 5. i.e., L has a generating set of cardinality 2g + 5.

Proof: Suppose that V admits a (non-trivial) free decomposition V = A ∗ B so that r ∈ A. The subgroup < c_{1}, f_{1}[f_{1}^{3}, f_{2}^{3}] >, which is a free group of rank 2, inherits a free decomposition from the given free decomposition of V. By lemma 1.2, since r = c_{1}[c_{1}^{4}, (f_{1}[f_{1}^{3}, f_{2}^{3}])^{4}] this free decomposition inherited by the subgroup < c_{1}, f_{1}[f_{1}^{3}, f_{2}^{3}] > is trivial, so c_{1}, f_{1}[f_{1}^{3}, f_{2}^{3}] ∈ A.

Now, the subgroup < f_{1}, f_{2} > inherits a free decomposition from the given free decomposition of V. Since < f_{1}, f_{2} > admits no free decomposition in which the element f_{1}[f_{1}^{3}, f_{2}^{3}] is contained in one of the factors, and since f_{1}[f_{1}^{3}, f_{2}^{3}] ∈ A, it follows that f_{1}, f_{2} ∈ A. Hence, c_{1}, f_{2}, f_{2} ∈ A, and these elements generate L_{g}, so the entire group L_{g} is a subgroup of A, a contradiction. Therefore, V admits no non-trivial free decomposition in which r is contained in one of the factors. The argument for an essential cyclic decomposition of V in which r is elliptic is identical, and we get part (1) of the lemma.

Let:

D_{g} = F_{2} ∗_{<w>=<c_{2}>} V T_{g} = V ∗_{<r>=<b>} U.

be the corresponding subgroups of L_{g}. To prove part (2), we first show that T_{g} is freely indecomposable and its essential JSJ decomposition is given by the amalgamated product presented above. We first observe that T_{g} is not a free group. If T_{g} was a free group, then the element r = b must be an element in a free basis of the subgroup V, a contradiction to part (1). Therefore, T_{g} is not a free group. Suppose that T_{g} is freely decomposable. If the element r = b can be conjugated into one of the factors, then both V and U can be conjugated into that factor, a contradiction. Hence, we may assume that T_{g} = A ∗ B and r = b can not be conjugated into the factors. Now, since both V and U are free, any non-trivial subgroup of T_{g} that does not intersect any conjugate of the subgroup < r >=< b > is either cyclic or free. Therefore, both A and B are free groups, which implies that T_{g} is free, a contradiction. The argument that shows the essential JSJ decomposition of T_{g} is given by the amalgamated product: T_{g} = V ∗_{<r>=<b>} U is essentially identical.

Suppose that L_{g} is freely indecomposable. Assume L_{g} admits the non-trivial free decomposition: L_{g} = A ∗ B. Since T_{g} < L_{g} is freely indecomposable, we may assume that T_{g} < A. which, in particular, implies that w = c_{2} ∈ A. Since F_{2} admits no non-trivial free decomposition in which w is contained in one of the factors, we get that F_{2} < A as well, so L_{g} < A, a contradiction, hence, L_{g} is freely indecomposable. Since T_{g} < L_{g}, and the element w = c_{2} is elliptic in the JSJ decomposition of T_{g}, w = c_{2} must be elliptic in the essential JSJ decomposition of L_{g}. Since by lemma 1.2, F_{2} admits no essential cyclic decomposition in which the element w is elliptic, F_{2} is elliptic in the essential JSJ decomposition of L_{g}. Since T_{g} < L_{g}, V is elliptic in the essential JSJ decomposition of L_{g}. Therefore, the essential JSJ decomposition of L_{g} is given by the amalgamated product:

L_{g} = F_{2} ∗_{<w>=<c_{2}>} V ∗_{<r>=<b>} U

and part (2) follows.

To prove part (3), let R_{1} and R_{2} be free groups of rank 2g − 2, which we view as the fundamental group of a once-punctured surface of genus g − 1, Let e_{1} ∈ R_{1} and e_{2} ∈ R_{2}, be generators of the cyclic boundary subgroups of R_{1} and R_{2} in correspondence. We set M_{g} and N_{g} to be the groups:

M_{g} = D_{g} ∗_{<c_{1}>=<e_{1}>} R_{1} N_{g} = F_{2} ∗_{<x_{1}>=<e_{2}>} R_{2}

Clearly, N_{g} is a free group of rank 2g − 1. Furthermore, the limit group L admits a resolution Res:

L_{g} → M_{g} → N_{g}

and this is a strict MR resolution, so by theorem 5.12 of [Se1], L_{g} is a limit group.

L_{g} is generated by the subgroups U, V and F_{2}, and these are free groups of degrees 2g, 3, and 2 in correspondence, hence, deg(L_{g}) ≤ 2g + 5, and we get part (4) of the lemma.

□

We are now ready to construct a completion of L_{g} which we denote C_{g}, which is also one of the minimal (canonical) NTQ subgroup associated with the limit group L_{g} according to theorems 4 and 5 of [Kh-My], a completion that will allow us to construct the non-terminating procedure presented in the statement of theorem 2.1. We set R_{1} and R_{2} to be free groups of rank 2g−2, which we view as the fundamental group of a once-punctured surface of genus g − 1. Let e_{1} ∈ R_{1} and e_{2} ∈ R_{2}, be generators of the cyclic boundary subgroups of R_{1} and R_{2} in correspondence. We set C_{g} to be the group given by the amalgamated product:

C_{g} = R_{1} ∗_{<e_{1}>=<c_{1}>} L_{g} ∗_{<x_{1}>=<e_{2}>} R_{2}.

Lemma 2.3.

(1) L_{g} is naturally embedded in C_{g}.

(2) C_{g} is freely indecomposable, and its essential JSJ decomposition is a tree of groups with 5 vertices stabilized by: R_{1}, R_{2}, U, V, F_{2}, and 4 edges stabilized by cyclic subgroups generated by the elements: r, c_{1}, c_{2}, x_{1}.

(3) C_{g} is a completion of L_{g}.

(4) C_{g} is one of the minimal (canonical) NTQ groups associated with L according to theorems 4 and 5 in [Kh-My].

(5) C_{g} has a free (proper) quotient G of rank 3g − 2.

Proof: C_{g} is the amalgamated product:

C_{g} = R_{1} ∗_{<c_{1}>=<e_{1}>} L_{g} ∗_{<x_{1}>=<e_{2}>} R_{2}

so L_{g} is naturally embedded in C_{g}. Since L_{g} is freely indecomposable, and R_{1} and R_{2} admit no free decomposition in which e_{1} and e_{2} are contained in a factor, C_{g} is freely indecomposable as well. Since F_{2} and V are elliptic in the JSJ decomposition of L_{g}, the structure of the essential JSJ decomposition of C_{g} presented in part (2) of the lemma, follows from the structure of the JSJ decomposition of L_{g} presented in part (2) of lemma 2.2.

Recall, that we have set:

M_{g} = D_{g} ∗_{<c_{1}>=<e_{1}>} R_{1} N_{g} = F_{2} ∗_{<x_{1}>=<e_{2}>} R_{2}.

One of the resolutions in the strict Makanin-Razborov diagram of L_{g} is the (two level) resolution Res: L → M_{g} → N_{g}. By definition ([Se2],1.11), the completion corresponding to this resolution, is C_{g}.

Since C_{g} is a completion, it is, in particular, a NTQ subgroup in the sense of [Kh-My]. The element x_{1} ∈ C_{g} is not in the commutator subgroup when viewed as an element x_{1} ∈ F_{2}, is an element of genus g + 3 as an element in L_{g}, an element of genus g + 1 as an element of M_{g}, and an element of genus g − 1 in C_{g}. Similarly, the element c_{1} ∈ C_{g} is not in the commutator subgroup when viewed as an element c_{1} ∈ V, is an element of genus g + 1 as an element in L_{g}, an element of genus g + 1 as an element in the subgroup L_{g} ∗_{<x_{1}>=<e_{2}>} R_{2}, and is an element of genus g − 1 in C_{g}. Since every specialization that factors through the limit group L_{g}, can be completed to a specialization of at least one of the the minimal (canonical) NTQ groups associated with L_{g} according to theorems 4 and 5 of [Kh-My], the elements x_{1} and c_{1} have to be of genus g−1 in at least one of those minimal (canonical) NTQ groups. Since all the specializations of L_{g} that can be completed to specializations that factor through the completion C_{g} must factor through at least one of the minimal (canonical) NTQ groups, and in particular a test sequence ([Se2],1.19) that factors through the completion C_{g} factors through at least one of the minimal (canonical) NTQ groups associated with L_{g} according to [Kh-My], the completion C_{g} must be one of the minimal (canonical) NTQ groups associated with L_{g} according to [Kh-My], and we get part (4).

By mapping the subgroups V and F_{2} of C_{g} to the identity element, we get an epimorphism of C_{g} onto the free product Q_{g} ∗ Q_{g−1} ∗ Q_{g−1}, where Q_{g} is the fundamental group of a surface of geus g, and Q_{g−1} is the fundamental group of a surface of genus g − 1. Clearly, the group Q_{g} ∗ Q_{g−1} ∗ Q_{g−1} has a proper quotient G, which is a free group of rank 3g − 2, which finally proves part (5) of the lemma.

□

At this point we are finally ready to present the non-terminating procedure that agrees with the notions and constructions of theorems 4 and 5 of [Kh-My], and complete the proof of theorem 2.1. We set g(i) = i + 10. In this case, for every positive integer i, 3g(i) − 2 > 2(g(i) + 1) + 5. Hence, if for every integer i we set L̂_{i} to be L_{g(i)}, and Comp_{i} to be C_{g(i)}, then:

(1) L̂_{i} is a limit group.

(2) rk(L̂_{i}) ≥ g(i) = i + 10.

(3) Comp_{i} is the completion of a resolution in the strict Makanin-Razborov diagram of the limit group L̂_{i}, and L̂_{i} naturally embeds in Comp_{i}.

(4) Comp_{i} is one of the minimal (canonical) NTQ subgroups associated with the limit group L̂_{i} according to theorems 4 and 5 of [Kh-My].

(4) L̂_{i+1} is a proper quotient of Comp_{i}. Therefore, the iterative procedure:

L̂_{1} → Comp_{1} → L̂_{2} → Comp_{2} → … →
… → L̂_{i} → Comp_{i} → L̂_{i+1} → Comp_{i+1} → …

does not terminate, and the proof of theorem 2.1 is completed.

□

References

[Kh] O. Kharlampovich, On Z. Sela’s misunderstanding of our results and definitions, preprint (1 page), www.math.mcgill.ca/ olga.

[Kh-My] O. Kharlampovich and A. Myasnikov, Elementary theory of free non-abelian groups, preprint (16 pages), www.math.mcgill.ca/ olga (the original version was removed around May 17th, 2001, around a month after this note was posted).

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

[Os-Zi] R. P. Osborne and H. Zieschang, Primitives in the free group on two generators, Inventiones Math. 63 (1981), 17-24.

[Se1-Se6] Z. Sela, Diophantine geometry over groups I-VI, preprints.

[Se] , On some non-terminating procedures in the elementary theory of a free group, preprint.