A Ould Houcine

K Tent

Ampleness in the free group

We show that the theory of the free group -and more generally the theory of any torsionfree hyperbolic group -is n-ample for any n ≥ 1. We give also an explicit description of the imaginary algebraic closure in free groups.

Introduction

Work of Kharlampovich-Myasnikov [START_REF] Kharlampovich | Elementary theory of free nonabelian groups[END_REF] and Sela [START_REF] Sela | Diophantine geometry over groups VI: The elementary theory of a free group[END_REF] showed that the theory of a nonabelian free group does not depend on the rank of the free group and so we can let T f g denote the theory of nonabelian free groups. Sela [START_REF] Sela | Diophantine Geometry over Groups IX: Envelopes and Imaginaries[END_REF] showed that this theory is stable as well as the theory of any torsion-free hyperbolic group.

Having a quantifier elimination result down to ∀∃-formulas [START_REF] Kharlampovich | Elementary theory of free nonabelian groups[END_REF][START_REF] Sela | Diophantine geometry over groups VI: The elementary theory of a free group[END_REF], elimination of imaginaries down to some very restricted class of imaginaries [START_REF] Sela | Diophantine Geometry over Groups IX: Envelopes and Imaginaries[END_REF], homogeneity [START_REF] Houcine | Homogeneity and prime models in torsion-free hyperbolic groups[END_REF][START_REF] Perin | Homogeneity in the free group[END_REF], a better understanding of stability theoretic independence [START_REF] Pillay | Forking in the free group[END_REF][START_REF] Pillay | On genericity and weight in the free group[END_REF] and more recently a description of the algebraic closure [START_REF] Ould Houcine | Algebraic and definable closure in free groups[END_REF] now gives us the tools for studying the model theoretic geometry of forking in the free group and in torsion-free hyperbolic groups.

Ampleness is a property that reflects the existence of geometric configurations behaving very much like projective space over a field. Pillay [START_REF] Pillay | A note on CM-triviality and the geometry of forking[END_REF] first defined the notion of n-ampleness. We use here the slightly stronger definition given by Evans in [START_REF] Evans | Ample Dividing[END_REF]. Definition 1.1. [START_REF] Evans | Ample Dividing[END_REF] Suppose T is a complete stable theory and n ≥ 1 is a natural number. Then T is n-ample if (in some model of T , possibly after naming some parameters) there exist tuples a 0 , . . . , a n such that:

(i) a n | ⌣ a 0 ; (ii) a 0 . . . a i-1 |
⌣ a i a i+1 . . . a n for 1 ≤ i < n; (iii) acl eq (a 0 ) ∩ acl eq (a 1 ) = acl eq (∅); (iv) acl eq (a 0 . . . a i-1 a i ) ∩ acl eq (a 0 . . . a i-1 a i+1 ) = acl eq (a 0 . . . a i-1 ) for 1 ≤ i < n.

We call T ample if it is n-ample for all n ≥ 1.

In n + 1-dimensional projective space such a tuple a 0 , . . . a n can be chosen as a maximal flag of subspaces and this example can guide the intuition. It is well-known that a stable structure which type-interprets an infinite field is ample. In this paper we study ampleness in torsion-free hyperbolic groups and we show: Theorem 1.2. The theory of any nonabelian torsion-free hyperbolic group is ample.

We also state the following special case, whose proof -as we will see -implies the general statement:

Corollary 1.3. The theory T f g of nonabelian free groups is ample.

In fact, our construction is very explicit: given a basis {c 0 , a i , b i , t i : i < ω} of the free group of rank ω we find witnesses for ampleness as the tuples h 2i = (a 2i , b 2i , c 2i ), i < ω, where the sequence (c i ) i<ω is defined inductively as follows

c i+1 = t i c -1 i [a i , b i ] -1 t i -1 .
We do not know whether the free group interprets an infinite field. While we do not believe this to be the case, ampleness is certainly consistent with the existence of a field.

In [START_REF] Pillay | Forking in the free group[END_REF] Pillay gave a proof showing that the free group is 2-ample. However, his proof relied on a result by Bestvina and Feighn which has not yet been completely established. His conjecture that the free group is not 3-ample is refuted in this paper.

The present paper is organized as follows. In Section 2 we collect the preliminaries about elimination of imaginaries, JSJ-decompositions and related notions needed in the sequel. In Section 3, we study the imaginary algebraic closure and give a geometric characterization of those conjugacy classes which are elements of the imaginary algebraic closure. Section 4 is devoted to the construction of sequences witnessing the ampleness in the free group. The last section the shows how the general theorem follows from the special case.

Preliminaries

In this section we put together some background material needed in the sequel. The first subsection deals with imaginaries and the two next subsections deal with splittings, JSJ-decompositions, homogeneity, algebraic closure and independence.

Imaginaries

Let T be a complete theory and M a (very saturated) model of T . Recall that T has geometric elimination of imaginaries if for any ∅-definable equivalence relation E on M k and any equivalence class a E ∈ M eq there is a finite tuple ā ⊂ M with acl eq (ā) = acl eq (a E ), i.e., a E ∈ acl eq (ā) and ā ∈ acl eq (a E ).

For a subset E of the set of ∅-definable equivalence relations in T , we let M E denote the restriction of M eq to the sorts in E. That is, for every E ∈ E defined on M k , we add a new sort S E to the language interpreted as M k /E and a new function π E : M k → S E which associates to a k-tuple x ∈ M k its equivalence class x E . Then the L E -structure M E is the disjoint union of M/E for E ∈ E. We say that T has geometric elimination of imaginaries relative to E if M E has geometric elimination of imaginaries.

Remark 2.1. Suppose that T has geometric elimination of imaginaries relative to E. Then for tuples ā, b, c ⊂ M we have acl eq (ā) ∩ acl eq ( b) = acl eq (c)

if and only if

(acl eq (ā) ∩ M E ) ∩ (acl eq ( b) ∩ M E ) = (acl eq (c) ∩ M E ).
In order to prove ampleness for torsion-free hyperbolic groups we can therefore restrict our attention to some basic equivalence relations. For the theory of a nonabelian torsion-free hyperbolic group Sela established geometric elimination of imaginaries relative to the following small collection of basic equivalence relations: let E denote the collection of the following ∅-definable equivalence relations where C(x) denotes the centralizer of x:

E 0 (x; y) : ∃zx z = y E 1 (x, y; x ′ , y ′ ) : C(x) = C(x ′ ) ∧ y ′ ∈ yC(x) E 2 (x, y; x ′ , y ′ ) : C(x) = C(x ′ ) ∧ y ′ ∈ C(x)y E 3 (x, y, z; x ′ , y ′ , z ′ ) : C(x) = C(x ′ ) ∧ C(y ′ ) = C(y) ∧ z ∈ C(x)z ′ C(y).
For an L-structure M we denote by P n (M m ) the set of finite subsets of M m of cardinality at most n. A function f : M r → P n (M m ) is said to be definable if there exists a formula ϕ(x; ȳ) such that for any

ā ∈ M r , for any b ∈ M m , b ∈ f (ā) if and only if M |= ϕ(ā, b).
Sela proves the following strong form of geometric elimination of imaginaries:

Theorem 2.2. [17, Theorem 4.6] For any ∅-definable equivalence relation E(x, ȳ), |x| = n in the theory T of a torsion-free hyperbolic group M (in the language of groups), there exist k, p ∈ N and a function f :

M n → P p (M E k ) ∅-definable in L E such that for all ā, b ∈ M n M |= E(ā, b) ⇔ M E |= f (ā) = f ( b).
Clearly, this implies that for any 0-definable equivalence relation E in T with corresponding definable function f E in L E , the equivalence class āE is interalgebraic in M E with the finite set f E (ā) of elements in M E : namely, if f E (ā) = (c 1 , . . . ck ) where the ci are tuples from M E , then c1 , . . . , ck ∈ acl eq (ā E ) and āE ∈ acl eq (c 1 , . . . , ck ). Hence: Corollary 2.3. [START_REF] Sela | Diophantine Geometry over Groups IX: Envelopes and Imaginaries[END_REF] The theory of a torsion-free hyperbolic group has geometric elimination of imaginaries relative to E.

Splittings, JSJ-decompositions

Let G be a group and let C be a class of subgroups of G. By a (C, H)-splitting of G (or a splitting of G over C relative to H), we understand a tuple Λ = (G(V, E), T, ϕ), where G(V, E) is a graph of groups such that each edge group is in C and H is elliptic, T is a maximal subtree of G(V, E) and ϕ : G → π(G(V, E), T ) is an isomorphism; here π(G(V, E), T ) denotes the fundamental group of G(V, E) relative to T . If C is the class of abelian groups or cyclic groups, we will just say abelian splitting or cyclic splitting, respectively. If every edge group is malnormal in the adjacent vertex groups, then we say that the splitting is malnormal.

Given a group G and a subgroup H of G, G is said to be freely

H-decomposable if G has a nontrivial free decomposition G = G 1 * G 2 such that H ≤ G 1 . Otherwise, G is said to be freely H-indecomposable.
Following [START_REF] Guirardel | JSJ decompositions: definitions, existence, uniqueness. I: The JSJ deformation space[END_REF], given a group G and two (C, H)-splittings Λ 1 and Λ 2 of G, Λ 1 dominates Λ 2 if every subgroup of G which is elliptic in Λ 1 is also elliptic in Λ 2 . A (C, H)-splitting of G is said to be universally elliptic if all edge stabilizers in Λ are elliptic in any other (C, H)-splitting of G.

A JSJ-decomposition of G over C relative to H is an universally elliptic (C, H)-splitting dominating all other universally elliptic (C, H)-splittings. If C is the class of abelian subgroups, then we simply say abelian JSJ-decomposition; similarly when C is the class of cyclic subgroups. It follows from [START_REF] Rips | Cyclic splittings of finitely presented groups and the canonical JSJ decomposition[END_REF][START_REF] Guirardel | JSJ decompositions: definitions, existence, uniqueness. I: The JSJ deformation space[END_REF] that torsion-free hyperbolic groups (so in particular nonabelian free groups of finite rank) admit (relative) cyclic JSJ-decompositions.

Given an abelian splitting Λ of G (relative to H) and a vertex group G v of Λ, the elliptic abelian neighborhood of G v is the subgroup generated by the elliptic elements that commute with nontrivial elements of G v . It was shown in [START_REF] Champetier | Limit groups as limits of free groups: compactifying the set of free groups[END_REF]Proposition 4.26] that if G is commutative transitive then any abelian splitting Λ of G (relative to H) can be transformed to an abelian splitting Λ ′ of G such that the underlying graph is the same as that of Λ and for any vertex v, the corresponding new vertex group Ĝv in Λ ′ is the elliptic abelian neighborhood of G v (similarly for edges); in particular any edge group of Λ ′ is malnormal in the adjacent vertex groups. We call that transformation the malnormalization of Λ. If Λ is a (cyclic or abelian) JSJ-decomposition of G and G is commutative transitive then the malnormalization of Λ will be called a malnormal JSJ-decomposition. If G v is a rigid vertex group then we call Ĝv also rigid; similarly for abelian and surface type vertex groups. Strictly speaking a malnormal JSJ-decomposition is not a JSJ-decomposition in the sense of [START_REF] Guirardel | JSJ decompositions: definitions, existence, uniqueness. I: The JSJ deformation space[END_REF], however it possesses the most important properties of JSJ-decompositions that we need.

We end with the definition of generalized malnormal JSJ-decomposition relative to a subgroup A. First, split G as a free product G = G 1 * G 2 , where A ≤ G 1 and G 1 is freely A-indecomposable. Then, define a generalized malnormal (cyclic) JSJ-decomposition of G relative to A as the (cyclic) splitting obtained by adding G 2 as a new vertex group to a malnormal (cyclic) JSJ-decomposition of G 1 (relative to A). We call G 2 the free factor. In a similar way the notion of a generalized cyclic JSJ-decomposition, without the assumption of malnormality, is defined

We denote by Aut H (G) the group of automorphisms of a group G that fix a subgroup H pointwise. The abelian modular group of G relative to H, denoted M od H (G), is the subgroup of Aut H (G) generated by Dehn twists, modular automorphisms of abelian type and modular automorphisms of surface type (For more details we refer the reader for instance to [START_REF] Ould Houcine | Algebraic and definable closure in free groups[END_REF]). We will use the following property of modular automorphisms whose proof is essentially contained in [START_REF] Champetier | Limit groups as limits of free groups: compactifying the set of free groups[END_REF] (see for instance [START_REF] Champetier | Limit groups as limits of free groups: compactifying the set of free groups[END_REF]Proposition 4.18]).

Lemma 2.4. Let Γ be torsion-free hyperbolic group and A a nonabelian subgroup of Γ. Let Λ be a generalized malnormal cyclic JSJ-decomposition of Γ relative to A. Then any modular automorphisms σ ∈ M od A (Γ) retrict to a conjugation on rigid vertex groups and on boundary subgroups of surface type vertex groups of Λ.

We note that when Γ is a torsion-free hyperbolic group which is freely A-indecomposable, then any abelian vertex group in any cyclic JSJ-decomposition Λ of Γ relative to A is rigid; this a consequence of the fact that abelian subgroups of Γ are cyclic and of the fact that edge groups of Λ are universally elliptic. The same property holds also for abelian vertex groups (different from free factors) in generalized malnormal JSJ-decompositions.

Rips and Sela showed that the modular group has finite index in the group of automorphisms. We will use that result in the relative case.

Theorem 2.5. (See for instance [START_REF] Ould Houcine | Algebraic and definable closure in free groups[END_REF]) Let Γ be a torsion-free hyperbolic group and A a nonabelian subgroup of Γ such that Γ is freely A-indecomposable. Then M od A (Γ) has finite index in Aut A (Γ).

We end this subsection with the following standard lemma needed in the sequel. Lemma 2.6. Let G be the fundamental group of an orientable surface S with boundaries such that 2g(S) + b(S) ≥ 4, where here g(S) denotes the genus of S and b(S) denotes the number of boundary components. Then for any nontrivial element g which is not conjugate to any element of a boundary subgroup, there exists a malnormal cyclic splitting of G in which g is hyperbolic and boundary subgroups are elliptic.

Proof. The proof is by induction on g(S). If g(S) = 0, then

G = s 1 , • • • , s n |s 1 • • • s n = 1 and n ≥ 4. Note that s 1 , • • • , s n-1 is a basis of G.
Since g is not conjugate to any boundary subgroup, the normal form of g involves at least two elements s i , s j with 1 ≤ i < j ≤ n -1. Since n ≥ 4, replacing the relation s 1 • • • s n = 1 by a cyclic permutation and by relabeling s 1 , • • • , s n , we may assume that 1 < i < j ≤ n -1. Then g is hyperbolic in the following malnormal cyclic splitting

G = s 1 , • • • , s i | * s 1 •••s i =s -1 n •••s -1 i+1 s i+1 , • • • , s n | .
The geometric picture in that case is that the curve representing g intersects at least one simple closed curve which separates the surface into two subsurfaces each of which has at least two boundary components. Now suppose that g(S) ≥ 1. Let c be a non null-homotopic simple closed curve represented in a handle of S. Let Λ be the dual splitting induced by c which is in this case an HNN-extension. If g is hyperbolic in that splitting (in particular if g is a conjugate to a power of the element represented by c) then we are done. Otherwise g is elliptic and thus it is conjugate to an element represented by a curve in the surface obtained by cutting along c. This new surface S ′ has genus g(S) -1 and two new boundary components and thus we have 2g(S ′ ) + b(S ′ ) = 2g(S) + b(S) ≥ 4. By induction, since g is not conjugate to any element of a boundary subgroup (also the new two boundaries) of S ′ , there exists a malnormal cyclic splitting of S ′ in which g is hyperbolic and the boundary subgroups are elliptic. Since that splitting is compatible with Λ we get the required result.

Homogeneity, algebraic closure, independence

In this subsection we collect facts about algebraic closure and independence which will be used in the sequel. We start from known facts which we cite for convenient reference and extend them for our purposes.

Whenever there is more than one group around we may write acl G (A) and acl eq G (A) to denote the algebraic closure of A in the sense of the theory of G, and similarly A | ⌣ G C B to describe independence in the theory of G.

Proposition 2.7. Let G be a torsion-free CSA-group. Let Λ be a malnormal cyclic splitting of G. Then for any nontrivial vertex group A we have acl(A) = A.

Proof. A consequence of [7, Proposition 4.3].
Theorem 2.8. [7, Theorem 4.5] If F is a free group of finite rank with nonabelian subgroup A, then acl(A) coincides with the vertex group containing A in the generalized malnormal (cyclic) JSJ-decomposition of F relative to A. Theorem 2.9. [START_REF] Ould Houcine | Algebraic and definable closure in free groups[END_REF] Let Γ be a torsion-free hyperbolic group and A a subgroup of Γ. Then acl(A) is finitely generated. Proposition 2.10. [6, Proposition 5.9] Let F be a nonabelian free group of finite rank and ā a tuple from F such that the subgroup A generated by ā is nonabelian and F is freely A-indecomposable. Then for any tuple b contained in F , the type tp( b/c) is isolated.

Theorem 2.11. [START_REF] Houcine | Homogeneity and prime models in torsion-free hyperbolic groups[END_REF][START_REF] Perin | Homogeneity in the free group[END_REF] Let F be a nonabelian free group of finite rank. For any tuples ā, b ∈ F n and for any subset P ⊆ F , if tp F (ā/P ) = tp F ( b/P ) then there exists an automorphism of F fixing P pointwise and sending ā to b.

One ingredient in the proof of Theorem 1.2 is a result of Sela which essentially allows us to work in a free group. In [Sel09], Sela shows that if Γ is a torsion-free hyperbolic group which is not elementarily equivalent to a free group, then Γ has a minimal elementary subgroup, denoted by EC(Γ), called the elementary core of Γ (see for instance [START_REF] Houcine | Homogeneity and prime models in torsion-free hyperbolic groups[END_REF]Section 8] for some properties of the elementary core). It follows from the definition of the elementary core that if Γ is a nonabelian torsion-free hyperbolic group then Γ is elementarily equivalent to Γ * F n for any free group of rank n. Combined with [START_REF] Sela | Diophantine geometry over groups X: The Elementary Theory of Free Products of Groups[END_REF]Theorem 7.2] it gives the following stronger result: Theorem 2.12. Any nonabelian torsion-free hyperbolic group Γ is elementarily equivalent to Γ * F for any free group F .

We will be using the following variant of this result: Lemma 2.13. Let Γ be a torsion-free hyperbolic group not elementarily equivalent to a free group. Let F be a free group and C a free factor of F . Then EC(Γ) * C Γ * F .

Proof. Suppose first that F has a finite rank. The proof is by induction on the rank n of C. If n = 0 then the result is a consequence of the definition of elementary cores (see [START_REF] Sela | Diophantine Geometry over Groups VII. The elementary theory of a hyperbolic group[END_REF]). Suppose that the result holds for free factors of rank n and set C = cn , c n+1 | . Let ϕ(x) be a formula (without parameters) and ḡ ∈ EC(Γ) * C such that ϕ(ḡ) holds in EC(Γ) * C. Then there exists a tuple of words w(x n ; y) such that ḡ = w(c n ; c n+1 ). By induction EC(Γ) * cn | is an elementary subgroup of EC(Γ) * C and thus by [START_REF] Ould Houcine | Algebraic and definable closure in free groups[END_REF]Lemma 8.10], the formula ϕ( w(c n ; y)) is generic. Since by induction EC(Γ) * cn | is an elementary subgroup of Γ * F we conclude that there exists

g 1 , • • • , g p ∈ EC(Γ) * cn | such that Γ * F = ∪ i g i X where X = ϕ( w(c n ; Γ * F )). Hence c n+1 ∈ g i X
for some i. There exists an automorphism of Γ * F fixing EC(Γ) * cn | pointwise and sending c n+1 to g i c n+1 and thus ϕ( w(c n ; c n+1 )) holds in Γ * F as required.

Suppose now that F has an infinite rank and C has a finite rank. By quantifier elimination and Theorem 2.12 it is sufficient to show that for any formula ϕ of the form ∀∃ or ∃∀ with parameters from

EC(Γ) * C if Γ * F |= ϕ then EC(Γ) * C |= ϕ.
Suppose that ϕ is of the form ∀x∃yϕ 0 (x; y) where x and y are finite tuples and ϕ 0 is quantifierfree. If Γ * F |= ϕ then for any g ∈ EC(Γ) * C there exists a free factor C ′ of F of finite rank such that C ≤ C ′ and a tuple a ∈ Γ * C ′ such that Γ * C ′ |= ϕ 0 (g; a). By the previous case, EC(Γ) * C is an elementary subgroup of Γ * C ′ and thus we get EC(Γ) * C |= ∃yϕ 0 (g; y). Hence we conclude that EC(Γ) * C |= ϕ. The case ϕ is of the form ∃∀ can be treated in a similar way. Finally, the case F and C both have infinite rank follows from the previous cases.

Corollary 2.14. Suppose H = Γ * F where Γ is a torsion-free hyperbolic group and F a free group of finite rank. Then EC(Γ) and F are (in H) independent over the emptyset.

Proof. If EC(Γ) = 1 the result is clear. So we suppose that EC(Γ) = 1; that is Γ is not elementarily equivalent to a free group. Combining Lemma 2. [START_REF] Perin | [END_REF]

A | ⌣ {e i : i < ω}
and this is enough.

The following characterization of forking independence over free factors in free groups was recently proved by Perin and Sklinos [START_REF] Perin | [END_REF]

F = A * C * B with ā ∈ A * C and b ∈ C * B.
We will need slight extensions of the previous results to free products of a torsion-free hyperbolic group with a free group: Proposition 2.17. (Generic homogeneity) Let H = Γ * F where Γ is a torsion-free hyperbolic group (possibly trivial) and F a free group of finite rank. Let ā, b, c be finite tuples from

F . If tp H (ā/c) = tp H ( b/c) then there exists an automorphism f ∈ Aut c(F ) such that f (ā) = b.
In

′ : E 1 → E 1 such that (E 1 , E ′ 1 , r ′
) is a hyperbolic floor. This implies that F has a structure of hyperbolic tower over a proper subgroup contradicting [START_REF] Perin | Homogeneity in the free group[END_REF]Proposition 6.5].

We conclude that there exists u : E 1 → H which fixes c and sends ā to b. Symmetrically, there exists v : E 2 → H which fixes c and sends b to ā. Since E 1 (resp. E 2 ) is freely indecomposable relative to A (resp. B) by using Grushko theorem u : E 1 → E 2 is an isomorphism sending ā to b and fixing c which can be extended to F and also to H. This shows in particular that tp F (ā/c) = tp F ( b/c). Conversely, if this last property holds then by homogeneity of F , there exists an automorphism f of F fixing c and sending ā to b. Such an automorphism can be extended to an automorphism f of H (fixing Γ pointwise) and thus tp H (ā/c h) = tp H ( b/c h) for any generating set h of Γ. Then clearly, we also have tp H (ā/c) = tp H ( b/c).

Corollary 2.18. Let H = Γ * F where F is a free group (of any rank) and Γ is a torsion-free hyperbolic group not elementarily equivalent to a free group. Let ā, b, c be finite tuples from F . Then the conclusions of Proposition 2.17 hold also in this case.

Proof. Let F n be a free factor of finite rank of F containing the tuples ā, b, c and set H n = Γ * F n . Suppose that tp H (ā/c) = tp H ( b/c). By Lemma 2.13, EC(Γ) * F n H n and EC(Γ) * F n H and hence we get tp Hn (ā/c) = tp Hn ( b/c). By Proposition 2.17 there exists an automorphism f ∈ Aut c(F n ) such that f (ā) = b which can be easily extended to F . Proof

F n = (A ∩ F n ) * C * (B ∩ F n ) such that ā ∈ (A ∩ F n ) * C, b ∈ C * (B ∩ F n ). Set H ′ = EC(Γ) * F n . Since H ′ H, it is sufficient to show that ā | ⌣ H ′ hc b.

The imaginary algebraic closure

In this section we study acl eq (A) with respect to the three basic equivalence relations conjugacy, left (right) cosets of cyclic groups, and double cosets of cyclic groups. Note that the algebraic closure is independent of the model. We first prove a proposition of independent interest: Proposition 3.1. Suppose that G is a torsion-free CSA-group, A a nonabelian subgroup of G. Let Λ = (G(V, E), T, ϕ) be a malnormal abelian splitting of G relative to A. If g ∈ G is hyperbolic with respect to this splitting, there exist

f n ∈ Aut A (G), n ∈ N such that the f n (g), n ∈ N are pairwise non-conjugate and C(f n (g)) = C(f m (g)) for n = m.
We reduce the proof to the following basic configurations. Lemma 3.2. Let G be a torsion-free CSA-group and A a nontrivial subgroup of G. Suppose that one of the following cases holds.

(i) G = H * C K, C is abelian and malnormal, A ≤ H, H is nonabelian and g is not in a conjugate of H or K.

(ii) G = H, t|C t = ϕ(C) , C (and ϕ(C)) is abelian and malnormal in H, A ≤ H and g is not in a conjugate of H.

Then there exists infinitely many automorphisms f i ∈ Aut A (G) whose restriction to H is the identity and to K a conjugation such that f i (g) is not conjugate to f j (g) and C(f i (g)) = C(f j (g)) for i = j.

Proof. We treat the case (i). Write g in normal form g = g 1 • • • g r , with r ≥ 2, where we may assume that g is cyclically reduced. If C = 1 choose c ∈ H such that [c, g i ] = 1 for at least one g i appearing in the normal form of g with g i ∈ H. Such a choice is possible since H is nonabelian and CSA. If C = 1 we take c ∈ C nontrivial. We define the automorphism f n by being the identity on H and conjugation by c n on K. We see that f n ∈ Aut A (G).

Suppose towards a contradiction that the orbit {f n (g); n ∈ N} is finite up to conjugacy. Hence there exists n 0 and infinitely many n such that each f n is conjugate to f n 0 .

Suppose that C = 1 and thus c ∈ C. In that case, we see that

f n (g 1 ) • • • f n (g r ) is a normal form of f n (g)
which is moreover cyclically reduced for any n. Hence by the conjugacy theorem, there exists d ∈ C such that f n (g) is conjugate by d to the product of a cyclic permutation of the normal form of f n 0 (g). Since the number of that cyclic permutations is finite we conclude that there exist

n = m such that f n (g) = f m (g) d , where d ∈ C. Suppose that g r ∈ K. Then g r c (n-m) d -1 g -1 r
∈ C and thus we must have c n-m d -1 = 1 and g r-1 c m-n g -1 r-1 ∈ C. Since G is torsion-free and C is malnormal, we conclude that g r-1 ∈ C; a contradiction.

Suppose that g r ∈ H. Then d = 1 and g r-1 c n-m g -1 r-1 ∈ C and the conclusion follows as in the previous case. Hence the set of orbits of {f n (g), n ∈ N} is infinite up to conjugacy. Using a similar argument, we see also that C(f n (g)) = C(f m (g)) for n = m.

Suppose that C = 1. We treat the case g r ∈ L 2 , the other case can be treated in a similar way. Then we see that c n f n (g)c -n is a cyclically reduced conjugate of f n (g). Proceeding as above, we conclude that there exists n = m such that c n f n (g)c -n = c m f m (g)c -m . Then using normal forms, we get that [g i , c] = 1 for any g i appearing in the normal form of g with g i ∈ H; a contradiction. Using a similar argument, we see also that C(f n (g)) = C(f m (g)) for n = m.

We treat now the case (ii). Let c ∈ G be a nontrivial element of C H (C) (if C = 1, since A is nontrivial, then we take c to be any nontrivial element of H) and define for n ≥ 1, f n by being the identity on H and sending t to c n t. Then f n ∈ Aut A (G). Now g can be written in a normal form g 0 t ǫ 0 g 1 • • • g r t ǫr g r+1 , where ǫ i = ±1. Since any element is conjugate to a cyclically reduced element, we may assume that g is cyclically reduced and we may take g r+1 = 1. We have

f n (g) = g 0 f n (t ǫ 0 )g 1 • • • g r f n (t ǫr ), f n (t ǫ i ) = c ǫ i n t ǫ i if ǫ i = 1 and f n (t ǫ i ) = ϕ(c) ǫ i n t ǫ i if ǫ i = -1. Therefore f n (t ǫ i )g i+1 f n (t ǫ i+1 ) = c ǫ i n t ǫ i g i+1 ϕ(c) ǫ i+1 n t ǫ i+1 if ǫ i = 1 and ǫ i+1 = -1. Similarly we have f n (t ǫ i )g i+1 f n (t ǫ i+1 ) = ϕ(c) ǫ i n t ǫ i g i+1 c ǫ i+1 n t ǫ i+1 if ǫ i = -1 and ǫ i+1 = 1.
If C = 1 then g i+1 c ǫ i+1 n ∈ C and g i+1 ϕ(c) ǫ i+1 n ∈ ϕ(C) and thus replacing each f n (t ǫ i ) by its value we obtain a normal form of f n (g) which is moreover cyclically reduced.

If C = 1 then, since G is torsion-free, for all but infinitely many n, g i+1 c ǫ i+1 n = 1 and g i+1 ϕ(c) ǫ i+1 n = 1 and thus replacing each f n (t ǫ i ) by its value we obtain as above a normal form of f n (g) which is moreover cyclically reduced.

Suppose that the set {f n (g)|n ∈ N} is finite up to conjugacy. Hence there exist n 0 and infinitely many n such that f n (g) is cyclically reduced and is conjugate to f n 0 (g). By the conjugacy theorem, there exists d ∈ C ∪ ϕ(C) such that f n (g) is conjugate by d to the product of a cyclic permutation of the normal form of f n 0 (g). Since the number of that cyclic permutations is finite we conclude that there exist n = m such that

f n (g) = f m (g) d , where d ∈ C ∪ ϕ(C).
Since G is a CSA group, either C and ϕ(C) are conjugate in H and in this case we may assume that C = ϕ(C) and thus G is an extension of a centralizer; or C and ϕ(C) are conjugately separated, that is

C h ∩ ϕ(C) = 1 for any h ∈ H. Suppose first that C = ϕ(C) = 1. Since f n (g)(f m (g) d ) -1 = 1
, using normal forms we have g r c ǫrn t ǫr d -1 t -ǫr c -ǫrm g -1 r ∈ C and hence g r c ǫr(n-m) d -1 g -1 r ∈ C. By induction on 0 ≤ l ≤ r, we get

g l • • • g r c (ǫ l +•••+ǫr)(n-m) d -1 g -1 r • • • g -1 l ∈ C
and thus, we conclude that

c (ǫ 0 +•••+ǫr)(n-m) d -1 = d -1 ,
and we get c

(ǫ 0 +•••+ǫr)(n-m) = 1.
Suppose that there is no indice l such that c

(ǫ l +•••+ǫr)(n-m) d -1 = 1.
Then it follows from above that g i ∈ C for any i and thus

g = g 0 • • • g r t ǫ 0 +•••+ǫr . Hence (ǫ 0 + • • • + ǫ r ) = 0 and since c (ǫ 0 +•••+ǫr)(n-m) = 1 and G is torsion-free we get a contradiction.
Suppose that there is some indice l such that c

(ǫ l +•••+ǫr)(n-m) d -1 = 1. Then for any i > l or i < l we get g i ∈ C. Then g = t ǫ 0 +•••+ǫ l-1 g 0 • • • g r t ǫ l +•••+ǫr . If we suppose that ǫ 0 + • • • + ǫ r =
0 then g will be a conjugate of an element of H; a contradiction. Hence (ǫ 0 + • • • + ǫ r ) = 0 and since c (ǫ 0 +•••+ǫr)(n-m) = 1 and G is torsion-free we get a contradiction.

Suppose that C = ϕ(C) = 1. Then d = 1 and c m-n = 1; which is a contradiction. Suppose now that C 1 and C 2 are conjugately separated. As in the previous case, we conclude after calculation that c n-m = 1; which is a contradiction.

We conclude that the orbit {f n (g)|n ∈ N} is infinite up to conjugacy as required. Using a similar argument with normal forms we get that [f n (g), f m (g)] = 1 for n = m and thus C(f n (g)) = C(f m (g)) for n = m.

Proof of Proposition 3.1.

To simplify, identify G with π(G(V, E), T ). For an edge e i outside T , let G i (V, E i ) be the graph of groups obtained by deleting e i . Then G is an HNN-extension of the fundamental group

G i = π(G i (V, E i ), T ) and we can write G = G i , t|C t = ϕ(C) with A ≤ G i .
Suppose that for some edge e i outside T the element g is hyperbolic in the corresponding splitting. Then we conclude by Lemma 3.2. Now assume that there is no edge in G(V, E) outside T such that g is hyperbolic in the corresponding splitting as above. Let L be the fundamental group of the graph of groups G(V, E ′ ) obtained by deleting all the edges outside the maximal subtree T . Since g is not hyperbolic in any splitting G = G i , t|C t = ϕ(C) , we may assume that g is in L and g is hyperbolic in L. Thus we can write L = L 1 * C L 2 with g is hyperbolic. We may suppose without loss of generality that A ≤ L 1 . By Lemma 3.2, there exists infinitely many automorphisms f i ∈ Aut A (L) whose restriction to L 1 is the identity and to L 2 a conjugation such that f i (g) is not conjugate to f j (g) and

C(f i (g)) = C(f j (g)) for i = j.
Since each f n sends each boundary subgroup to a conjugate of itself, f n has a natural extension fn to G. If we suppose that { fn (g); n ∈ N} is finite up to conjugacy (in G), then for infinitely many n, f n (g) is conjugate to an element of a vertex group; which is a contradiction. Hence { fn (g); n ∈ N} is infinite up to conjugacy (in G) and we see also that C(f n (g)) = C(f m (g)) for n = m (in G). This ends the proof of the proposition. Definition 3.3. Let G be a group and A a subgroup of G, c ∈ G. We say that c is malnormaly universally elliptic relative to A if c is elliptic in any malnormal abelian splitting of G relative to A. Proof. This follows from Proposition 3.1.

We write acl c (ā) = acl eq (ā) ∩ S E 0 , that is acl c (ā) is the set of conjugacy classes b F in acl eq (ā). For any subset A of a group G we also write A c = {b G | b ∈ A} for the set of conjugacy classes with representatives in A.

In the special case that G is free we do have the converse of Corollary 3.4. We can formulate the following list of equivalent criteria for a conjugacy class c F to be contained in the imaginary algebraic closure of a subset in the free group. Proposition 3.5. Let F be a free group of finite rank, A a nonabelian subgroup of F and c ∈ F . The following are equivalent:

(1) c F ∈ acl c (A).

(2) There exists finitely many automorphisms

f 1 , . . . , f p ∈ Aut A (F ) such that for any f ∈ Aut A (F ), f (c) is conjugate in F to some f i (c).
(3) c is malnormaly universally elliptic relative to A.

(4) In any generalized cyclic JSJ-decomposition of F relative to A, either c is conjugate to some element of the elliptic abelian neighborhood of a rigid vertex group or it is conjugate to an element of a boundary subgroup of a surface type vertex group.

Proof. (1) ⇒ (2). Suppose that there exists infinitely many automorphisms f i ∈ Aut A (F ) such that f i (c) is not conjugate to f j (c) for i = j. Then each f i has an unique extension fi to F eq and we get that fi (c F ) = fj (c F ) for i = j. Hence c F ∈ acl eq (A).

(2) ⇒ (3). This follows from Proposition 3.1 or Corollary 3.4.

(3) ⇒ (4). We let ∆ be a malnormal generalized cyclic JSJ-decomposition of F relative to A. Hence c is elliptic in ∆. Clearly c is not in a conjugate of the free factor of ∆. If c is in a conjugate of a rigid vertex group, there is nothing to prove. Otherwise c is in a conjugate of a surface type vertex group and without loss of generality we may assume that it is included. In this case, by [START_REF] Guirardel | JSJ decompositions: definitions, existence, uniqueness. I: The JSJ deformation space[END_REF]Proposition 7.6] (or by a general version of Lemma 2.6 and Proposition 3.1) c is in a conjugate of a boundary subgroup.

(4) ⇒ (2). Write F = F 1 * F 2 where F 1 contains A and freely A-indecomposable. Let ∆ be a malnormal cyclic JSJ-decomposition of F relative to A. Suppose that c is in some conjugate of a rigid vertex group or it is conjugate to an element of a boundary subgroup of a surface type vertex group in a generalized malnormal cyclic JSJ-decomposition of F relative to A. W.l.o.g, we can assume that it is contained in a rigid vertex group or it is contained in a boundary subgroup of a surface type vertex group. Since M od A (F 1 ) has finite index in Aut A (F 1 ) (Theorem 2.5), there are

f 1 , . . . , f p ∈ Aut A (F ) such that for any f ∈ Aut A (F 1 ) there exists σ ∈ M od A (F 1 ) such that f = f i • σ for some i. Since F 1 is freely A-indecomposable by Grushko theorem for any f ∈ Aut A (F ), f |F 1 ∈ Aut A (F 1 ). By Lemma 2.4, any σ ∈ M od A (F 1 ) sends c to a conjugate of itself. Hence f (c) = f i (c α ) = f i (c) f i (α) and thus for any f ∈ Aut A (F ), f (c) is conjugate to some f i (c).
(2) ⇒ (1). Since acl(A) is finitely generated (Theorem 2.9), we may assume that A is finitely generated. Write F = F 1 * F 2 where A ≤ F 1 and F 1 is freely A-indecomposable. Since F 1 is an elementary subgroup of F , c is a in a conjugate of F 1 . We assume that c = c ′g where c ′ ∈ F 1 .

By Proposition 2.10 let ϕ 0 (x) be a formula isolating the type of c ′ over ā where ā is a finite generating tuple of A. Let ϕ(z) be the following formula in the language L eq ϕ(z)

:= ∃x( φ0 (x) ∧ π(x) = z),
where φ0 is the relativisation of ϕ 0 to the real sort of F and π is the projection from the real sort of F to the sort of the conjugacy classes. Then F eq |= ϕ(c F ). We claim that ϕ has finitely many realizations, which shows that c F ∈ acl eq (A).

Let d F ∈ F eq such that F eq |= ϕ(d F ). Then there exists α ∈ F such that F |= ϕ 0 (α) and α F = d F . Since ϕ 0 isolates the type of c ′ over ā and F is homogeneous (Theorem 2.11), we conclude that there exists an automorphism f ∈ Aut A (F ) such that f (c ′ ) = α. Hence f (c) = α f (g) and thus α is conjugate to some f i (c) and thus d F = f i (c) F as required.

Remark 3.6. Let F be the free group with basis {a, b}. The following example shows that in the previous proposition we cannot remove the assumption that A be nonabelian. Let A be the subgroup generated by a. We claim that acl c (A) = A c . Indeed, let H = F * c| . Then F is an elementary subgroup of H as well as the subgroup K generated by a, c . Hence . Hence we see that the implication (2) ⇒ (1) is not true in this case. However if we suppose that A is abelian but not contained in a cyclic free factor in Proposition 3.5 then the same proof of (2) ⇒ (1) works in this case.

acl c (A) ⊆ H c ∩ K c = A c .
For later reference we also note the following: Corollary 3.7. Let H = Γ * F where F is a free group and Γ is a torsion-free hyperbolic group not elementarily equivalent to a free group. Let ā be a finite tuple from F generating a nonabelian subgroup. Then any conjugacy class g H ∈ acl c H (ā) has a representative g ′ either in Γ or in F . If g ′ ∈ Γ, then in fact g ′ H ∈ acl c H (1) = acl c Γ (1) and if g ′ ∈ F , then g ′ F ∈ acl c F (ā). Proof. Let A to be the subgroup generated by ā. The first part follows directly from Corollary 3.4. For the second part, just note that acl eq H (EC(Γ)) ∩ acl eq H (F ) = acl eq H (1) since EC(Γ) and F are independent by Corollary 2.14 or Lemma 2.15. Since EC(Γ)

Γ and EC(Γ)

Γ * F , we get acl c H (1) = acl c Γ (1). Let F n be a free factor of F of finite rank containing A. Again since EC(Γ) * F n H any g H ∈ acl c H (ā) has a representative g ′ in EC(Γ) * F n . If g ′ ∈ F and if we suppose that g ′ Fn ∈ acl c Fn (A) then by Proposition 3.5, we get infinitely many f n ∈ Aut A (F n ) such the f n (g ′ ) are pairwise non conjugate and each f n has a natural extension to H; which is a contradiction. Remark 3.8. Note that if Γ is elementarily equivalent to a free group then acl c Γ (1) = 1 c . Indeed, by elementary equivalence it is sufficient to show this when Γ is free. In that case we see that any g Γ ∈ acl c Γ (1) is also an element of acl c Γ (a) ∩ acl c Γ (b) where {a, b} is a part of a basis and we see that acl c Γ (a) = a c ; which gives the required conclusion. However it may be happen that acl c Γ (1) = Γ c when Γ is not elementarily equivalent to a free group. Indeed let Γ be a rigid torsion-free hyperbolic group. Then Out(Γ) is finite by Paulin's theorem [START_REF] Paulin | Topologie de Gromov équivariante, structures hyperboliques et arbres réels[END_REF] and Γ is homogeneous and prime by [START_REF] Houcine | Homogeneity and prime models in torsion-free hyperbolic groups[END_REF]. The same method as in the proof of Proposition 3.5 (2) ⇒ (1), shows that for any g ∈ Γ, g Γ ∈ acl c Γ (1).

For the equivalence relations E i , i = 1, 2, 3 given in Theorem 2.2, we denote the corresponding equivalence classes by [x] i , i = 1, 2, 3. We start with the following lemma: Lemma 3.9. Let H = Γ * F where Γ is torsion-free hyperbolic (possibly trivial) and F is a free group. For a finite tuple ā from F such that acl H (ā) = acl F (ā) and c ∈ H the following properties are equivalent:

(1) C(c) ∈ acl eq H (ā).

(2) c ∈ acl H (ā).

Proof. Clearly, (2) implies (1). Let A to be the subgroup generated by ā. If A is trivial the result is clear. To prove (1) implies (2) suppose first that A is abelian; so cyclic and generated by a. Let

f n (x) = x a n . If c ∈ acl(A) = C(a), then C(f n (c)) = C(f m (c))
for n = m. Hence C(c) / ∈ acl eq H (A). Suppose now that A is nonabelian. Let F p be a free factor of finite rank of F containing A and which is freely A-indecomposable and set F = ∈ acl eq H (A). Therefore we may assume that c is in a conjugate of F p . Proceeding as above we get c ∈ F p . Suppose now that c is not in a conjugate of acl(A). Write ∆ = (G(V, E), T, ϕ) and let L to be the fundamental group of the graph of groups obtained by deleting the edges which are outside T . Hence c is in a conjugate of L and without loss of generality we may assume that c ∈ L. Let e 1 , • • • , e q be the edges adjacent to acl(A) and let C i be the edge group corresponding to e i . Hence we can write L = L i1 * C i L i2 with acl(A) ≤ L i1 . Since c is elliptic and c is not in a conjugate of acl(A), we get, without loss of generality that c ∈ L i2 for some i. If c ∈ C i then c is in a conjugate of acl(A) contrary to our hypothesis. So c ∈ C i . Proceeding as in the proof of Proposition 3.1, we take infinitely many Dehn twists Then we find infinitely many automorphisms

f n ∈ Aut A (F n ) around C i if C i =
f i ∈ Aut A (F p ) such that f n (α) = f m (α) for n = m. Clearly, these f i extend to H. Hence C(f n (c)) = C(f n (d)) fn(α) = C(f m (c))
for infinitely many n, m and thus C(c) ∈ acl eq (A); a contradiction. We conclude that c ∈ acl(A). Proposition 3.10. Let H = Γ * F where Γ is torsion-free hyperbolic (possibly trivial) and F is a free group. For a finite tuple ā of F such that acl H (ā) = acl F (ā) and c, d, e ∈ H the following properties are equivalent:

(1) [(c, d)] 1 ∈ acl eq H (ā).

(2) c, d ∈ acl H (ā).

(

(x) = x a n . If d ∈ acl H (A) = C(a), then f n (d) ∈ f m (d)C(a) for n = m. Hence (f n (c), f n (d)) ∼ (f m (c), f m (d)) for n = m and thus [c, d] 1 ∈ acl eq (A); a contradiction. Therefore d ∈ C(a) = acl(A).
If A is nonabelian and d ∈ H \ acl(A), proceeding as in the proof of Lemma 3.9, we can again find infinitely many automorphisms

f i ∈ Aut A (F ) such that f n (d) ∈ f m (d)C(c) for n = m. Clearly, these f i extend to H and so [(c, d)] 1 / ∈ acl eq (A)
.

Recall that we write acl c (ā) = acl eq (ā) ∩ S E 0 . For any subset A of a group G we also write

A c = {b G | b ∈ A}
(acl eq (ā) ∩ F E ) ∩ (acl eq ( b) ∩ F E ) = acl eq (c) ∩ F E
where E is the set of equivalence relations given in Theorem 2.2. For E 0 this is assumption (1), for E 1 , E 2 , E 3 this follows from (2) and Proposition 3.10. Definition 3.12. Let G be a group and ā a tuple from G. We say that ā represents conjugacy (in

G) if acl c G (ā) = acl G (ā) c .
To verify the properties of an ample sequence in a free factor of a torsion-free hyperbolic group it now suffices to restrict to this free factor: Lemma 3.13. Let H = Γ * F where F is a free group and Γ is torsion-free hyperbolic not elementarily equivalent to a free group. For finite tuples ā, b, c ∈ F generating nonabelian subgroups, representing conjugacy in F and such that acl H (ā) = acl F (ā), acl H ( b) = acl F ( b), acl H (c) = acl F (c), we have acl eq F (ā) ∩ acl eq F ( b) = acl eq F (c) if and only if acl eq H (ā) ∩ acl eq H ( b) = acl eq H (c).

Proof. By Corollary 3.11 and the assumption on ā, b and c it suffices to verify that Corollary 3.14. Let H = Γ * F where F is a free group and Γ is torsion-free hyperbolic not elementarily equivalent to a free group. Suppose that a 0 , . . . , a n are finite tuples in F , each a i generating a nonabelian free factor of F and witnessing that F is n-ample and such that for 0 ≤ i ≤ k we have acl F (a 0 , . . . a i , a k ) = acl H (a 0 , . . . a i , a k ), acl c F (a 0 , . . . a i , a k ) = acl F (a 0 , . . . a i , a k ) c . Then a 0 , . . . , a n witness the fact that T h(Γ) is n-ample.

acl c F (ā) ∩ acl c F ( b) = acl c F (c)
Proof. This follows from Lemma 3.13 and Theorem 2.19.

The construction in the free group

In this section we will be working exclusively in nonabelian free groups and therefore all notions of algebraic closure and independence refer to the theory T f g . Our main objective here is to construct sequences witnessing the ampleness. Corollary 3.14 then allows us to transfer the results in Section 5 to torsion-free hyperbolic groups to obtain our main theorem.

Let H i = c i , d i , a i , b i | c i d i [a i , b i ] = 1 ,
that is H i is the fundamental group of an orientable surface with Proof. Since G 2k is a free factor we may work in G 2k . Let g ∈ G 2i ∩ acl(h 0 , h 2 , . . . , h 2i , h 2k ) and suppose towards a contradiction that g ∈ G 2i \ acl(h 0 , h 2 , . . . , h 2i ). Then there exist infinitely many automorphisms f p ∈ Aut(G 2i ) which fix h 0 , h 2 , . . . , h 2i such that f p (g) = f q (g) for p = q. Recall that has a natural extension to G 2k that we denote by fp and such that fp (g) = fq (g) for p = q. We see that each f p fixes h 0 , h 2 , . . . , h 2i , h 2k and fp (g) = fq (g) for p = q.

G 2k = G 2i *
Therefore g ∈ acl(h 0 , h 2 , . . . , h 2i , h 2k ); which is a contradiction.

Similarly if g G 2i ∈ G c 2i \ acl c (h 0 , h 2 , . . . , h 2i ) there exist infinitely many automorphisms f p ∈ Aut(G 2i ) which fix h 0 , h 2 , . . . , h 2i such that f p (g) and f q (g) are not conjugate for p = q. We extend these f p to G 2k as in the previous paragraph. Clearly fp (g) and fq (g) are not conjugate in G 2i * H 2i+1 * . . . * H 2k-1 * H 2k . Suppose towards a contradiction that { fp (g) | p ∈ N} is finite up to conjugacy in G 2k . By applying [6, Lemma 3.1] it follows that for p = q the pair (f p (g), f q (g)) is conjugate in G 2i * H 2i+1 * . . . * H 2k-1 * H 2k to a one of the pairs (d r j , c r j+1 ) for 2i ≤ j ≤ 2k -1 and r ∈ Z; this is clearly a contradiction. By Proposition 3.5 g G 2k ∈ acl c (h 0 , h 2 , . . . , h 2i , h 2k ); which is a contradiction. Proof. We first prove (i). By rewriting the splitting We prove (ii). We assume inductively that acl c (h 0 , h 2 , . . . , h 2i , h 2k ) = acl(h 0 , h 2 , . . . , h 2i , h 2k ) c .

G 2k = H 0 * H 1 * • • • * H 2k-1 * H 2k , t i , 0 ≤ i ≤ 2k -1 | d t i i = c i+1 , as G 2k = (H 0 * H 2 * • • • * H 2i * H 2k ) * K, t i , 0 ≤ i ≤ 2k -1 | d t i i = c i+1 ,

Theorem 2 . 19 .

 219 Let H = Γ * F where F is a free group and Γ is a torsion-free hyperbolic group not elementarily equivalent to a free group. For finite tuples ā, b ∈ F and a free factor C (possibly trivial) with finite basis c of F we have ā

H

  bc h. Therefore, again using transitivity and monotonicity of forking we have The proof is an adaptation of the argument in[START_REF] Perin | [END_REF] by using the characterisation of forking independence in F given in Proposition 2.16 and Proposition 2.17. Write F = C * D and let {d i : i < λ} be a basis of D.Since EC(Γ) * F Γ * F we may work in EC(Γ) * F and thus without loss of generality we assume that Γ = EC(Γ). Suppose that ā | ⌣ H hc b. Let D ′ be another copy of D with basis {d ′ i : i < λ} and consider H ′ = Γ * F * D ′ = Γ * C * D * D ′ . Let w(x; ȳ) be a tuple of words such that ā = w( d, c) and consider ā′ = w( d′ , c). Since H H ′ , we have ā | ⌣ H ′ hc b. Then ā | ⌣ H ′ hc b and ā′ | ⌣ H ′ hc b by Corollary 2.14 and Lemma 2.15. Since by Lemma 2.13, Γ * C is an elementary subgroup of H ′ , it is algebraically closed in H ′eq . It follows that for any ā ∈ F , tp(ā/ hc) is stationary; that is if ā′ , ā′′ , b ∈ F , tp(ā ′ / hc) = tp(ā ′′ / hc) = tp(ā/ hc) and a ′ | ⌣ H hc b, a ′′ | ⌣ H hc b then tp(ā ′ / bh c) = tp(ā ′′ / bh c). By stationarity we get tp H ′ (ā/ hc, b) = tp H ′ (ā ′ / hc, b) and in particular tp H ′ (ā/c, b) = tp H ′ (ā ′ /c, b). By Proposition 2.17, there exists an automorphism f of F * D ′ fixing c, b pointwise and sending ā′ to ā. We have F * D ′ = f (D) * C * f (D ′ ), ā ∈ C * f (D ′ ) and b ∈ f (D) * C. The conclusion now follows from Grushko's theorem. For the converse suppose that F = A * C * B, such that ā ∈ A * C, b ∈ C * B. Since ā, b, c are finite tuples we have a free factor F n of finite rank with the property

Corollary 3 . 4 .

 34 Let G be a torsion-free CSA-group and A a nonabelian subgroup of G. If c G or C(c) is in acl eq (A), then c is malnormaly universally elliptic relative to A.

  By a result of Neilsen (see for instance [5, Proposition 5.1]) any automorphism of F sends [a, b] to a conjugate of [a, b] or [a, b] -1

  F p * D. Let ∆ be the malnormal cyclic JSJdecomposition of F p relative to A. Extend this to a decomposition ∆ ′ of H = (Γ * D) * F p . Then by Theorem 2.8 and Proposition 2.7 the vertex group in ∆ ′ containing A is acl Fn (A) = acl F (A) = acl H (A) and by Corollary 3.4 c is elliptic with respect to ∆ ′ . Suppose that c is in a conjugate of Γ * D and set c = c a 0 with c 0 ∈ Γ * D. If a = 1, let f n denote the automorphism of H given by conjugation by a n on Γ * D and the identity on F p . Then clearly c a n and c a m do not centralize each other for n = m showing that C(c) / ∈ acl eq H (A). Hence a = 1 and c ∈ Γ * D. Again let a ∈ F p and let f n denote the automorphism of H given by conjugation by a n on Γ * D and the identity on F p . As above c a n and c a m do not centralize each other for n = m showing that C(c) /

  1 and a conjugation by a nontrivial element of L i1 if C i = 1 and thus we find C(f n (c)) = C(f m (c)) for n = m. Now each f n has a standard extension fn ∈ Aut A (H) and we see also that C( fn (c)) = C( fm (c)) for n = m. It follows that C(c) ∈ acl eq (A); a contradiction. Hence c is in a conjugate of acl(A). Suppose that c = d α with d ∈ acl(A) and α ∈ F p \ acl(A).

Lemma 4 . 6 .

 46 For 0 ≤ i ≤ k we have(i) acl(h 0 , h 2 , . . . , h 2i , h 2k ) = H 0 * H 2 * • • • * H 2i * H 2k and (ii) acl c (h 0 , h 2 , . . . , h 2i , h 2k ) = acl(h 0 , h 2 , . . . , h 2i , h 2k ) c

  and [7, Lemma 8.10], if e ∈ F is a primitive element then tp(e/EC(Γ)) is the unique generic type of H over EC(Γ). If h is a generating tuple for EC(Γ) we therefore have e | ⌣ H h for any primitive element e ∈ F . Again combining Lemma 2.13 and [7, Lemma 8.10] we conclude that ē | ⌣ It follows that the e i form a Morley sequence in the sense of T H over G. Clearly, the e i are indiscernible over any finite subset A ⊂ G. Therefore (see e.g. [19, Lemma 7.2.19])

H h for any basis ē of F . The result now follows.

In a free group of infinite rank, we obtain the following of indepedent interest: Lemma 2.15. Suppose that G is a group such that the theory T H of H = G * F is simple where F is a free group of infinite rank. Then G | ⌣ F.

Proof. Let {e i : i < ω} be part of a basis for F . By using Poizat's observation as in

[START_REF] Pillay | Forking in the free group[END_REF]

, if X is a definable generic subset of H with parameters from G, X contains all but finitely many elements of any basis of F .

  using [9, Corollary 2.7] and Theorem 2.11. Proposition 2.16. [13] Let F be a free group of finite rank, ā, b be finite tuples from F and C a free factor of F . Then ā | ⌣

C b if and only if

  . Let h be a generating tuple for EC(Γ). By Corollary 2.14 or Lemma 2.15 we have āc | ⌣ H h and āb c | ⌣ H h. Using transitivity and monotonicity of forking in stable theories (see e.g. [19, Corollary 7.2.17]) we have hence ā | ⌣

H c h and ā | ⌣

  By Lemma 2.13 and[START_REF] Houcine | Homogeneity and prime models in torsion-free hyperbolic groups[END_REF] Lemma 8.10], if {e 1 , • • • , e n } is a basis of A ∩ F n and {e ′ 1 , • • • , e ′ m} is a basis of B ∩ F n , then they are independent realisations of the generic type over hc. The result follows by the same argument as in the proof of Corollary 2.14.

  ) [(c, d)] 2 ∈ acl eq H (ā). Similarly we have [(c, d, e)] 3 ∈ acl eq H (ā) if and only if c, d, e ∈ acl H (ā).Proof. Let A to be the subgroup generated by ā. The implications (2) ⇒ (1) and (2) ⇒ (3) are clear. By symmetry it suffices to prove (1) ⇒ (2). By Lemma 3.9, we have c ∈ acl H (A).If A is abelian and generated by a, let f n

  for the set of conjugacy classes with representatives in A.Corollary 3.11. Let H = Γ * F where Γ is torsion-free hyperbolic (possibly trivial) and F is a nonabelian free group. For finite tuples ā, b, c ∈ F we have Proof. By Theorem 2.12 we have Γ * F 2 is elementarily equivalent to H and thus we can apply Theorem 2.2.One direction is clear. For the other direction, by Theorem 2.2 and Remark 2.1 it suffices to show that

		acl eq	H (ā) ∩ acl eq	H ( b) = acl eq	H (c)
	if and only if
	(1)	acl c H (ā) ∩ acl c H ( b) = acl c H (c)
	and
	(2)	acl

H (ā) ∩ acl H ( b) = acl H (c).

  But this follows from Corollary 3.7 and the assumption that the considered tuples represent conjugacy: for any nonabelian subgroup A ≤ F the conjugacy classes in acl c H (A) have representatives either in acl c F (A) or in acl c H (1) and since ā say represent conjugacy in F we have in fact that g H ∈ acl c H (ā) if and only if either g H ∈ acl c H (1) or g has a representative g ′ ∈ F such that g ′F ∈ acl c F (ā).

	if and only if	acl c H (ā) ∩ acl c H ( b) = acl c H (c).

  2 boundary components and genus 1, where c i and d i are the generators of boundary subgroups. Note that H i is a free group of rank 3 with bases a i , b i , c i or a i , b i , d i . LetP n = H 0 * H 1 * • • • * H n-1 * H n , Lemma 4.5. For 0 ≤ i < k we have G 2i ∩ acl(h 0 , h 2 , . . . , h 2i , h 2k ) = acl(h 0 , h 2 , . . . , h 2i )andG c 2i ∩ acl c (h 0 , h 2 , . . . , h 2i , h 2k ) = acl c (h 0 , h 2 , . . . , h 2i ).

  H 2i+1 * . . . * H 2k-1 * H 2k , t j , 2i ≤ j ≤ 2k -1 | d t j j = c j+1 . We extend each f p to G 2i * H 2i+1 * . . . * H 2k-1 *H 2k by the identity on the factor H 2i+1 * . . . * H 2k-1 * H 2k . Hence each f p

  where K is the free product of the remaining of the H i , we get a malnormal cyclic splitting in whichH 0 * H 2 * • • • * H 2i * H 2k is a vertex group. Hence by Proposition 2.7 acl(h 0 , h 2 , . . . , h 2i , h 2k ) = H 0 * H 2 * • • • * H 2i * H 2kas required.

Acknowledgement: The authors would like to thank Zlil Sela, Anand Pillay and Gilbert Levitt for helpful discussions.

The author was supported by SFB 878.

and

Remark 4.1. Note that for any k < n we have

One of the principal properties that we will use is that gluing together surfaces on boundary subgroups gives new surfaces. For i ≥ 0, let h i = (a i , b i , c i ) be the given basis of H i . We are going to show that the sequence h 0 , h 2 , . . . , h 2n is a witness for the n-ample property in G 2n . The proof is divided into a sequence of lemmas. Lemma 4.2.

(1) For 0 ≤ i ≤ n, G i is a free factor of G n and G n is a free group of rank 3(n + 1).

(2) For each 0 ≤ i ≤ n, H i is a free factor of G n .

Proof. [START_REF] Champetier | Limit groups as limits of free groups: compactifying the set of free groups[END_REF] The proof is by induction on n. For n = 0, we already noted that G 0 = H 0 is a free group of rank 3. For the induction step it suffices to show that G n is a free factor of G n+1 with a complement which is free of rank 3. We have

and since c n+1 is primitive in c n+1 , a n+1 , b n+1 | , the free group generated by t n , a n+1 , b n+1 is a free factor in G n+1 . This proves the claim.

(2) In view of (1) it suffices to show by induction on i that H i is a free factor of G i for 0 ≤ i ≤ n. For i = 0, there is nothing to prove. For i + 1, we have as above

and since by induction H i is a free factor of G i , d i is primitive in G i . In particular, d t i i is primitive in (G i * t i | ) and we conclude that H i+1 is a free factor of G i+1 , as required.

for a surface group S with

Proof. We have

where

Replacing successively and setting s -1 i = t 0 . . . t i we obtain:

, and

.

Then

Then

As S is the fundamental group of an orientable surface with genus ≥ 1 and two boundary subgroups generated by c 0 and d ′ n we may apply Lemma 2.6 to S and obtain the following corollary:

Corollary 4.4. Suppose n = 2k ≥ 2 and g ∈ G n \ {1} is not conjugate to a power of c 0 or of d n . Then there exists a malnormal cyclic splitting of G n such that c 0 and d n are elliptic and g is hyperbolic.

Proof. Write g = g 1 • • • g k in normal form with respect to the splitting appearing in Lemma 4.3. W.l.o.g, we may assume that g is cyclically reduced. If k ≥ 2, then g is hyperbolic in the given malnormal splitting. Hence we may assume that g ∈ S or g ∈ t i | for some i ≤ n -1.

If g ∈ S, by Lemma 2.6, there exists a malnormal cyclic splitting S in which g is hyperbolic and c 0 and d n are elliptic. This yields a refinement of the cyclic splitting of G n in Lemma 4.3 in which g is hyperbolic.

Next suppose that g ∈ t 0 | . For any

the same proof works and we are done.

Recall that for i ≥ 0, h i = (a i , b i , c i ). Having diposed by some needed properties of G n in the previous lemmas, we are now ready to show that the sequence h 0 , h 2 , . . . , h 2n satisfies conditions of Definition 1.1. Since G i is a free factor of G k for 0 ≤ i ≤ k which implies that G i is an elementary subgroup of G k , in computing the algberaic closure -as well as the imganiary algebraic closureof tuples of

Suppose first that c is in a conjugate of L and thus w.l.o.g, we may assume that c ∈ L. Note that L ∼ = G 2m with m = ki -1. By Corollary 4.4 when 2m ≥ 2 and Lemma 2.6 when 2m = 0, if c is not conjugate to an element of c 2i+1 or d 2k-1 then L has a malnormal cyclic splitting such that c 2i+1 and d 2k-1 are elliptic and c is hyperbolic. Hence we get a refinement of the previous splitting of G 2k where K is still a vertex group and such that c is hyperbolic, contradicting Corollary 3.4.

Therefore c is either conjugate to an element of c 2i+1 or of d 2k-1 . But since d

Suppose now that c is in a conjugate of K and thus w.l.o.g, we may assume that c ∈ K. Write c = g 1 • • • g in form with respect to the free product structure of K = G 2i * H 2k . Since any element is conjugate to a cyclically reduced one, w.l.o.g, we may assume that c is cyclically reduced

by Lemma 4.5 and induction hypothesis. If m > 1, we claim that for any 1 ≤ l ≤ m if g l ∈ G 2i then g l ∈ acl(h 0 , h 2 , . . . , h 2i ) and so c ∈ acl(h 0 , h 2 , . . . , h 2i , h 2k ). Suppose towards a contradiction that g l ∈ G 2i \acl(h 0 , h 2 , . . . , h 2i ) for some 1 ≤ l ≤ m. Then proceeding as in the proof of Lemma 4.5 there exist infinitely many automorphisms f p ∈ Aut(K) fixing h 0 , h 2 , . . . , h 2i , h 2k and with f p (c) = f q (c) for p = q. Each f p has a natural extension to G 2k that we denote by fp and such that fp (c) = fq (c) for p = q.

Suppose that the set {f p (c) | p ∈ N} is finite up to conjugacy in K. Hence there exists an infinite set I ⊆ N and p 0 such that f p (c) is conjugate to f p 0 (c) for every p ∈ I. We see that f p (c) = f p (g 1 ) • • • f p (g k ) and (f p (g 1 ), . . . , f p (g k )) is a normal form and f p (c) = f p (g 1 ) • • • f p (g k ) is cyclically reduced. Therefore (f p (g 1 ), . . . , f p (g k )) is a cyclic permutation of (f p 0 (g 1 ), . . . , f p 0 (g k )). Since the number of such cyclic permutations is finite, we conclude that there exists p = q ∈ I such that f p (c) = f q (c) and thus f p (g l ) = f q (g l ), a contradiction.

Hence the set {f p (c) | p ∈ N} is infinite up to conjugacy in K. Suppose towards a contradiction that { fp (c) | p ∈ N} is finite up to conjugacy in G 2k . Since { fp (c) | p ∈ N} is infinite up to conjugacy in K, we conclude that there exists p = q such that f p (g) is conjugate to f q (c) in G 2k and f p (c) is not conjugate to f q (c) in K * L. By applying [6, Lemma 3.1] it follows that the pair (f p (c), f q (c)) is conjugate in K * L to a one of the pairs (d r 2i , c r 2i+1 ), (d r 2k-1 , c r 2k ) for some r ∈ Z; this is clearly a contradiction as f p (c), f q (c) ∈ K. Hence the set { fp (c) | p ∈ N} is infinite up to conjugacy in G 2k and by Proposition 3.5 c G 2k ∈ acl c (h 0 , h 2 , . . . , h 2i , h 2k ); which is a contradiction. Proof. As G 2 is a free factor, we work in F = G 2 . Let a ∈ acl( h0 ) ∩ acl( h2 ). Since acl( h0 ) = H 0 , acl( h2 ) = H 2 and a ∈ acl( h0 , h2 ) = H 0 * H 2 we conclude that a = 1. We note that acl(1) = acl(∅). Let a F ∈ acl c ( h0 ) ∩ acl c ( h2 ). Therefore a F ∈ H c 0 ∩ H c 2 . Hence there exists α ∈ H 0 , β ∈ H 2 such that α F = β F = a F . Suppose that α = 1. Clearly α and β are not conjugate in

By applying [6, Lemma 3.1] it follows that the pair (α, β) is conjugate in P 2 to a one of the pairs (d r 0 , c r 1 ), (c r 1 , d r 0 ), (d r 1 , c r 2 ), (c r 2 , d r 1 ) for some r ∈ Z; this a contradiction. Therefore a F = 1 F . By Remark 3.8 we have acl c (∅) = acl c (1) = {1 F } which concludes the proof. Lemma 4.8. For i ≥ 0 we have the following: acl(h 0 , h 2 , . . . , h 2(i-1) , h 2i ) ∩ acl(h 0 , h 2 , . . . , h 2(i-1) , h 2(i+1) ) = acl h 0 , h 2 , . . . , h 2(i-1) ) and acl c (h 0 , h 2 , . . . , h 2(i-1) , h 2i ) ∩ acl c (h 0 , h 2 , . . . , h 2(i-1) , h 2(i+1) ) = acl c (h 0 , h 2 , . . . , h 2(i-1) ).

Proof. We may work in F = G . first result follows from Lemma 4.6 and normal forms: if

By Lemma 4.6 (ii) there exist α ∈ acl(h 0 , h 2 , . . . , h 2(i-1) , h 2i ) and β ∈ acl(h 0 , h 2 , . . . , h 2(i-1) , h 2(i+1) ) such that α F = β F = c F . We have

First suppose that α and

, it follows from properties of normal forms that α is conjugate to an element of G 2(i-1) . But since α ∈ acl(h 0 , h 2 , . . . , h 2(i-1) ) * H 2i it follows that α is conjugate to an element of acl(h 0 , h 2 , . . . , h 2(i-1) ); which is the required result. Now suppose that α and

. Then α (and similarly β) is conjugate in L to a power of one the elements

Since α ∈ G 2(i-1) * H 2i , we conclude that α is conjugate to a power of c 2i or d 2i or d 2(i-1) . Similarly, since β ∈ G 2(i-1) * H 2(i+1) , we conclude that β is conjugate to a power of c 2(i+1) or d 2(i-1) .

If α is conjugate to a power of c 2i then β is conjugate (in L ) to a power of d 2i-1 ; which is a contradiction. Similarly, if α is conjugate to a power of d 2i then β is conjugate (in L ) to a power of c 2i+1 ; which is also a contradiction. Hence α is conjugate to d 2(i-1) and thus c F ∈ acl c (h 0 , h 2 , . . . , h 2(i-1) ) as required.

By Corollary 3.11 we thus have proved the following: Corollary 4.9. We have acl eq (h 0 ) ∩ acl eq (h 2 ) = acl eq (∅)

and for i ≥ 1 acl eq (h 0 , h 2 , . . . , h 2(i-1) , h 2i ) ∩ acl eq (h 0 , h 2 , . . . , h 2(i-1) , h 2(i+1) ) = acl eq (h 0 , h 2 , . . . , h 2(i-1) ).

To finish the proof of the fact that our sequence is a witness for the n-ample property we prove the two next lemmas which yield the required properties of independence. Lemma 4.10. For i = 1, . . . , n -1, there exists a free decomposition

and thus we can write G 2i-1 = K 0 * d 2i-1 for some free group K 0 . Similarly, c 2i+1 is primitive in L i and thus we can write L i = c 2i+1 * L 0 for some free group L 0 .

Therefore

and by setting

Lemma 4.11. There is no free decomposition G n = K * L such that h 0 ∈ K and h n ∈ L.

Proof. Suppose towards a contradiction that such a free decomposition exists. Since H i is a free factor, it follows that H 0 is a free factor of K and H n is a free factor of L. Since c 0 is primitive in H 0 it is primitive in K and since d n is primitive in H n it is primitive in K. We conclude that {c 0 , d n } is part of a basis of G n . Therefore in the abelianisation

However in G ab n we have c i d i = 1 = c i+1 and thus c 0 = d ±1 n depending on whether n is odd or even, a contradiction. By Proposition 2.16 we have thus proved the following: Corollary 4.12. We have

Putting Corollary 4.9 and Corollary 4.12 together we therefore have proved the following:

Theorem 4.13. The u i = h 2i ∈ G 2n , i = 0, . . . n witness the fact that T f g is n-ample, i.e. we have the following:

iii) acl eq (u 0 ) ∩ acl eq (u 1 ) = acl eq (∅). (iv) acl eq (u 0 , u 1 , . . . , u i-1 , u i ) ∩ acl eq (u 0 , u 1 , . . . , u i-1 , u i+1 ) = acl eq (u 0 , u 1 , . . . , u i-1 ).

Remark 4.14. In fact, since

iii) acl eq (u 0 ) ∩ acl eq (u 1 ) = acl eq (∅). (iv) acl eq (u 0 , u 1 , . . . , u i-1 , u i ) ∩ acl eq (u 0 , u 1 , . . . , u i-1 , u i+1 ) = acl eq (u 0 , u 1 , . . . , u i-1 ). In particular, F ω contains an explicit sequence (u n : n < ω) such that for every n the finite sequence u 0 , u 1 , • • • , u n is a witness of the n-ampleness.

We now move back to working in a torsion-free hyperbolic group. Let H = Γ * G 2n where Γ is torsion-free hyperbolic and G 2n is as before. In order to finish the proof of the main theorem we just need the following observation: Lemma 5.1. With h 0 , h 2 , . . . , h 2n defined as in Section 4, we have for 0 ≤ i ≤ k acl G 2n (h 0 , h 2 , . . . , h 2i , h 2k ) = acl H (h 0 , h 2 , . . . , h 2i , h 2k ).

Proof. By Lemma 4. [START_REF] Lyndon | Combinatorial group theory[END_REF] ⌣ u i u i+1 for 1 ≤ i < n; (iii) acl eq (u 0 ) ∩ acl eq (u 1 ) = acl eq (∅). (iv) acl eq (u 0 , u 1 , . . . , u i-1 , u i ) ∩ acl eq (u 0 , u 1 , . . . , u i-1 , u i+1 ) = acl eq (u 0 , u 1 , . . . , u i-1 ).


F Ben Saïd

J.-L Nicolas
email: jlnicola@in2p3.fr

Kálmán Győry

Attila Pethő

János Pintz

On the counting function of sets with even partition functions by

Keywords:

, it is proved that if A(P, x) is the counting function of the set A(P ) then A(P, x) ≪ x(log x) -r/ϕ(q) , where r is the order of 2 modulo q and ϕ is the Euler's function. In this paper, we improve on the constant c = c(q) for which A(P, x) ≪ x(log x) -c .

1 Introduction.

Let N be the set of positive integers and A = {a 1 , a 2 , ...} be a subset of N. For n ∈ N, we denote by p(A, n) the number of partitions of n with parts in A, i.e. the number of solutions of the equation a 1 x 1 + a 2 x 2 + ... = n, in non-negative integers x 1 , x 2 , .... We set p(A, 0) = 1.

Let F 2 be the field with two elements and f = 1 + ǫ 1 z + ...

+ ǫ N z N + • • • ∈ F 2 [[z]
]. Nicolas et al proved (see [START_REF] Nicolas | On the parity of additive representation functions[END_REF], [START_REF] Saïd | On some sets with even valued partition function[END_REF] and [START_REF] Lahouar | Fonctions de partitions à parité périodique[END_REF]) that there is a unique subset A = A(f ) of N such that ∞ n=0 p(A, n)z n ≡ f (z) (mod 2).

(1.1)

When f is a rational fraction, it has been shown in [START_REF] Lahouar | Fonctions de partitions à parité périodique[END_REF] that there is a polynomial U such that A(f ) can be easily determined from A(U ). When f is a general power series, nothing about the behaviour of A(f ) is known. From now on, we shall restrict ourselves to the case f = P , where

P = 1 + ǫ 1 z + ... + ǫ N z N ∈ F 2 [z]
is a polynomial of degree N ≥ 1.

Let A(P, x) be the counting function of the set A(P ), i.e.

A(P, x) =| {n : 1 ≤ n ≤ x, n ∈ A(P )} | .

(1.2)

In [START_REF] Dai | On the parity of the partition function[END_REF], it is proved that

A(P, x) ≥ log x log 2 - log(N + 1) log 2 . (1.3)
More attention was paid on upper bounds for A(P, x). In [5, Theorem 3], it was observed that when P is a product of cyclotomic polynomials, the set A(P ) is a union of geometric progressions of quotient 2 and so A(P, x) = O(log x).

Let the decomposition of P into irreducible factors over F 2 [z] be

P = P α 1 1 P α 2 2 • • • P α l l .
We denote by β i , 1 ≤ i ≤ l, the order of P i (z), that is the smallest positive integer such that

P i (z) divides 1 + z β i in F 2 [z]
; it is known that β i is odd (cf. [START_REF] Lidl | Introduction to finite fields and their applications[END_REF]). We set

q = q(P ) = lcm(β 1 , β 2 , ..., β l ). (1.4)
If q = 1 then P (z) = 1 + z and A(P ) = {2 k , k ≥ 0}, so that A(P, x) = O(log x). We may suppose that q ≥ 3. Now, let

σ(A, n) = d | n, d∈A d = d | n dχ(A, d), (1.5)
where χ(A, .) is the characteristic function of the set A,

χ(A, d) = 1 if d ∈ A 0 otherwise.
In [START_REF] Saïd | Sets of parts such that the partition function is even[END_REF] (see also [START_REF] Saïd | On a conjecture of Nicolas-Sárközy about partitions[END_REF] and [START_REF] Baccar | On the divisor function of sets wiht even partition functions[END_REF]), it is proved that for all k ≥ 0, q is a period of the sequence (σ(A, 2 k n) mod 2 k+1 ) n≥1 , i.e.

n 1 ≡ n 2 (mod q) ⇒ σ(A, 2 k n 1 ) ≡ σ(A, 2 k n 2 ) (mod 2 k+1 ) (1.6)
and q is the smallest integer such that (1.6) holds for all k ′ s. Moreover, if n 1 and n 2 satisfy n 2 ≡ 2 a n 1 (mod q) for some a ≥ 0, then

σ(A, 2 k n 2 ) ≡ σ(A, 2 k n 1 ) (mod 2 k+1 ). (1.7)
If m is odd and k ≥ 0, let

S A (m, k) = χ(A, m) + 2χ(A, 2m) + . . . + 2 k χ(A, 2 k m). (1.8)
It follows that for n = 2 k m, one has

σ(A, n) = σ(A, 2 k m) = d | m dS A (d, k), (1.9)
which, by Möbius inversion formula, gives

mS A (m, k) = d | m µ(d)σ(A, n d ) = d | m µ(d)σ(A, n d ), (1.10)
where µ is the Möbius's function and m = p | m p is the radical of m, with 1 = 1.

In [START_REF] Saïd | Even partition functions[END_REF] and [START_REF] Ben Saïd | On the parity of generalised partition function III[END_REF], precise descriptions of the sets A(1 + z + z 3 ) and A(1

+ z + z 3 + z 4 + z 5
) are given and asymptotics to the related counting functions are obtained,

A(1 + z + z 3 , x) ∼ c 1 x (log x) 3 4 , x → ∞, (1.11)
A(1

+ z + z 3 + z 4 + z 5 , x) ∼ c 2 x (log x) 1 4 , x → ∞, (1.12)
where c 1 = 0.937..., c 2 = 1.496.... In [START_REF] Baccar | On sets such that the partition function is even from a certain point on[END_REF], the sets A(P ) are considered when P is irreducible of prime order q and such that the order of 2 in (Z/qZ) * is q-1 2 . This situation is similar to that of A(1 + z + z 3 ), and formula (1.11) can be extended to A(P, x) ∼ c ′ x(log x) -3/4 , x → ∞, for some constant c ′ depending on P .

Let P = QR be the product of two coprime polynomials in F 2 [z]. In [START_REF] Saïd | On some sets with even valued partition function[END_REF], the following is given

A(P, x) ≤ A(Q, x) + A(R, x) (1.13)
and

| A(P, x) -A(R, x) |≤ 0≤i≤ log x log 2 A(Q, x 2 i ). (1.14)
As an application of (1.14), choosing Q = 1 + z + z 3 , R = 1 + z + z 3 + z 4 + z 5 and P = QR, we get from (1.11)-(1.14),

A(P, x) ∼ A(R, x) ∼ c 2 x(log x) -1/4 , x → ∞.
In [START_REF] Ben Saïd | On the counting function of the sets of parts such that the partition function takes even values for n large enough[END_REF], a claim of Nicolas and Sárközy [START_REF] Nicolas | On the parity of generalised partition functions[END_REF], that some polynomials with A(P, x) ≍ x may exist, was disapproved. More precisely, the following was obtained Theorem 1.1. Let P ∈ F 2 [z] be such that P (0) = 1, A = A(P ) be the unique set obtained from (1.1) and q be the odd number defined by (1.4). Let r be the order of 2 modulo q, that is the smallest positive integer such that 2 r ≡ 1 (mod q). We shall say that a prime p = 2 is a bad prime if

∃ i, 0 ≤ i ≤ r -1 and p ≡ 2 i (mod q). (1.15) (i) If p is a bad prime, we have gcd(p, n) = 1 for all n ∈ A.
(ii) There exists an absolute constant c 3 such that for all x > 1,

A(P, x) ≤ 7(c 3 ) r x (log x) r ϕ(q) , (1.16)
where ϕ is Euler's function.

2 The sets of bad and semi-bad primes.

Let q be an odd integer ≥ 3 and r be the order of 2 modulo q. Let us call "bad classes" the elements of

E(q) = {1, 2, ..., 2 r-1 } ⊂ (Z/qZ) * . (2.1)
From (1.15), we know that an odd prime p is bad if p mod q belongs to E(q). The set of bad primes will be denoted by B. The fact that no element of A(P ) is divisible by a bad prime (cf. Theorem 1.1 (i)) has given (cf. [START_REF] Ben Saïd | On the counting function of the sets of parts such that the partition function takes even values for n large enough[END_REF]) the upper bound (1.16). Two other sets of primes will be used to improve (1.16) cf. Theorem 2.1 below.

Remark 2.1. 2 is not a bad prime although it is a bad class.

Definition 2.1. A class of (Z/qZ) * is said semi-bad if it does not belong to E(q) and its square does. A prime p is called semi-bad if its class modulo q is semi-bad. We denote by E ′ (q) the set of semi-bad classes, so that

p semi-bad ⇐⇒ p mod q ∈ E ′ (q).
We denote by |E ′ (q)| the number of elements of E ′ (q). Lemma 2.1. Let q be an odd integer ≥ 3, r be the order of 2 modulo q and

q 2 = 1 if 2 is a square modulo q 0 if not.
The number |E ′ (q)| of semi-bad classes modulo q is given by

|E ′ (q)| = 2 ω(q) r + 1 2 + q 2 r 2 -r = r(2 ω(q)-1 -1) if r is even and q 2 = 0 r(2 ω(q) -1) otherwise, (2.2)
where ω(q) is the number of distinct prime factors of q and ⌊x⌋ is the floor of x.

Proof. We have to count the number of solutions of the r congruences

E i : x 2 ≡ 2 i (mod q), 0 ≤ i ≤ r -1,
which do not belong to E(q). The number of solutions of E 0 is 2 ω(q) . The contribution of E i when i is even is equal to that of E 0 by the change of variables x = 2 i/2 ξ, so that the total number of solutions, in (Z/qZ) * , of the

E ′ i s for i even is equal to r+1 2 2 ω(q) .
The number of odd i ′ s,

0 ≤ i ≤ r -1, is equal to r 2 .
The contribution of all the E ′ i s for these i ′ s are equal and vanish if q 2 = 0. When q 2 = 1, E 1 has 2 ω(q) solutions in (Z/qZ) * . Hence the total number of solutions, in (Z/qZ) * , of the E ′ i s for i odd is equal to q 2 r 2 2 ω(q) . Now, we have to remove those solutions which are in E(q). But any element 2 i , 0 ≤ i ≤ r-1, from E(q) is a solution of the congruence x 2 ≡ 2 j (mod q), where j = 2i mod r. Hence

|E ′ (q)| = 2 ω(q) r + 1 2 + q 2 r 2 -r.
The second formula in (2.2) follows by noting that q 2 = 1 when r is odd.

Definition 2.2. A set of semi-bad classes is called a coherent set if it is not empty and if the product of any two of its elements is a bad class.

Lemma 2.2. Let b be a semi-bad class; then

C b = {b, 2b, . . . , 2 r-1 b}
is a coherent set. There are no coherent sets with more than r elements.

Proof. First, we observe that, for 0 ≤ u ≤ r -1, 2 u b is semi-bad and, for 0

≤ u < v ≤ r -1, (2 u b)(2 v b) is bad so that C b is coherent.
Further, let F be a set of semi-bad classes with more than r elements; there exists in F two semi-bad classes a and b such that a / ∈ C b . Let us prove that ab is not bad. Indeed, if ab ≡ 2 u (mod q) for some u, we would have a ≡ 2 u b -1 (mod q). But, as b is semi-bad, b 2 is bad, i.e. b 2 ≡ 2 v (mod q) for some v, which would imply b ≡ 2 v b -1 (mod q), b -1 ≡ b2 -v (mod q), a ≡ 2 u-v b (mod q) and a ∈ C b , a contradiction. Therefore, F is not coherent. Lemma 2.3. If ω(q) = 1 and ϕ(q)/r is odd, then E ′ (q) = ∅; while if ϕ(q)/r is even, the set of semi-bad classes E ′ (q) is a coherent set of r elements.

If ω(q) ≥ 2, then E ′ (q) = ∅ and there exists a coherent set C with |C| = r.

Proof. If ω(q) = 1, q is a power of a prime number and the group (Z/qZ) * is cyclic. Let g be some generator and d be the smallest positive integer such that g d ∈ E(q), where E(q) is given by (2.1). We have d = ϕ(q)/r, since d is the order of the group (Z/qZ) * / E(q) . The discrete logarithms of the bad classes are 0, d, 2d, • • • , (r -1)d. The set E ′ (q) ∪ E(q) is equal to the union of the solutions of the congruences

x 2 ≡ g ad (mod q) (2.3)
for 0 ≤ a ≤ r -1. By the change of variable x = g t , (2.3) is equivalent to 2t ≡ ad (mod ϕ(q)).

(2.4)

Let us assume first that d is odd so that r is even. If a is odd, the congruence (2.4) has no solution while, if a is even, say a = 2b, the solutions of (2.4) are t ≡ bd (mod ϕ(q)/2) i.e. t ≡ bd (mod ϕ(q)) or t ≡ bd + (r/2)d (mod ϕ(q)), which implies E ′ (q) ∪ E(q) = {g 0 , g d , . . . , g (r-1)d } = E(q)

and E ′ (q) = ∅.

Let us assume now that d is even. The congruence (2.4) is equivalent to

t ≡ ad/2 (mod ϕ(q)/2) which implies E ′ (q) ∪ E(q) = {g αd/2 , 0 ≤ α ≤ 2r -1} yielding E ′ (q) = {g d 2 , g 3 d 2 , • • • , g (2r-1) d 2 } = C b (with b = (g d 2 )
), which is coherent by Lemma 2.2.

If ω(q) ≥ 2, then, by Lemma 2.1, E ′ (q) = ∅. Let b ∈ E ′ (q); by Lemma 2.2, the set C b is a coherent set of r elements.

Let us set

c(q) = 3 2 if E ′ (q) = ∅ 1 if E ′ (q) = ∅.
(2.5)

We shall prove Theorem 2.1. Let P ∈ F 2 [z] with P (0) = 1, q be the odd integer defined by (1.4) and r be the order of 2 modulo q. We denote by A(P ) the set obtained from (1.1) and by A(P, x) its counting function. When x tends to infinity, we have

A(P, x) ≪ q x (log x) c(q) r ϕ(q) , (2.6)
where c(q) is given by (2.5).

When P is irreducible, q is prime and r = q-1 2 , the upper bound (2.6) is best possible; indeed in this case, from [START_REF] Baccar | On sets such that the partition function is even from a certain point on[END_REF], we have A(P, x) ≍ x (log x) 3/4 . As ϕ(q)/r = 2, Lemma 2.3 implies E ′ (q) = ∅ so that c = 3/2 and in (2.6), the exponent of log x is 3/4. Moreover, formula (1.12) gives the optimality of (2.6) for some prime (q = 31) satisfying r = q-1 6 .

Theorem 2.2. Let P ∈ F 2 [z] be such that P (0) = 1 and P = P 1 P 2 • • • P j , where the P ′ i s are irreducible polynomials in F 2 [z]. For 1 ≤ i ≤ j, we denote by q i the order of P i , by r i the order of 2 modulo q i and we set c = min 1≤i≤j c(q i )r i /ϕ(q i ), where c(q i ) is given by (2.5). When x tends to infinity, we have

A(P, x) ≪ x (log x) c • (2.7)
where the symbol ≪ depends on the q ′ i s,

1 ≤ i ≤ j.
Let C be a coherent set of semi-bad classes modulo q. Let us associate to C the set of primes S defined by p ∈ S ⇐⇒ p mod q ∈ C.

We define ω S as the additive arithmetic function

ω S (n) = p | n, p∈S 1. (2.9)
Lemma 2.4. Let m be an odd positive integer, not divisible by any bad prime.

If ω S (m) = k + 2 ≥ 2 then 2 h m ∈ A(P ) for all h, 0 ≤ h ≤ k. In other words, if 2 h m ∈ A(P ), then h ≥ ω S (m) -1 holds. Proof. Let us write m = m ′ m", with m ′ = p | m, p∈S p and m" = p | m, p ∈S p. From (1.10), if n = 2 k m then mS A (m, k) = d | m µ(d)σ(A, n d ) = d ′ | m ′ d" | m" µ(d ′ )µ(d")σ(A, n d ′ d"
).

(2.10)

Let us write d ′ = p i 1 • • • p i j and take some p S from S. If j is even then µ(d ′ ) = 1 and, from the definition of a coherent set, d ′ ≡ 2 t (mod q) for some t (depending on d ′ ), 0 ≤ t ≤ r -1.

Whereas, if j is odd then µ(d ′ ) = -1 and d ′ ≡ 2 t ′ p -1 S (mod q) for some t ′ (depending on d ′ ), 0 ≤ t ′ ≤ r -1. From (1.7), we obtain

µ(d ′ )σ(A, n d ′ d" ) ≡ σ(A, n d" ) (mod 2 k+1 ) if j is even, (2.11) µ(d ′ )σ(A, n d ′ d" ) ≡ -σ(A, np S d" ) (mod 2 k+1 ) if j is odd.
(2.12)

Since α = ω S (m) = k + 2 > 0, the number of d ′ with odd j is equal to that with even j and is given by

1 + α 2 + α 4 + • • • = α 1 + α 3 + • • • = 2 α-1 .
From (2.10), we obtain

mS A (m, k) ≡ 2 α-1 d" | m" µ(d") σ(A, n d" ) -σ(A, np S d" ) (mod 2 k+1 ), (2.13)
which, as α = ω S (m) = k + 2, gives S A (m, k) ≡ 0 (mod 2 k+1 ), so that from (1.8),

χ(A, m) = χ(A, 2m) = • • • = χ(A, 2 k m) = 0. (2.14)
Let us assume that E ′ (q) = ∅ so that there exists a coherent set C with r semi-bad classes modulo q; we associate to C the set of primes S defined by (2.8) and we denote by Q = Q(q) and N = N (q) the sets Q = {p prime, p | q} and N = {p prime, p ∈ B ∪ S and gcd(p, 2q) = 1}, so that the whole set of primes is equal to B ∪ S ∪ N ∪ Q ∪ {2}. For n ≥ 1, let us define the multiplicative arithmetic function

δ(n) = 1 if p | n ⇒ p ∈ B (i.e. p ∈ S ∪ N ∪ Q ∪ {2}) 0 otherwise. and for x > 1, V (x) = V q (x) = n≥1, n2 ω S (n) ≤x δ(n). (2.15)
Lemma 2.5. Under the above notation, we have

V (x) = V q (x) = O q x (log x) c(q) r ϕ(q) , (2.16)
where c(q) is given by (2.5).

Proof. To prove (2.16), one should consider, for complex s with R(s) > 1, the series

F (s) = n≥1 δ(n) (n2 ω S (n) ) s • (2.17)
This Dirichet series has an Euler's product given by

F (s) = p∈N ∪Q∪{2} 1 - 1 p s -1 p∈S 1 + 1 2 s (p s -1) , (2.18)
which can be written as

F (s) = H(s) p∈N 1 - 1 p s -1 p∈S 1 - 1 p s -1 2 s , (2.19)
where

H(s) = p∈Q∪{2} 1 - 1 p s -1 p∈S 1 + 1 2 s (p s -1) 1 - 1 p s 1 2 s . ( 2

.20)

By applying Selberg-Delange's formula (cf. [START_REF] Saïd | Sur une application de la formule de Selberg-Delange[END_REF], Théorème 1 and [9], Lemma 4.5), we obtain some constant c 4 such that

V (x) = c 4 x (log x) c(q) r ϕ(q) + O q x log log x log x . ( 2

.21)

The constant c 4 is somewhat complicated, it is given by

c 4 = CH(1) Γ(1 -c(q) r ϕ(q) ) , (2.22)
where Γ is the gamma function,

H(1) = 2q ϕ(q) p∈S 1 + 1 2(p -1) 1 - 1 p 1 2 (2.23)
and

C = p∈N 1 - 1 p -1 p∈S 1 - 1 p -1 2 p 1 - 1 p 1-c(q) r ϕ(q)
, where in the third product, p runs over all primes.

3 Proof of the results.

Proof of Theorem 2.1. If r = ϕ(q) then 2 is a generator of (Z/qZ) * , all primes are bad but 2 and the prime factors of q; hence by Theorem 2 of [START_REF] Ben Saïd | On the counting function of the sets of parts such that the partition function takes even values for n large enough[END_REF], A(P, x) = O ((log x) κ ) for some constant κ, so that we may remove the case r = ϕ(q). If E ′ (q) = ∅, from (2.5), c = 1 holds and (2.6) follows from (1.16). We now assume E ′ (q) = ∅, so that, from Lemma 2.2, there exists a coherent set C satisfying |C| = r. We define the set of primes S by (2.8). Let us write V (x) defined in (2.15) as

V (x) = V ′ (x) + V "(x), (3.1)
with

V ′ (x) = n≥1, n2 ω S (n) ≤x, ω S (n)=0
δ(n) and V "(x) = n≥1, n2 ω S (n) ≤x, ω S (n)≥1 δ(n).

Similarly, we write A(P, x) = a∈A(P ), a≤x 1 = A ′ + A", with A ′ = a∈A(P ), a≤x, ω S (a)=0

An element a of A(P ) counted in A ′ is free of bad and semi-bad primes, so that

A ′ ≤ V ′ (x) ≤ V ′ (2x). (3.2)
By Lemma 2.4, an element a of A(P ) counted in A" is of the form n2 ω S (n)-1 with ω S (n) = ω S (a) ≥ 1; hence A" ≤ V "(2x).

(3. 3 ) 5 .

 35 Therefore, from (3.1)-(3.3), we getA(P, x) = A ′ + A" ≤ V ′ (2x) + V "(2x) = V (2x)and (2.6) follows from Lemma 2.Proof of Theorem 2.2. Just use Theorem 2.1 and (1.13).

and A" = a∈A(P ), a≤x, ω S (a)≥1 1.

Acknowledgements. It is a great pleasure for us to thank András Sárközy for initiating the study of the sets A(P ) and for all the mathematics that we have learnt from him.


S Xin

Xavier Nicolas

P Le Quere

published or not. The documents may come

Stability analyses of longitudinal rolls of poiseuille-Rayleigh-bénard flows in air-filled channels of finite transversal extension