TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 350, Number 3, March 1998, Pages 947–974 S 0002-9947(98)01798-X

EQUATIONS IN A FREE Q-GROUP

O. KHARLAMPOVICH AND A. MYASNIKOV

Abstract. An algorithm is constructed that decides if a given finite system of equations over a free Q-group has a solution, and if it does, finds a solution.

0. Introduction

Systems of equations over a group have been widely studied (see, for instance, [4],[5],[11]). This is currently one of the main streams of combinatorial group theory. The problem of deciding if a system of equations in a group has a solution is a generalization of the word and conjugacy problems. Makanin [8] and Razborov [11] proved one of the most significant results in this area: the algorithmic solvability of systems of equations in free groups. Rips and Sela [12] solved equations over hyperbolic groups by reducing the problem to free groups. Myasnikov and Remeslennikov proved that the universal theory is decidable over free A-groups, where A is an integral domain of characteristic 0 and Z is a pure subgroup of A.

If Z is not a pure subgroup of A then the structure of a free A-group is much more complicated. It turned out (see [3]) that the crucial case is A = Q. Baumslag [1] proved that the word problem is decidable in free Q-groups. In [6] we proved that the conjugacy problem in these groups is decidable.

A subring C of the ring Q is said to be recursive if there is an algorithm which decides whether a given rational number belongs to C. Any subring of Q is of the form Q_{π}, i.e. generated by the set \{\frac{1}{p} |p ∈ π\}, where π is a set of primes. It is not difficult to see that the recursive subrings of Q are exactly the rings Q_{π} for recursive subsets π. If the set π is not recursive then the Diophantine problem over a free Q_{π}-group F^{Q_{π}} is undecidable. Indeed, let a ∈ F^{Q_{π}} be an element which Q_{π}-generates its own centralizer in F^{Q_{π}} (i.e. if 1 ≠ a = b^{r}, then r is invertible in Q_{π}); then an equation x^{p} = a has a solution in F^{Q_{π}} if and only if p ∈ π.

The main result of this paper is the following.

Theorem 1. Let π be a recursive set of primes. Then there exists an algorithm that decides if a given finite system of equations over a free Q_{π}-group has a solution, and if it does, finds a solution.

In particular, the Diophantine problem over a free Q-group F^{Q} is decidable. Let A be an arbitrary ring of characteristic 0 with a prime subring Z. The

additive isolator Is_{A}(Z) = {a ∈ A | ∃n(na ∈ Z)} of Z in A is a subring of A which

\begin{matrix}c \\ ◯ \end{matrix}1998 American Mathematical Society

Received by the editors April 5, 1996.

1991 Mathematics Subject Classification. Primary 20E05, 20F10.

The first author was supported by grants from NSERC and FCAR; the second author was supported by the NSF Grant DMS-9103098.

is embeddable in Q. Therefore, Is_{A}(Z) = Q_{π(A)}, where π(A) is the set of all prime integers which are invertible in A.

Theorem 1 and approximation results from [3] imply the following fact.

Theorem 2. Let A be a ring of characteristic 0 with identity 1. Then an algorithm that decides if a given finite system W = 1 of equations with coefficients in F has a solution in a free A-group F^{A} exists if and only if the set π(A) is recursive. Moreover, if W = 1 has a solution, the algorithm finds one.

In particular, for any field K of characteristic 0 the Diophantine problem with coefficients in F over F^{K} is decidable.

In order to solve a system of equations in a free Q_{π}-group, we develop some methods to reduce a system of equations in such a group to a finite set of systems in a free group. The reduction guarantees that for every so-called “minimal” solution of the system in the free Q_{π}-group, there exists a solution to at least one of the systems in the free group satisfying certain conditions restricting the range of values of the unknowns, and for every such solution to one of the systems in the free group there exists a corresponding solution for the original system in the free Q_{π}-group. Since by [8], [7] and [11] it is possible to decide if a system of equations in a free group has a solution (satisfying certain restrictions), this reduction allows one to decide if the system over the free Q_{π}-group has a solution. This idea was used for the first time in [12]. Notice that a system of equations over a free Q_{π}-group is equivalent to a system of equations (over the free Q_{π}-group) with coefficients that lie in the free group with the same set of generators. Notice also that a free Q_{π}- group is a direct limit of hyperbolic groups [6], but this does not help us directly. Indeed, if a solution of the system exists in the free Q_{π}-group then it belongs to some member of the union (direct limit), so to some hyperbolic group, but we do not know which member.

We can prove the same result as Theorem 1 for a tensor Q_{π}-completion of an arbitrary torsion-free hyperbolic group, but a lot of additional work is required. With a view to proving the more general result in a subsequent paper, we formulate most of the notions and lemmas in this paper in more general terms than are required for proving Theorem 1.

Let G be a torsion-free hyperbolic group with generators d_{1}, …, d_{N}. We will consider a finite system of equations over the Q_{π}-group G^{Q_{π}} (see the definition in the next section). By adding a finite number of new variables and new equations we can reduce this system to a system with coefficients in G (indeed, every constant of the form d^{m/n} can be replaced by a new variable z satisfying the equation z^{n} = d^{m}). We also can replace this system by an equivalent system of triangular equations (every equation contains no more than three terms). We will consider now a finite system of triangular equations with coefficients in G:

ϕ_{i}(d_{1}, …, d_{N}, x_{1}, …, x_{L}) = 1 (1)

1. A-groups

Let A be an arbitrary associative ring with identity and G a group. Fix an action of the ring A on G, i.e. a map G × A → G. The result of the action of α ∈ A on g ∈ G is written as g^{α}. Consider the following axioms:

1. g^{1} = g, g^{0} = 1, 1^{α} = 1;

2. g^{α+β} = g^{α} · g^{β}, g^{αβ} = (g^{α})^{β}; 3. (h^{−1}gh)^{α} = h^{−1}g^{α}h;

4. [g, h] = 1 ⟹ (gh)^{α} = g^{α}h^{α}.

Definition 1. Groups with A-actions satisfying axioms 1)–4) are called A–groups.

In particular, an arbitrary group G is a Z-group. We now recall the definition of A-completion.

Definition 2. Let G be a group. Then an A–group G^{A} together with a homomorphism G → G^{A} is called a tensor A–completion of the group G if G^{A} satisfies the following universal property: for any A–group H and a homomorphism φ : G → H there exists a unique A–homomorphism ψ : G^{A} → H (a homomorphism that commutes with the action of A) such that the following diagram commutes:

[figure: G; G^{A}; H; φ; ψ; λ]

It was proved in [2] that for every group G the tensor Q_{π}-completion of G exists and is unique; in [9] this fact was proved for an arbitrary ring A.

We describe below the Q_{π}-completion G^{Q_{π}} of a torsion-free hyperbolic group G as the union of an effective chain of hyperbolic subgroups (details can be found in [6]).

An element v of a group is called a primitive element if it is not a proper power. Let Z_{π} be the multiplicative submonoid of Z generated by the set π, Z_{π} =

{m_{1}, m_{2}, … }, where m_{1} < m_{2} < …. For an arbitrary torsion-free hyperbolic group R and natural number n ≥ 2, choose a set of elements V_{n} = {v_{1} … v_{t}} ∈ R satisfying the following condition (S_{n}):

1) V_{n} consists of cyclically minimal (of minimal length in its conjugacy class) primitive elements of length not more than m_{n};

2) no two centralizers in the set of centralizers {C(v), v ∈ V_{n}} are conjugate in R;

3) the set V_{n} is maximal with properties 1) and 2), i.e. any element of length

not more then m_{n} is conjugate to a power of some v ∈ V_{n}. By definition,

R(V_{n}) = (… (R ∗_{v_{1}=w_{1}^{mn}} ⟨w_{1}⟩) ∗_{v_{2}=w_{2}^{mn}} ⟨w_{2}⟩) ∗ …) ∗_{v_{t}=w_{t}^{mn}} ⟨w_{t}⟩). (2)

Notice that this definition does not depend on the order of elements in V_{n}. It was proved in [6] that G^{Q_{π}} is the union of a chain of hyperbolic groups

G = T_{0} < T_{1} < T_{2} < … < ⋃_{n=0}^{∞} T_{n},

with T_{n} = T_{n−1}(V_{n}), where V_{n} satisfies the condition S_{n} in the group T_{n−1}.

Definition 3. Let a group H be an amalgamated product H = S ∗_{w=t^{r}} ⟨t⟩. Then t-syllables of the word b_{0}t^{α_{1}}b_{1}t^{α_{2}} … b_{n}, where b_{j} ∈ S, are the subwords t^{α_{1}}, …, t^{α_{n}}. If u is an element in H, then |u|_{H} is the number of occurrences of ⟨t⟩-syllables in a reduced word representing u. We call this number the t-length of u.

Any finite set of elements {g_{1}, …, g_{n}} in G^{Q_{π}} is contained in some subgroup H that is obtained from the group G by adding a finite number of roots. It is the union of a chain of subgroups H_{i}. The groups H_{i} together with a canonical set of generators are defined below. Let G = H_{0}.

1. Step 1. Consider pairwise nonconjugated cyclically minimal primitive elements u_{1}, …, u_{k_{1}} ∈ G, |u_{1}| ≤ … ≤ |u_{k_{1}}| (here |u| denotes the length of u in G), and add roots t_{1}, …, t_{k_{1}} such that u_{j} = t_{j}^{s_{j}}. (Notice that u_{i+1} does not become a proper power after we add roots t_{1}, …, t_{i}.) The corresponding groups are denoted by H_{1}, …, H_{k_{1}}, where H_{j+1} = H_{j} ∗_{u_{j+1}=t_{j+1}^{s_{j+1}}} ⟨t_{j+1}⟩.

2. Step 2. Consider pairwise nonconjugated primitive elements u_{k_{1}+1}, …, u_{k_{2}} ∈ H_{1}, cyclically reduced in the amalgamated product, each having the reduced form u = t_{1}^{α_{1}}c_{1} … t_{1}^{α_{k}}c_{k}, where α_{i} ≠ 0, α_{i} ∈ Z, c_{i} ∈ G, |u_{k_{1}+1}|_{H_{1}} ≤ … ≤ |u_{k_{2}}|_{H_{1}}; and add roots t_{k_{1}+1}, …, t_{k_{2}}, such that u_{j} = t_{j}^{s_{j}}, to the group H_{k_{1}}. The corresponding groups are denoted by H_{k_{1}+1}, …, H_{k_{2}}, where H_{j+1} = H_{j} ∗_{u_{j+1}=t_{j+1}^{s_{j+1}}} ⟨t_{j+1}⟩.

3. Step i + 1. Suppose that H_{1}, …, H_{k_{i}} have been constructed.

Consider pairwise nonconjugated primitive elements u_{k_{i}+1}, …, u_{k_{i+1}} ∈ H_{i}, cyclically reduced in the amalgamated product, each having the following reduced form t_{i}^{α_{1}}c_{1} … t_{i}^{α_{k}}c_{k}, where α_{i} ≠ 0, α_{i} ∈ Z, c_{i} ∈ H_{i−1} (c_{k} is not a power of u_{i}, because the elements are cyclically reduced), |u_{k_{i}+1}|_{H_{i}} ≤ … ≤ |u_{k_{i+1}}|_{H_{i}} , and add roots t_{k_{i}+1}, …, t_{k_{i+1}}, such that u_{j} = t_{j}^{s_{j}}, to the group H_{k_{i}}. The corresponding groups are denoted by H_{k_{i}+1}, …, H_{k_{i+1}}, where H_{j+1} = H_{j} ∗_{u_{j+1}=t_{j+1}^{s_{j+1}}} ⟨t_{j+1}⟩.

Finally, for some number i one has H = H_{k_{i+1}}.

The canonical set of generators of H_{0} = G is {d_{1}, …, d_{N}}: the canonical set of generators of H_{j+1} is defined inductively as the union of the canonical set of generators of H_{j} and t_{j+1}.

The group H_{k_{i+1}} is called the group at level i, corresponding to the sequence u_{1}, …, u_{k_{i+1}}. The group H_{i} will be called the group of rank i. We also order the set of t_{j}’s: t_{k} < t_{l} if k < l.

Let F be the free group with the same set of generators as G and F_{k_{j}+p} = F ∗K_{k_{j}+p}, where j ≤ i and K_{k_{j}+p} is the free group with the generators t_{1}, …, t_{k_{j}+p}. Let π be the natural homomorphism of F_{k_{i}+p} onto H_{k_{i}+p}. If v ∈ F_{j}, then by ṽ we denote π(v) ∈ H_{j}.

2. Diagrams

Recall that a map is a finite, planar, connected 2-complex.

By a diagram Δ over a presentation ⟨a_{1}, …, a_{m}|R_{1}, …, R_{n}⟩, where the words R_{i} are cyclically reduced, we mean a map with a function ϕ which assigns to each edge of the map one of the letters a_{k}^{±1}, 1 ≤ k ≤ m, such that ϕ(e^{−1}) = (ϕ(e))^{−1} and if p = e_{1} … e_{d} is the contour of some cell Φ of Δ, then ϕ(p) = ϕ(e_{1}) … ϕ(e_{d}) in the free group F (a_{1}, …, a_{m}) is a cyclic shift of one of the defining words R_{i}^{±1}. In general the word ϕ(p) is called the label of the path p. The label of a diagram Δ (whose contour is always taken with a counterclockwise orientation) is defined analogously.

Van Kampen’s Lemma states that a word W represents the identity of the group G if and only if there is a simply connected (or Van Kampen, or disk) diagram Δ over G such that the boundary label of Δ is W.

Suppose we have a diagram over H_{j}. A t_{j}-strip is a subdiagram with the boundary label t_{j}^{s_{j}n}u_{j}^{−n} (see Figure 1(a)), consisting of cells with the boundary t_{j}^{s_{j}}u_{j}^{−1} (see Figure 1(b)). Two t_{j}-strips can be glued together to form a paired t_{j}-strip (see Figure 1(c)). More than two t_{j}-strips can be glued together to form a t_{j}-star (see Figure 1(d)).

Every minimal (with minimal number of t_{j}-cells) diagram over H_{j} consists of paired t_{j}-strips, t_{j}-stars, t_{j}-strips on the boundary and H_{j−1}-subdiagrams between them (annular paired t_{j}-strips can be assumed not to occur). Suppose we have a H_{k_{i}}-diagram. Notice that for i ≤ j, l ≤ k_{i}, t_{j}-stars, t_{l}-stars, and paired strips cannot meet as in Figure 1(e), because u_{i}, …, u_{k_{i}} do not contain t_{i}, …, t_{k_{i}}.

For every word w which represents the identity element in H_{k_{i}} there is a diagram over H_{k_{i}} with the boundary label w that has the form shown in Figure 1(f). 1f. It consists of glued t_{j}-strips, and t_{j}-strips on the boundary for j ∈ {i, …, k_{i}}, and H_{i−1}-subdiagrams between them.

3. Some properties of the Cayley graph of H

A generating set J of H = H_{k_{i+1}} consists of d_{1}, …, d_{N} and the added roots t_{1}, …, t_{k_{i+1}}. Recall that the vertices of the Cayley graph Γ(H) = Γ(H, J) are elements of H; and two vertices g, h, are connected by an edge e = (g, d), with label ϕ(e) = d ∈ J, if h = gd.

Definition 4. Let u be a cyclically reduced word in H_{i}. A word X is called a u-periodic word if it is a subword of some power u^{k}.

Lemma 1. Let p, s ∈ H_{i−1}, let u, v ∈ F_{i} be words representing the reduced forms of elements ũ, ṽ ∈ {u_{k_{i}+1}, …, u_{k_{i+1}}}, let X, Y be u- and v-periodic words respectively, and let sX̃p = Ỹ .

If ũ ≠ ṽ, then |X̃|_{H_{i}}, |Ỹ |_{H_{i}} < |ũ|_{H_{i}} + |ṽ|_{H_{i}} + 2.

If ũ = ṽ and X, Y begin and end with t_{i} belonging to distinct ⟨t_{i}⟩-syllables of u, s ≠ 1, then |X̃|_{H_{i}}, |Ỹ |_{H_{i}} ≤ |ũ|_{H_{i}}.

If ũ = ṽ, X, Y begin and end with t_{i} belonging to the same ⟨t_{i}⟩-syllables of u, s ≠ 1, then s = u_{i}^{β}, p = u_{i}^{γ} in H_{i} and the canonical image of t_{i}^{βs_{i}}Xt_{i}^{γs_{i}} equals the canonical image of Y in H_{i−1} ∗ ⟨t_{i}⟩.

Proof. We will prove the first assertion of the lemma. Suppose |ṽ|_{H_{i}} ≥ |ũ|_{H_{i}}. Taking a cyclic permutation of u instead of u and a cyclic permutation of v instead of v, we can suppose that X starts with u, Y starts with v, ũ = a_{0}t_{i}^{β_{1}}a_{1} … t_{i}^{β_{n}}a_{n}, 0 < β_{k} < s_{i} for all k, and ṽ = s(a_{0}t_{i}^{β_{1}}a_{1} … t_{i}^{β_{n}}a_{n})^{c}a_{0} … t_{i}β̄_{m}b.

Suppose that |X̃|_{H_{i}} ≥ |ũ|_{H_{i}} +|ṽ|_{H_{i}} +2. The case β̄_{m} < β_{m} is impossible, because it implies β_{1} = β_{m} = β_{m} − β̄_{m}. We have

\begin{aligned}& bsa_{0}t_{i}^{β_{1}}a_{1} … t_{i}^{β_{n}}a_{n}a_{0}t_{i}^{β_{1}}a_{1}t_{i}^{β_{2}} … \\ (3) \end{aligned} ; = a_{m}t_{i}^{β_{m+1}}a_{m+1} … t_{i}^{β_{n}}a_{n}a_{0}t_{i}^{β_{1}}a_{1} … a_{m+1}t_{i}^{β_{m+2}} ….

Now instead of a_{r}, r < n, we write ā_{r} and instead of a_{0}a_{n} we just write ā_{n}. We have β_{j} = β_{j+m} for any j (indices are taken modulo n). These equations for powers imply a_{0} ≠ 1 or a_{n} ≠ 1. Let d = (n, m); then this implies that β_{j} = β_{j+d} (indices are taken

952 O. KHARLAMPOVICH AND A. MYASNIKOV

Figure 1 modulo n). We also have from equation (3) bsa_{0} = a_{m}u_{i}^{α_{0}}, u_{i}^{α_{j−1}} ā_{j} = ā_{m+j}u_{i}^{α_{j}}, j = 1, …, n (the subscripts of the ā’s are taken modulo n). Then α_{n} = α_{0}, because u_{i}^{α_{0}} ā_{1} = ā_{m+1}u_{i}^{α_{1}} and u_{i}^{α_{n}} ā_{1} = ā_{m+1}u_{i}^{α_{n+1}} and the subgroup ⟨u_{i}⟩ is malnormal. Hence

u_{i}^{α_{0}}a_{1} … t_{i}^{β_{n}}a_{n}a_{0}t_{i}^{β_{1}}u_{i}^{−α_{0}} = a_{m+1} … t_{i}^{β_{n}}a_{n}a_{0}t_{i}^{β_{1}}a_{1} … a_{m}t_{i}^{β_{m+1}}.

We have for some β and γ, u_{i}^{β}ā_{d} = ā_{n}u_{i}^{γ}. We also have ∑_{k} α_{j+dk} = 0. And ũ is the (n/d)-th power of the element a_{0}t_{i}^{β_{1}} … t_{i}^{β_{d}}u_{i}^{−β}a_{n} = a_{0}t_{i}^{β_{1}} … t_{i}^{β_{d}}a_{d}u_{i}^{−γ}. Then ṽ is also a proper power.

In the case m = 0, |ṽ|_{H_{i}} > |ũ|_{H_{i}}, we have ṽ = s(a_{0}t_{i}^{β_{1}}a_{1} … t_{i}^{β_{n}}a_{n})^{c}b and

bsa_{0}t_{i}^{β_{1}}a_{1} … t_{i}^{β_{n}}a_{n}a_{0}t_{i}^{β_{1}}a_{1}t_{i}^{β_{2}} … = a_{0}t_{i}^{β_{1}}a_{1} … t_{i}^{β_{n}}a_{n}a_{0}t_{i}^{β_{1}}a_{1}t_{i}^{β_{2}} …. (4)

Then bsa_{0} = a_{0}u_{i}^{α_{0}} and u_{i}^{α_{j−1}} ā_{j} = ā_{j}u_{i}^{α_{j}}. This implies that α_{0} = 0 and b = s^{−1}, and ṽ is conjugated to a power of ũ.

In the case |ṽ|_{H_{i}} = |ũ|_{H_{i}}, we have ṽ = sa_{0}t_{i}^{β_{1}}a_{1} … t_{i}^{β_{n}}a_{n}b and

bsa_{0}t_{i}^{β_{1}}a_{1} … t_{i}^{β_{n}}a_{n}bsa_{0}t_{i}^{β_{1}}a_{1}t_{i}^{β_{2}} … = a_{0}t_{i}^{β_{1}}a_{1} … t_{i}^{β_{n}}a_{n}a_{0}t_{i}^{β_{1}}a_{1}t_{i}^{β_{2}} …,

and again b = s^{−1} and ũ and ṽ are conjugated.

The second and third assertions of the lemma can be proved similarly.

Corollary 1. Let p, s ∈ H_{i−1} and ũ, ṽ ∈ {u_{k_{i}+1}, …, u_{k_{i+1}}}, ũ ≠ ṽ, |ṽ|_{H_{i}} ≥ |ũ|_{H_{i}}. Let X, Y be u- and v-periodic words respectively and sXp = Y. Then |X̃|_{H_{i}}, |Ỹ |_{H_{i}} < 3|ṽ|_{H_{i}}.

This follows directly from the lemma in the case |ṽ|_{H_{i}} > 1. If |ṽ|_{H_{i}} = |ũ|_{H_{i}} = 1, then taking cyclic permutations of u, v instead of u and v, we have ũ = a_{0}t^{β}a_{1}, ṽ = sa_{0}t^{β}b_{1}. If |X̃|_{H_{i}} = |Ỹ_{H_{i}}| ≥ 3, then

sa_{0}t_{i}^{β}a_{1}a_{0}t_{i}^{β}a_{1}a_{0}t_{i}^{β} … = sa_{0}t_{i}^{β}b_{1}sa_{0}t_{i}^{β}b_{1}sa_{0}t_{i}^{β} ….

Hence a_{1}a_{0} = b_{1}sa_{0}u_{i}^{α_{0}}, u_{i}^{α_{0}}a_{1}a_{0} = b_{1}sa_{0}u_{i}^{α_{1}} for some α_{0}, α_{1} ∈ Z. Then α_{0} = α_{1} = 0, a_{1}a_{0} = b_{1}sa_{0} and ũ = ṽ, a contradiction.

Definition 5. An element in H_{i+r} is said to be written in reduced form in rank i if it belongs to H_{i} and is in reduced form as an element in the amalgamated product H_{i} = H_{i−1} ∗_{u_{i}=t_{i}^{s_{i}}} ⟨t_{i}⟩. If r = 0, then the element is said to be in reduced form in all ranks ≥ i if it is in reduced form in rank i. An element h in H_{i+r} is defined by induction on r to be written in reduced form in all ranks ≥ i if it is written in reduced form in the amalgamated product H_{i+r} = H_{i+r−1} ∗_{u_{i+r}=t_{i+r}^{s_{i+r}}} ⟨t_{i+r}⟩, h = b_{0}t_{i+r}^{α_{1}}b_{1}t_{i+r}^{α_{2}} … b_{n}, where the b_{1}, …, b_{n} ∈ H_{i+r−1} are in reduced form in all ranks ≥ i.

Definition 6. A ⟨t_{i}⟩-syllable of a path is a subpath labelled by some ⟨t_{i}⟩-syllable of the label of the path.

Definition 7. A u-path is a path labelled by a u-periodic word.

Definition 8. Let ũ, ṽ ∈ {u_{k_{i}+1}, …, u_{k_{i+1}}}, |ũ|_{H_{i}} ≥ |ṽ|_{H_{i}}. Consider in Γ(H) two paths: a u-path r_{1} and a v-path r_{2}, where r_{1} connects the sequence of vertices

…, gũ^{−2}, gũ^{−1}, g, gũ, gũ^{2}, …,

r_{2} connects the sequence of vertices

…, ghṽ^{−2}, ghṽ^{−1}, gh, ghṽ, ghṽ^{2}, …,

the label of every subpath of r_{1} or r_{2} is a reduced word in H_{i}, and h ∈ H_{k_{i}}. Then a path q that connects r_{1} with r_{2} is called a minimal path if

1. ϕ(q) represents an element in reduced form in all ranks greater than or equal to i,

2. the number of ⟨t_{i}⟩-syllables in ϕ(q) is minimal for all paths connecting r_{1} with r_{2}.

Lemma 2. Let r_{1} and r_{2} be the paths from Definition 8, h ∈ H_{k_{i}}. Then there are two possibilities:

1. h contains some t_{j} that is greater than or equal to t_{i}. Then there are a uniquely determined number s_{1} and consecutive ⟨t_{i}⟩-syllables z_{1}, z_{2} and z_{3} of the subpath of r_{1}, with the label u, between gũ^{s_{1}} and gũ^{s_{1}+2}, such that the initial points of all the minimal paths connecting r_{1} with r_{2} belong to the subpath of r_{1} joining z_{1} with z_{3}. (And, similarly, there are a uniquely determined number s_{2} and consequtive ⟨t_{i}⟩-syllables z_{4}, z_{5} and z_{6} of the subpath of r_{2}, with the label v, between ghṽ^{s_{2}} and ghṽ^{s_{2}+2}, such that the terminal points of all the minimal paths connecting r_{1} with r_{2} belong to the subpath of r_{2} joining z_{4} with z_{6}.)

2. h does not contain any t_{j} that is greater than or equal to t_{i}. Then either the same conclusion is true as in the previous case, or, for any two paths q and q′ connecting r_{1} with r_{2} and such that |q|_{H_{i}} = |q′|_{H_{i}} = 0, we have the equality πϕ(q^{−1})X̃πϕ(q′) = Ỹ, where X is a u- and Y is a v-periodic word corresponding to the subpaths of r_{1} and r_{2} connecting the initial and terminal points of q and q′ respectively . Then |X̃|_{H_{i}}, |Ỹ |_{H_{i}} ≤ |ũ|_{H_{i}} + |ṽ|_{H_{i}} + 1.

The numbers s_{1}, s_{2} above do not depend on g.

Proof. The assertion of the lemma in the second case follows directly from Lemma 1.

To prove the assertion in the first case, suppose that q and q̄ are two minimal paths connecting r_{1} with r_{2}. Let p_{1}, p̄_{1} be their initial points and p_{2}, p̄_{2} their terminal points. We have to prove that the each of the paths p_{1}p̄_{1} and p_{2}p̄_{2} contains at most one ⟨t_{i}⟩-syllable.

Consider a minimal diagram Θ, with contour consisting of the subpath of r_{1} between the points p_{1} and p̄_{1}, the path q̄, the subpath of r_{2}^{−1} between p̄_{2} and p_{2}, and the path q^{−1}.

Every subpath of r_{1} or r_{2} is reduced (i.e. has a reduced label), and the elements q and q̄ are reduced; hence there cannot be t_{j}-arcs and t_{j}-stars with two ends on the same side of Θ, as in Figure 2(a), for j ≥ i. The diagram Θ has the form shown in Figure 2(b), where the strips are paired t_{j}-strips for j ≥ i , the 3-ended stars are t_{i}-stars and the regions between the strips and stars must be H_{i−1} subdiagrams. Hence the paths p_{1}p̄_{1} and p_{2}p̄_{2} cannot contain more than one t_{i}-syllable each.

The lemma is proven.

The lemma immediately implies the following result.

Corollary 2. Let ũ = u_{k_{i}+p}, h ∈ H_{k_{i}+p−1}. Consider in Γ(H) two u-paths r_{1} and r_{2}, where r_{1} connects the sequence of vertices

…, gũ^{−2}, gũ^{−1}, g, gũ, gũ^{2}, …,

r_{2} connects the sequence of vertices

…, ghũ^{−2}, ghũ^{−1}, gh, ghũ, ghũ^{2}, …,

Figure 2

and every subpath of r_{1} or r_{2} is labelled by a reduced word in H_{i}.

Then there are uniquely determined numbers s_{1}, s_{2}, such that for every path q̄ connecting some gũ^{s_{3}} with ghũ^{s_{4}}

1. ϕ(q̄) = ϕ(q_{1})ϕ(q)ϕ(q_{2}), where q_{1} is a u-path connecting gũ^{s_{3}} with some vertex p_{1} on the subpath of r_{1} joining gũ^{s_{1}} and gũ^{s_{1}+3} (see Figure 3), q is a path connecting p_{1} with a vertex p_{2} on the subpath of r_{2} joining ghũ^{s_{2}} and ghũ^{s_{2}+3}, q_{2} is a u-path connecting p_{2} with ghũ^{s_{4}},

2. q is reduced in all ranks j ≥ i, and

3. the sum of t_{i}-lengths of pieces of q between ⟨t_{j}⟩-syllables, for j > i, is minimal

for all paths q with the above property. These numbers s_{1}, s_{2} and the labels of the paths q_{1}, q, q_{2} depend only on h and u, and not on g.

There is a uniquely determined number s_{1} such that, for every path q̄ connecting some vertex g with ghu^{s_{3}},

1. ϕ(q̄) = ϕ(q_{3})ϕ(q_{4}), where q_{4} connects g with some vertex p_{1} on the subpath of r_{2} joining gũ^{s_{1}} and gũ^{s_{1}+3}, q_{4} is a u-path connecting p_{1} with ghũ^{s_{3}},

2. q_{3} is reduced in all ranks j ≥ i, and

3. the sum of t_{i}-lengths of pieces of q_{3}, between ⟨t_{j}⟩-syllables for j > i, is minimal

for all paths q_{3} with the above property. This number s_{1} and the labels of the paths q_{3}, q_{4} do not depend on g.

The label of the path q satisfying the conditions of this corollary will be called a (u, u)-pseudoconnector for h, the label of the path q_{3} will be called a u-pseudocon-nector for h. Notice that all elements of the form u^{k}hu^{s} have the same (u, u)- pseudoconnectors and all the elements of the form hu^{s} have the same u-pseudoconnectors.

Definition 9. In this definition we keep the notation of the corollary. A connecting zone for the element h is defined as follows. Consider a path q labelled by a (u, u)- pseudoconnector for h. Consider the two phase vertices b_{1} and b_{2} closest to p_{2} on either side of p_{2} on the u-path r_{2}, with the property that the path from p_{2} to b_{j} has t_{i}-length at least one. (If p_{2} is not a phase vertex, then b_{1} = ghũ^{s_{2}}, b_{2} = ghũ^{s_{2}+k}, where k is either 1 or 2; if p_{2} is a phase vertex, then b_{1} = ghũ^{s_{2}−1} and b_{2} = ghũ^{s_{2}+1}.)

Figure 3

The connecting zone for h with respect to g is the union of all phase vertices between such b_{1} and b_{2} for all (u, u)-pseudoconnectors (u-pseudoconnectors) for h; see Figure 3(a). (Sometimes the connecting zone can consist of five phase vertices; they are shown in Figure 3(b).)

If the vertex ghũ^{s} belongs to the connecting zone for h with respect to g, then the vertex g_{1}hũ^{s} belongs to the connecting zone for h with respect to g_{1}. If it is clear from the context what the initial vertex g of the path labelled by h is (or if it does not matter), then we denote by (h)_{1} and (h)_{2} the initial and terminal vertices of the connecting zone for h with respect to g, and will talk about the connecting zone for h without mentioning the initial point g.

4. Construction of canonical representatives

We will define a section β : H_{k_{i}+p} → F_{k_{i}+p} (a mapping of sets such that π ∘ β = id). For X ∈ H_{k_{i}+p} we call β(X) the canonical representative of X.

Figure 4

The canonical representative of an element in G is just some fixed geodesic word representing this element. (If G is a free group, then it is the reduced word representing this element.) Suppose we have already constructed representatives for all elements in H_{k_{i}+p−1}. Now take an element X in H_{k_{i}+p} that contains t_{k_{i}+p} and construct a representative of this element in F_{k_{i}+p}. The representative of X will be a word (or a label of a path in Γ(H_{k_{i}+p})) corresponding to a reduced form of X in rank k_{i} + p. For each syllable b of this element between two consecutive ⟨t_{k_{i}+p}⟩-syllables we will denote the canonical representative of the label of a path connecting the vertices (b^{−1})_{2} and (b)_{2} by b̄ (see Figure 4). Suppose X = b_{0}t^{α_{1}}b_{1}t^{α_{2}} … b_{n}. Take some path labelled by X in Γ(H_{k_{i}+p}). The path corresponding to b̄_{i} connects the points (b_{i}^{−1})_{2} and (b_{i})_{2}. Then the points (b_{i−1})_{2} and (b_{i}^{−1})_{2} can be connected by a path with the label t_{i_{k}+p}^{γ_{i}}. Then the canonical representative for X is b̄_{0}t_{i_{k}+p}^{γ_{1}}b̄_{1}t_{i_{k}+p}^{γ_{2}} … b̄_{n}.

Definition 10. Let ũ = u_{k_{i}+p}, h ∈ H_{k_{i}+p−1}, h an element from Corollary 2. The (u, u)-connector (resp. a u-connector) for the element h is the canonical representative of the label of a path, reduced in ranks i, …, k_{i} +p−1, connecting the vertex (h^{−1})_{2} (resp. g) with (h)_{2}.

Let ũ = u_{j}, ṽ = u_{k}, j < k, j, k ∈ {i + 1, …, k_{i+1}}, and suppose that q connects some vertex gũ^{s_{1}} with ghṽ^{s_{2}}, h ∈ H_{i}. Consider the point (h)_{2} (the terminal point of the path labelled by the v-connector for h). Let the path p connect (h)_{2} with gũ^{s_{1}}. Consider the point (ϕ(p)^{−1})_{2} (the terminal point of the path labelled by the u-connector for ϕ(p)^{−1}). The (u, v)-connector for h is the canonical representative of the label of a path in H_{i} connecting (ϕ(p)^{−1})_{2} with (h)_{2}.

It is important that the elements u_{j} that do not belong to G be chosen in such a way that β(u_{k_{i}+p}^{n}) = (β(u_{k_{i}+p}))^{n}. For this we first take connectors for u_{k_{i}+p}^{n} and then, if necessary, replace u_{k_{i}+p} by its cyclic permutation starting with t_{i}. (If G is a free group then this equality can be made true for all u_{i}’s.) Below, all the elements u_{j} will always be represented by the words β(u_{j}), and we will write u_{j} instead of β(u_{j}). It will be clear from the context when u_{i} means a word and when it means the element represented by this word.

In Figure 4 we considered the following example. Denote t_{k_{i}+p} by t and u_{k_{i}+p} by u. Let u = t^{3}, X = b_{0}t^{11}b_{1}t^{−7}b_{2} and u = u_{1}u_{2} = u_{3}u_{4} = u_{5}u_{6} = u_{7}u_{8} in H_{i}. Let b_{0} = c_{0}u_{1}^{−1}u^{−2}, where c_{0} is a pseudoconnector for b_{0}, b_{1} = uu_{3}c_{1}u_{6}u, where c_{1} is a pseudoconnector for b_{1}, b_{2} = u^{−1}u_{8}^{−1}c_{2}, where c_{2} is a pseudoconnector for b_{2}. Let b̄_{k} (k = 0, 1, 2) be a connector corresponding to b_{k}. In this example, β(X) = β(b̄_{0})t^{8}β(b̄_{1})t^{−10}β(b̄_{2}).

5. Middles

Let X = {X_{1}, …, X_{L}} be a solution of system (1) in the group G^{Q_{π}}. Suppose this solution contains the least possible number of roots. Then for some i this solution belongs to the group H_{k_{i+1}} = H. Let τ_{i}(X) be the sum of the numbers of t_{i}-syllables in all X_{1}, …, X_{L}. Denote τ(X) = (τ_{1}(X), …, τ_{k_{i+1}}(X)). Let X < Y if τ(X) < τ(Y). Let X = {X_{1}, …, X_{L}} be a minimal solution with respect to this order.

By an equational triangle (resp. equational diagram) we mean a triangular equation XY Z = 1 (resp. an equation X_{1} … X_{n} = 1) together with a solution A, B, C (resp. A_{1}, …, A_{n}) and a diagram over H having β(A)β(B)β(C) (resp. β(A_{1}) … β(A_{n})) as its boundary label. A system of equational diagrams is a system of equations together with the system of diagrams, such that the solution associated to each equational diagram must be a solution of the whole system.

For the solution X_{1}, …, X_{L} of system (1) we will construct another solution X′_{1}, …, X′_{L} and a system of equations over the group G ∗ K_{k_{i+1}} (if G = F, then G ∗ K_{k_{i+1}} = F_{k_{i+1}}), such that β(X′_{1}), …, β(X′_{L}) will be a part of a solution of this new system, and every solution of the new system will give a solution of system (1).

Denote u_{k_{i}+p} by u and t_{k_{i}+p} by t.

Figure 6

Consider an equational triangle in H_{k_{i}+p} with at least one side label containing t (hence at least two side labels containing t). It is represented by a diagram in the form shown in Figure 5 (we showed only t_{j}-strips for t_{j} = t).

Lemma 3. Suppose that in H_{k_{i+1}} we have a diagram (see Figure 6) with the boundary label (b_{1}t_{j_{1}}^{r_{j_{1}}} … t_{j_{n}}^{r_{jn}} b_{n}t_{j_{n+1}})t_{j_{n+1}}^{r_{j_{n+1}}} (c_{1}t_{j_{1}}^{p_{j_{1}}} … t_{j_{n}}^{p_{jn}} c_{n}t_{j_{n+1}})^{−1}, where j_{1}, …, j_{n+1} ∈ {k_{i} + 1, …, k_{i+1}}, b_{1}, c_{1} …, b_{n}, c_{n} ∈ H_{k_{i}}. Then β(b_{1}t_{j_{1}}^{r_{j_{1}}} … t_{j_{n}}^{r_{jn}} b_{n}t_{j_{n+1}})t_{j_{n+1}}^{r_{j_{n+1}}} = β(c_{1}t_{j_{1}}^{p_{j_{1}}} … t_{j_{n}}^{p_{jn}} c_{n}t_{j_{n+1}}) in F_{k_{j+1}}.

This assertion follows immediately from the choice of canonical representatives. It follows from Lemma 3 that every equational triangle either does not contain

any cells or takes on one of the forms shown in Figure 7, and hence has a unique maximal nontrivial H_{k_{i}+p−1}-subdiagram.

Definition 11. Consider an equational triangle in Γ(H_{k_{i}+p}) (p ≥ 1) with the boundary label β(X_{1})β(X_{2})β(X_{3}). Suppose X_{1} contains t. Then the maximal nontrivial H_{k_{i}+p−1}-subdiagram of this triangle is called the middle of the triangle. (The subdiagrams ABCDEF (Fig. 7(a)), ABCD (Fig. 7(b)), ABC (Figure 7(c)) are middles.)

A boundary of a middle is canonically subdivided into paths; each of the paths either belongs to the u-side of a t-strip (is a u-path, joining two phase vertices) or is a connector. The u-paths are called pseudoangles of the middle. Every diagram over H_{k_{i}+p} can be embedded into Γ(H_{k_{i}+p}). A pseudoangle is long if the corresponding strippath is nontrivial and the connecting zones for two pseudoconnectors touching this pseudoangle do not intersect, and short if the corresponding strippath is nontrivial and the zones of two pseudoconnectors touching this pseudoangle intersect. A pseudoangle is trivial if the corresponding strippath is trivial. A middle is called triangular if all the pseudoangles are trivial; it is called short if it is not triangular and does not have long pseudoangles; otherwise it is long.

If none of the X_{i}’s contains t, then the middle of the triangle coincides with the triangle itself and is a triangular middle.

As an example, consider the middle ABCDEF in Figure 7(a). The paths AB, CD, EF are pseudoangles of this middle.

Lemma 4. Consider an equational triangle over the group H_{k_{i}+p}, p ≥ 1, and the middle of this triangle. Let AB, CD and EF be the pseudoangles of the middle (see Figure 7 (a)) and ϕ(F A), ϕ(BC), ϕ(DE) be the connectors. Suppose ϕ(AB) = u_{k_{i}+p}^{n}, n > 0. Then β(ϕ(F A)ϕ(AB)) = ϕ(F A)ϕ(AB). If AB is a long pseudoangle and B_{1} is the left end of the zone for ϕ(CB), then A is the right end of the connecting zone for ϕ(EA), B_{1} is the left end of the connecting zone for ϕ(DB) and

β(ϕ(F A)ϕ(AB_{1})ϕ(B_{1}C)) = ϕ(F A)ϕ(AB_{1})βϕ(B_{1}C),
β(ϕ(EA)ϕ(AB_{1})ϕ(B_{1}C)) = βϕ(EA)ϕ(AB_{1})βϕ(B_{1}C),
β(ϕ(F A)ϕ(AB_{1})ϕ(B_{1}D)) = ϕ(F A)ϕ(AB_{1})βϕ(B_{1}D),
β(ϕ(EA)ϕ(AB_{1})ϕ(B_{1}D)) = βϕ(EA)ϕ(AB_{1})βϕ(B_{1}D).

Proof. Let HGG_{1}H_{1} be the paired t_{j}-strip closest to the point A, and KLL_{1}K_{1} the paired t_{j_{1}}-strip closest to the point B, j, j_{1} > i. If there is no the strip HGG_{1}H_{1}, we just take F = H_{1}, E = G_{1}. If there is no strip KLL_{1}K_{1}, we take K = D, L = C. We show this case in Figure 8(a). There is no t_{k}-strip , k ≥ i, connecting the paths H_{1}A and BL, because if there were, then from the description of representatives it would follow that A = B.

The label of the path F H is the beginning of the canonical representative for ϕ(F B). From the construction of representatives it follows that H_{1}A contains a ⟨t_{i}⟩-syllable; let P P_{1} be the ⟨t_{i}⟩-syllable closest to the vertex A. The path AB begins with a ⟨t_{i}⟩-syllable. Then P_{1}A is the last u_{i}-connector in u_{k_{i}+p}. It follows from the choice of u_{k_{i}+p} that P_{1}A connects these ⟨t_{i}⟩-syllables and connects the P P_{1}-syllable with the vertex A at the same time. So ϕ(F A)ϕ(AB) is the canonical representative of itself. Hence β(ϕ(F A)ϕ(AB)) = ϕ(F A)ϕ(AB).

Because the pseudoangle AB is long, there should be at least two paired t_{i}-strips that begin on AB and end on ED, as in Figure 8(b). This implies that in the case when D ≠ C, the left end of the connecting zone for ϕ(DB) is B_{1}, and in the case when F ≠ E, the right end of the connecting zone for ϕ(EA) is A.

The four equalities follow by symmetry considerations from the first one. The lemma is proved.

Figure 8

Lemma 5. Consider the diagram over the group H_{k_{i}+p}, p ≥ 1, shown in Fig. 7(a) or 7(b). Suppose the middle of this diagram is not triangular.

1. If all three connectors contain some t_{j}’s greater than t_{i}, then two pseudoangles are trivial.

2. If only two connectors contain some t_{j} greater than t_{i}, then one pseudoangle is trivial and another one is either trivial or short.

3. If none of the connectors contain a t_{j} greater than t_{i}, then two pseudoangles are either trivial or short.

Proof. Consider the middle shown in Fig. 7(a). Suppose there is a paired t_{j}-strip HGG_{1}H_{1} or a t_{j}-star HGG_{1}I_{1}IH_{1} for j > i, as shown in Fig. 8(c). Let this strip be the strip closest to F E. If j > k_{i} then by Lemma 3 E = F and this pseudoangle is trivial. If j ≤ k_{i}, then the path HG does not contain any t_{k} for k ≥ i. Let E_{1} and F_{1} be the closest terminal points of (u_{k_{i}+p}, u_{k_{i}+p})-pseudoconnectors for ϕ(DE) and ϕ(AF) respectively. There are no paired t_{i}-arcs or t_{i}-stars as shown by broken lines in Fig. 8(c). Hence the path F_{1}E_{1} does not contain any t_{i}-syllable; hence F = E. If HGG_{1}H_{1} is a paired t_{i}-strip, then again the path HG does not contain t_{i}, and this implies F = E. If HH_{1}G_{1}GJ_{1}J is a t_{i}-star, then F_{1} and E_{1} must coincide, because AE_{1} is also a (u_{k_{i}+p}, u_{k_{i}+p})-pseudoconnector for AF. Now if all the three connectors contain some t_{j}’s greater than t_{i}, then either there are at least two paired strips for t_{j} and for t_{j_{1}}, as shown in Fig. 8(a), or there is a t_{j}-star. Then F = E, D = C. So at least two pseudoangles are trivial.

Figure 9

If only two connectors contain some t_{j} greater than t_{i}, then there is a paired t_{j}-strip HGG_{1}H_{1} closest to the vertex A as in Fig. 8(c); hence F = E and this pseudoangle is trivial. Suppose that the pseudoangle CD is nontrivial; the proof that it is short is similar to the proof of the third assertion, given below.

If none of the connectors contains a t_{j} greater that t_{i}, then there are no paired t_{j}-strips in the middle, and the t_{i}-strips are situated as in Fig. 9(a), 9(b), 9(c), 9(d), 9(e). In Fig. 9(a) the pseudoangles F E and DC are trivial, in Fig. 9(b) the pseudoangles F E, AB and DC are short, in Fig. 9(c) the pseudoangle F E is short and DC is trivial, in Fig.9(d) the pseudoangle F E is short and CD is trivial. In the case shown in Fig. 9(e) two pseudoangles are trivial and one is short. Indeed, A_{1} and A_{2} are both the beginnings of some (u_{k_{i}+p}, u_{k_{i}+p})-pseudoconnectors for BC, while D_{1} and C_{1} are both the beginnings of some (u_{k_{i}+p}, u_{k_{i}+p})-pseudoconnectors for CB.

The lemma is proved.

6. Reduction to the free group

We start with a system S of M equational triangles in rank k_{i+1}. We will construct a system of equations in G ∗ K_{k_{i+1}} such that the solution of S is a part of a solution of this system.

Consider in S an equational triangle with the boundary X_{1}X_{2}X_{3} corresponding to Figure 10. Recall that β(X_{i}) = X_{i} in F_{k_{i+1}}. Then

X_{1} = P_{1}Y_{1}(t^{s_{k_{i}+1}m_{1}+r_{1}})P_{2},
X_{2} = P_{2}^{−1}t^{s_{k_{i}+1}m_{2}+r_{2}}Y_{2}^{−1}P_{3}^{−1},
X_{3} = P_{3}Y_{3}P_{1}^{−1},
Y_{3} = Y_{4}u^{−(m_{1}+m_{2})}Y_{1}^{−1}

in the group F_{k_{i+1}}, and we have to add the conditions that u ∈ F_{i} , r_{1} + r_{2} = s_{i}, as well as the equational triangle over H_{k_{i+1}−1} with the boundary Y_{4}uY_{2}^{−1}.

Definition 12. A free equational diagram (resp. triangle) is an equational diagram (resp. triangle) with no cells.

The equational triangle with the boundary Y_{4}uY_{2}^{−1} over H_{k_{i+1}−1} is “non-free” (this means that the corresponding diagram might contain cells). We will say that the first three free equational diagrams are free equational diagrams (or free equations) of the first type and the fourth free equational diagram is a free equational diagram (or free equation) of the second type. We also can rewrite free equational triangles in F_{k_{i+1}} in the form

X_{1} = P_{1}Y_{1}T^{m_{1}}T_{1}P_{2},
X_{2} = P_{2}^{−1}T^{m_{2}}T_{2}(Y_{2})^{−1}P_{3}^{−1},
X_{3} = P_{3}Y_{3}P_{1}^{−1},
Y_{3} = Y_{4}u^{−(m_{1}+m_{2})}Y_{1}^{−1}

in the group F_{k_{i+1}}, and add equations

[T, t] = [T_{1}, t] = 1, [T_{2}, t] = 1, T_{1}T_{2} = T_{1}.

We also have to add the condition that u ∈ F_{i} .

Notice that the new “variables” in the non-free equational triangles are u, the connector Y_{2}, participating in the middle, and the canonical representative of the label of the path connecting C with the left end of the zone for ϕ(CB) (βϕ(Y_{2}u^{−1})). Notice also that the freeness of the equational triangles of the first type implies that some of the Y ’s are the same. Below we will often use the fact that they will still have a solution in X’s and P ’s if we replace some of the Y ’s by some other words.

We can rewrite every equational triangle in a similar way. We will obtain a system of free equations over F_{k_{i+1}} and a system of triangular equations over H_{k_{i+1}−1}. Denote the union of these systems by S_{1}. At the next step we repeat this process for the non-free equations over H_{k_{i+1}−1} with unknowns Y_{i}. Finally, after k_{i+1} steps we will obtain a system S_{k_{i+1}} over a group G ∗ K_{k_{i+1}}, which, in the case when G is free, is just a free group F_{k_{i+1}}. Every solution of S_{k_{i+1}} gives a solution of the system (1).

Definition 13. For a given system of equational triangles in H, the union of all non-free equational triangles, in all ranks from 0 to k_{i+1} will be called a tower of non-free equational triangles generated by this system. The same non-free equational triangle can occur in different ranks; in this case we consider all these occurrences as one triangle of the tower.

Lemma 6. If a solution of a system of triangular equations is minimal, then in the tower of non-free equational triangles generated by this system there is at least one nontriangular middle for the non-free triangles in each rank .

Proof. Suppose that in rank j all the middles are triangular. Let β(X_{1}), …, β(X_{L}) be the canonical representatives of the elements of the solution. Then they are part of a solution of the system S_{k_{i+1}}. The constant t_{i} does not participate in the equations of the system S_{k_{i+1}}. Then we can cut out ⟨t_{j}⟩-syllables from all the elements in the solution of S_{k_{i+1}} and again have a solution of S_{k_{i+1}} . Every solution of S_{k_{i+1}} produces a solution of the system (1). This contradicts the minimality of the original solution.

Lemma 7. Every middle in rank k_{i} + p can be split into several free equational triangles and at most one non-free equational triangle in the previous rank.

Proof. Every triangular middle will be itself a triangular equation in the previous rank.

Consider the equational triangle in Fig. 7(a). Let ABCDEF be the middle of this triangle. Suppose the pseudoangle AB is nontrivial and AB is a positive power

Figure 11

of u. Let B_{1} the left end of the zone for ϕ(CB), and B_{2} be the left end of the zone for ϕ(DB). Consider the following possibilities. They all are shown in Fig. 11 with the corresponding letter; in the cases (a)–(d) the pseudoangle AB is long. Non-free equational triangles are marked by a star. All the assertions below follow directly from Lemma 4.

(a) Two other pseudoangles are trivial. We have E = F, C = D. Then there is a free equational diagram, with the boundary ϕ(F A)ϕ(AB_{1})βϕ(B_{1}C)ϕ(CF), and an equational triangle with the boundary ϕ(CB)ϕ(BB_{1})βϕ(B_{1}C).

(b) The pseudoangle EF is trivial, ϕ(CD) is a negative power of u. There is one non-free equational triangle, with the boundary ϕ(CB)ϕ(BB_{1})βϕ(B_{1}C), and two free equational diagrams, with the boundaries ϕ(CD)ϕ(DF)ϕ(F D) and ϕ(F A)ϕ(AB_{1})βϕ(B_{1}C).

(c) The pseudoangle CD is trivial, ϕ(F E) is a negative power of u. There is one non-free equational triangle, with the boundary ϕ(CB)ϕ(BB_{1})βϕ(B_{1}C), and two free equational diagrams with the boundaries, ϕ(CE)ϕ(EF)ϕ(F C) and ϕ(F A)ϕ(AB_{1})βϕ(B_{1}C).

(d) The pseudoangles CD and F E are both nontrivial, CD and F E are negative powers of u. There is one non-free equational triangle, with the boundary ϕ(CB)ϕ(BB_{1})βϕ(B_{1}C), and two free equational diagrams, with the boundaries ϕ(CD)ϕ(DE)ϕ(EF)ϕ(F C) and ϕ(F A)ϕ(AB_{1})βϕ(B_{1}C).

In the case where there are no long pseudoangles, the middle is short, and, up to the relabelling of the vertices, there are two different possibilities:

(e) EF and DC are positive powers of u. There is one non-free equational triangle, with the boundary ϕ(CB)βϕ(BF)βϕ(F C), and two free equational diagrams, with the boundaries ϕ(EF)ϕ(F C)ϕ(CD)ϕ(DE) and βϕ(F B)ϕ(BA)ϕ(AF).

(f) EF and CD are positive powers of u. There is one non-free equational triangle, with the boundary βϕ(F B)βϕ(BD)βϕ(DF), and three free equational diagrams, with the boundaries ϕ(CD)βϕ(DB)ϕ(BC), ϕ(EF)βϕ(F D)ϕ(DE) and ϕ(F A)ϕ(AB)βϕ(BF).

The lemma is proved.

Lemma 8. Consider n non-free equational triangles in rank k_{i} + p. Suppose the solution is minimal. Then we can rewrite the system as a system of free equational triangles and at most n non-free equational triangles in ranks less than k_{i} + p. The variables in the new non-free equational triangles are of the following types: the connectors in the middles in rank k_{i} + p, and variables Z̄_{q} such that there is a free equation, either of the form Z̄_{q} = u_{k_{i}+p}^{q} or of the form Z̄_{q} = u^{q_{1}}T u^{q_{2}}, where T is the label of some connector.

Proof. Every nontriangular middle can be split by the previous lemma into several free equational triangles and at most one non-free equational triangle. The form of the new variables is obtained in the proof of the previous lemma.

Lemma 9. In the minimal solution, the difference k_{j+1} − j, and hence the number of u’s containing some fixed t_{j} as the greatest root (which is equal to the difference k_{j+1} − k_{j}), cannot be more then 3M, where M is the number of equations in the original system.

Proof. We will show that, when we consider non-free equational triangles in ranks k_{j+1}, k_{j+1}−1, …, we have to come to rank j after not more than 3M steps. Indeed, consider one non-free equational triangle in rank k_{j+1}. In Fig. 12 we show three paired t_{p}-strips, for p > i, closest to the center of this triangle. Let them be t_{p_{1}}, t_{p_{2}} and t_{p_{3}}-strips. Then this triangle will produce non-free triangular equations with nontriangular middles in at most three ranks from k_{j+1} to j + 1. These ranks can be only p_{1}, p_{2} and p_{3}. In each rank we have at least one equational triangle with non-triangular middle. Hence the maximal possible number of ranks between k_{j+1} and j + 1 is 3M. The lemma is proved.

After considering some level j, we have an effectively bounded number of free equations of the second type connecting the variables Z_{1}, …, Z_{m}, formed on this level, and powers of u_{k}’s, where k ∈ {k_{j}, …, k_{j+1} − 1}. These equations have one of the following forms: Z_{j_{1}} = Z_{j_{2}}u_{k}^{q}Z_{j_{3}} or Z_{j} = u_{k}^{l}, Z_{j} = u_{k}^{l}Z_{s}u_{k}^{r}, where l, r ∈ {1, 2, 3, 4}.

7. Shortening of middle-strips

We now want to bound the powers of u_{j}’s in the free equational diagrams. Here j ≥ k_{1}, in the case when G is not a free group, and j ≥ 1 in the case when G is a free group.

We denote u = u_{k_{i+1}}, t = t_{k_{i+1}}.

Definition 14. A middle-t-strip is a t-strip formed by t-cells such that their usides belong to the long pseudoangle of the middle of some non-free equational triangle in rank k_{i+1}.

Notice that if two paths contain t_{i}, and represent the same element in H_{i}, then their canonical representatives are chosen in such a way that the part between the first and the last ⟨t_{i}⟩-syllable is the same word in F_{k_{i+1}}. So we can talk about the subword u in H_{i}. (Recall that we write u instead of β(u).)

Definition 15. A subword u^{k} of the label of a side of an equational triangle is called shrinkable if one of the following conditions is satisfied:

1. There is an occurrence of u in u^{k} which is on the boundary of some t-cell belonging to some middle-t-strip.

2. u^{k} is a subword of some shrinkable subword u^{l} of a side of an equational triangle.

3. Suppose there is a common subpath of two sides of an equational triangle labelled by β(X) and β(Y). Suppose that the label of this common subpath is a shrinkable subword of β(X). Then it is also a shrinkable subword of β(Y).

So, to be precise, the set of all shrinkable subwords of labels β(X) of sides of equational triangles is the smallest class of subwords satisfying the above description.

A similar definition can be given for shrinkable subwords t^{k}.

Suppose we have an equational triangle with the boundary label XY Z. Suppose this triangle contains a middle-t-strip. Then some maximal shrinkable subword u^{k} of some variable, say X, contains a part of the boundary of this middle-t-strip. There are two possibilities. Either some maximal shrinkable subwords t^{k_{i+1}n_{1}} of Y and t^{k_{i+1}n_{2}} of Z both contain a part of the boundary of this middle-t-strip (Fig. 13(a) or the maximal shrinkable subword t^{k_{i+1}n_{1}} of Y contains the t-side of the boundary of this middle-t-strip, and the maximal shrinkable subword t^{k_{i+1}n_{2}} of Z is the label of a common path of Y and Z (going along the other part of the subword t^{k_{i+1}n_{1}} of Y) (Fig. 13(b).

Suppose the triangle XY Z does not contain a middle-t-strip. It might happen that one part of some maximal shrinkable subword u^{k} (resp. t^{ks_{k_{i+1}}} ) of X labels some common path of X and Y and another part labels some common path of X

Figure 13

and Z (see Fig. 13(c), 13(d). In both cases amaximal shrinkable piece of the triangle is the minimal subdiagram having these three maximal shrinkable subwords on its boundary. (In the cases shown in Fig. 13(c), 13(d), these pieces ABCD and ABC do not contain any cells.)

Denote the set of maximal shrinkable pieces by S. The following lemma is obvious.

Lemma 10. Every maximal shrinkable piece has one of the forms shown in Fig. 14 (broken line for t, bold line for u).

Below, we will consider only shrinkable subwords u^{k}, k ≥ 4, and t^{l}, l > 4s_{k_{i+1}}.

Definition 16. The length of the shrinkable subword u^{k} is k − 4, and the length of the shrinkable subword t^{s_{k_{i+1}} j+r}, where 0 < r < s_{k_{i+1}}, is j − 4.

Figure 14

Every maximal shrinkable piece contains three maximal shrinkable subwords. Denote them by a_{kj}, j = 1, 2, 3, and their lengths by ℓ_{i1}, ℓ_{i2}, ℓ_{i3}. For example, a_{k3} = u^{4+ℓ_{k3}}, a_{k1} = t^{s_{k_{i+1}} (4+ℓ_{k1})}, a_{k2} = t^{s_{k_{i+1}} (4+ℓ_{k2})}. Each diagram in S gives one of the equations ℓ_{i1} + ℓ_{i2} + s = ℓ_{i3} , where s ∈ {1, 2, 3, 4, 5}. Denote this system of equations, assigned to S, by L. Add to this system (with less than 3M unknowns) the equalities and inequalities ℓ_{ij} = ℓ_{tp}, ℓ_{ij} > 0, ℓ_{ij} = 0, and the equations that keep the length of the short pseudoangles and maximal shrinkable subwords of nonpositive length.

It is possible to obtain only a finite number (depending on M) of distinct linear systems of this form. Every such system is algorithmically solvable. This follows from the fundamental result of Presburger [10] about the decidability of the elementary theory of the natural numbers with addition. Take one solution for each system. Let L̄ be the maximum of the ℓ_{ij} in these solutions. Then the system L also has a solution bounded by L̄. Let

{ℓ̄_{kj}, i = 1, …, M, j = 1, 2, 3}

be this solution, b_{kj} the pieces corresponding to a_{kj}, but of length ℓ̄_{kj} (for example, if a_{k3} = u^{4+l_{k3}}, then b_{k3} = u^{4+l̄_{k3}}.)

Lemma 11. Replace all the pieces a_{ij} by the analogous pieces b_{ij}. We get another solution of the original system of equations.

Suppose we replaced all a_{ij} by the corresponding b_{ij}. If some a_{ij} participated in several maximal shrinkable pieces, then ℓ_{ij}, and hence ℓ̄_{ij}, satisfy linear equations for all these pieces. In the places which do not meet shrinkable pieces, replacing a_{ij} by b_{ij} also does not destroy the solution. The lemma is proved.

We have described how to obtain another solution with the length of middle strips in rank k_{i+1} bounded by L̄ + 4. We now use induction. Suppose that the middle strips are bounded for all u_{k_{i+1}−1} … u_{k_{i+1}−j+1}, and bound them for u_{k_{i+1}−j}. We add new variables and rewrite free equational diagrams of the second type as equational triangles. We will obtain a bounded number of equational triangles, because the length of the middle strips for u_{k_{i+1}−1} … u_{k_{i+1}−j+1} is bounded and the number of equational triangles obtained from free equational diagrams depends on the lengths of the middle strips.

We got some shrinkable pieces in rank k_{i+1} − j; we name then a_{rl}, l = 1, 2, 3. If a_{rl} coincides with a piece of another solution not in the middle, we also name this piece a_{rl}. The word a_{rl} = u_{k_{i+1}−j}^{m} can be a subword of some greater word u_{k_{i+1}−p} and touch it somewhere, but since we consider all free and non-free equational triangles, this is taken into consideration in the equations. The replacement of a_{rl} in u_{k_{i+1}−p} by b_{rl} can turn u_{k_{i+1}−p} into a proper power (in which case we turn the corresponding t_{k_{i+1}−p} into the same power), but it cannot turn u_{k_{i+1}−p} and u_{k_{i+1}−p_{1}} into proper powers of the same word, because the number of roots was taken to be minimal.

Indeed, if we obtained u = v^{s}, u = t_{1}^{α}, v = t_{2}^{γ}, we could put t_{1} = t_{3}^{sγ}, t_{2} = t_{3}^{α}, and this would be another solution with fewer roots added.

Now suppose by induction that we have bounded the lengths of the middle-strips at all levels higher than j. Free equational triangles at levels higher that j do not affect the maximal shrinkable pieces at level j. Indeed, free equations on levels higher than j just equate some of the ⟨t_{r}⟩-syllables, for r > k_{j+1}, and some of the (u_{k}, u_{l})-connectors between two neighboring ⟨t_{k}⟩, ⟨t_{l}⟩-syllables, where k, l > j are equal. All the maximal shrinkable subwords u_{j}^{k} at level j are inside these connectors. All the maximal shrinkable subwords t_{r}^{k}, where r ∈ {k_{j} +1, …, k_{j+1}}, coincide with some of these ⟨t_{r}⟩-syllables. For the level j we just repeat the procedure described for the level i. Because there are only a bounded number of u’s on the same level, and the number of non-free equations does not exceed M, we can get a boundary for the lengths of middles at each level. So all middle t-strips, at all the levels greater than 0, can be shortened.

If G is a free group, the middle t-strips at level 0 can be shortened by the same procedure.

Lemma 12. Starting with a minimal solution, with bounded lengths of middle t_{k}- strips at all levels, it is possible to construct a solution with bounded depth in every rank j of the root t_{j} (i.e. the s_{j}’s are bounded).

Proof. Suppose, by induction, that we have bounded the depth of the roots on all levels higher than j, and in the ranks k_{j+1}, …, k_{j+1} − p + 1 . Now we will bound it in rank k_{j+1}−p. Consider all non-free equational triangles in rank k_{j+1}−p, together with all their middle strips as shown in Fig. 14(a), 14(b), 14(c). Let a_{ik} = t_{k_{j+i}−p}^{4+l_{ik}} be a shrinkable t_{k_{j+i}−p}-subword. For the middle strips we can write the system of linear equations with variables l_{ik} and d, where d is the depth of the root t_{k_{j+1}−p}.

We have no more than M equations of the form t_{k_{j+1}−p}^{x_{1}}t_{k_{j+1}−p}^{x_{2}} = u_{k_{j+1}−p}^{s} (s is bounded by the maximal length of middle-strips) or t_{k_{j+i}−p}^{x_{1}}t_{k_{j+i}−p}^{x_{2}} = t_{k_{j+i}−p}^{x_{3}}. So we have a homogeneous system of linear equations with not more than 3M variables. These equations can only be of the form x_{i} ± x_{j} = sd (s is bounded, by L̄), or x_{i} + x_{j} = x_{k} The prime divisors of d must belong to the set π, x_{i} ≥ 0. The minimality of the solution X = {X_{1}, …, X_{L}} implies that the linear system does not admit solutions in which one of the x’s is divisible by d. This implies that, after transforming the system to reduced row-echelon form, we can only have d as a free variable, and can either solve the system or see that it is unsolvable.

There can be only a finite number of such systems, with each system having some solution; if L̃ is the greatest value of d in all these solutions, then we always can find a solution of system (1) where the depth of the roots is bounded by L̃. The lemma is proved.

8. The proof of Theorem 1

From now on we suppose that the group G is free. So F = G, and on level zero we have only free equations.

Proposition 1. It is possible to determine a recursive function ψ(M) such that if a system of M triangular equations has a solution in F^{Q}, then it also has a solution in some group H_{ψ(n)}, where H_{0} = F and H_{i+1} is obtained from H_{i} by adding some root.

Proof. It is possible to find a number ψ(M) such that if k_{i+1} is greater than ψ(M), there will be some numbers r and s < r such that k_{r+1} − r = k_{s+1} − s and the following conditions are satisfied:

1. The systems of non-free equations in ranks r and s are equivalent (there exists a bijection between their sets of variables that induces a bijection between their solution sets).

2. Let Y_{1}, …, Y_{p}, u_{r+1}, …, u_{k_{r+1}} be the variables in the system of non-free equations in rank r and Z_{1}, …, Z_{p}, u_{s+1}, …, u_{k_{s+1}} the variables in the system of non-free equations in rank s. As variables, u_{r+1}, …, u_{k_{r+1}} correspond to u_{s+1}, …, u_{k_{s+1}}.

3. The corresponding roots of u_{r+1}, …, u_{k_{r+1}} and of u_{s+1}, …, u_{k_{s+1}} have the same depth.

4. Consider first free equations of the second type in ranks from r + 1 to k_{r+1}. They imply certain free equations for (u_{j}, u_{k})- and u_{j}-connectors in H_{r} (those which are defined) and original variables in H_{r} , j, k ∈ {r + 1, …, k_{r+1}}. Hence the variables Y_{1}, …, Y_{p}, u_{r+1}, …, u_{k_{r+1}} satisfy some free equations. Next, consider the free equations of the second type in ranks from s + 1 to k_{s+1}. They likewise imply certain free equations for (u_{j}, u_{k})- and u_{j}- connectors and original variables in H_{s}, j, k ∈ {s + 1, …, k_{s+1}}. Hence the variables Z_{1}, …, Z_{p}, u_{s+1}, …, u_{k_{s+1}} also satisfy some free equations. The systems of the free equations for the variables Y_{1}, …, Y_{p}, u_{r+1}, …, u_{k_{r+1}} and for the variables Z_{1}, …, Z_{p}, u_{s+1}, …, u_{k_{s+1}} must be equivalent.

Indeed, the number of roots on a given level, as well as the difference k_{j+1} − j, are bounded by Lemma 9, the length of middlestrips is bounded, the number of free equations of the second type at every level is bounded, and the depth of the roots is bounded by Lemma 12.

We now replace all the variables in equational triangles in rank r by the corresponding variables in equational triangles in rank s. In particular u_{r+1}, …, u_{k_{r+1}} will be replaced by u_{s+1}, …, u_{k_{s+1}}; (u_{k}, u_{l})- and u_{k}-connectors, for k, l ∈ {r + 1, …, k_{r+1}} participating in non-free equational triangles, will be replaced by the corresponding (u_{k}, u_{l})- and u_{k}-connectors, for k, l ∈ {s+1, …, k_{s+1}}. If some (u_{k}, u_{l})- or u_{k}-connector, for k, l ∈ {r + 1, …, k_{r+1}}, or original variable in H_{r} does not participate in nonfree equations, then we can replace it by an arbitrary element in H_{s}.

Our purpose is to show that we will again obtain a solution. Indeed, consider first what will happen to the free equational triangles that come from the levels higher than r. These equations just indicate that some of the (u_{k}, u_{j})- and u_{j}- connectors are the same and some of the ⟨t_{j}⟩- syllables are the same, for j, k ∈ {r+1, …, k_{r+1}} . We will have to replace the pieces corresponding to u_{r+1}, …, u_{k_{r+1}} in these equations by the pieces corresponding to u_{s+1}, …, u_{k_{s+1}}, and hence to change u_{k_{r+1}+1} and all the highest u’s. But all these pieces are between two neighboring occurrences of t_{j} and t_{k}, j, k ∈ {r + 1, …, k_{i+1}}, so do not affect the other structure of free equations. We also will replace the pieces corresponding to (u_{j}, u_{k})-connectors in H_{r}, for j, k ∈ {r + 1, …, k_{r+1}}, by the pieces corresponding to (u_{j}, u_{k})-connectors in H_{s}, for j, k ∈ {s + 1, …, k_{s+1}}, and again this will change some connectors; however, all the connectors which were the same will remain the same.

So we obtain a solution with fewer roots (we do not need t_{s+1}, …, t_{k_{s+1}} if k_{s+1} < r + 1, or t_{s+1}, …, t_{r+1−1} if k_{s+1} ≥ r + 1). Indeed, now t_{r+1}, …, t_{k_{r+1}} will be the roots of u_{s+1}, …, u_{k_{s+1}}. We have obtained a contradiction with the minimality of our solution.

The proposition is proved.

It follows from the proposition that k_{i+1} = ψ(M). The length of the middle t_{j}-strips, in all the ranks j, is bounded. We will construct a system of equational triangles in F_{k_{i+1}}, as it was described in Section 6. The number of possible systems of free equations that correspond to these systems of equational triangles is bounded, and we can list them. Finally we have a finite number of possible systems of equations in the free group F_{k_{i+1}}, with the restriction that some of the variables belong to subgroups generated by only a part of the generating set of the free group F_{k_{i+1}}. Each such system is algorithmically decidable [7]. If all these systems are incompatible, then our system does not have a solution. If at least one of them is consistent, we obtain a solution of our system by substituting the corresponding P_{i}’s u_{j}’s and T_{k}’s in the expressions for unknowns.

9. The proof of Theorem 2

To prove Theorem 2 we first need some definitions.

A subgroup G is called existentially closed in a group H if any existential sentence, with constants from G, holds in the whole group H if and only if it holds in the subgroup G.

Let G be a subgroup of H. A finite system of equations W (x, g) = {w_{1}(x, g) = 1, …, w_{k}(x, g) = 1}, with variables x = (x_{1}, …, x_{n}) and constants g = (g_{1}, …, g_{m}) from G, has a solution in H (resp. in G) if and only if the following formula holds in H (resp. in G):

∃x(w_{1}(x, g) = 1 ∧ … ∧ w_{k}(x, g) = 1).

Therefore, if G is existentially closed in H, then any system W (x, g) = 1, with constants in G, has a solution in H if and only if it has a solution in G.

Let G be a subgroup of H. Following [3] we will say that H is locally ω-separated in G by retractions if for finitely many arbitrary nontrivial elements h_{1}, …, h_{n} ∈ H there exists a homomorphism ψ : H ⟶ G, which is the identity on G, such that the images of h_{1}, …, h_{n} under ψ are also nontrivial in G.

In [3] the following result has been proven: Let G be a torsion-free hyperbolic group and A a ring of characteristic 0. Then G^{A} is locally ω-separated in G^{Q_{π(A)}} by retractions.

Lemma 13. Let G be a subgroup of H. If H is locally ω-separated in G by retractions, then G is existentially closed in H.

Proof. From general predicate calculus we know that any existential sentence in the group theory language with constants from G is equivalent to a sentence of the following type:

Φ = ∃x(⋀_{1}^{s} u_{i}(x, g) = 1 ⋀_{1}^{t} v_{j}(x, g) ≠ 1),

where the u_{i}’s and v_{j}’s are group words, x = (x_{1}, …, x_{n}) are variables and g = (g_{1}, …, g_{k}) are some constants from G.

Let the elements h = (h_{1}, …, h_{n}) ∈ H satisfy the quantifier-free part of this sentence in H. Denote by H_{0} the subgroup ⟨h_{1}, …, h_{n}⟩ in H. By the conditions of the lemma there exists a homomorphism f : H_{0} ⟶ G which separates the elements v_{1}(h_{1}, …, h_{n}), …, v_{t}(h_{1}, …, h_{n}) in G. This implies that the images f(h_{1}), …, f(h_{n}) satisfy in G the same equalities u_{i}(f(h_{1}), …, f(h_{n})) = 1, i = 1, …, s, and inequalities v_{i}(f(h_{1}), …, f(h_{n})) ≠ 1, i = 1, …, t. Therefore, the sentence Φ holds in G. This shows that G is existentially-closed in H.

Corollary 3. Let G be a torsion-free hyperbolic group and A a ring of characteristic 0. Then G^{Q_{π(A)}} is existentially closed in G^{A} .

Now we can complete the proof of Theorem 2. By the corollary above, F^{Q_{π(A)}} is existentially closed in F^{A}; hence any system W = 1 with coefficients from F has a solution in F^{A} if and only if it has a solution in F^{Q_{π(A)}}. The result now follows from Theorem 1.

10. Equations and inequalities in F^{Q_{π}}

In this section we show how to prove the algorithmic decidability of the universal theory of the group F^{Q_{π}} (with constants from F^{Q_{π}}) to a question in the free group F.

To prove the decidability of the universal theory of F^{Q_{π}} one has to construct an algorithm solving finite systems of equations and inequalities in F^{Q_{π}}. Such a system can be reduced to the system of triangular equations (1) together with some inequalities X_{k} ≠ 1. The algorithm constructed in this paper can be used to reduce the system to a finite number of possible systems of equations and inequalities in the free group F_{k_{i+1}}, with the restriction that some of the variables belong to subgroups generated by only a part of the generating set of the free group F_{k_{i+1}}.

This problem can be solved by methods described in [7].

References

1. G Baumslag, On free D-group, Comm. Pure and Appl. Math., 18 (1965) 25–30. MR 31:1293 2. , Some aspects of groups with unique roots, Acta Math., 104 (1960), 217–303. MR

23:A191

3. G. Baumslag, A. Myasnikov, and V. Remeslennikov, Residually hyperbolic groups, preprint, 4. L. P. Comerford Jr., and C. C. Edmunds, Solutions of equations in free groups, Group Theory

(Singapore, 1987; K. N. Cheng and Y. K. Leong, editors), de Gruyter, Berlin, 1989, pp. 347– 356. MR 90a: 20067

5. R. I. Grigorchuk and P. F. Kurchanov, On quadratic equations in free groups, Proc. Internat. Conf. Algebra (Novosibirsk, 1989), Part 1, Contemp. Math., vol. 131, Amer. Math. Soc., Providence, RI 1992, pp. 159–171. MR 94m:20074

6. O. Kharlampovich and A. G. Myasnikov, Hyperbolic groups and free constructions, Trans. Amer. Math. Soc. 350 (1998), 571–613.

7. G.S. Makanin, Decidability of the universal and positive theories of a free group, Izv. Akad. Nauk SSSR, Ser. Mat. 48 (1984), 735–749; English transl., Math. USSR Izv. 25, (1985), 75–88. MR 86c:03009.

8. , Equations in a free group, Izv. Akad. Nauk SSSR, Ser. Mat. 46 (1982), 1199–1273; English transl., Math. USSR Izv. 21 (1983), 483–546. MR 84m:20040

9. A. G. Myasnikov and V. N. Remeslennikov. Exponential groups II: Extension of centralizers and tensor completion of CSA-groups, Internat. J. Algebra Comput. 6 (1996), 687–712.

10. H. Presburger, Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzen Zahlen, C. R. 1 Congr. Math. Pays Slaves, Warsaw, 1929, pp. 92–101.

11. A. A. Razborov, On systems of equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), 779–832; English transl., Math. USSR Izv. 25 (1985), 115–162. MR 86c:20033

12. E. Rips and Z. Sela, Canonical representatives and equations in hyperbolic groups, Invent. Math. 120 (1995), 489–512. MR 96c:20053

Department of Mathematics and Statistics, McGill University, Montréal, P.Q., Canada H3A 2K6

E-mail address: olga@triples.math.mcgill.ca

Department of Mathematics, City College (CUNY), Convent Avenue and 138th Street, New York, New York 10031-9100

E-mail address: alexei@rio.sci.ccny.cuny.edu