Nikos Frantzikinakis

AND Emmanuel Lesigne

M Át

É Wierdl

POWERS OF SEQUENCES AND RECURRENCE

Keywords: Mathematics Subject Classification. Primary: 37A45; Secondary: 28D05, 05D10, 11B25 Intersective sets, sets of recurrence, multiple recurrence

We study recurrence, and multiple recurrence, properties along the k-th powers of a given set of integers. We show that the property of recurrence for some given values of k does not give any constraint on the recurrence for the other powers. This is motivated by similar results in number theory concerning additive basis of natural numbers. Moreover, motivated by a result of Kamae and Mendès-France, that links single recurrence with uniform distribution properties of sequences, we look for an analogous result dealing with higher order recurrence and make a related conjecture.

November 16, 2007

Motivation, historical remarks

In their 1912 paper ([HarLi]), Hardy and Littlewood proved that for any irrational number α, the set (α, α), (2α, 2 2 α), (3α, 3 2 α), . . . mod 1 is dense in the two dimensional torus, and the obvious extension of this result to higher dimensional tori, and arbitrary powers. This result can be considered as an indication that in some sense the sequences 1, 2, 3 . . . and 1 2 , 2 2 , 3 2 . . . behave independently. Soon after Hardy-Littlewood's work, Weyl proved that, in fact, the sequence (α, α), (2α, 2 2 α), (3α, 3 2 α), . . . mod 1 is uniformly distributed in the two dimensional torus ([We]).

Since these results, a number of theorems appeared that could be interpreted to express the independence of sequences of powers of n. A direct motivation for our work is the result of Deshouillers, Erdös and Sárközy ([DESa]) on bases. A set B of positive integers 2000

is called a basis if there exists an h ∈ N such that every n ∈ N can be written in the form n

= b 1 + b 2 + • • • + b h , b i ∈ B ∪ {0}.
The result of Deshouillers, Erdös and Sárközy, says that there exists a set of integers B = {b 1 , b 2 , . . .} which is not a basis, but the set B 2 = {b 2 1 , b 2 2 , . . .} is a basis. They also construct a set of integers which is a basis, but the set of squares of its elements is not a basis. The ultimate generalization of this result appears in a paper by Deshouillers and Fouvry ([DFou]). It says the following: given any set G (the set of "good" exponents), there exists a set of integers B = {b 1 , b 2 , . . .} such that, for all k ∈ N, the set B k = {b k 1 , b k 2 , . . .} is a basis if and only if k ∈ G. Again, this result can be interpreted as expressing the independent behavior of powers, and indeed, the proof utilizes a quantitative version of Weyl's theorem via the Hardy-Littlewood circle method.

Our work is for intersective sets. A set of integers R is called intersective (this adjective was introduced by Ruzsa in [Ruz]) if for every set of integers Λ with positive upper density1 , the equation xy = r is solvable in x, y ∈ Λ and r ∈ R \ {0}. The reason the word "intersective" is used here is because the solvability of the equation xy = r in x, y ∈ Λ and r ∈ R \ {0} can be written in the following way Λ ∩ (Λr) = ∅ for some nonzero r ∈ R.

It is a well known theorem of Sárközy ([Sa]), that for any fixed k, the set of k-th powers is intersective. Bergelson and Håland ([BeHål]) constructed a set of integers that is not intersective but the set of squares of its elements is intersective. We establish a generalization of their result to the setting of the Deshouillers-Fouvry theorem we mentioned above:

Theorem A. Let G be a set of positive integers.

There exists a set of integers R = {r 1 , r 2 , . . .} such that: for all k ∈ N, the set R k = {r k 1 , r k 2 , . . .} is intersective if and only k ∈ G. In our paper we go further, and prove a generalization of this result to arithmetic progressions. The famous result of Szemerédi ([Sz]) states that every set of integers with positive upper density contains arbitrarily long arithmetic progressions. Bergelson and Leibman proved in [BeLei] that, for any fixed k, every set of positive density contains arbitrarily long arithmetic progressions so that the difference of the progression is a kth power. To be able to talk about our result, we introduce the following definition. A set R is called ℓ-intersective if every set Λ of positive density contains an ℓ + 1 long arithmetic progression with a common difference from R\{0}. In other words, Λ contains configurations of the form m, m + r, m + 2r, . . . , m + ℓr for some nonzero r ∈ R. Similarly to single intersectivity, we can rewrite this condition as Λ ∩ (Λr) ∩ (Λ -2r) ∩ • • • ∩ (Λℓr) = ∅ for some nonzero r ∈ R. In this language our result is the exact "multiple" analog of Theorem A: Theorem B. Let ℓ be a positive integer and G be a set of positive integers.

There exists a set of integers R = {r 1 , r 2 , . . .} such that: for all k ∈ N, the set R k = {r k 1 , r k 2 , . . .} is ℓ-intersective if and only k ∈ G. Note that, for example, we do not claim the existence of a set R such that is ℓintersective for every ℓ ∈ N but the set R 2 is not ℓ-intersective for some ℓ ∈ N. Actually, it may very well be impossible to construct such an example (see Question 2 in Section 5.3).

We will use Furstenberg's correspondence principle to translate the previous statements to ergodic theory and will then verify the corresponding ergodic statements. In the next section we explain the ergodic theoretical analogs of the previous theorems, and we state our main results.

Main results

2.1. Good and bad powers for sets of recurrence and ℓ-recurrence. All along the article we will use the word system, or the term measure preserving system, to designate a quadruple (X, B, µ, T ), where (X, B, µ) is a probability space, and T : X → X is a measurable map such that µ(T -1 A) = µ(A) for all A ∈ B. In [START_REF] Furstenberg | Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions[END_REF], Furstenberg perceived a connection between existence of structures in sets of integers having positive upper density and recurrence properties of measure preserving systems. He used this, and other ideas, to give an ergodic theoretic proof of Szemerédi's theorem on arithmetic progressions. This new approach gave rise to the field of ergodic Ramsey theory, where problems in combinatorial number theory are treated using techniques from ergodic theory, and led to several far reaching extensions of Szemerédi's theorem. We will use this correspondence to translate statements about "intersectivity" to statements about "recurrence". The following formulation is from [Be]:

Furstenberg Correspondence Principle. Let Λ be a set of integers. There exist a system (X, B, µ, T ) and a set A ∈ B with µ(A) = d(Λ) such that

(1) d(Λ ∩ (Λ -n 1 ) ∩ . . . ∩ (Λ -n ℓ )) ≥ µ(A ∩ T -n 1 A ∩ • • • ∩ T -n ℓ A),
for all n 1 , . . . , n ℓ ∈ Z and l ∈ N.

Using this principle, we can reformulate Theorems A and B in ergodic theoretic language. We first translate the notion of intersectivity.

Definition 2.1. We say that the set of integers R is a set of recurrence for the system (X, B, µ, T ) if for every set A ∈ B of positive measure, we have (2) µ(A ∩ T -r A) > 0 for some nonzero r ∈ R.

We say that the set of integers R is a set of recurrence, or good for recurrence, if it is a set of recurrence for every system.

Note that if R is a set of recurrence then (2) is in fact satisfied for infinitely many r ∈ R.

Using Furstenberg's correspondence principle it is easy to see that if R is a set of recurrence then it is intersective (the converse is also true and not hard to show). As a consequence, the following result implies Theorem A:

Theorem A ′ . Let G be a set of positive integers.
There exists a set of integers R = {r 1 , r 2 , . . .} such that: for all k ∈ N, the set R k = {r k 1 , r k 2 , . . .} is good for recurrence if and only k ∈ G. Although Theorem A ′ will be later subsumed by a stronger result (Theorem B ′ ), we choose to give an independent proof of it in Section 3, as in this case the analysis does not depend upon complicated multiple ergodic theorems, and so it becomes easier to see the main ideas of the proof. Now to formulate the ergodic theoretical analog of Theorem B, we first translate the notion of ℓ-intersectivity.

Definition 2.2. Let ℓ be a positive integer. We say that the set R of integers is a set of ℓ-recurrence for the system (X, B, µ, T ) if for every set A ∈ B of positive measure, we have

µ(A ∩ T -r A ∩ T -2r A ∩ • • • ∩ T -ℓr A) > 0 for some nonzero r ∈ R.
We say that the set of integers R is a set of ℓ-recurrence, or good for ℓ-recurrence, if it is a set of ℓ-recurrence for every system.

Some examples of sets of ℓ-recurrence (or ℓ-intersective), for every ℓ ∈ N, are IP sets, meaning sets that consist of all finite sums (with distinct entries) of some infinite set [START_REF] Furstenberg | An ergodic Szemerédi theorem for IP-systems and combinatorial theory[END_REF]), and sets of the form n∈N {a n , 2a n , . . . , na n } where a n ∈ N (follows from a finite version of Szemerédi's theorem). It is also known that the set of values of any non-constant integer polynomial with zero constant term is a set of ℓ-recurrence for all ℓ ∈ N ( [BeLei]). Examples of sets which are not sets of recurrence are sets which do not contain any multiple of a given d ∈ N, and lacunary sets. An example of a set of ℓ-recurrence but not (ℓ + 1)-recurrence is n ∈ N : {n ℓ+1 α} ∈ [1/4, 3/4] where α is any irrational number ( [FrLesWi]).

The ergodic theoretical analog of Theorem B is:

Theorem B ′ .
Let ℓ be a positive integer and G be a set of positive integers.

There exists a set of integers R = {r 1 , r 2 , . . .} such that: for all k ∈ N, the set R k = {r k 1 , r k 2 , . . .} is good for ℓ-recurrence if and only k ∈ G. We prove this result in Section 5 using an argument similar to the one used to prove Theorem A ′ . There are some extra difficulties in this case though, since we have to establish some equidistribution results on nilmanifolds, and also a uniform multiple recurrence result that we state and prove in the Appendix.

2.2. Good and bad powers for sets of (n a 1 , . . . , n a ℓ )-recurrence. The previous results deal with sets of recurrence along families of polynomials of the form {n k , 2n k , . . . , ℓn k }. We also study the other extreme case, of sets of recurrence along families of linearly independent polynomials, like families of the form {n a 1 , . . . , n a ℓ }, where a 1 , . . . , a ℓ ∈ N are distinct. The next definition will facilitate our discussion.

Definition 2.3. Let u 1 (n), . . . , u ℓ (n) be integer sequences. We say that the set R ⊂ Z is good for recurrence along the sequence (u 1 (n), . . . , u ℓ (n)) if for every system (X, B, µ, T ) and A ∈ B of positive measure, there exist infinitely many r ∈ R such that

µ(A ∩ T -u 1 (r) A ∩ . . . ∩ T -u ℓ (r) A) > 0.
Using Furstenberg's correspondence principle it is easy to define an analogous notion in combinatorics. We will show:

Theorem C. Let A ℓ = {(a 1 , a 2 , . . . , a ℓ ) ∈ N ℓ : a 1 < a 2 < . . . < a ℓ } and G ⊂ A ℓ .
There exists a set of integers R such that: R is good for recurrence along the sequence (n a 1 , . . . , n a ℓ ) if and only if (a 1 , . . . , a ℓ ) ∈ G.

The proof of this result is similar to the proof of Theorem B ′ and we give it in Section 6.

2.3. Powers of sequences and sufficient conditions for ℓ-recurrence. When ℓ ≥ 2, there is currently no general criterion providing usable sufficient conditions for a set of positive integers R = {r 1 , r 2 , . . .} to be good for ℓ-recurrence. In contrast, when ℓ = 1 such a criterion exists, it is a result of Kamae and Mendès-France [KaMe] that links recurrence properties of a set R with uniform distribution properties of sequences of the form (r n α) n∈N in T, where α is irrational (see Theorem 7.1).

In Section 7 we are seeking for a similar result for ℓ-recurrence. When ℓ = 2 it is well understood that such a criterion should be related to stronger uniform distribution properties of "quadratic nature", forcing at the very least good single recurrence properties for the sequence (r n ) n∈N and its sequence of squares (r 2 n ) n∈N . We show why a plausible statement involving only quadratic functions of r n fails (Theorem 7.2), the reason turns out to be that one has to also take into account generalized quadratic functions of r n , so sequences like ([r n α]r n ) n∈N where α is irrational (Lemma 7.4). Using the language of nilsystems we state a conjecture that, if true, would provide a natural generalization of the Kamae and Mendès-France criterion for ℓ-recurrence. In Theorem 7.5 we verify this conjecture when the set R has positive density.

Notation:

The following notation will be used throughout the article:

T f = f • T , e(x) = e 2πix , {x} = x -[x].
For a bounded numerical sequence (a n ) n∈N we will write D-lim n→∞ (a n ) = 0 if one of the following equivalent properties is satisfied : -For every ε > 0, d {n :

|a n | > ε} = 0; -There exists E ∈ N, with d(E) = 1, such that lim n→∞,n∈E a n = 0; -lim N →+∞ 1 N N n=1 |a n | = 0.

Good and bad powers for sets of recurrence

In this section we will prove Theorem A ′ . The proof is based on the following ergodic result: Proposition 3.1. Let (X, B, µ, T ) be a system, f ∈ L ∞ (µ), h 1 , . . . , h s : T → C be Riemann integrable functions, and β be an irrational number. If k, k 1 , . . . , k s are distinct positive integers then

(3) lim N →∞ 1 N N n=1 h 1 (n k 1 β) • . . . • h s (n k s β) • T n k f = h 1 dt • . . . • h s dt • lim N →∞ 1 N N n=1 T n k f,
where the convergence takes place in L2 (µ).

Remark. It is well known, as a direct consequence of the spectral theorem and Weyl's uniform distribution theorem, that both limits exist in L 2 (µ).

Proof. Using a standard estimation by continuous functions from above and below 2 , it suffices to check that (3) holds when h 1 , . . . , h s are continuous functions. Using Weierstrass approximation theorem of continuous functions by trigonometric polynomials, and linearity, it suffices to check the result when h 1 (t) = e(l 1 t), . . . , h s (t) = e(l s t) for some l 1 , . . . , l s ∈ Z. If all the l i 's are zero then (3) holds trivially. So without loss of generality we can assume that l 1 = 0. Using the spectral theorem for the unitary action T on L 2 (µ), we associate to the function f a finite positive measure σ f on the torus T, such that, for any complex numbers a 1 , . . . , a N we have

(4) 1 N N n=1 a n • T n k f L 2 (µ) = 1 N N n=1 a n • e(n k t) L 2 (σ f (t))
.

Setting a n = e(l 1 n k 1 β) • . . . • e(l s n ks β) in (4), we see that it suffices to show that (5) lim

N →∞ 1 N N n=1 e(l 1 n k 1 β) • . . . • e(l s n ks β) • e(n k t) L 2 (σ f (t)) = 0.
In this case, the average in (5) becomes

1 N N n=1 e l 1 n k 1 β + . . . + l s n ks β + n k t .
Since the integers k, k 1 , . . . , k s are distinct, the coefficient of n k 1 is l 1 β, which is irrational since β is irrational and l 1 = 0. By Weyl's uniform distribution theorem the last average converges to zero for every t ∈ [0, 1), which gives (5).

We will also use the following result of Forrest [For] (a more general result is proved in the Appendix of the present paper): Theorem 3.2 (Forrest [For]). Suppose that R is a set of single recurrence. Then for every ε > 0 there exists an N = N (ε) and δ = δ(ε) > 0, such that for every system (X, B, µ, T ) and set A ∈ B with µ(A) ≥ ε we have

µ(A ∩ T -n A) ≥ δ for some n ∈ R ∩ [1, N ].
Proof of Theorem A ′ . We first consider the case where the complement B of G is empty or finite. If B is empty then R = N works (see [START_REF] Furstenberg | Recurrence in ergodic theory and combinatorial number theory[END_REF]). If B is finite then B = {b 1 , . . . , b s } for some b i ∈ N. Fix an irrational number β, and for k ∈ N let

R k = {n ∈ N : {n k β} ∈ [1/4, 3/4]}.
We claim that the set R = R b 1 ∩ . . . ∩ R bs has the advertised property.

The set R b is not good for single recurrence for b ∈ B since it is not good for recurrence for the rotation by β on T. Now take g ∈ G. Using Proposition 3.1 we will show that R g is a set of single recurrence. Let (X, B, µ, T ) be a system and A ∈ B with µ(A) > 0. Set h i = 1 [1/4,3/4] , k i = b i , for i = 1, . . . , s, k = b, and f = 1 A in (3), then multiply by 1 A and integrate with respect to µ. We get lim

N →∞ 1 N 1≤n≤N,n∈R µ(A ∩ T -n g A) = 1 2 s lim N →∞ 1 N N n=1 µ(A ∩ T -n g A).
The last limit is positive (this is implicit in [START_REF] Furstenberg | Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions[END_REF] and [START_REF] Furstenberg | Recurrence in ergodic theory and combinatorial number theory[END_REF] and explicit in [BeLei]), showing that R g is a set of single recurrence. Now we deal with the general case where the set of bad powers B is infinite. Fix s ∈ N and let R s = b∈B,b≤s R b . We showed before that (R s ) g is a set of single recurrence for g ∈ G. By Theorem 3.2 there exists a finite set F s ⊂ R s such that for g ∈ G ∩ [1, s] the following is true: For every system (X, B, µ, T ) and every A ∈ B with µ(A) > 1/s we have that µ(A ∩ T -n A) > 0 for some n ∈ (F s ) g .

We claim that R = s∈N F s is the set we are looking for. We first show that R b is not a set of single recurrence for k ∈ B. So let b be an element of B. Since R is contained in R b up to a finite set, and (R b ) b is not a set of single recurrence, we conclude that R b is not a set of single recurrence. Suppose now that g ∈ G, it remains to show that R g is a set of single recurrence. Let (X, B, µ, T ) be a system and A ∈ B be such that µ(A) > 0. Then µ(A) > 1/s for some s ∈ N with s > g. By the definition of F s we have that µ(A ∩ T -n A) > 0 for some n ∈ (F s ) g . Since F s ⊂ R we conclude that R g is a set of single recurrence. This completes the proof.

Background in ergodic theory

4.1. Factors in ergodic theory. Throughout the article we consider invertible measure preserving systems (X, B, µ, T ) where the probability space (X, B, µ) is a Lebesgue space. This classical assumption allows us to use Rokhlin's theory of factors and disintegration. (The basic reference here is [Ro], see also [Zim] Section 1.1, [Rud] Chapter 2, or [Wa] Section 2.3.) These two extra assumptions are not at all restrictive for our purposes, the reason being that the measure preserving systems constructed using the correspondence principle of Furstenberg are invertible and Lebesgue.

A homomorphism from a system (X, B, µ, T ) onto a system (Y, D, ν, S) is a measurable map π :

X ′ → Y ′ , where X ′ is a T -invariant subset of X and Y ′ is an S-invariant subset of Y , both of full measure, such that µ • π -1 = ν and S • π(x) = π • T (x) for x ∈ X ′ .
When we have such a homomorphism we say that the system (Y, D, ν, S) is a factor of the system (X, B, µ, T ). If the factor map π : X ′ → Y ′ can be chosen to be injective, then we say that the systems (X, B, µ, T ) and (Y, D, ν, S) are isomorphic (bijective maps on Lebesgue spaces have measurable inverses).

A factor can be characterized (modulo isomorphism) by the data π -1 (D) which is a T -invariant sub-σ-algebra of B, and any T -invariant sub-σ-algebra of B defines a factor; by a classical abuse of terminology we denote by the same letter the σ-algebra D and its inverse image by π. In other words, if (Y, D, ν, S) is a factor of (X, B, µ, T ), we think of D as a sub-σ-algebra of B. A factor can also be characterized (modulo isomorphism) by a T -invariant sub-algebra F of L ∞ (X, B, µ), in which case D is the sub-σ-algebra generated by F, or equivalently,

L 2 (X, D, µ) is the closure of F in L 2 (X, B, µ).
If D is a T -invariant sub-σ-algebra of B and f ∈ L 2 (µ), we define the conditional expectation E(f |D) of f with respect to D to be the orthogonal projection of f onto L 2 (D). We frequently make use of the identities

E(f |D) dµ = f dµ, T E(f |D) = E(T f |D).
(If we want to indicate the dependence on the reference measure, we write E = E µ .)

For each d ∈ N, we define K d to be the factor induced by the function algebra

{f ∈ L ∞ (µ) : T d f = f }.
We define the rational Kronecker factor K rat to be the factor induced by the algebra generated by the functions

{f ∈ L ∞ (µ) : T d f = f for some d ∈ N} .
This algebra is the same as the algebra spanned by the bounded functions that satisfy

T f = e(a) • f for some a ∈ Q.
The Kronecker factor K is induced by the algebra spanned by the bounded eigenfunctions of T , that means, functions that satisfy

T f = e(a) • f for some a ∈ R. It is known that if f is a bounded function such that E µ (f |K(T )) = 0, then E µ⊗µ (f ⊗ f |K rat (T × T )) = 0 (see for example [Fu2], Section 4.4).
The transformation T is ergodic if T f = f implies that f = c (a.e.) for some c ∈ C. Every system (X, B, µ, T ) has an ergodic decomposition, meaning that we can write µ = µ t dλ(t), where λ is a probability measure on [0, 1] and µ t are T -invariant probability measures on (X, B) such that the systems (X, B, µ t , T ) are ergodic for t ∈ [0, 1]. We sometimes denote the ergodic components by T t , t ∈ [0, 1].

We say that (X, B, µ, T ) is an inverse limit of a sequence of factors (X, B j , µ, T ) if (B j ) j∈N is an increasing sequence of T -invariant sub-σ-algebras such that j∈N B j = B up to sets of measure zero. 4.2. Characteristic factors. Following [START_REF] Host | Nonconventional ergodic averages and nilmanifolds[END_REF], for every system (X, B, µ, T ) and function f ∈ L ∞ (µ), we define inductively the (functional valued) seminorms |||f ||| ℓ as follows:

For ℓ = 1 we set |||f ||| 1 = |E(f |I)|, where I is the σ-algebra of T -invariant sets. For ℓ ≥ 2 we set (6) |||f ||| 2 ℓ+1 ℓ+1 = lim N →+∞ 1 N N -1 n=0 |||f • T n f ||| 2 ℓ ℓ .
It was shown in [START_REF] Host | Nonconventional ergodic averages and nilmanifolds[END_REF] 3 that for every integer

ℓ ≥ 1, ||| • ||| ℓ is a seminorm on L ∞ (µ) and it defines factors Z ℓ-1 = Z ℓ-1 (T ) in the following manner: the T -invariant sub-σ-algebra Z ℓ-1 is characterized by for f ∈ L ∞ (µ), E(f |Z ℓ-1 ) = 0 if and only if |||f ||| ℓ = 0. If f is a bounded function such that E µ (f |Z ℓ (T )) = 0 then E µ⊗µ (f ⊗ f |Z ℓ-1 (T × T )) = 0
(this is implicit in [START_REF] Host | Nonconventional ergodic averages and nilmanifolds[END_REF]). Also, if T t where t ∈ [0, 1] are the ergodic components of the system, then

E(f |Z ℓ (T )) = 0 if and only if E(f |Z ℓ (T t )) = 0 for a.e. t ∈ [0, 1].
We note that for ergodic systems the factor Z 0 = I is trivial and Z 1 = K. The factors Z ℓ are of particular interest because they can be used in order to study the limiting behavior in L 2 of some multiple ergodic averages.

Theorem 4.1 , Leibman [Lei2]). Let p 1 , p 2 , . . . , p s be polynomials with integer coefficients. There exists a nonnegative integer ℓ = ℓ(p 1 , p 2 , . . . , p s ) with the following property: If (X, B, µ, T ) is a system and f 1 , f 2 , . . . , f s ∈ L ∞ (X) then the limit

lim N →+∞ 1 N N n=1 T p 1 (n) f 1 • T p 2 (n) f 2 • . . . • T p s (n) f s exists in L 2 (µ)
; and it is equal to zero as long as one of the functions f i is orthogonal to the factor Z ℓ (T ).

(We say that Z ℓ (T ) is a characteristic factor associated to p 1 , p 2 , . . . , p s when this last fact is true.)

Here are some examples that will be used later:

(i) [HoKr1] If p i (n) = in, 1 ≤ i ≤ s, then ℓ(p 1 , p 2 , . . . , p s ) = s -1.
(ii) [Fr] More generally, if p is a nonconstant integer polynomial and if [START_REF] Frantzikinakis | Ergodic averages for independent polynomials and applications[END_REF] If the polynomials p 1 , p 2 , . . . , p s are linearly independent and have zero constant term then K rat (T ) is a characteristic factor.

p i (n) = ip(n), 1 ≤ i ≤ s, then ℓ(p 1 , p 2 , . . . , p s ) = s -1. (iii)
Proposition 4.2. Let p 1 , p 2 , . . . , p s be a family of polynomials with integer coefficients and Z ℓ (T ) a characteristic factor associated to this family. Let (X, B, µ, T ) be a system and f 0 , f 1 , . . . , f s ∈ L ∞ (X). If one of the functions f i is orthogonal to the factor Z ℓ+1 (T ), then

D-lim n→∞ f 0 • T p 1 (n) f 1 • . . . • T ps(n) f s dµ = 0. Proof. If f i is orthogonal to the factor Z ℓ+1 (T ), then f i ⊗ f i is orthogonal to the factor Z ℓ (T × T ), hence the averages 1 N N n=1 f 0 (x)f 0 (y)f 1 (T p 1 (n) x)f 1 (T p 1 (n) y) . . . f s (T ps(n) x)f s (T ps(n) y) dµ(x)dµ(y)
converge to zero. This can be written as lim

N →+∞ 1 N N n=1 f 0 • T p 1 (n) f 1 • . . . • T ps(n) f s dµ 2 = 0
and gives the announced convergence in density.

Similarly, we have the following result:

Proposition 4.3. Let p 1 , p 2 , . . . , p s be a family of linearly independent integer polynomials with zero constant term. Let (X, B, µ, T ) be a system and f 0 , f 1 , . . . , f s ∈ L ∞ (X).

If one of the functions f i is orthogonal to the Kronecker factor Z 1 (T ), then

D-lim n→∞ f 0 • T p 1 (n) f 1 • . . . • T ps(n) f s dµ = 0.
Proof. A characteristic factor associated to the family of polynomials is K rat and if f i is orthogonal to the factor Z 1 (T ), then f i ⊗ f i is orthogonal to the factor K rat (T × T ). The same argument as in the preceding proof applies.

4.3. Nilsystems. We will now define a class of systems of purely algebraic structure that will be crucial for our study. Given a topological group G, we denote the identity element by e and we let G 0 denote the connected component of e. Nilsystems play a central role in our study because they provide a sufficient class for verifying several multiple recurrence results for general measure preserving systems. In fact when one deals with "polynomial recurrence" this is usually a consequence of Theorem 4.1 and the following result of Host and Kra (a closely related result was subsequently proved by Ziegler ([Zie])):

G 1 = G and G ℓ+1 = [G, G ℓ ]. A group G is said to be ℓ-step nilpotent if its (ℓ + 1) commutator G ℓ+1 is trivial. If G is an ℓ-step nilpotent
Theorem 4.4 (Host & Kra [HoKr1]). Let (X, B, µ, T ) be a system. Then for every ℓ ∈ N the factor Z ℓ (T ) is an inverse limit of ℓ-step nilsystems.

Fundamental properties of nilsystems, related to our discussion, were studied in [AGHah], [Parry], [START_REF] Lesigne | Sur une nil-variété, les parties minimales associées à une translation sont uniquement ergodiques[END_REF], and [START_REF] Leibman | Pointwise convergence of ergodic averages for polynomial sequences of translations on a nilmanifold[END_REF]. Below we summarize some facts that we shall use, all the proofs can be found in [START_REF] Leibman | Pointwise convergence of ergodic averages for polynomial sequences of translations on a nilmanifold[END_REF].

If H is a closed subgroup of G and x ∈ X then Hx may not be a closed subset of X (take X = R/Z, x = Z, and H = {k √ 2 : k ∈ Z}), but if Hx is closed in X then the compact set Hx can be given the structure of a nilmanifold. More precisely, if x = gΓ and Hx is closed, we have Hx ≃ H/∆ where ∆ = H ∩ gΓg -1 , and h → hgΓ induces the isomorphism from H/∆ onto Hx. We call any such set a sub-nilmanifold of X.

Let (X = G/Γ, G/Γ, m, T a ) be an ergodic nilsystem. The subgroup G 0 , a projects to an open subset of X that is invariant under a. By ergodicity this projection equals X. Hence, X = G 0 , a /Γ ′ where Γ ′ = Γ ∩ G 0 , a . Using this representation of X for ergodic nilsystems, we have that G is generated by G 0 and a. From now on, when we work with an ergodic nilsystem, we will freely assume that this extra hypothesis is satisfied, and so for example we can assume that the commutator subgroups G ℓ are connected for ℓ ≥ 2 ([Les2]). 4.4. Uniform distribution properties in nilmanifolds. If G is a nilpotent Lie group, a 1 , . . . , a s ∈ G, and p 1 , . . . , p s are integer polynomials N → Z, then a sequence of the form g

(n) = a p 1 (n) 1 a p 2 (n) 2 • • • a ps(n) s
is called a polynomial sequence in G. In the sequel we need to establish various uniform distribution properties of polynomial sequences on nilmanifolds. The next result will simplify our task: Theorem 4.5 (Leibman [Lei1]). Let X = G/Γ be a nilmanifold and g(n) be a polynomial sequence in G. Define Z = G/([G 0 , G 0 ]Γ) and let π Z : X → Z be the natural projection. Then for every x ∈ X:

(i) There exist x i ∈ X and connected sub-nilmanifolds

Y i = Hx i of X, 1 ≤ i ≤ t, where H is a closed subgroup of G (depending on x), such that Y = {g(n)x : n ∈ N} = t i=1 Y i , and for i = 1, . . . , t the sequence (g(tn + i)) n∈N is uniformly distributed in Y i . If Y is connected then t = 1. (ii) If X is connected, then the sequence (g(n)x) n∈N is dense in X if and only if it is uniformly distributed in X. Moreover, (g(n)x) n∈N is dense in X if and only if (g(n)π Z (x)) n∈N is dense in Z.
We remark that the groups G 0 and [G 0 , G 0 ] are normal subgroups of G. The group G/[G 0 , G 0 ] has the additional property that the connected component of its identity element is Abelian. This forces every rotation on the nilmanifold Z = G/([G 0 , G 0 ]Γ) to have very special structure. More precisely, a map T : G → G is said to be affine if T (g) = bA(g) for an endomorphism A of G and some b ∈ G. Let ℓ ∈ N; the endomorphism A, or the affine transformation T , is said to be ℓ-step unipotent if (A -Id) ℓ = 0.

Theorem 4.6 (F. & Kra [START_REF] Frantzikinakis | Polynomial averages converge to the product of integrals[END_REF]). Let X = G/Γ be an ℓ-step connected nilmanifold with the Haar measure m such that G 0 is Abelian and a ∈ G. The nilsystem (X, G/Γ, m, T a ) is isomorphic to an ℓ-step unipotent affine transformation on some finite dimensional torus with the Haar measure. Furthermore, the conjugation can be taken to be continuous.

Good and bad powers for sets of ℓ-recurrence

In this section we will prove Theorem B ′ , but before delving into the proof let us motivate a bit the choice of the set R. Suppose we just want to construct a set R that is bad for double recurrence but the set of squares of its elements R 2 is good for double recurrence. In view of Proposition 5.1 below, it makes sense to take R = n ∈ N : {p(n)β} ∈ [1/4, 3/4] for some quadratic polynomial p, this way we guarantee that R will be bad for double recurrence. It remains to choose the polynomial p such that the set R 2 is good for double recurrence. The obvious choice p(n) = n 2 will not work since then R 2 will not even be good for single recurrence. But the choice p(n) = n 2 + n will do the job (for any irrational β ∈ R) and this will be formally shown using Proposition 5.2 below.

5.1. Proof of main theorem modulo a multiple ergodic theorem. We shall first establish Theorem B ′ modulo an ergodic theorem that we will prove in subsequent sections. We need two preliminary results. The first is elementary and was proved in [FrLesWi] in the special case where the polynomial p is a monomial. The same argument gives the following more general result: Proposition 5.1. Let R be a set of ℓ-recurrence and p be an integer polynomial with zero constant term and deg p ≤ ℓ. Then for every α ∈ R and ε > 0 there exists r ∈ R such that {p(r

)α} ∈ [0, ε] ∪ [1 -ε, 1).
The second is a multiple ergodic theorem, its proof uses deeper results from ergodic theory and will be given in the next section.

Proposition 5.2. Let (X, B, µ, T ) be a system, f 1 , . . . , f ℓ ∈ L ∞ (µ), h 1 , . . . , h s : T → C be Riemann integrable functions, and β be an irrational number. If k, k 1 , . . . , k s are distinct positive integers then

lim N →∞ 1 N N n=1 h 1 (n ℓk 1 + n k 1 )β • . . . • h s (n ℓks + n ks )β • T n k f 1 • . . . • T ℓn k f ℓ = (7) h 1 dt • . . . • h s dt • lim N →∞ 1 N N n=1 T n k f 1 • . . . • T ℓn k f ℓ ,
where the convergence takes place in L 2 (µ).

Remarks. (i) The limits appearing in the statement exist by [START_REF] Host | Convergence of polynomial ergodic averages[END_REF] or [START_REF] Leibman | Convergence of multiple ergodic averages along polynomials of several variables[END_REF].

(ii) As it will become clear from the proof, the integer polynomials n ℓk 1 +n k 1 , . . . , n ℓks + n ks can be replaced by any family of polynomials p 1 , . . . , p s with zero constant term having the following property: For every nonzero polynomial p of the form p(n) = c 1 n k + c 2 n 2k + ... + c ℓ n ℓk the set {p 1 , ..., p s , p} is linearly independent.

We will also need an extension of Theorem 3.2. In order to not interrupt our discussion we state and prove the result needed in the Appendix.

Proof of

∈ N let R k = n ∈ N : {(n ℓk + n k )β} ∈ [1/4, 3/4] . We claim that the set R = R b 1 ∩ . . . ∩ R bs has the advertised property. Let b ∈ B. If p(n) = n ℓ + n then the set p(R b
) is not good for single recurrence for the rotation by β. It follows from Proposition 5.1 that the set R b is not good for ℓ-recurrence. On the other hand, let g ∈ G, (X, B, µ, T ) be a system and A ∈ B with µ(A) > 0. We will show that R g is good for ℓ-recurrence using Proposition 5.2. We set h i = 1 [1/4,3/4] , k i = b i , for i = 1, . . . , s, and f i = 1 A for i = 1, . . . , ℓ in (7), then multiply by 1 A and integrate with respect to µ. We get lim

N →∞ 1 N 1≤n≤N,n∈R µ(A ∩ T -n g A ∩ . . . ∩ T -ℓn g A) = 1 2 s lim N →∞ 1 N N n=1 µ(A ∩ T -n g A ∩ . . . ∩ T -ℓn g A).
Using the polynomial extension of Szemerédi's theorem ( [BeLei]) we get that the last limit is positive, proving that R g is a set of ℓ-recurrence.

The case where the set of bad powers B is infinite is treated as in the proof of Theorem A ′ . We use the finite case and Theorem 8.2. 5.2. Proof of the multiple ergodic theorem. In order to prove Proposition 5.2 we will use a "reduction to affine" technique. The first step is a reduction to nil-systems and is based on Theorems 4.1 and 4.4. Next we show that it suffices to check the result for a particular class of nilsystems, namely, for unipotent affine transformations on finite dimensional tori (the reduction is done in the course of proving Lemma 5.4). Lastly, we verify the result for such transformations (the main ingredient is Lemma 5.3).

We now execute our plan.

Lemma 5.3. Let T be an ℓ-step unipotent affine transformation acting on some finite dimensional torus T d , β be an irrational number, and k, k 1 , . . . , k s ∈ N be distinct for some s ∈ N. Then for every x ∈ T d and functions

f ∈ C(T d ), h 1 , . . . , h s ∈ C(T) we have lim N →∞ 1 N N n=1 h 1 (n ℓk 1 + n k 1 )β • . . . • h s (n ℓks + n ks )β • f (T n k x) = (8) h 1 dt • . . . • h s dt • lim N →∞ 1 N N n=1 f (T n k x).
Proof. Without loss of generality we can assume that k 1 < k 2 < . . . < k s . Arguing as in the proof of 3.1, it suffices to check (8) when f (x) = χ(x) is a character of T d and h 1 (t) = e(c 1 t), . . . , h s (t) = e(c s t), where c 1 , . . . , c s ∈ Z. Equivalently, we need to show that if one of the c i 's is nonzero then for every x ∈ T d we have ( 9) lim

N →∞ 1 N N n=1 e (c 1 (n ℓk 1 + n k 1 ) + . . . + c s (n ℓks + n ks ))β • χ(T n k x) = 0.
Let i min be the minimum i ∈ {1, . . . , s} such that c i = 0 and i max be the maximum i ∈ {1, . . . , s} such that c i = 0. Notice that since the affine transformation T is ℓstep nilpotent, by the definition of matrix multiplication the coordinates of T n x are polynomials in n of degree at most ℓ. Hence,

χ(T n k x) = e(q(n k ))
for some real valued polynomial q (depending on x) with deg q ≤ ℓ. We denote p(n) = q(n k ). Consider two cases:

Case 1. Suppose that k i min < k. Notice that the non-constant terms of the polynomial p have degree greater or equal to k. Therefore, in (9) we are averaging a sequence of the form e(P (n)) for some polynomial P that has a nonconstant irrational coefficient (namely the coefficient of n k i min ). By Weyl's uniform distribution theorem ( [We]) this average must converge to zero.

Case 2. Suppose that k i min > k. Since deg p ≤ ℓk, in (9) we are again averaging a sequence of the form e(P (n)) for some polynomial P that has a nonconstant irrational coefficient (namely the coefficient of n ℓk imax ). We conclude by Weyl's uniform distribution theorem that this average must converge to zero.

Lemma 5.4. Let (X = G/Γ, G/Γ, m, T a ) be an ℓ-step nilsystem, x ∈ X, β be an irrational number, and k, k 1 , . . . , k s be distinct positive integers for some s ∈ N. Let g(n) = (n ℓk 1 + n k 1 )β, . . . , (n ℓks + n ks )β, a n k x . Then the sequence (g(n)) n∈N has an asymptotic distribution of the form λ ⊗ ρ where λ is the Lebesgue measure on T s and ρ is the asymptotic distribution of the sequence a n k x n∈N in X.

Proof. Let us denote Y = {a n k x : n ∈ N}. Suppose first that the set Y is connected. It follows from part (i) of Theorem 4.5 and the discussion in Section 4.3 that Y is isomorphic to a connected sub-nilmanifold H/∆ of X, so we can assume that Y = H/∆.

We need to show that (g(n)) n∈N is uniformly distributed on the nilmanifold T s ×Y . By part (ii) of Theorem 4.5 it suffices to show that the sequence (n ℓk 1 + n k 1 )β, . . . , (n ℓks + n ks )β, a n k π Z (x) n∈N is uniformly distributed on T s × Z where Z = H/([H 0 , H 0 ]∆) and π Z : Y → Z is the natural projection. Substituting H/[H 0 , H 0 ] for H we can assume that Z = H/∆ where H 0 is Abelian. Since Z is connected and H 0 is Abelian, by Theorem 4.6 we can assume that T a , acting on Z, is an ℓ-step unipotent affine transformation on some finite dimensional torus. In this case the result follows from Lemma 5.3.

In the general case we argue as follows: By part (i) of Theorem 4.5 we have Y = ∪ t i=1 Y i where Y i are connected subnilmanifolds of X such that Y i = {a (tn+i) k x : n ∈ N} for i = 0, . . . , t -1. Applying the previous argument (coupled with the analogous version of Lemma 5.3) we get that for i = 0, . . . , t -1 the sequence (g(tn + i)) n∈N is uniformly distributed on the set T s ×Y i . We obtain the announced result with ρ being the arithmetic mean of the uniform probabilities on the Y i 's.

Proof of Proposition 5.2. First notice that using an ergodic decomposition argument we can assume that the system is ergodic. Since both limits in (7) exist (see [START_REF] Host | Convergence of polynomial ergodic averages[END_REF], [START_REF] Leibman | Convergence of multiple ergodic averages along polynomials of several variables[END_REF]), it suffices to show that identity (7) holds weakly, that means, for f 0 , . . . , f ℓ ∈ L ∞ (µ), and Riemann integrable functions h 1 , . . . , h s : T → C we have lim

N →∞ 1 N N n=1 h 1 (n ℓk 1 + n k 1 )β • . . . • h s (n ℓks + n ks )β • f 0 • T n k f 1 • . . . • T ℓn k f ℓ dµ = (10) h 1 dt • . . . • h s dt • lim N →∞ 1 N N n=1 f 0 • T n k f 1 • . . . • T ℓn k f ℓ dµ,
If f i ⊥Z ℓ for some i ∈ {0, 1, . . . , ℓ}, then by Proposition 4.2 and Example (ii) after Theorem 4.1, both limits in (10) are zero. So we can assume that f i ∈ Z ℓ for all i ∈ {0, 1, . . . , ℓ}. By [START_REF] Host | Nonconventional ergodic averages and nilmanifolds[END_REF], we know that the factor Z ℓ is isomorphic to an inverse limit of ℓ-step nilsystems. Moreover, using a standard approximation argument we reduce our study to the case where the system is an ℓ-step nilsystem, say (X = G/Γ, G/Γ, m, T a ) for some a ∈ G. Hence, (10) would follow if we show that for every x ∈ X the sequence (n ℓk 1 + n k 1 )β, . . . , (n ℓk s + n k s )β, a n k x, . . . , a ℓn k x n∈N has an asymptotic distribution in T s × X ℓ of the form λ ⊗ ρ, where λ is the Lebesgue measure on T s and ρ is the asymptotic distribution of the sequence a n k x, . . . , a ℓn k x n∈N in X ℓ . But this follows from Lemma 5.4 applied to the nilsystem induced by the rotation by b = (a, a 2 , . . . , a ℓ ) on the ℓ-step nilmanifold X ℓ for the diagonal point (x, x, . . . , x) ∈ X ℓ . 5.3. Related results and questions. We discuss here some possible variations on Theorems B and B ′ . We have shown that if G is a prescribed set of integers then there exists R ⊂ N such that the set R g is good for ℓ-recurrence for all g ∈ G, and R b is bad for ℓ-recurrence for b ∈ B = N \ G. A natural question is whether it is possible to strengthen this result and make R b have bad 1-recurrence properties? In several cases this can be done, but there are some limitations too. For example, if R g is good for ℓ-recurrence then the set R kg , k = 1, . . . ℓ, is good for 1-recurrence for all circle rotations (see Proposition 5.1). We can show that this is actually the only restriction.

Theorem 5.5. Let G ⊂ N and ℓ : G → N. If B = N \ G then the condition B ∩ kG = ∅, for 1 ≤ k ≤ ℓ(g)
is necessary and sufficient for the existence of a set R ⊂ N such that

• for all g ∈ G, the set R g is good for ℓ(g)-recurrence,

• for all b ∈ B, the set R b is bad for recurrence for some circle rotation.

The proof is analogous to the proof of Theorem B ′ so we are just going to sketch it. If B is finite, say B = {b 1 , b 2 , . . . , b s }, we fix an irrational number β and define R to be the intersection of the sets n ∈ N : {n b i β} ∈ [1/4, 3/4] for i = 1, . . . , s. Then for b ∈ B the set R b is obviously bad for the 1-recurrence for rotation by β. To show that R g is good for ℓ(g)-recurrence when g ∈ G, we study the limiting behavior of the following multiple ergodic averages:

1 N N n=1 h 1 (n b 1 β) • . . . • h s (n bs β) • f (T n g x) • f (T 2n g x) • . . . • f (T ℓ(g)n g x).
We can establish an ergodic theorem analogous to Proposition 5.2 using a minor modification of the argument used in Section 5.2, showing that the set R g is good for ℓ(g)recurrence. The case where B is infinite can be treated using the finite case and Theorem 8.2, much like it was done in the proof of Theorem A ′ .

As we remarked before, if R is a set of 2-recurrence then R 2 is a set of recurrence for circle rotations. The same method shows that it is actually a set of recurrence for rotations on any multidimensional torus. But is R 2 necessarily a set of 1-recurrence?

Question 1. If R ⊂ Z is a set of 2-recurrence, is it true that R 2 = {r 2 : r ∈ R} is a set of 1-recurrence?
Another closely related question is the following (a similar question was asked in [BrGrLa]):

Question 2. If R ⊂ Z is a set of ℓ-recurrence for every ℓ ∈ N, is the same true for the set R 2 = {r 2 : r ∈ R}?

Theorem B ′ is a model for a variety of multiple recurrence results one may attempt to prove. For example, the following question is related to a plausible generalization of Theorem B ′ : Question 3. Let p 1 , . . . , p ℓ be a family of integer polynomials with zero constant term and G be a set of positive integers. Does there exist a set R ⊂ N such that: for all k ∈ N, the set R k = {r k : r ∈ R} is good for recurrence along the sequence (p 1 (n), . . . , p ℓ (n)) if and only if k ∈ G?

We are unable to give a positive answer because we lack detailed information about the limiting behavior of multiple ergodic averages along general polynomial schemes.

6. Good and bad powers for sets of (n a 1 , . . . , n a ℓ )-recurrence We begin by a multiple ergodic theorem that will be used in the proof of Theorem C. We remind the reader that the set A ℓ consists of all ℓ-tuples (a 1 , a 2 , . . . , a ℓ ) ∈ N ℓ such that a 1 < a 2 < . . . < a ℓ . Proposition 6.1. Let (X, B, µ, T ) be an ergodic system, f 1 , . . . , f ℓ ∈ L ∞ (µ), h 1 , . . . , h s : T → C be Riemann integrable functions. Furthermore let (a 1,1 , . . . , a 1,ℓ ), . . ., (a s,1 , . . . , a s,ℓ ), (b 1 , . . . , b ℓ )∈ A ℓ be distinct vectors, and suppose that the real numbers 1, α 1 , . . . , α s are rationally independent. If p i (n) = n a i,1 + . . . + n a i,ℓ for i = 1, . . . , s, then

lim N →∞ 1 N N n=1 h 1 p 1 (n)α 1 • . . . • h s p s (n)α s • T n b 1 f 1 • . . . • T n b ℓ f ℓ = (11) h 1 dt • . . . • h s dt • lim N →∞ 1 N N n=1 T n b 1 f 1 • . . . • T n b ℓ f ℓ ,
where the convergence takes place in L 2 (µ).

Remark. Both limits exist by [START_REF] Host | Convergence of polynomial ergodic averages[END_REF] and [START_REF] Leibman | Convergence of multiple ergodic averages along polynomials of several variables[END_REF].

Proof. First notice that using an ergodic decomposition argument we can assume that the system is ergodic. Since the limits in (11) exist, it suffices to show that identity (11) holds weakly, that means, for f 0 , f 1 , . . . , f ℓ ∈ L ∞ (µ), and Riemann integrable functions

h 1 , . . . , h s : T → C we have lim N →∞ 1 N N n=1 h 1 p 1 (n)α 1 • . . . • h s p s (n)α s • f 0 • T n b 1 f 1 • . . . • T n b ℓ f ℓ dµ = (12) h 1 dt • . . . • h s dt • lim N →∞ 1 N N n=1 f 0 • T n b 1 f 1 • . . . • T n b ℓ f ℓ dµ.
If f i ⊥K for some i ∈ {0, 1, . . . , ℓ} then by Proposition 4.3 both limits in ( 12) are zero. So we can assume that f i ∈ K for all i ∈ {0, 1, . . . , ℓ}. Every Kronecker system is isomorphic to a rotation on a monothetic compact Abelian group with the Haar measure, and any such group is the inverse limit of groups of the form T k × Z d for some nonnegative integers k, d. Hence, using a standard approximation argument we can furthermore assume that our system is a rotation on T k × Z d with the Haar measure m, and also that f i (x) = χ i (x), i = 0, 1, . . . , ℓ, for some characters χ 0 , χ 1 , . . . , χ ℓ of T k × Z d , and h i (t) = e(l i t), i = 1, . . . , s, for some l 1 , . . . , l s ∈ Z. If l i = 0 for i = 1, . . . , s then ( 12) is obvious. If this is not the case, without loss of generality we can assume that l 1 = 0. Then the right hand side of ( 12) is zero. Furthermore, notice that the integral

χ 0 • T n b 1 χ 1 • . . . • T n b ℓ χ ℓ dm is either zero or has the form e(n b 1 β 1 + . . . + n b ℓ β ℓ ) for some β 1 , . . . , β ℓ ∈ R.
Keeping in mind these two facts, we see that in order to verify (12) it suffices to show that (13) lim

N →∞ 1 N N n=1 e(l 1 p 1 (n)α 1 + . . . + l s p s (n)α s + n b 1 β 1 + . . . + n b ℓ β ℓ ) = 0.
Since (a 1,1 , . . . , a 1,ℓ ) and (b 1 , . . . , b ℓ ) are distinct vectors in A ℓ , there exists j ∈ {1, . . . , ℓ} such that a 1,j = b i for every i ∈ {1, . . . , ℓ}. Then the coefficient γ of n a 1,j in ( 13) is equal to l 1 α 1 plus an integer linear combination of the numbers α 2 , . . . , α s . Since l 1 = 0 and the numbers 1, α 1 , α 2 , . . . , α s are rationally independent it follows that γ is nonzero. By Weyl's uniform distribution theorem ( [We]) we conclude that ( 13) is satisfied, completing the proof.

We will also use the following simple lemma: Lemma 6.2. If R is a set of recurrence along the sequence (n a 1 , . . . , n a ℓ ) then for every α ∈ R and ε > 0 there exists r ∈ R such that {(r

a 1 + . . . + r a ℓ )α} ∈ [0, ε] ∪ [1 -ε, 1).
Proof. Consider the system induced by the rotation by α on T with the Haar measure, and let A = [0, ε/ℓ]. Our assumption easily implies that there exists r ∈ R such that {r a 1 α}, . . . , {r a ℓ α} ∈ [0, ε/ℓ] ∪ [1ε/ℓ, 1). The result follows.

Proof of Theorem B. If G = A ℓ the polynomial Szemerédi theorem ( [BeLei]) shows that R = N works. So we can assume that G = A ℓ . Suppose first that the nonempty set

B = A ℓ \ G is finite and consists of the vectors (b 1,1 , . . . , b 1,ℓ ), . . ., (b s,1 , . . . , b s,ℓ ). Let R = n ∈ N : {p 1 (n)α 1 }, . . . , {p s (n)α s } ∈ [1/4, 3/4]
where p i (n) = n b i,1 + . . . + n b i,ℓ , i = 1, . . . , ℓ, and 1, α 1 , . . . , α s ∈ R are rationally independent. We claim that R is a set of recurrence along the sequence (n a 1 , . . . , n a ℓ ) if and only if (a 1 , . . . , a ℓ ) ∈ G.

Let (b i,1 , . . . , b i,ℓ ) ∈ B. Since {p i (n)α i } ∈ [1/4, 3/4
] for every n ∈ R, we get by Lemma 6.2 that R is not a set of recurrence along the sequence (n b i,1 , . . . , n b i,ℓ ). We will now use Proposition 6.1 to show that if (g 1 , . . . , g ℓ ) ∈ G then R is a set of recurrence along the sequence (n g 1 , . . . , n g ℓ ). Let (X, B, µ, T ) be a system, and A ∈ B with µ(A) > 0. Set h i = 1 [1/4,3/4] for i = 1, . . . , s, and f i = 1 A for i = 1, . . . , ℓ in (11), multiply by 1 A and integrate with respect to µ. We find that lim

N →∞ 1 N 1≤n≤N,n∈R µ(A ∩ T -n g 1 A ∩ . . . ∩ T -n g ℓ A) = 1 2 s lim N →∞ 1 N N n=1 µ(A ∩ T -n g 1 A ∩ . . . ∩ T -n g ℓ A).
By the polynomial extension of Szemerédi's Theorem ( [BeLei]) we have that the last limit is positive, proving that R is a set of recurrence along the sequence (n g 1 , . . . , n g ℓ ).

The case where B is infinite is treated as in the proof of Theorem A ′ using the finite case and Theorem 8.2.

Powers of sequences and sufficient conditions for ℓ-recurrence

Useful sufficient conditions for a given set of integers R to be good for single recurrence were given in [KaMe] 4 . Our objective in this section is to discuss analogous sufficient conditions for higher order recurrence. 7.1. Sufficient conditions for single recurrence. We first prove a single recurrence result, similar to the one given in [KaMe], that will serve as a prototype for the higher order statement we have in mind. The argument is very similar to the one used by Furstenberg ([Fu2]) to prove that the set of squares is good for single recurrence.

Theorem 7.1 (Kamae & Mendès-France [KaMe]). Let (r n ) n∈N be sequence of positive integers that satisfies (i) The sequence (r n α) n∈N is uniformly distributed in T for every irrational α. (ii) The set {n ∈ N : d|r n } has positive upper density for every d ∈ N. Then the set R = {r 1 , r 2 , . . .} is good for single recurrence.

Proof. We first use assumption (i) to show the following: If (X, B, µ, T ) is a system and

f ∈ L ∞ (µ) is such that E(f |K rat ) = 0 then (14) lim N →∞ 1 N N n=1 f • T rn f dµ = 0.
Let σ f be the spectral measure of the function f with respect to our system. Then the limit in ( 14) is equal to (15) lim

N →∞ 1 N N n=1 [0,1) e(r n t) dσ f (t) = [0,1) lim N →∞ 1 N N n=1
e(r n t) dσ f (t).

Since by assumption lim

N →∞ 1 N N n=1
e(r n t) = 0 for t irrational and the measure σ f has no rational point masses (since E(f |K rat ) = 0), the limit in ( 15) is zero and ( 14) follows.

Next we use ( 14) and assumption (ii) to finish the proof. 14) we find that lim

Let A ∈ B with µ(A) > 0. Setting f = 1 A -E(1 A |K rat ) in (
N →∞ 1 N N n=1 µ(A ∩ T -rn A) - 1 N N n=1 E(1 A |K rat ) • T rn E(1 A |K rat ) dµ = 0.
Hence, it suffices to show that ( 16) lim sup

N →∞ 1 N N n=1 E(1 A |K rat ) • T rn E(1 A |K rat ) dµ > 0.
To see this, let ε > 0 (to be determined later), and choose d ∈ N such that

E(1 A |K d ) -E(1 A |K rat ) L 2 (µ) ≤ ε.
Let R ∩ dN = {t 1 , t 2 , . . .}. Since by assumption the set {n ∈ N : d|r n } has positive upper density, in order to show (16) it suffices to show that (17) lim inf

N →∞ 1 N N n=1 E(1 A |K rat ) • T tn E(1 A |K rat ) dµ > 0.
Using the triangle inequality twice we see that the limit in ( 17) is greater or equal than lim inf

N →∞ 1 N N n=1 E(1 A |K d ) • T tn E(1 A |K d ) dµ -2ε.
For g ∈ K d and n ∈ N we have T tn g = g, hence the last expression is equal to

E(1 A |K d ) 2 dµ -2ε. Finally, since E(1 A |K d ) 2 dµ ≥ µ(A) 2
, we see that it suffices to choose ε < µ(A) 2 /2 in order to obtain (17). This completes the proof.

Using standard estimates on exponential sums one can use Theorem 7.1 to deduce some well known results (see [Sa]), for example that the set of squares {n 2 : n ∈ N} and the set of shifted primes {p -1 : p prime} are good for single recurrence. See [BeLes] for a stronger version of the preceding result and several other applications. 7.2. A counterexample for double recurrence. As stated in Proposition 5.1, double recurrence for a set R forces nontrivial single recurrence properties for sets of the form p(R) where p is any quadratic integer polynomial with zero constant term. So in order to extend Theorem 7.1 to double recurrence, one is lead to consider uniform distribution properties of "quadratic nature" as possible substitutes for condition (i) of Theorem 7.1. We first show why the term "quadratic nature" cannot be characterized using standard quadratic polynomials only.

Theorem 7.2. There exists a sequence of positive integers (r n ) n∈N that satisfies: (i) If either γ or δ is irrational then the sequence (r 2 n γ + r n δ) n∈N is uniformly distributed in T. (ii) The set {n ∈ N : d|r n } has density for every d ∈ N. (iii) The set R = {r 1 , r 2 , . . .} is not good for double recurrence.

In order to prove Theorem 7.2 we need two preparatory lemmas. The first one is proven in [Hål] using van der Corput's inequality and some elementary manipulations of the resulting exponential sums. It shows that some simple generalized quadratic sequence is asymptotically orthogonal to standard quadratic sequences.

Lemma 7.3. Suppose that 1, α, β are rationally independent real numbers. Then for every real valued polynomial p with deg p ≤ 2 we have lim

N →∞ 1 N N n=1 e([nα]nβ + p(n)) = 0.
The next result has similar context with Proposition 5.1, it strengthens the single recurrence properties that we can deduce when we know that a set is good for double recurrence.

Lemma 7.4. Suppose that 1, α, β are rationally independent real numbers. If R is a set of double recurrence then for every ε > 0 there exists nonzero r ∈ R such that

{[rα]rβ} ∈ [0, ε] ∪ [1 -ε, 1).
Remark. The conclusion actually holds for every α, β ∈ R but we will not use this.

Proof. Let 0 < ε < 1 and β ′ = β/4. From Lemma 7.3 and Weyl's criterion for uniform distribution it follows that the sequence (

[nα]nβ ′ , nβ ′ ) is uniformly distributed in T 2 . As a result, the set Λ = n ∈ N : {[nα]nβ ′ } and {nβ ′ } ∈ [0, ε/4]
has positive density. Since R is a set of double recurrence and Λ has positive density, there exist m ∈ N and nonzero r ∈ R such that m, m + r, m + 2r ∈ Λ. Then (18)

{mβ ′ }, {(m + r)β ′ }, {(m + 2r)β ′ } ∈ [0, ε/4],
and if for some e 1 , e 2 , e 3 ∈ {0, 1}. Since

A = {[mα]mβ ′ }, B = {[(m + r)α](m + r)β ′ }, C = {[(m + 2r)α](m + 2r)β ′ }.
{A + C -2B} ∈ [0, ε/2] ∪ [1 -ε/2, 1) and {(e 1 + e 2 )(m + 2r)β ′ -2e 3 (m + r)β ′ } ∈ [0, ε/2] ∪ [1 -ε/2, ) (by (18)), equation (19) gives that {4[rα]rβ ′ } ∈ [0, ε] ∪ [1 -ε, 1). Keeping in mind that 4β ′ = β, the proof is complete.
Proof of Theorem 7.2. Let α and β be two real numbers such that 1, α and β are rationally independent. We claim that the set R = n ∈ N : {[nα]nβ} ∈ [1/4, 3/4] has the advertised properties. First notice that by Lemma 7.3 the sequence ([nα]nβ) n∈N is uniformly distributed in T, so we deduce that d(R) = 1/2.

We verify (i). Since the sequence (n 2 γ + nδ) n∈N is uniformly distributed in T, using Weyl's criterion and Lemma 7.3 we can easily derive that the sequence ([nα]nβ, n 2 γ + nδ) n∈N is uniformly distributed in T 2 . It follows that for nonzero integers k we have lim

N →∞ 1 N N n=1 1 [1/4,3/4] ({[nα]nβ}) • e k(n 2 γ + nδ) = 0. Since d(R) = 1/2 this gives for nonzero integers k that lim N →∞ 1 N N n=1 e k(r 2 n γ + r n δ) = 0.
Hence, the sequence (r 2 n γ + r n δ) n∈N is uniformly distributed in T. Next we verify (ii). Using Lemma 7.3 we can show as in the proof of (i) that lim

N →∞ 1 N N n=1 1 [1/4,3/4] ({[nα]nβ}) • e(np/q) = 0
for every noninteger rational number p/q. It follows that the set R is uniformly distributed in arithmetic progressions, a statement stronger than (ii).

Finally we verify (iii). By construction, for every r ∈ R we have {[rα]rβ} ∈ [1/4, 3/4]. Hence, Lemma 7.4 shows that R is not a set of double recurrence, completing the proof. 7.3. Conjecture for ℓ-recurrence. The discussion in the previous section indicates that in order to give necessary conditions for double recurrence, uniform distribution properties in T of generalized quadratic sequences of the form ([r n α]r n β) n∈N should also be taken into account. In the same manner, higher order recurrence forces us to look for uniform distribution properties involving more complicated generalized polynomials, the general form of which we will not attempt to spell out. It has become apparent in recent years5 that a more efficient way to encode all these conditions is to work in a non-Abelian setup, and look into uniform distribution properties of linear sequences on nilmanifolds. Using this language, we can formulate what we think is a natural generalization of the result of Kamae & Mendès-France (Theorem 7.1), and thus state some potentially sufficient conditions for ℓ-recurrence in a very condense form.

Firstly, we need to extend the notion of an irrational rotation on T to general connected nilmanifolds: Given a connected nilmanifold X = G/Γ, an irrational nilrotation in X is an element a ∈ G such that the sequence (a n Γ) n∈N is uniformly distributed on X. We remark that if a ∈ G is irrational nilrotation then a d is irrational for every d ∈ N.

Conjecture I. Let (r n ) n∈N be sequence of positive integers that satisfies: (i) For every connected ℓ-step nilmanifold X and every irrational nilrotation a in X the sequence (a rn Γ) n∈N is uniformly distributed in X. (ii) The set {n ∈ N : d|r n } has positive upper density for every d ∈ N. Then the set R = {r 1 , r 2 , . . .} is good for ℓ-recurrence.

Notice that for ℓ = 1 the conjecture is true since it easily reduces to Theorem 7.1. It can be shown that conditions (i) and (ii) are satisfied for nonconstant polynomials with zero constant term (see [Fr]), and recent work of Green and Tao (see [START_REF] Green | Quadratic uniformity of the Möbius function[END_REF] and [START_REF] Green | Linear equations in primes[END_REF]) indicates that they are probably satisfied for the set of shifted primes {p -1 : p prime} (the shift is needed only for condition (ii)).

For ℓ = 2 the definition of multiplication on a 2-step nilpotent group is simple enough to find it beneficial to rewrite condition (i) in coordinates, much like it is done in the Appendix B of [START_REF] Green | Quadratic uniformity of the Möbius function[END_REF]. One is then led to consider uniform distribution properties involving generalized quadratics, that means, functions p : R → R of the form p(t) = k i=1 [α i t]β i t + γt 2 + δt + c where α i , β i , γ, δ, c ∈ R for i = 1, . . . , k. We say that a generalized quadratic is irrational if the sequence (p(n)) n∈N is uniformly distributed in T.

Conjecture II. Let (r n ) n∈N be a sequence of positive integers that satisfies: (i) The sequence (p(r n )) n∈N is uniformly distributed in T for every irrational generalized quadratic p. (ii) The set {n ∈ N : d|r n } has positive upper density for every d ∈ N. Then the set R = {r 1 , r 2 , . . .} is good for double recurrence. Remark. Our argument can actually be used to verify Conjecture I for any sequence (r n ) n∈N for which the nilfactor Z ℓ turns out to be characteristic for the multiple ergodic averages related to the family {r n , 2r n , . . . , ℓr n }.

We first prove a lemma that will help us deal with systems that have nontrivial "periodic part". for j = 1, . . . , d. Averaging over j we get (21) 0 = lim

N k →∞ 1 N k N k n=1 1 d 1≤j≤d g(b rn j x) = lim N k →∞ 1 N k N k n=1 g(a rn Γ) • 1 d 1≤j≤d χ(e jrn d ) = lim N k →∞ 1 N k N k n=1 g(a rn Γ)•1 I d (n) = lim N k →∞ |I d ∩ [1, N k ]| N k • lim N k →∞ 1 |I d ∩ [1, N k ]| n∈I d ∩[1,N k ] g(a rn Γ).
Note that we used the nontriviality of χ to justify the third equality. Since by condition (ii) the density of the set I d with respect to the intervals [1, N k ] is positive, (21) gives that lim

N k →∞ 1 |I d ∩ [1, N k ]| n∈I d ∩[1,N k ] g(a rn Γ) = 0.
So ( 20) is satisfied with g in place of f . This completes the proof.

Proof of Theorem 7.5. Let ℓ ∈ N. It suffices to show that for every system (X, B, µ, T ) and f ∈ L ∞ (µ), nonnegative and not a.e. zero, we have ( 22) lim sup

N →∞ 1 N N n=1 f • T rn f • . . . • T ℓrn f dµ > 0.
We start with some reductions. Using an ergodic decomposition argument we can assume that the system is ergodic. Furthermore, since d(R) > 0, by example (i) right after Theorem 4.1 and Proposition 4.2, the factor Z ℓ is characteristic for the multiple ergodic averages appearing in (22). Notice also that the projection of f onto Z ℓ is also nonnegative and not a.e. zero. Since by Theorem 4.4 the factor Z ℓ is an inverse limit of ℓ-step nilsystems, we have reduced the problem to establishing (22) for such systems. Moreover, an argument completely analogous to that of Lemma 3.2 in [START_REF] Furstenberg | An ergodic Szemerédi theorem for commuting transformations[END_REF] shows that the positiveness property ( 22) is preserved by inverse limits. Hence, we can further assume that the system is an ergodic ℓ-step nilsystem.

In this case, by Proposition 7.2 of [BeHoKr], there exists an ergodic ℓ-step nilsystem (Y = G/Γ, m, T a ) and a continuous function F on X such that

(23) f • T n f • . . . • T ℓn f dµ = F (a n Γ)
for every n ∈ N.

We can assume that for some

k such that lim N k →∞ |I d ∩ [1, N k ]/N k > 0.
So in order to establish (22), it suffices to show that (24) lim sup

N k →∞ 1 |I d ∩ [1, N k ]| n∈I d ∩[1,N k ] f • T rn f • . . . • T ℓrn f dµ > 0.
Using (23), and noticing that a rn = b rn for n ∈ I d , we see that the last limit is equal to lim sup

N k →∞ 1 |I d ∩ [1, N k ]| n∈I d ∩[1,N k ] F (a rn Γ) = lim sup N k →∞ 1 |I d ∩ [1, N k ]| n∈I d ∩[1,N k ] F (b rn Γ).
Since b is an irrational nilrotation of {0} × Y 0 , by Lemma 7.6 the sequence (b rn Γ) n∈I d is uniformly distributed in {0} × Y 0 with respect to the sequence of intervals [1, N k ]. Also, since b d is irrational, the sequence (b dn Γ) n∈N is uniformly distributed in {0} × Y 0 . It follows that the last lim sup is equal to lim

N k →∞ 1 |I d ∩ [1, N k ]| n∈I d ∩[1,N k ] F (b rn Γ) = lim N →∞ 1 N N n=1 F (b dn Γ).
Using once again that b d = a d and ( 23), we find that the last limit is equal to lim

N →∞ 1 N N n=1 F (a dn Γ) = lim N →∞ 1 N N n=1 f • T dn f • . . . • T dℓn f dµ
which is positive by Furstenberg's multiple recurrence theorem [START_REF] Furstenberg | Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions[END_REF]. This completes the proof.

Appendix: Uniformity for sets of multiple recurrence

We establish some uniform estimates that were used in the proofs of Theorems B' and C. Related estimates were obtained in [BeHoMcParre], but our result is more general and our proof shorter. Definition 8.1. A sequence (u 1 (n), . . . , u ℓ (n)) n∈N with values in Z ℓ is a good sequence for multiple recurrence if, given any system (X, B, µ, T ) and any A ∈ B with µ(A) > 0, there exists n ∈ N such that µ(A ∩ T -u 1 (n) A ∩ . . . ∩ T -u ℓ (n) A) > 0. Using Furstenberg's correspondence principle it is not hard to verify that the sequence (u 1 (n), . . . , u ℓ (n)) n∈N is good for multiple recurrence if and only if for any set Λ of positive upper density in Z, there exists n ∈ N such that |Λ ∩ (Λu 1 (n)) ∩ . . . ∩ (Λu ℓ (n))| > 0.

Theorem 8.2. Let (u 1 (n), . . . , u ℓ (n)) n∈N be a good sequence for multiple recurrence. Then (ii) For every ε > 0 there exist γ = γ(ε) > 0 and N 1 = N 1 (ε), such that for every system (X, B, µ, T ) and A ∈ B with µ(A) ≥ ε, we have that

µ(A ∩ T -u 1 (n) A ∩ . . . ∩ T -u ℓ (n) A) ≥ γ for some n ∈ [1, N 1 ].
Proof. (i) The argument is similar to one used in [START_REF] Frantzikinakis | Ergodic averages for independent polynomials and applications[END_REF]. Suppose that the result fails. Then there exist ε 0 > 0, sequence (δ m ) m∈N of positive real numbers with lim m→∞ δ m = 0, increasing integer sequences (K m ) m∈N , (N m ) m∈N , with N m ≥ K m , and integer sets Λ m ⊂ [-N m , N m ], such that On the sequence space (X = {0, 1} Z , B), where B is the Borel σ-algebra, we define a measure µ on cylinder sets as follows:

µ({x n 1 = i 1 , x n 2 = i 2 , . . . , x ns = i s }) = lim m→∞ |(Λ i 1 m -n 1 ) ∩ (Λ i 2 m -n 2 ) ∩ . . . ∩ (Λ is m -n s ) ∩ [-N m , N m ]| 2N m
where n 1 , n 2 , . . . , n s ∈ Z, and i 1 , i 2 , . . . , i s ∈ {0, 1}. Thus defined, µ extends to a premeasure on the algebra of sets generated by cylinder sets and hence by Carathéodory's extension theorem ( [C]) to a probability measure on B. Then the shift transformation T defined by T (x j ) j∈Z = (x j+1 ) j∈Z preserves the measure µ and gives rise to the system (X, B, µ, T ). If A = {x ∈ X : x(0) = 1}, using the definition of µ we see that

µ(A ∩ T -u 1 (n) A ∩ . . . ∩ T -u ℓ (n) A) = µ({x 0 = 1, x u 1 (n) = 1, . . . , x u ℓ (n) = 1}) = lim m→∞ |Λ m ∩ (Λ m -u 1 (n)) ∩ . . . ∩ (Λ m -u ℓ (n))| 2N m ,
for every n ∈ N. Combining this with ( 25) and ( 26), and remembering that lim m→∞ δ m = 0, we find that µ(A) ≥ ε 0 /2 > 0 and

µ(A ∩ T -u 1 (n) A ∩ . . . ∩ T -u ℓ (n) A) = 0
for all n ∈ N. This contradicts the fact that the sequence (u 1 (n), . . . , u ℓ (n)) n∈N is good for multiple recurrence and completes the proof of (i).

(ii) The argument is similar to one used in [BeHoMcParre]. Let ε > 0 and A ∈ B with µ(A) ≥ ε. Set N 1 = N 0 (ε/2) where N 0 was defined in part (i). For x ∈ X let

f (x) = 1 N 1 N 1 m=1
1 A (T m x).

Since f dµ = µ(A) ≥ ε, if B = {x ∈ X : f (x) ≥ ε/2} we have that 27) holds for all x ∈ C. We have that µ(A∩T -u 1 (n 0 ) A∩. . .∩T -u ℓ (n 0 ) A) = 1 A (T m 0 x)•1 A (T m 0 +u 1 (n 0 ) x)•. . .•1 A (T m 0 +u ℓ (n 0 ) x) dµ which is greater than 1 B (x) • 1 A (T m 0 x) • 1 A (T m 0 +u 1 (n 0 ) x) • . . . • 1 A (T m 0 +u ℓ (n 0 ) x) dµ ≥ µ (C), where the last inequality is valid because (27) holds for all x ∈ C. We have thus verified (ii) with γ = µ(B)/N 2 1 ≥ ε/(2N 2 1 ).

  If A, B ⊂ G, then [A, B] is defined to be the subgroup generated by elements of the form {[a, b] : a ∈ A, b ∈ B} where [a, b] = aba -1 b -1 . We define the commutator subgroups recursively by

  Lie group and Γ is a discrete cocompact subgroup, then the compact space X = G/Γ is said to be an ℓ-step nilmanifold. The group G acts on G/Γ by left translation where the translation by a fixed element a ∈ G is given by T a (gΓ) = (ag)Γ. Let m denote the unique probability measure on X that is invariant under the action of G by left translations (called the Haar measure) and let G/Γ denote the Borel σ-algebra of G/Γ. Fixing an element a ∈ G, we call the system (G/Γ, G/Γ, m, T a ) an ℓ-step nilsystem.

  Theorem B ′ . If G = N then by the polynomial Szemerédi theorem ([BeLei]) R = N works. If G = N then the complement B of G is nonempty. Let us first consider the case where B is finite, say B = {b 1 , . . . , b s }, for some b i ∈ N. Fix an irrational number β and for k

  we have that A, B, C ∈ [0, ε/4]. Using the identity [a + b] = [a] + [b] + 1 {a}+{b}>1 (a, b) we get that A + C -2B =[mα]mβ ′ + ([mα] + 2[rα] + e 1 + e 2 )(m + 2r)β ′ -(19) 2([mα] + [rα] + e 3 )(m + r)β ′ (mod 1) =4[rα]rβ ′ + (e 1 + e 2 )(m + 2r)β ′ -2e 3 (m + r)β ′ (mod 1)

7. 4 .

 4 Proof of conjecture for positive density sets. To add credibility to the previous conjectures we will verify Conjecture I in a special case.Theorem 7.5. Conjecture I holds if d(R) > 0.

  d ∈ N we have Y = Z d × Y 0 where Y 0 is a connected nilmanifold (the torsion part is cyclic since Y admits an ergodic nilrotation). By changing the first coordinate of a to 0 ∈ Z d , we get an irrational element b of the connected nilmanifold {0} × Y 0 that satisfies b d = a d . Let I d = {n ∈ N : d|r n }. Since d(I d ) > 0, there exists an increasing sequence of integers N

  (i) For every ε > 0 there exist δ = δ(ε) > 0 and N 0 = N 0 (ε), such that for everyN ≥ N 0 and integer set Λ ⊂ [-N, N ] with |Λ| ≥ εN , we have |Λ ∩ (Λu 1 (n)) ∩ . . . ∩ (Λu ℓ (n))| ≥ δN for some n ∈ [1, N 0 ].

  |Λ m ∩ (Λ mu 1 (n)) . . . ∩ (Λ mu ℓ (n))| ≤ δ m N m for every m ∈ N and n ∈ [1, K m ].In order to get a contradiction, we will construct a measure preserving system with bad recurrence properties.Form ∈ N set Λ 0 m = Z \ Λ m and Λ 1 m = Λ m .Using a diagonal argument we can find a subsequence of (N m ) m∈N , which for convenience we denote again by (N m ) m∈N , such that the limitlim m→∞ |(Λ i 1 mn 1 ) ∩ (Λ i 2 mn 2 ) ∩ . . . ∩ (Λ i s mn s ) ∩ [-N m , N m ]| 2N mexists for every s ∈ N, n 1 , . . . , n s ∈ Z, and i 1 , . . . , i s ∈ {0, 1}.

  µ(B) + (1µ(B)) • ε/2 ≥ ε, which implies that µ(B) ≥ ε/2. Notice that for x ∈ B we have that |{m ∈ [1, N 1 ] : T m x ∈ A}| ≥ ε 2 N 1 . Letting Λ x = {m ∈ [1, N 1 ] : T m x ∈ A} we get by part (i) that Λ x ∩ (Λ xu 1 (n)) ∩ . . . ∩ (Λ xu ℓ (n)) = ∅, which implies that (27) 1 A (T m x) • 1 A (T m+u 1 (n) x) • . . . • 1 A (T m+u ℓ (n) x) = 1 for some m ∈ [1, N 1 ] and n ∈ [1, N 1 ].Since we have N 1 choices for m and n, we can choose m 0 , n 0 ∈ [1, N 1 ], and a set C ⊂ B such that µ(C) ≥ µ(B)/N 2 1 and (

If Λ ⊂ Z, the upper density of Λ is the number d(Λ) = lim sup N →∞ |Λ ∩ {-N, . . . , N }|/(2N + 1). If the previous limit exists we call it the density of Λ and denote it by d(Λ).

For every ε > 0 we can find continuous functions h, h, such that h ≤ h ≤ h and (hh) dt ≤ ε.

In[START_REF] Host | Nonconventional ergodic averages and nilmanifolds[END_REF] the authors work with ergodic systems, in which case |||f ||| 1 = f dµ , and real valued functions, but the whole discussion can be carried out for nonergodic systems as well and complex valued functions without extra difficulties.

In[KaMe] it is shown that a set R ⊂ N is good for recurrence if for every d ∈ N there exists a sequence (r d,n ) n∈N with values in the set R d = {r ∈ R : d!|r} such that the sequence (r d,n α) n∈N is uniformly distributed (mod 1) for every irrational number α.

See for example[START_REF] Green | Quadratic uniformity of the Möbius function[END_REF],[START_REF] Green | Linear equations in primes[END_REF], where a similar problem arises in the study of asymptotics of ℓ-term arithmetic progressions in the prime numbers.

The first author was partially supported by NSF grant DMS-0701027.

Lemma 7.6. Let d ∈ N and (N k ) k∈N be an increasing sequence of positive integers. Suppose that (r n ) n∈N is a sequence of positive integers that satisfies: (i) For every connected ℓ-step nilmanifold X and every irrational nilrotation a in X the sequence (a r n Γ) n∈N is uniformly distributed in X with respect to the intervals Then the subsequence (r n ) n∈I d also satisfies property (i).

Proof. Let m denote the Haar measure on X. It suffices to show that for every connected ℓ-step nilmanifold and irrational nilrotation a ∈ X we have (20) lim

We will prove (20) by induction on ℓ. For ℓ = 1 we are reduced to the Abelian case and the proof is easy (if not, look at the proof of the inductive step). Suppose that the statement holds for all connected (ℓ -1)-step nilmanifolds, and let X = G/Γ be a connected ℓ-step nilmanifold and a ∈ G be an irrational nilrotation in X.

We start with a reduction. Since G is ℓ-step nilpotent, the subgroup

Using this representation for X we can assume that Γ ℓ = {e} and so G ℓ is a compact Abelian Lie group. Since G ℓ is connected if ℓ ≥ 2 (see discussion at the end of Section 4.3) we can further assume that it is some finite dimensional torus.

By F we denote the set of g ∈ C(X) with the following property: there exists a character χ of the torus G ℓ such that for every b ∈ G ℓ we have g(bx) = χ(b) • g(x) for every x ∈ X. It follows from [START_REF] Lesigne | Théorèmes ergodiques pour une translation sur un nilvariété[END_REF] (see the proof of Proposition on page 121) that linear combinations of functions in F form a dense subset of C(X). So it suffices to verify (20) for functions in F.

Let g ∈ F. If the character χ defined before is trivial then g is G ℓ -invariant and so it factors through the connected (ℓ -1)-step nilmanifold (G/G ℓ )/(Γ/Γ ℓ ). Applying the induction hypothesis we get that (20) holds for g in place of f . Suppose now that there exists a nontrivial character χ of G ℓ such that g(bx) = χ(b) • g(x) for x ∈ X. Integrating this equation with respect to x and using that x → bx is measure preserving gives g dm = 0. So it suffices to show that the limit in ( 20) is zero when g takes the place of f . Since G ℓ is a torus there exists e d ∈ G ℓ such that e d d = 1 and e j d = 1 for j = 1, . . . d -1, where 1 is the identity element in G ℓ . Since a is an irrational nilrotation, for every j ∈ N, the sequence (a j+nd Γ) n∈N is uniformly distributed in X. It follows that for j = 1, . . . , d, the nilrotations b j = a • e j d are also irrational on X. So condition (i) gives that lim