ON SOME NON-TERMINATING PROCEDURES

IN THE ELEMENTARY THEORY OF A FREE GROUP

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 demonstrate some of the inherent difficulties in tackling Tarski’s problems on the elementary theory of a free group.

In a sequence of papers on Diophantine geometry over groups [Se1]-[Se6] we developed basic techniques and objects required for the analysis of sentences and elementary sets defined over a free group, techniques that finally enable us to answer some of A. Tarski problems on the elementary theory of a free group and to classify those f.g. groups that are elementary equivalent to a (non-abelian) 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 known to us, 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 much more involved than the structure of varieties defined over a free group. To demonstrate the difficulties for constructing such procedures for analyzing AE sentences (which are still considerably easier than general first order sentences), we present a natural non-terminating procedure. This non-terminating procedure (theorem 2.1) is a counter-example to theorem 5 in [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.

Before we present such a non-terminating iterative procedure, we preferred to present a more basic phenomena, which we call the increase of the rank. 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

1Hebrew University, Jerusalem 91904, Israel.

2Partially supported by an Israel academy of sciences fellowship.

Before demonstrating the existence of a non-terminating procedure associated with the validation of an AE sentence, we present another natural phenomena which we call the increase of the rank.

Definition 1.1. Let L be a limit group. The rank of 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).

The next proposition demonstrates that the rank of a proper quotient of the completion of a resolution of in the strict Makanin-Razborov diagram, can be bigger than the rank of the original limit group. To understand why this increase of rank may cause (conceptual) difficulties in examining the termination of certain iterative procedures associated with an AE set, an interested reader may want to look at the proof of theorem 5 in [Kh-My].

Proposition 1.2. 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:

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

Proof: Let Q_{10} be the fundamental group of an orientable surface of genus 10. i.e.:

Q_{10} = < x_{1}, …, x_{20} | [x_{1}, x_{2}] … [x_{19}, x_{20}] = 1 > .

Clearly, Q_{10} admits a (standard) epimorphism onto a free group of rank 10, F_{10}. Since Q_{10} is a limit group (ω-residually free group), we can further modify the standard epimorphism to get an epimorphism: mu : Q_{10} → F_{10}, for which μ([x_{1}, x_{2}]) ≠ 1.

Similarly, let Q_{2} be the fundamental group of a surface of genus 2, S_{2}:

Q_{2} = < y_{1}, …, y_{4} | [y_{1}, y_{2}][y_{3}, y_{4}] = 1 > .

There exists a standard epimorphism from Q_{2} onto F_{2}, the free group of rank 2. We modify the standard epimorphism to get an epimorphism: ν : Q_{2} → F_{2} with several additional properties.

Lemma 1.3. There exists an epimorphism ν : Q_{2} → F_{2} with the following properties:

(i) ν([y_{1}, y_{2}]) ≠ 1.

(ii) the free group F_{2} admits no (non-trivial) cyclic decomposition in which ν(< y_{1}, y_{2} >) is elliptic.

Proof: Left for the interested reader.

□

We are now ready to prove proposition 1.2. We set U_{1} to be the subgroup of Q_{10} which is the fundamental group of a subsurface of genus 9 with a single puncture:

U_{1} =< x_{3}, …, x_{20} >

. We set U_{2} to be the subgroup of F_{10} which is the image (under μ) of the subgroup < x_{1}, x_{2} >: U_{2} = μ(< x_{1}, x_{2} >). U_{2} is isomorphic to a free group of rank 2. We set U_{3} to be the subgroup of Q_{2} which is the fundamental group of a subsurface of genus 1 with a single puncture: U_{3} =< y_{3}, y_{4} >.

Lemma 1.4. Let L be the group L = U_{1} ∗_{C_{1}} U_{2} ∗_{C_{2}} U_{3}, where C_{1} and C_{2} are (maximal) cyclic subgroups and the generators of the amalgamated subgroups are:

c_{1} = [x_{3}, x_{4}] … [x_{19}, x_{20}] = μ([x_{1}, x_{2}])
c_{2} = ν([y_{1}, y_{2}]) = [y_{3}, y_{4}]

Then:

(1) L is a limit group.

(2) L is freely indecomposable and the (canonical) abelian (cyclic) JSJ decomposition of L is given by:

L = U_{1} ∗_{C_{1}} U_{2} ∗_{C_{2}} U_{3}.

where U_{1} and U_{3} are QH subgroups.

(3) rk(L) ≤ 11.

Proof: Part (1) follows from theorem 5.12 of [Se1]. L is generated by two surface groups U_{1} ∗_{C_{1}} U_{2} and ν(< y_{1}, y_{2} >) ∗_{C_{2}} U_{3}, hence, it is freely indecomposable. The splitting given in part (2) is its JSJ decomposition since C_{1} and C_{2} are elliptic in every cyclic decomposition of L, and U_{2} admits no cyclic decomposition in which both C_{1} and C_{2} are elliptic. The rank of a surface group of genus 10 is 10, and that of a surface group of genus 2 is 2. Since L is generated by two such surface groups, and given their intersection in L, rk(L) ≤ 10 + 2 − 1 = 11.

□

One of the resolutions in the strict Makanin-Razborov diagram of the limit group L, denoted Res, corresponds to the natural epimorphism: τ : L → F_{10}, obtained by mapping U_{3} into U_{2} by the map ν, and mapping the subgroup U_{1} ∗_{C_{1}} U_{2} which is isomorphic to Q_{10} onto F_{10} by the map μ. The completion of Res, denoted Comp(Rlim), is the limit group which is the amalgamated free product:

Comp(Rlim) = U_{1} ∗_{C_{1}} F_{10} ∗_{C_{2}} U_{3}.

Lemma 1.5. There exists a proper quotient G of Comp(Rlim) that is isomorphic to a free group of rank 18.

Proof: We first map U_{3} < Comp(Rlim) into F_{10} by the map ν. Then we decompose the punctured surface group U_{1} as: U_{1} = B_{1} ∗ CB_{2} where B_{1} is the fundamental group of a punctured surface of genus 8 with one puncture, and B_{2} is the fundamental group of a twice punctured surface of genus 1. We map the amalgamated subgroup C into the identity element. We map B_{2} onto U_{2} < F_{10} and B_{1} onto a free group of rank 8. Hence L maps onto a free group F_{10} ∗F_{8}, which is a free group of rank 18.

□

Therefore, we finally found a limit group L, a strict Makanin-Razborov resolution of it, Res, and a proper quotient of its completion, G, for which:

rk(L) ≤ 11 < 18 = rk(G)

which finally proves proposition 1.2.

□

§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. To demonstrate the difficulties for constructing such procedures for analyzing AE sentences (which are still considerably easier than general first order sentences), we present a natural non-terminating procedure. This non-terminating 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) L_{i+1} is a proper quotient of Comp_{i}.

Proof: The procedure we construct is based on the ”increasing rank” phenomena presented in section 1. The structures of the limit groups L_{i} and the completions Comp_{i} are similar, hence, we present 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 Q_{g} be the fundamental group of an orientable surface of genus g. i.e.:

Q_{g} , = < x_{1}, …, x_{2g} | [x_{1}, x_{2}] … [x_{2g−1}, x_{2g}] > .

Clearly, Q_{g} admits a (standard) epimorphism onto a free group of rank g, F_{g}. Since Q_{g} is a limit group (ω-residually free group), we can further modify the standard epimorphism to get an epimorphism: μ : Q_{g} → F_{g}, for which μ([x_{1}, x_{2}]) ≠ 1. We further set Q_{2} to be the fundamental group of a surface group of genus 2, and

Q_{2} = < y_{1}, …, y_{4} | [y_{1}, y_{2}][y_{3}, y_{4}] = 1 >

and ν : Q_{2} → F_{2} to be the epimorphism that satisfies the properties listed in lemma 1.3.

We are now ready to construct a limit group R_{g}. We set U_{1} to be the subgroup of Q_{g} which is the fundamental group of a subsurface of genus g − 1 with a single puncture:

U_{1} =< x_{3}, …, x_{2g} >

. We set U_{2} to be the subgroup of F_{g} which is the image (under μ) of the subgroup < x_{1}, x_{2} >: U_{2} = μ(< x_{1}, x_{2} >). U_{2} is isomorphic to a free group of rank 2. We set U_{3} to be the subgroup of Q_{2} which is the fundamental group of a subsurface of genus 1 with a single puncture: U_{3} =< y_{3}, y_{4} >.

Lemma 2.2. Let M_{g} be the group M_{g} = U_{1} ∗_{C_{1}} U_{2} ∗_{C_{2}} U_{3}, where C_{1} and C_{2} are (maximal) cyclic subgroups and the amalgamated subgroups are:

C_{1} = [x_{3}, x_{4}] … [x_{2g−1}, x_{2g}] = μ([x_{1}, x_{2}])
C_{2} = ν([y_{1}, y_{2}]) = [y_{3}, y_{4}]

Then:

(1) M_{g} is a limit group.

(2) M_{g} is freely indecomposable and the (canonical) abelian (cyclic) JSJ decomposition of M_{g} is given by:

M_{g} = U_{1} ∗_{C_{1}} U_{2} ∗_{C_{2}} U_{3}.

(3) M_{g} admits a map onto F_{g}, obtained by mapping U_{3} into U_{2} using the homomorphism ν, and then mapping U_{1} ∗_{C_{1}} U_{2}, that is isomorphic to Q_{g}, onto F_{g} using the epimorphism μ.

Proof: Identical to lemma 1.4.

□

Starting with the limit group M_{g}, we construct a limit group R_{g}, so that M_{g} < R_{g}, and one of the resolutions in the strict Makanin-Razborov diagram of R_{g} is of the form: R_{g} → M_{g} → F_{g}. The limit group R_{g} is obtained from M_{g} by adding the fundamental groups of two punctured tori, which we denote U_{4} and U_{5}, amalgamated along their boundaries to U_{1} and U_{3} in correspondence, i.e.,

R_{g} = U_{4} ∗_{C_{4}} M_{g} ∗_{C_{5}} U_{5}

C_{4} < U_{1} and C_{5} < U_{5}.

U_{3} is a punctured torus so its fundamental group is a free group of rank 2. Hence, ν maps Q_{2} onto U_{3}. We set C_{5} to be generated by the element:

c_{5} = ν([y_{1}, y_{2}]) = [y_{3}, y_{4}].

We further set V_{1} to be the subgroup of U_{1}: V_{1} =< x_{2g−1}, x_{2g} >. V_{1} is the fundamental group of a punctured torus, hence, it is isomorphic to F_{2}, so ν maps Q_{2} onto V_{1}. We set C_{4} to be generated by the element:

c_{4} = ν([y_{1}, y_{2}]) = [y_{3}, y_{4}].

Lemma 2.3. Let V_{2} < U_{1} be the fundamental group of the twice punctured surface of genus g − 2, obtained by cutting the once punctured surface of genus g associated with U_{1} along the boundary of the punctured surface associated with V_{1}. Let C_{6} be the (cyclic) boundary subgroup of V_{1}. Then:

(1) R_{g} is a limit group. rk(R_{g}) ≥ g.

(2) the cardinality of the minimal generating set of R_{g}, deg(R_{g}), satisfies: deg(R_{g}) ≤ 2g + 6.

(3) R_{g} is freely indecomposable, and:

R_{g} = U_{4} ∗_{C_{4}} V_{1} ∗_{C_{6}} V_{2} ∗_{C_{1}} U_{2} ∗_{C_{2}} U_{3} ∗_{C_{5}} U_{5}

is the canonical abelian (cyclic) JSJ decomposition of R_{g}, where U_{4}, V_{2} and U_{5} are QH subgroups.

(4) one of the resolutions in the strict Makanin-Razborov diagram of R_{g} is: R_{g} → M_{g} → F_{g}. We denote this resolution of R_{g}, Res_{g}.

(5) The completed limit group C_{g} associated with the resolution Res_{g} is obtained as a graph of groups having two vertex groups and two edge groups. The first vertex group, denoted V̂_{2}, is isomorphic to V_{2}, and the second vertex group is:

D_{g} = U_{4} ∗_{C_{4}} V_{1} ∗_{C_{6}} V_{2} ∗_{C_{1}} F_{g} ∗_{C_{2}} U_{3} ∗_{C_{5}} U_{5}.

The graph of groups is obtained by identifying the two boundary components of V̂_{2} and V_{2} < D_{g}.

(6) R_{g} embeds into the completion C_{g}.

(7) There exists an epimorphism from C_{g} onto the free group of rank 3g − 6.

Proof: R_{g} maps onto M_{g} by mapping U_{4} into V_{1} using the homomorphism ν, and U_{5} into U_{3} using ν as well. Hence, the sequence of maps R_{g} → M_{g} → F_{g} satisfies the assumptions of theorem 5.12 of [Se1], which implies that R_{g} is a limit group. Since R_{g} maps onto F_{g}, rk(R_{g}) ≥ g and we get part (1). R_{g} is generated by U_{1}, U_{2}, U_{3}, U_{4} and U_{5}. U_{1} is isomorphic to a free group of rank 2g-2, and the groups U_{i} are all isomorphic to F_{2} for i = 2, …, 5. Hence:

rk(R_{g}) ≤ 2g − 2 + 2 · 4 = 2g + 6.

R_{g} is generated by the subgroup U_{1} ∗_{C_{1}} U_{2}, that is isomorphic to the surface group of genus g, Q_{g}, together with several subgroups (containing U_{3}, U_{4}, U_{5} in correspondence) that are all isomorphic to the surface group of genus 2, Q_{2}. Hence, R_{g} is freely indecomposable. M_{g} is a subgroup of R_{g}, hence, C_{1} and C_{2} that are elliptic in the abelian JSJ decomposition of M_{g}, must be elliptic in the abelian JSJ decomposition of R_{g}. Since C_{2} is elliptic in the JSJ of R_{g}, it is not difficult to see that C_{4} and C_{5} must be elliptic in the JSJ of R_{g} as well, hence, the JSJ decomposition of R_{g} is the one given in part (3) of the proposition.

Given the JSJ decomposition of the limit group R_{g}, we observe that the limit group M_{g}, that is isomorphic to a subgroup of R_{g}, is a shortening quotient of R_{g}, and in fact it is a maximal shortening quotient of R_{g}. Hence, the resolution: R_{g} → M_{g} → F_{g}, denoted Res_{g}, is a resolution that appers in the Makanin-Razborov diagram of R_{g}, and since it is a strict resolution, it appears in the strict Makanin-Razborov diagram of R_{g}. The structure of the completion of Res_{g}, C_{g}, given in part (5) of the proposition, is immediate from the definition of the completion presented in [Se2] (definition 1.11). By the construction of the completion, the limit group R_{g} is embedded in the completion C_{g} and we get part (6).

To get a map from the completion C_{g} onto a free group of rank 3g − 6 we do the following. We start by mapping U_{4} into V_{1} and U_{5} into U_{3} using the map ν. We continue by mapping the subgroup U_{3} into U_{2} using the map ν as well. We further decompose the twice punctured surface of genus g − 2, associated with V_{2}, into:

V_{2} = Y_{1} ∗_{A_{1}} Y_{2} ∗_{A_{2}} ∗Y_{3}

where Y_{1} and Y_{3} are the fundamental groups of a twice punctured torus, and Y_{3} is the fundamental group of a twice punctured surface of genus g − 4. We map A_{1} and A_{2} to the identity element, Y_{1} onto V_{1} and Y_{3} onto U_{2} (that is embedded in F_{g}, and Y_{2} onto a free group of rank g − 4, F_{g−4}. We map V̂_{2}, that is isomorphic to V_{2}, in precisely the same way we have mapped V_{2} and further map the Bass-Serre generator in the graph of groups used for the construction of the completion C_{g} into the identity element. Therefore, C_{g} is mapped onto a free group of the form: F_{g} ∗ F_{g−4} ∗ F_{g−4} ∗ F_{2}, which is a free group of rank 3g − 6, and we get part (7) of the proposition.

□

At this point we are finally ready to present the non-terminating procedure, and complete the proof of theorem 2.1. We set g(i) = i + 20. In this case, for every positive integer i, 3g(i) − 6 > 2(g(i) + 1) + 6. Hence, if for every integer i we set L_{i} to be R_{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 + 20.

(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) 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} → Ł_{i+1} → Comp_{i+1} → …

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

□

References

[Kh-My] O. Kharlampovich and A. Myasnikov, Elementary theory of free non-abelian groups, preprint (16 pages), www.math.mcgill.ca/ olga.

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

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