Emmanuel Lesigne
email: lesigne@univ-tours.fr

Vitaly Bergelson
email: vitaly@math.ohio-state.edu

VAN DER CORPUT SETS IN Z d

Keywords: 1991 Mathematics Subject Classification. 11K06, 28D05, 37A45, 42A82 van der Corput inequality, van der Corput set, set of recurrence, intersective set, uniform distribution, positive-definite sequences, ergodic sequences

In this partly expository paper we study van der Corput sets in Z d , with a focus on connections with harmonic analysis and recurrence properties of measure preserving dynamical systems. We prove multidimensional versions of some classical results obtained for d = 1 in [Kam-MF] and [Ruz], establish new characterizations, introduce and discuss some modifications of van der Corput sets which correspond to various notions of recurrence, provide numerous examples and formulate some natural open questions.

Introduction

The main topic of our paper is the intriguing connection between positivedefinite sequences, recurrence properties of measure preserving dynamical systems, and the theory of uniform distribution mod 1.

Let (X, A, µ, T ) be an invertible probability measure preserving dynamical system 1 . Given a set A ∈ A with µ(A) > 0, let R A = {n ∈ Z, n = 0 : µ (A ∩ T n A) > 0}. While the classical Poincaré recurrence theorem, which states that the set R A is non-empty (and hence infinite), is nowadays an easy exercise, quite a few of the more subtle properties of sets of returns R A and of related sets R A,ǫ = {n ∈ Z, n = 0 : µ (A ∩ T n A) > ǫ} are still not fully understood.

Following Furstenberg ([Fu2]), let us call a set of integers D a set of recurrence, if for any m.p.s. (X, A, µ, T ) and any A ∈ A with µ(A) > 0 one has D ∩ R A = ∅. For example, for any k ∈ N, the set kN is a set of recurrence (just consider the system (X, A, µ, T k )) and any set of recurrence has a non-empty intersection with the set kN (just consider a permutation of a finite set). A more general (and still rather trivial) example is provided by the set of differences {n in j : i > j}, where (n i ) i≥1 is an increasing sequence of integers. (To see that this is a set of recurrence, just observe that if µ(A) > 0, then the sets T n i A cannot be pairwise disjoint, µ(X) being finite.) The following generalization of the Poincaré recurrence theorem obtained by Furstenberg (see [START_REF] Furstenberg | Poincaré recurrence and number theory[END_REF], [START_REF] Furstenberg | Recurrence in Ergodic Theory and Combinatorial Number Theory[END_REF]) gives a much less trivial example of a set of recurrence.

Theorem 0.1. For any polynomial p(n) ∈ Z[n], satisfying p(0) = 0, for any m.p.s. (X, A, µ, T ) and for any A ∈ A with µ(A) > 0, there exists n ∈ N such that p(n) = 0 and µ A ∩ T p(n) A > 0.

Following Ruzsa ([Ruz]), let us call a set D ⊂ N intersective, if for any S ⊂ N of positive upper density 2 there exist x, y ∈ S such that xy ∈ D. 1 Unless explicitly stated otherwise, we will assume in this paper that the measure preserving transformations we are dealing with are invertible and that invariant measures are normalized. We will write m.p.s. for invertible probability measure preserving dynamical system. It is not hard to show that a set D is intersective if and only if it is a set of combinatorial recurrence, that is, such that for any S ⊂ N with d(S) > 0, there exists n ∈ D such that d (S ∩ (Sn)) > 0. This hints that the notions "set of recurrence" and "intersective set" are related and, indeed, it turns out that these notions coincide. (The fact that intersectivity implies measure-theoretic recurrence has been remarked by several authors, see for example [BM] and [Berg.1]. The fact that measure-theoretic recurrence implies combinatorial recurrence is a consequence of Furstenberg's correspondence principle, see for example [Berg.3].) Thus, for example, Theorem 0.1 implies Sàrközy's theorem ( [S]), which states that for any polynomial p(n) ∈ Z[n] satisfying p(0) = 0 and any set S ⊂ N with d(S) > 0 there exist x, y ∈ S and n ∈ N such that xy = p(n). We remark that it was shown in [Kam-MF] that a necessary and sufficient condition for a polynomial p(n) ∈ Z [n] to satisfy the Furstenberg-Sàrközy theorem is that for any positive integer k there exists an integer n such that p(n) is divisible by k. Actually, Kamae and Mendès France in [Kam-MF] showed that many sets of recurrence, including the mentioned above sets have a stronger property which they called the van der Corput property. Definition. A set D of positive integers is a van der Corput set (or vdC set) if it has the following property : given a real sequence (x n ) n∈N , if all the sequences (x n+dx n ) n∈N , d ∈ D, are uniformly distributed mod 1, then the sequence (x n ) n∈N is itself uniformly distributed mod 1.

This concept and terminology3 come from the van der Corput inequality, which is presented at the beginning of the next section, and which motivates the following van der Corput trick : if for a given real sequence (x n ) n∈N and any h ∈ N the sequence (x n+hx n ) n∈N is uniformly distributed mod 1, then the sequence (x n ) n∈N is uniformly distributed mod 1. Van der Corput's inequality and its application to uniform distribution appeared for the first time in [vdC], under the name Dritte Haupteigenschaft (third principal property).

Kamae and Mendès France showed in [Kam-MF] that every vdC set is a set of recurrence. The other implication is false : Bourgain has constructed in [Bou] an example of a set of recurrence which is not a vdC set.

The notions introduced above are connected via the notion of positivedefiniteness. Indeed, it is easy to check that the sequence (µ(A ∩ T n A)) is positive-definite4 , which establishes the connection between sets of recurrence and properties of positive-definite sequences. As for the vdC property, let us first note that in light of Weyl's criterion (see [Ku-N]), the sequence (x n+dx n ) n∈N is uniformly distributed mod 1 if and only if, for any k ∈ Z, k = 0, one has (1) lim

N →+∞ 1 N N n=1
e 2πik(x n+d -xn) = lim

N →+∞ 1 N N n=1
e 2πikx n+d e 2πikxn = 0. Now, given a bounded sequence α : N → C, it is not hard to see that for some increasing sequence of integers (N j ) j∈N the limit

(2) lim j→+∞ 1 N j N j n=1 α(n + d)α(n) = γ(d)
exists for all d ∈ Z and that, moreover, the sequence γ is positive-definite (see [Bert]). Juxtaposing (1) and (2) we see that the vdC property is also connected to the properties of positive-definite sequences. By the Bochner-Herglotz theorem (see for example [Rud], Subsection 1.4.3), any positive-definite sequence ϕ is given by the Fourier coefficients of a positive measure ν ϕ on the circle :

ϕ(n) = T e 2πinx dν ϕ (x) ,
and the properties of this measure play a crucial role in verifying that certain sets are vdC and in establishing the connections between (various versions of) vdC sets and sets of recurrence (see in particular Section 3 below ).

The following fact is also useful for a better understanding of the link between vdC sets and sets of recurrence. Let D ⊂ Z. We prove (see Corollary 1.31) that D is a vdC set if and only if the following is true : given a bounded sequence of complex numbers (u n ) n∈N , if for all d ∈ D, the sequence (u n+d u n ) converges to zero in the Cesàro sense, then the sequence (u n ) also converges to zero in the Cesàro sense. We also prove (see Theorem 3.1) that D is a set of recurrence if and only if the analagous property holds with "(u n ) is a bounded sequence of complex numbers" replaced by "(u n ) is a bounded sequence of positive real numbers".

Driven by the desire to obtain new applications to combinatorics and to better understand the recurrence properties of measure-preserving Z dactions, we focus in this paper on Z d versions of vdC sets. As we will see, many known properties extend from Z to Z d with relative ease. Still, some properties turn out to be more recalcitrant and their extensions to Z d demand more work.

The definition of vdC set in Z d is given in Subsection 1.2. Here are some examples of facts/theorems which will be obtained in subsequent sections. -The set S is a set of multiple recurrence for Z-actions6 .

•

-For any q ∈ N, there exists n ∈ N such that p 1 (n), p 2 (n), . . . , p d (n) are all divisible by q. Moreover these equivalent properties are also necessary and sufficient for the set S to be an enhanced vdC set (see Definition 3 in Subsection 2.2) and a set of strong recurrence (see Definition 5 in Subsection 3.1).

• Let P be the set of prime numbers. For any finite family f 1 , f In order to make the paper more readable we will restrict discussion mainly to dimension d = 2. The reader should have no problem verifying that our proofs work for general d ∈ N.

In Section 2, we introduce the notion of "enhanced vdC set". We show that the enhanced vdC property is equivalent to the FC + property (which appears in [Kam-MF], with a reference to Y. Katznelson). Moreover, the enhanced vdC property is related to the notion of strong recurrence in the same way as vdC sets are related to sets of recurrence. In Subsection 2.4 we collect some natural open questions.

In Section 3 we discuss links between recurrence and vdC properties. We also introduce and discuss the notions of density vdC set and nice vdC set.

In Section 4 we briefly discuss some modifications of the notion of vdC set which are connected to various notions of uniform distribution.

It is worth mentioning that in practically every paper in the area of Ergodic Ramsey Theory, some version of the van der Corput trick for sequences in Hilbert spaces is used. See for example [Fu-Kat-O], , [Berg-Lei-McC], [Berg-McC], [Fr-Les-Wi] dealing with multiple recurrence, and [Berg.2], , [Ho-Kr], [Z] and [Lei] dealing with mean convergence of multiple ergodic averages. The van der Corput trick is also useful in establishing results pertaining to pointwise convergence : see for example [Les] and [Fr].

The influence on our work of the above-mentioned paper of Kamae and Mendès France, and of the fundamental ideas developed by Ruzsa in [Ruz], cannot be exaggerated. We are especially grateful to Randall McCutcheon for numerous useful suggestions, and would like to thank Inger Håland-Knutson, Anthony Quas and Máté Wierdl for pertinent communications.

Throughout the paper, we will use the classical notation e(t) := e 2πit for t ∈ R or t ∈ T = R/Z.

Van der Corput sets in Z d

In this section we develop a theory of van der Corput sets in the multidimensional lattice Z d , which is parallel to the known theory in Z (see [Kam-MF], [Ruz], [Mo]). As we have already mentioned in the introduction, we limit our presentation to the case d = 2. Definitions, results and arguments in this section follow the one dimensional case, except at one point : in order to obtain a generalized van der Corput inequality, Ruzsa uses in [Ruz] a theorem of Fejer stating that any positive trigonometric polynomial in one variable is the square modulus of another trigonometric polynomial ; this fact is no longer true for trigonometric polynomial of several variables, hence we are forced to use a different argument to derive the generalized van der Corput inequality in the multidimensional case (cf. Subsection 1.4).

1.1. Van der Corput's inequality and van der Corput's principle.

, 0) ∈ Z 2 . Theorem 1.1. Let N = (N 1 , N 2 ) ∈ N 2
, and (u n ) 0<n≤N be a finite family of complex numbers indexed by

([1, N 1 ] × [1, N 2 ]) ∩ Z 2 . For h = (h 1 , h 2 ) ∈ Z 2 , we define γ(N, h) := 0<n≤N 0<n+h≤N u n+h • u n .
For any

H = (H 1 , H 2 ) ∈ N 2 , we have 0<n≤N u n 2 ≤ (N 1 + H 1 )(N 2 + H 2 ) H 2 1 H 2 2 -H<h<H (H 1 -|h 1 |)(H 2 -|h 2 |)γ(N, h) .
The preceding inequality is usually used in the following form

(3) 0<n≤N u n 2 ≤ (N 1 + H 1 )(N 2 + H 2 ) H 1 H 2 -H<h<H |γ(N, h)| .
(The proof of Theorem 1.1 is an elementary application of Cauchy's inequality. It is a particular case of the calculations presented in Subsection 1.1.3.)

1.1.2. Van der Corput's principle in Z 2 .
Let (u n ) n∈N 2 be a family of complex numbers. Starting from inequality (3), dividing by (N 1 N 2 ) 2 , then letting N 1 and N 2 go to infinity, we obtain that, for any H ∈ N 2 , lim sup

N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N u n 2 ≤ 1 H 1 H 2 -H<h<H lim sup N 1 ,N 2 →+∞ 1 N 1 N 2 |γ(N, h)| .
As a direct consequence we obtain the following proposition.

Proposition 1.2. If (u n ) n∈N 2 is a family of complex numbers such that inf H>0 1 H 1 H 2 -H<h<H lim sup N 1 ,N 2 →+∞ 1 N 1 N 2 |γ(N, h)| = 0 then lim N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N
u n = 0 .

We use the following notion of uniform distribution for a family indexed by N 2 . Definition 1. A family (x n ) n∈N 2 of real numbers is uniformly distributed mod 1 if for any continuous function f on R, invariant under translations by elements of Z, we have (4) lim

N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N f (x n ) = [0,1] f (t) dt .
Other useful notions of uniform distribution can be introduced : for example, one can replace in (4) the averages

1 N 1 N 2 0<n≤N . . . N 1 ,N 2 →+∞ by 1 (N 1 -M 1 )(N 2 -M 2 ) M ≤n<N . . . N 1 -M 1 ,N 2 -M 2 →+∞
; this leads to the notion of well distributed sequences. Or, one can consider averages defined by a given Følner sequence. We postpone remarks on these variations to Section 4. Note that since property (4) has an asymptotic nature, it makes sense even if the entries in the sequence (x n ) are defined only for indices n = (n 1 , n 2 ) for n 1 , n 2 large enough. We tacitly utilize this observation in the formulation of Corollary 1.3 below and throughout the paper.

Let us recall the classical Weyl's criterion for uniform distribution (see [We], [Ku-N]). A family (x n ) n∈N 2 of real numbers is u.d. mod 1 if and only if, for any k ∈ Z \ {0}, lim

N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N
e(kx n ) = 0 .

As in dimension 1, van der Corput's principle in Z d has a useful corollary pertaining to uniform distribution.

Corollary 1.3. Let (x n ) n∈N 2 be a family of real numbers. If for any h ∈ Z 2 \ {0} the family (x n+h -x n ) n∈N 2 is u.d. mod 1, then the family (x n ) n∈N 2 is u.d. mod 1.
When we apply Proposition 1.2 in order to prove Corollary 1.3, we see that it is sufficient to let only one of H 1 , H 2 go to infinity. The following definition will allow us to give a more general version of this corollary.

Let D be a subset of Z 2 . We define δ(D) := sup

H 1 ,H 2 ≥0 1 (2H 1 + 1)(2H 2 + 1) card (D ∩ [-H 1 , H 1 ] × [-H 2 , H 2 ]) .
( Proof. There exists a sequence H (k) (with

H (k) := (H (k) 1 , H (k) 2 )) in (N ∪ {0}) 2 such that lim k→+∞ 1 (2H (k) 1 + 1)(2H (k) 2 + 1) card D ∩ [-H (k) 1 , H (k) 1 ] × [-H (k) 2 , H (k) 2 ] = 1 .
Let (u n ) n∈N 2 be a family of complex numbers of modulus 1 such that, for any d ∈ D, lim

N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N
u n+d u n = 0 .

For any d ∈ D, we have lim

N 1 ,N 2 →+∞ 1 N 1 N 2 γ(N, d) = 0 .
We deduce from van der Corput's inequality that 1

N 1 N 2 0<n≤N u n 2 ≤ (N 1 + H 1 + 1)(N 2 + H 2 + 1) N 1 N 2 (H 1 + 1)(H 2 + 1) -H≤d≤H 1 N 1 N 2 |γ(N, d)| .
Using the fact that |γ(N, d)| ≤ N 1 N 2 , we obtain lim sup

N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N u n 2 ≤ 1 (H 1 + 1)(H 2 + 1) card (D c ∩ [-H 1 , H 1 ] × [-H 2 , H 2 ]) .
The right hand side of the last inequality goes to zero along the sequence H (k) . This argument can be applied to u n = e(kx n ) (no matter how x n is defined for n ∈ Z 2 \ N 2 ) for any choice of k ∈ Z, k = 0. Thus, the result follows from Weyl's criterion.

Example. If, for any positive integer j, the family (x n+(j,0) -x n ) is u.d. mod 1, then the family (x n ) is u.d. mod 1.

Example. The first application of van der Corput's inequality was to Weyl's equidistribution theorem for polynomial sequences ( [We], [vdC]). The twoparameter version of this theorem says the following : if P ∈ R[X, Y ] is a real polynomial in two variables and if at least one coefficient of a non constant monomial in P is irrational, then the family (P (n 1 , n 2 )) (n 1 ,n 2 )∈N 2 is uniformly distributed mod 1. (This result has a straightforward generalization to polynomials in more than two variables.) This multiparameter equidistribution theorem is a direct consequence of either Corollary 1. Let u be a complex-valued function defined on E. We have

(5) n∈E u(n) 2 ≤ |E • D -1 | |D| d∈D•D -1 n∈E n∈E•d -1 u(n • d)u(n) . Proof. Define u(n) to be zero if n / ∈ E. We have n∈E u(n) 2 = 1 |D| d∈D n∈E•d -1 u(n • d) 2 = 1 |D| n∈E•D -1 d∈D u(n • d) 2 .
Using Cauchy's inequality, we obtain

n∈E u(n) 2 ≤ |E • D -1 | |D| 2 n∈G d∈D u(n • d) 2 ,
and this last expression is equal to

|E • D -1 | |D| 2 d,d ′ ∈D n∈G u(n • d)u(n • d ′ ) = |E • D -1 | |D| 2 d ′ ∈D d∈D•d ′-1 n∈G u(n • d)u(n) ≤ |E • D -1 | |D| 2 d ′ ∈D d∈D•D -1 n∈G u(n • d)u(n) .
Note that inequality (5) contains inequality (3) as a special case corresponding to

G = Z 2 , E = ([1, N 1 ] × [1, N 2 ]) ∩ Z 2 and D = ([1, H 1 ] × [1, H 2 ]) ∩ Z 2 .
Remark 1.6. The vdC inequality that has been stated above for a family of complex numbers can be extended verbatim to any family of vectors in a linear complex space equipped with a scalar product. This fact is very useful in many applications to mean convergence theorems or recurrence theorems in Ergodic Theory (see for example Lemma A6 and the references in [Berg-McC]).

1.2. Van der Corput sets.

1.2.1. Definition. Definition 2. A subset D of Z 2 \ {0} is a van der Corput set (vdC-set) if for any family (u n ) n∈Z 2 of complex numbers of modulus 1 such that ∀d ∈ D, lim N 1 ,N 2 →+∞ 1 N 1 N 2 0≤n<(N 1 ,N 2 )
u n+d u n = 0 we have (6) lim

N 1 ,N 2 →+∞ 1 N 1 N 2 0≤n<(N 1 ,N 2 ) u n = 0 .
Equivalently, D is a vdC-set if any family (x n ) n∈N 2 of real numbers having the property that for all d ∈ D the family (x n+dx n ) n∈N 2 is u.d. mod 1, is itself u.d. mod 1.

(A natural Cesàro summation method is also given by "bilateral averages". One obtains an equivalent definition of vdC set if we replace in Definition 2 sums 0≤n<(N 1 ,N 2 ) by sums

(-N 1 ,-N 2 )<n<(N 1 ,N 2 ) . See Section 4.) Example 1.7. If δ(D) = 1, the set D is a vdC-set (see Corollary 1.4).
Note that various modifications of the notion of uniform distribution (for example, considering other types of averages) lead, generally speaking, to different notions of vdC set. See Section 4 for some remarks and open questions.

1.2.2. Spectral characterization. If σ is a finite measure on the 2-torus T 2 , we define its Fourier transform σ by σ(n) = T 2 e(n 1 x 1 + n 2 x 2 ) dσ(x 1 , x 2 ), for any n = (n 1 , n 2 ) ∈ Z 2 . (Note that we prove in the sequel (Subsection 1.5) that (S1), (S2) and (S3) are equivalent to the following property : any positive measure σ on the 2-torus

T 2 such that d∈D | σ(d)| < +∞ is continuous.)
The equivalence of (S2) and ( S3) is clear, since a translation of a measure does not change the modulus of its Fourier coefficients. For one dimensional space of parameters the implication (S2)⇒(S1) is proved in [Kam-MF] and the implication (S1)⇒(S2) can be found in [Ruz].

Lemma 1.9. Let (u n ) n∈Z 2 be a bounded family of complex numbers and (N (j)

) j∈N = (N (j) 1 , N (j) 2 ) j∈N be a sequence in N 2 such that min(N (j) 1 , N (j) 2 ) → +∞ when j → +∞. If, for all h ∈ Z 2 , γ(h) := lim j→+∞ 1 N (j) 1 N (j) 2 0≤n<N (j) u n+h u n exists ,
then there exists a positive measure σ on the 2-torus T 2 such that, for all

h ∈ Z 2 , σ(h) = γ(h)
and this measure satisfies

lim sup j→+∞ 1 N (j) 1 N (j) 2 0≤n<N (j) u n ≤ σ ({(0, 0)}) .
Sketch of the proof of Lemma 1.9. We denote x = (x 1 , x 2 ), n = (n 1 , n 2 ), etc. . . The family (γ h ) h∈Z 2 is positive-definite and the Bochner-Herglotz Theorem guarantees the existence of the positive measure σ (see for example [Rud], Subsection 1.4.3). This measure is the weak limit of the sequence of absolutely continuous measures (σ N (j) ) where σ N has density

g N (x) := 1 N 1 N 2 0≤n<N u n e(-n 1 x 1 -n 2 x 2 )
2 with respect to Lebesgue measure dx 1 dx 2 . We define

h N (x) := 1 N 1 N 2 0≤n<N e(-n 1 x 1 -n 2 x 2 ) 2 .
The sequence of measures with density h N converges weakly to the Dirac delta measure at (0, 0), denoted by δ.

We follow the method of [Co-Kam-MF], in particular their Theorem 2, which utilizes the connection between the affinity 7 of two probability measures and weak convergence. Denoting by ρ(µ, ν) the affinity of two probability measures on T 2 , we have

ρ (g N (x)dx, h N (x)dx) = T 2 g N (x)h N (x) dx 1 dx 2 , ρ(σ, δ) = σ({(0, 0)}) , and lim sup j→+∞ T 2 g N (j) (x)h N (j) (x) dx 1 dx 2 ≤ σ ({(0, 0)}) .
The conclusion of the lemma then follows from the inequality 1

N (j) 1 N (j) 2 0≤n<N (j) u n ≤ T 2 g N (j) (x)h N (j) (x) dx 1 dx 2 .
Proof of Theorem 1.8. Let us first prove that (S2)⇒(S1). Let (u n ) n∈Z 2 be a bounded family of complex numbers such that, for all d ∈ D, lim

N 1 ,N 2 →+∞ 1 N 1 N 2 0≤n<(N 1 ,N 2 ) u n+d u n = 0 .
There exists a sequence (N (j) ) j∈N in N 2 such that

• min(N (j) 1 , N (j)
2 ) → +∞ ,

• lim j→+∞ 1 N (j) 1 N (j) 2 0≤n<N (j) u n = lim sup N 1 ,N 2 →+∞ 1 N 1 N 2 0≤n<N u n , • ∀h ∈ Z 2 , γ(h) := lim j→+∞ 1 N (j) 1 N (j) 2 0≤n<N (j)
u n+h u n exists .

7 Let µ and ν be two probability measures on T 2 . The affinity ρ(µ, ν) is defined as

ρ(µ, ν) = T 2 dµ dm 1/2 dν dm 1/2 dm ,
where m is any measure with respect to which both µ and ν are absolutely continuous. Note that affinity is also called the Hellinger integral by probabilists. It is proved in [Co- Kam-MF] that if (µ n ) and (ν n ) are two weakly convergent sequences of probability measures, then lim sup

n→+∞ ρ(µ n , ν n ) ≤ ρ(lim µ n , lim ν n ).
The map γ is the Fourier transform of a positive measure σ on the 2-torus.

We have σ(d) = 0 for all d ∈ D. By condition (S2), the measure σ has no point mass at (0, 0), and, using Lemma 1.9, we conclude that the family (u n ) n∈Z 2 converges to zero in the sense of ( 6). We have proved that D is a vdC-set. Following Ruzsa ([Ruz]), we will use a probabilistic argument in order to prove that (S1)⇒(S2). The next two lemmas are routine variations on the theme of the law of large numbers.

Lemma 1.10. Let (θ(n)) n∈N 2 be an i.i.d. family of random variables with values in the 2-torus T 2 . We write

θ(n) = (θ 1 (n), θ 2 (n)). We define a family of complex random variables (Y (n)) n∈N 2 by Y (n 1 , n 2 ) := e (r 1 θ 1 (m 1 , m 2 ) + r 2 θ 2 (m 1 , m 2 )) , if n i = m 2 i + r i , with 0 ≤ r i ≤ 2m i , i = 1, 2. We have, almost surely, lim N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N Y (n) = P (θ = 0) .
Lemma 1.11. Let (X(n)) n∈N 2 be an i.i.d. family of bounded complex random variables. We define a new family of complex random variables

(Z(n)) n∈N 2 by Z(n 1 , n 2 ) := X(m 1 , m 2 ) if n i = m 2 i + r i , with 0 ≤ r i ≤ 2m i , i = 1, 2. We have, almost surely, lim N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N Z(n) = E [X] .
Let us explain briefly how (S1)⇒(S2) follows from these lemmas. Suppose that a vdC set D ⊂ Z 2 and a measure σ on T 2 are given. We suppose that the Fourier transform of σ is null on D. Without loss of generality, we can suppose that σ is a probability measure, and we consider a family of random variables (θ(n)) n∈N 2 independent and of law σ. We define, as in Lemma 1.10, a family of complex random variables (Y (n)) n∈N 2 . A slight modification 8 of Lemma 1.11 gives us the following result: for all 8 Details are provided after Lemma 2.4 in Section 2.2 .

h ∈ Z 2 , almost surely, lim N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N Y (n + h)Y (n) = E [e(h 1 θ 1 + h 2 θ 2 )] .
This last quantity is exactly σ(h) and, by hypothesis, it is null for h ∈ D.

Since D is a vdC set, we conclude that lim

N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N Y (n) = 0 .
By Lemma 1.10, this means that P (θ = 0) = 0, i.e. σ ({(0, 0)}) = 0.

1.2.3. Some corollaries. Here are some direct applications of the spectral characterization.

Corollary 1.12 (Ramsey property. Cf. [Ruz], Corollary 1.).

If D = D 1 ∪D 2 is a vdC set in Z 2 , then at least one of the sets D 1 or D 2 is a vdC set. (In particular, if D is a vdC set in Z 2 and E is a finite subset of D, then D \ E is still a vdC set in Z 2 .) Proof. If σ 1 and σ 2 are positive measures on T 2 such that σ i is null on D i , then the Fourier transform of their convolution σ 1 ⋆ σ 2 vanishes on D 1 ∪ D 2 .
And

σ 1 ⋆ σ 2 ({0}) ≥ σ 1 ({0}) × σ 2 ({0}).
If F is a family of subsets of Z 2 , we denote by F * its dual family, that is the family of all sets G ⊂ Z 2 such that G ∩ F = ∅ for all F ∈ F . The Ramsey property described in Corollary 1.12 has a remarkable consequence for the family of vdC * sets : if A is a vdC set and if B is a vdC * set, then A ∩ B is a vdC set ; this impies that the family of vdC * sets is stable with respect to finite intersections, hence is a filter. Corollary 1.13 (Sets of differences). If I is an infinite subset of Z 2 , then the set of differences D := {nm : n, m ∈ I and n = m} is a vdC set.

Proof. Suppose that σ is a probability measure on T 2 , whose Fourier transform vanishes on D. This means that the characters x → e(n • x), with n ∈ I, form an orthonormal family in L 2 (σ). For any finite subset J of I, we have

(cardJ) 2 σ({(0, 0)}) ≤ T 2 n∈J e(n • x) 2 dσ(x) = cardJ .
This implies that σ has no point mass at zero. Remark 1.14. The preceding proof gives, in fact, more. Namely, any set D which contains sets of differences of arbitrarily large finite sets is a vdC set. Let σ ′ be a positive measure on the d-torus such that σ ′ vanishes on D. The linear map t L from T d into T d is finite to one and onto. Since it is onto, it posseses an inverse on the right and we can see σ ′ as the image of a positive measure σ on the d-torus, under the map t L. The Fourier transform σ vanishes on L(D), hence the measure σ is continuous. Since the map t L is finite to one, we conclude that the measure σ ′ is also continuous. This proves the second assertion.

Z d = G ∪ ∪ k i=1 (z i + G) . Let D be a vdC set in Z d . We have D = (G ∩ D) ∪ ∪ k i=1 (z i + G) ∩ D .
Since none of the sets (z i + G) ∩ D is vdC, Corollary 1.12 tells us that the set (G ∩ D) is vdC.

Remark 1.17. As a consequence of the last two statements, we note the following fact, which is the direct extension of Corollary 2 in [Ruz].

Let L be a one to one linear transformation from

Z d into itself; let D be a vdC set in Z d ; the set of n ∈ Z d such that L(n) ∈ D is a vdC set in Z d .
Indeed, by Corollary 1.16, D ∩ L(Z d ) is a vdC set in Z d and, by Corollary 1.15, its inverse image by L is a vdC set.

The spectral characterization also implies that various formulations of the vdC property, associated to different averaging methods, are in fact equivalent (see Section 4).

1.3. The Kamae -Mendès France criterion.

1.3.1. The criterion. Let D ⊂ Z 2 and let P be a real trigonometric polynomial on T 2 . We say that the spectrum of P is contained in

D if P is a linear combination of the characters (x 1 , x 2 ) → e(d 1 x 1 + d 2 x 2 ) with (d 1 , d 2 ) ∈ ±D.
In the case of a one dimensional space of parameters, the following proposition appears in Ruzsa's article [Ruz], with the same proof.

Proposition 1.18. A subset D of Z 2 \ {0} is a van der Corput set if and only if for all ǫ > 0, there exists a real trigonometric polynomial P on the 2-torus T 2 whose spectrum is contained in D and which satisfies P (0) = 1, P ≥ -ǫ.

Proof. Let us assume that there exists such a trigonometric polynomial. Let σ be a positive measure on T 2 whose Fourier transform σ is null on D. Then we have

T 2 P dσ = 0 .
But from P (0) = 1 and P ≥ -ǫ we deduce that

T 2 P dσ ≥ σ ({0}) -ǫσ T 2 \ {0} .
Thus we necessarily have σ ({0}) = 0, and we deduce from Theorem 1.8 that D is a vdC set.

For the proof of the inverse implication, we follow Ruzsa's argument ( [Ruz], Section 5). We will denote m

• x := m 1 x 1 + m 2 x 2 if x = (x 1 , x 2 ) ∈ T 2 and m = (m 1 , m 2 ) ∈ Z 2 .
Let us suppose that D is a subset of Z 2 and that there exists 0 < ǫ < 1 such that, for any real trigonometric polynomial P with spectrum in D and such that P (0) = 1, we have min(P + ǫ) ≤ 0. In the Banach space C R (T 2 ) of real continuous functions on T 2 , equipped with the uniform norm, we consider the set F of strictly positive functions and the set Q of real trigonometric polynomials P , with spectrum in D and such that P (0) = 1. By hypothesis, the convex sets F and ǫ + Q are disjoint. By Hahn-Banach Theorem, there exists a non-zero real-valued continuous linear functional L on C R (T 2 ), which takes nonnegative values on F and nonpositive values on ǫ + Q. Let us denote by σ the measure on T 2 associated to L by Riesz representation theorem : L(f ) = T 2 f dσ, for all f ∈ C R (T 2 ). Since L ≥ 0 on F , this measure is positive and we can assume that it is normalized. Let m, n ∈ ±D.

If P ∈ Q, then, for all λ ∈ R, the function x → ǫ + P + λ(cos 2π(m • x) -cos 2π(n • x)) is still in ǫ + Q. This implies that cos 2π(m • x) dσ(x) = cos 2π(n • x) dσ(x). Similarly, for all λ ∈ R, the function x → ǫ + P + λ sin 2π(m • x) is still in ǫ + Q, and this implies that sin 2π(m • x) dσ(x) = 0. We define r := cos 2π(m • x) dσ(x), for m ∈ ±D. If P ∈ Q, we have T 2
(ǫ + P ) dσ ≤ 0 and, writing

P (x) = m∈±D a m cos 2π(m • x) + b m sin 2π(m • x) ,
we have

T 2 P dσ = r m∈±D a m = rP (0) = r .
Hence r ≤ -ǫ < 0. Denoting by δ the Dirac mass at 0, we consider a new probability measure σ ′ defined by

σ ′ := 1 1 -r (σ -rδ) .
We have σ ′ ({0}) ≥ -r 1-r > 0. But this probability satisfies σ ′ (m) = 0 for all m ∈ D, and, using Theorem 1.8, we conclude that D is not a vdC set. Proposition 1.19. Let D ⊂ Z 2 . For each q ∈ N, we denote

D q := {(d 1 , d 2 ) ∈ D : q! divides d 1 and d 2 } .
Suppose that, for every q, there exists a sequence (h q,n ) n∈N in D q such that, for every x = (x 1 , x 2 ) ∈ R 2 , if x 1 or x 2 is irrational, the sequence (h q,n • x) n∈N is uniformly distributed mod 1. Then D is a vdC set.

Proof. Let us define a family of trigonometric polynomials with spectrum contained in D, by the formula

(7) P q,N (x) := 1 N N n=1 e (h q,n • x) ,
where q and N are positive integers and x ∈ R 2 . By hypothesis, if x / ∈ Q 2 then lim N →+∞ P q,N (x) = 0. For each q, there exists a subsequence (P q,N ′ ) which is pointwise convergent to a function g q . For all x ∈ Q 2 , we have g q (x) = 1 for all large enough q, and for all x / ∈ Q 2 , we have g q (x) = 0. The sequence (g q ) is pointwise convergent to the characteristic function of Q 2 . Consider now a positive measure σ on T 2 whose Fourier transform σ vanishes on D. We have P q,N dσ = 0 for all q, N. Applying the dominated convergence theorem twice, we conclude that σ(Q 2 ) = 0. In particular σ({0}) = 0, and we are done.

A sequence (d n ) n∈N in Z 2 will be called a vdC sequence if the set of its values {d n : n ∈ N} is a vdC set.

The (d-dimensional version of the) following proposition extends Theorem 4.2 in [Berg.1].

Proposition 1.20. Let p 1 and p 2 be two polynomials with integer coefficients. The sequence (p 1 (n), p 2 (n)) n∈N is a vdC sequence in Z 2 if and only if for all positive integers q, there exists n ≥ 1 such that q divides p 1 (n) and p 2 (n).

Note that the divisibility condition is satisfied if p 1 and p 2 have zero constant term.

Proof of Proposition 1.20. By Corollary 1.16, the divisibility condition is necessary for the sequence (p 1 (n), p 2 (n)) to be vdC. Let us prove that this condition is sufficient. We are going to distinguish two cases: either p 1 and p 2 are proportional, or not.

In the first case, there exists a polynomial p ∈ Z[X], and integers a, b such that p 1 = ap and p 2 = bp. The polynomial p satisfies the divisibility property, which ensures that (p(n)) is a vdC sequence in Z (it is a direct consequence of the one-dimensional version of Proposition 1.19, cf. [Kam-MF]). By the first statement of Corollary 1.15, this implies that (ap(n), bp(n)) is a vdC sequence in Z 2 .

Consider now the second case, in which polynomials p 1 and p 2 are not proportional. Let q be a positive integer and (x 1 , x 2 ) ∈ R 2 \ Q 2 ; there exists n ≥ 1 such that q!|p 1 (n) and q!|p 2 (n) ; for all k ∈ Z, we have q!|p 1 (n + kq!) and q!|p 2 (n + kq!). We claim that the sequence

(8) (p 1 (n + kq!)x 1 + p 2 (n + kq!)x 2 ) k∈N is uniformly distributed mod 1. This fact implies, by Proposition 1.19, that (p 1 (n), p 2 (n)) is a vdC sequence in Z 2 .
In order to prove the claim, we consider first the case when 1, x 1 and x 2 are linearly independent over Q ; in this case the sequence (8) is u.d. mod 1 by Weyl's theorem. Let us consider now the case in which 1, x 1 and x 2 are linearly dependent over Q and x 1 is irrational ; in this case we have x 2 = rx 1 + s, with r, s ∈ Q, and, if q has been chosen enough large, the sequence (8) has (mod 1) the form

((p 1 (n + kq!) + rp 2 (n + kq!))x 1 ) k∈N ;
we conclude once more by Weyl's theorem since the polynomial p 1 + rp 2 is not constant. Finally, if x 1 is rational, then x 2 is irrational and the argument is similar.

Remark 1.21. (See Appendix) There exist pairs of polynomials p 1 , p 2 satisfying:

-for all integers a and b and for all positive integers q, there exists n such that q | ap 1

(n) + bp 2 (n) (hence (ap 1 (n) + bp 2 (n)) n∈N is a vdC sequence in Z).
-there exists a positive integer q such that for no n are the numbers p 1 (n) and p 2 (n) simultaneously multiples of q (hence (p 1 (n), p 2 (n)) n∈N is not a vdC sequence in Z 2 ).

Let P be the set of prime numbers. It is shown in [Kam-MF] that P -1 and P + 1 are vdC sets, and that no other translate of P is a vdC set. This can be extended to polynomials along P -1 and P + 1, and to the multidimensional setting. For example, we have the following result.

Proposition 1.22. Let f, g be two (non zero) polynomials with integer coefficients and zero constant term. The set {(f (p -1), g(p -1)) :

p ∈ P } is a vdC set in Z 2 .
The proof of this proposition relies on Proposition 1.19 and on the following Vinogradov-type theorem.

Theorem 1.23. Let q be a positive integer and h be a real polynomial such that the polynomial hh(0) has at least one irrational coefficient. The sequence (h(p)) is uniformly distributed mod 1, where p describes the increasing sequence of prime numbers in the congruence class 1 + qN.

The proof of this theorem can be given in a few sentences, by "quotation". It is proved in [Rh] (see also [N]) that if a real polynomial h is such that hh(0) has at least one irrational coefficient, then (9) the sequence ( h(p)) p∈P is u.d. mod 1.

Now we can use the following simple trick (cf. [Mo], p.34) :

p≤n p≡1[q]
e(h(p)) = 1 q q j=1 e -j q p≤n e(h(p) + pj/q) .

After division by π(n), the right term goes to zero as n goes to infinity because (9) can be applied to h(p) = h(p) + pj/q. Moreover it is well known that the Prime Number Theorem has a natural extension to the distribution of primes in arithmetic progressions : the number of primes less than n in 1 + qN is asymptotically equivalent to π(n)/ϕ(q) as n goes to infinity.

We obtain that

lim n→+∞ 1 #{p ≤ n, p ≡ 1[q]} p≤n p≡1[q] e(h(p)) = 0 .
This is still true when we replace h by a non zero integer multiple of h, which, via Weyl's criterion, gives uniform distribution (mod 1) of the sequence (h(p)) p∈P, p≡1 [q] .

Proof of Proposition 1.22. This proof is parallel to the proof of Proposition 1.20. If f and g are proportional, we use the fact that (f (p -1)) p∈P is a vdC sequence (which is a direct consequence of the one-dimensional version of Proposition 1.19 and of Theorem 1.23). If f and g are not proportional, we deduce from Theorem 1.23 that for all large enough positive integers q, and for all (

x 1 , x 2 ) ∈ R 2 \ Q 2 , the sequence (f (p -1)x 1 + g(p -1)x 2 ) p∈P, p≡1[q] is u.d.
(0) = 1, P k + 1 k > 0.
The existence of I k and P k can be proved by induction using the direct implication in Proposition 1.18 and the fact that, for each k, the set D \ (I 1 ∪ I 2 ∪ . . . ∪ I k ) is vdC (see Corollary 1.12). From the inverse implication in Proposition 1.18, we deduce that any infinite union of the I k 's is a vdC set. We can consider an infinite family of pairwise disjoint such sets.

1.4. Positive-definite multiparameter sequences and generalized vdC inequality.

1.4.1. The inequality. We show in this subsection that the Kamae-Mendès France criterion can be formulated in terms of positive-definite sequences. This will allow us, for a given vdC set D, to obtain a quantitative van der Corput type inequality in which only correlations γ(N, d) for d ∈ D are involved.

Proposition 1.25. Let (a h ) h∈Z 2 be a family of complex numbers such that all but finitely many of a h are zero. This family is positive-definite if and only if the trigonometric polynomial T (x) := h a h e(h • x), x ∈ R 2 , takes only nonnegative values.

Proof. Recall that the family (a h ) of complex numbers is positive-definite if, for any family (z h ) h∈Z 2 of complex numbers, all zero but finitely many,

h,h ′ ∈Z 2 a h-h ′ z h z h ′ ≥ 0 .
We will denote h = (h 1 , h 2 ).

The family (a h ) is the Fourier transform of the measure having density T with respect to Lebesgue measure on the 2-torus. Thus it is clear that if the trigonometric polynomial is positive, then the family is positive-definite. In the opposite direction, suppose that (a h ) is positive-definite (and that a h = 0 for all h but finitely many). For x ∈ R 2 and for all positive integers c,

0≤h,h ′ <(c,c) a h-h ′ e(h • x)e(-h ′ • x) ≥ 0 .
This can be written

(-c,-c)<h<(c,c) (c -|h 1 |)(c -|h 2 |)a h e(h • x) ≥ 0 .
Dividing this expression by c 2 , and letting c go to infinity, we obtain h a h e(h • x) ≥ 0 .

Remark 1.26. The Kamae -Mendès France criterion (Proposition 1.18) can now be rewritten as follows : a subset D of Z 2 \ {0} is a vdC set if and only if, for all ǫ > 0, there exists a positive-definite family (a d ) d∈Z 2 such that :

• all but finitely many a d are zero;

• a d = 0 whenever d = 0 and d / ∈ D ∪ (-D); • a 0 ≤ ǫ and d a d = 1.
As in the first section, we will denote

γ(N, h) := 0<n≤N 0<n+h≤N u n+h • u n , if h ∈ Z 2 , N ∈ N 2
and (u n ) 0≤n<N is a family of complex numbers. We will write also

u ∞ := max n |u n | .
Theorem 1.27. Let H ∈ N 2 and (a h ) -H<h<H be a finite positive-definite family of complex numbers, with h a h = 1. Let N ∈ N 2 and (u n ) 0<n≤N be a finite family of complex numbers. We have

0<n≤N u n 2 ≤ N 1 N 2 h a h γ(N, h)+5 u 2 ∞ h (|h 1 |N 2 +|h 2 |N 1 +|h 1 h 2 |)|a h | .
This inequality should be compared to the "generalized van der Corput Lemma" stated in [Mo] (Chap.2, Lemma 1).

If we consider a bounded family of complex numbers (u n ) n∈N 2 , we deduce from Theorem 1.27 the following inequality

1 N 1 N 2 0<n≤N u n 2 ≤ h a h 1 N 1 N 2 γ(N, h) + O max 1 N 1 , 1 N 2 ,
which will be utilized when describing the vdC property of Cartesian products of vdC sets.

Corollary 1.28 below, which is a direct consequence of Theorem 1.27, gives what one might call a quantitative version of the van der Corput trick. The "if" part of the Kamae-Mendès France criterion is a direct consequence of this corollary.

Corollary 1.28. Let (a h ) -H<h<H be a positive-definite family of complex numbers, and (u n ) n∈N 2 be a family of complex numbers. If, for any h such that h = 0 and a h = 0 we have lim

N 1 ,N 2 →+∞ 1 N 1 N 2 γ(N, h) = 0 then lim sup N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤N u n ≤ u ∞ √ a 0 .
Proof of Theorem 1.27. Let us define

m := 1 N 1 N 2 0<n≤N
u n and v n := u nm .

We have

γ(N, h) = 0<n≤N 0<n+h≤N (v n+h + m)(v n + m) = A h + B h + C h + D h ,
where :

A h := 0<n≤N 0<n+h≤N v n+h • v n , B h := m 0<n≤N 0<n+h≤N v n , C h := m 0<n≤N 0<n+h≤N v n+h , D h := |m| 2 0<n≤N 0<n+h≤N
1 .

Since the family (a h ) is positive-definite, we have

h a h A h ≥ 0 .
The number of points n in the square [1,

N 1 ] × [1, N 2 ], such that we do not have 0 < n+h ≤ N, is less or equal than |h 1 |N 2 +|h 2 |N 1 . Since 0<n≤N v n = 0 we deduce that |B h | ≤ |m| (|h 1 |N 2 + |h 2 |N 1 ) v ∞ ≤ 2|m| (|h 1 |N 2 + |h 2 |N 1 ) u ∞ ≤ 2 (|h 1 |N 2 + |h 2 |N 1 ) u 2 ∞ .
The same inequality holds for |C h |.

We have also

D h = (N 1 -|h 1 |)(N 2 -|h 2 |)|m| 2 ≥ 1 N 1 N 2 0<n≤N u n 2 -(|h 1 |N 2 + |h 2 |N 1 + |h 1 h 2 |) u 2 ∞ .
From these inequalities, we deduce that

h a h γ(N, h) ≥ h a h A h + h a h D h - h a h (|B h | + |C h |) ≥ 1 N 1 N 2 0<n≤N u n 2 -5 h |a h | (|h 1 |N 2 + |h 2 |N 1 + |h 1 h 2 |) u 2 ∞ .
and the result follows.

In the next two subsections we present corollaries of Theorem 1.27. Proof. Let us consider, as a typical example, the case k = ℓ = 2. We consider two vdC sets D and E in Z 2 . Let (u n,m ) n,m∈Z 2 be a family of complex numbers of modulus one indexed by Z 4 , and satisfying : for all d ∈ D and all e ∈ E, (10) lim

N 1 ,N 2 →+∞ M 1 ,M 2 →+∞ 1 N 1 N 2 M 1 M 2 0≤n<(N 1 ,N 2 ) 0≤m<(M 1 ,M 2 ) u n+d,m+e • u n,m = 0 .
0≤n<(N 1 ,N 2 ) 0≤m<(M 1 ,M 2 ) u n,m 2 ≤ P d,e a d b e 0≤n,n+d<(N 1 ,N 2 ) 0≤m,m+e<(M 1 ,M 2 ) u n+d,m+e •u n,m +P 2 O (1/p) .
Dividing by P 2 , letting p go to infinity and using (10), we obtain lim sup 1.4.3. Sequences in Hilbert space. The goal of this short subsection is to point out that generalized van der Corput inequalities can be extended from numerical sequence to sequences of vectors in a Hilbert space. One of the reasons to be interested in such extensions is that they provide useful convergence criteria for multiple ergodic averages (see for example the references mentioned at the end of the introduction).

N 1 ,N 2 →+∞ M 1 ,M 2 →+∞ 1 N 1 N 2 M 1 M 2 0≤n<(N 1 ,N 2 ) 0≤m<(M 1 ,M 2 ) u n,m
Let H be a Hilbert space and (u n ) n∈N 2 be a doubly indexed family of vectors in this space. We will denote, for any h ∈ Proposition 1.30. Let H ∈ N 2 and (a h ) -H<h<H be a finite positive-definite family of complex numbers, with h a h = 1. We have

0<n≤N u n 2 ≤ N 1 N 2 h a h γ(N, h)+5 u 2 ∞ h (|h 1 |N 2 +|h 2 |N 1 +|h 1 h 2 |)|a h | .
The proof of Proposition 1.30 is similar to the scalar case and will be omitted. Combined with Remark 1.26, this proposition leads to the following extension of the notion of vdC set to families in Hilbert space.

Corollary 1.31. Let D be a vdC set in Z 2 and (u n ) n∈Z 2 be a bounded family in H. If ∀d ∈ D, lim

N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤(N 1 ,N 2 ) < u n+d , u n >= 0 then lim N 1 ,N 2 →+∞ 1 N 1 N 2 0<n≤(N 1 ,N 2 )
u n = 0 . This result is not surprising. Why? Because we have a "parallel" fact pertaining to recurrence properties. It is not difficult to prove that if a set D is a set of recurrence, then, for any m.p.s. (X, A, µ, T ) and any set A in A such that µ(A) > 0, not only does there exist d ∈ D such that µ(A ∩ T d A) > 0, but also d∈D µ(A ∩ T d A) = +∞.

Proof of Theorem 1.32. Let D be a vdC set in Z, and fix ǫ > 0. By Remark 1.26, we know that there exists a positive-definite sequence (a h ) h∈Z such that :

• all but finitely many a h are zero;

• a h = 0 whenever h = 0 and h / ∈ D ∪ (-D); • a 0 ≤ ǫ and d a d = 1.
Moreover, for any positive-definite sequence (b h ) h∈Z with support in {-H + 1, . . . , H -1} and such that h b h = 1, we have the following vdC inequality (simply the one-dimensional version of Theorem 1.27): for any complex numbers u 1 , u 2 , . . . , u N ,

N n=1 u n 2 ≤ N h b h γ(N, h) + 5 u 2 ∞ h |hb h | .
We apply this inequality to the sequence (a h ) after noticing that since the sequence is positive-definite, we have |a h | ≤ a 0 . We obtain

N n=1 u n 2 ≤ Na 0     γ(N, 0) + d∈D∪(-D) |d|≤H |γ(N, d)| + 5 u 2 ∞ H 2     , Hence (11) 1 N N n=1 u n 2 ≤ ǫ     1 N N n=1 |u n | 2 + d∈D∪(-D) |d|≤H 1 N γ(N, d) + 5 N u 2 ∞ H 2    
Let σ be a probability measure on the torus such that d∈D | σ(d)| < +∞. Following Ruzsa ([Ruz]), we consider a sequence (Y n ) n∈N of complex random variables of modulus one such that almost surely, 1

N 0<n≤N Y n → σ({0}) and 1 N 0<n≤N Y n+h Y n → σ(h) .
(Details of a construction of such a sequence (Y n ) are given below, in Lemmas 2.3 and 2.4 and in the text which follows these lemmas.)

We apply (11) to u n = Y n and let N go to infinity. After noticing that

1 N γ(N, d) = 1 N 0<n≤N 0<n+d≤N Y n+d Y n → σ(d) ,
we obtain

|σ({0})| 2 ≤ ǫ 1 + 2 d∈D | σ(d)| .
This proves that σ({0}) = 0.

Enhanced van der Corput sets

2.1. Introduction. In this section, we introduce a new property which we call enhanced vdC. It is a natural concept for several reasons :

• the set of all integers is enhanced vdC, and it is often this property which is classicaly used in equidistribution theory and ergodic theory;

• the spectral characterization of enhanced vdC sets is given by the FC + property (Theorem 2.1); • in the manner that the notion of vdC set is linked to the notion of set of recurrence, the notion of enhanced vdC set is linked to the notion of set of strong recurrence (see Subsection 3.3).

We give here the definition and the spectral characterization of enhanced vdC sets in Z, extension to Z d being completely routine. This definition appears in [Kam-MF] and in [Bou]. We remark that in [Pe], Peres uses the notation FC + for sets satisfying the apparently weaker Condition (S3) of Theorem 1.8. We ask in Question 1 whether Condition (S3) is actually strictly weaker than Condition FC + .

Theorem 2.1. The notions of enhanced vdC set and FC + set coincide.

Proof. The proof of this proposition follows the lines of the spectral characterization of vdC sets. In order to prove that FC + sets are enhanced vdC, we use the following lemma, which is the one parameter version of Lemma 1.9. Lemma 2.2. Let (u n ) n∈N be a bounded sequence of complex numbers and (N j ) j∈N be an increasing sequence of positive integers. If for all h ∈ N γ(h) := lim

j→+∞ 1 N j N j n=1 u n+h u n exists ,
then there exists a positive measure σ on the torus such that, for all h ∈ N,

σ(h) = γ(h)
and this measure satisfies

lim sup j→+∞ 1 N j N j n=1 u n ≤ σ ({0}) .
Let D be an FC + set. Let (u n ) be a bounded sequence of complex numbers such that lim |d|→+∞,d∈D lim

N →+∞ 1 N N n=1 u n+d u n = 0 .
There exists an increasing sequence (N j ) j∈N of positive integers such that

• lim j→+∞ 1 N j N j n=1 u n = lim sup N →+∞ 1 N N n=1 u n , • ∀h ∈ N, γ(h) := lim j→+∞ 1 N j N j n=1 u n+h u n exists .
The map γ is the Fourier transform of a positive measure σ on the torus. We have lim |d|→+∞,d∈D σ(d) = 0. By hypothesis, this forces the measure σ to be continuous. We have σ ({0}) = 0 and, using the above lemma, we obtain the Cesàro convergence of (u n ) to zero. The set D is enhanced vdC.

In order to prove that any enhanced vdC set is FC + , the arguments of Ruzsa ( [Ruz]) can be adapted and we use the following probabilistic lemmas.

Lemma 2.3. Let (θ n ) n∈N be an i.i.d. sequence of random variables with values in the torus T. We define a new sequence of complex random variables (Y n ) by

Y n := e (rθ m ) , if n = m 2 + r, with 0 ≤ r ≤ 2m.
We have, almost surely,

lim N →+∞ 1 N N n=1
Y n = P (θ = 0) . Lemma 2.4. Let (X n ) n∈N be an i.i.d. sequence of bounded complex random variables. We define a new sequence of complex random variables (Z n ) by

Z n := X m if n = m 2 + r, with 0 ≤ r ≤ 2m.
We have, almost surely,

lim N →+∞ 1 N N n=1 Z n = E [X] .
Let D be an enhanced vdC set, and let σ be a positive measure on T. We suppose that the Fourier coefficient σ(d) goes to zero when d goes to infinity in D. Without loss of generality, we can suppose that σ is a probability measure, and we consider a sequence of independent random variables (θ n ) of law σ. We define, as in Lemma 2.3, the family of complex random variables (Y n ). Let us fix h ∈ N. We define Z n = e(hθ m ) for n = m 2 + r and 0 ≤ r ≤ 2m. By Lemma 2.4 we know that, almost surely, lim N →+∞ This last quantity is exactly σ(h) and, by hypothesis, it goes to zero when h goes to infinity in D. Since the set D is enhanced vdC, we conclude that lim

N →+∞ 1 N N n=1 Y n = 0 .
By Lemma 2.3, this means that P (θ = 0) = 0, that is to say σ ({0}) = 0. The same argument can be applied to all the images of σ by translations of the torus, and we conclude that σ is a continuous measure. Hence D is FC + .

The spectral characterization makes it possible to give an alternative definition of enhanced vdC sets. Proposition 2.5. An infinite set of integers D is enhanced vdC if and only if for any sequence (u n ) n∈Z of complex numbers of modulus 1 such that lim |d|→+∞,d∈D lim sup

N →+∞ 1 N N -1 n=0 u n+d u n = 0 , one has lim N →+∞ 1 N N -1 n=0 u n = 0 .
2.3. Some properties of enhanced vdC sets. From the spectral characterization we deduce various corollaries. We omit detailed proofs since they are similar to proofs of the corresponding statements for vdC sets (see Subsection 1.2.3). Corollary 2.7 (Sets of differences). Let D ⊂ N. Suppose that, for all n > 0 there exist a 1 < a 2 < . . . < a n such that {a ja i :

1 ≤ i < j ≤ n} ⊂ D.
Then D is an enhanced vdC set. 2.4. Questions.

Question 1. Our intuition is that there exist vdC sets which are not enhanced vdC. Is it true? Is it possible to exhibit a particular example?

Question 2. We know (Corollary 1.31) that the notions of vdC set for families in a Hilbert space and of vdC set coincide. Is the analogous fact true for enhanced vdC sets?

Question 3. We know (Corollary 1.24) that any vdC set can be partitionned into infinitely many vdC sets. Is the analogous fact true for enhanced vdC sets?

Question 4. We know (Corollary 1.29) that the Cartesian product of two vdC sets is a vdC set. Is the analogous fact true for enhanced vdC sets?

2.5. Examples.

2.5.1. Ergodic sequences. A sequence of integers (d n ) n∈N is called ergodic if the following mean ergodic theorem is valid : given an ergodic m.p.s. (X, A, µ, T ) and f ∈ L 2 (µ), the averages 1

N N n=1 f • T dn converge in L 2 to f dµ when N goes to infinity. It follows from the spectral theorem that the sequence (d n ) is ergodic if and only if, for all x ∈ R \ Z, (13) lim N
→+∞ 1 N N n=1 e(d n x) = 0 .
Proposition 2.10. Any ergodic sequence is an enhanced vdC sequence.

Proof. Let (d n ) be an ergodic sequence and σ a finite measure on the torus.

Using the dominated convergence theorem we deduce from (13) that lim

N →+∞ 1 N N n=1 σ(d n ) = σ ({0}) .
Hence it is immediate that the sequence (d n ) is FC + .

Propostion 2.10 can be used to exhibit many examples of enhanced vdC sets.

(i) In [Bos-Ko-Q-Wi] the authors consider sequences of the form d n = [a(n)] where the function a belongs to some Hardy field. They characterize those of them which are ergodic. See Theorems 3.2,3.3,3.4,. Here are some examples of ergodic sequences, coming from (ii) In a mean ergodic theorem along a tempered sequence is proved. More precisely, it is shown (see Theorem 8.1 in ) that, for any tempered function 9 g, the sequence ([g(n)]) is ergodic. This gives a new large class of examples. For example, the function g(x) = x a cos((log x) b ) + 2 , where a > 0 and 0 < b < 1 is a tempered function (which does not belong to any Hardy field).

[Bos-Ko-Q-Wi]. • {[bn c ] : n ∈ N}, where c is irrational > 1 and b = 0. • {[bn c + dn a ] : n ∈ N}, where b, d = 0, b/d is irrational, c ≥ 1, a > 0 and a = c. • {[bn c (log n) d ] : n ∈ N}, where b = 0, c is irrational > 1 and d is any number. • {[bn c (log n) d ] : n ∈ N}, where b = 0, c is rational > 1 and d = 0. • {[bn c + d(log n) a ] : n ∈ N},
(iii) A different type of example is provided by so-called "automatic sequences". Characterizations of ergodic automatic sequences are well known (see for example [Ma]). A typical example of such a sequence is the Morse sequence (0, 3, 5, 6, 9, 10, . . .), which is the sequence of integers the sum of whose digits in base two is even.

(iv) As a consequence of the Wiener-Wintner ergodic theorem, we know that for any weakly mixing m.p.s. (X, A, µ, T ) and for any A ∈ A with µ(A) > 0, for almost every x ∈ X the sequence {n ∈ N : T n x ∈ A} is ergodic.

In [Lem-Les-Pa-V-Wi] other types of random sequences that are almost surely ergodic are constructed, namely sequences of the form

N -1 n=0 f • T n 9 A
real valued function g defined on a half line [α, +∞) is called a tempered function if there exist k ∈ N such that g is k times continuously differentiable, g (k) (x) tends monotonically to zero as x → +∞, and lim x→+∞ x g (k) (x) = +∞. This notion is classical in the theory of uniform distribution, see [Ci].

where f is an integer valued function on a m.p.s. (X, A, µ, T ), under conditions on the m.p.s. and the function.

2.5.2. Polynomial sequences. The examples given in Subsection 1.3.2 not only have the ordinary vdC-property, but they have also the enhanced vdC property (in Z d ). We restrict ourselves here to the one-parameter case.

The following criterion, which generalizes Proposition 2.10, is useful in obtaining additional interesting examples.

Proposition 2.11. Let D = (d n ) n∈N be a sequence of nonzero integers. Suppose that (i) For all q ∈ N, D ∩ qZ has positive upper density in D;

(ii) For all irrational real numbers x, the sequence (d n x) is uniformly distributed mod 1.

Then D is an enhanced vdC sequence.

Proof. Fix q ∈ N. There exists an increasing sequence of positive integers

N (q) k k∈N such that (14) lim inf k→+∞ 1 N (q) k # n ∈ 1, N (q) k : q! divides d n > 0 .
Let us define a family of uniformly bounded trigonometric polynomials with spectrum contained in D, by the formula (15) P q,k (x) := 1

#{n ≤ N (q) k , q!|d n } n≤N (q)
k , q!|dn e (d n x) .

Replacing if necessary the sequence N (q) k by a subsequence, we can suppose that, for all rational numbers y, the sequence (P q,k (y)) converges as k → +∞.

Consider now an irrational real number x. We have

P q,k (x) = 1 #{n ≤ N (q) k , q!|d n } n≤N (q) k e (d n x) 1 q! q!-1 j=0 e(d n j/q!) = N (q) k #{n ≤ N (q) k , q!|d n } 1 q! q!-1 j=0 1 N (q) k n≤N (q) k e d n x + j q! .
Using (14) and hypothesis (ii), we see that lim k→+∞ P q,k (x) = 0.

We denote by g q the pointwise limit of the sequence (P k,q ) k∈N . For all rational numbers y, we have P q,k (y) = 1 for all large enough q.

Letting q go to infinity, we see that the sequence (g q ) converges everywhere to the characteristic function of the rationals. Applying the dominated convergence theorem twice, we observe that, for all finite measures σ on T,

lim q→+∞ lim k→+∞ T P q,k dσ = σ (Q/Z) .
Let σ be a positive measure on T such that lim n→+∞ σ(d n ) = 0. From (15), we deduce that lim k→+∞ T P q,k dσ = 0, hence σ (Q/Z) = 0, and in particular σ({0}) = 0.

We have proved that D is an FC + set.

From Proposition 2.11, one can deduce the following (not too surprising) corollaries.

Corollary 2.12. Let p be a polynomial with integer coefficients. The sequence (p(n)) n∈N is enhanced vdC if and only if for all positive integers q, there exists n ≥ 1 such that q divides p(n). Let us describe one more family of examples, coming from generalized polynomials10 , dealt with in [Berg-Ha]. Let q be an integer valued generalized polynomial. Corollary 3.5 of [Berg-Ha] gives a sufficient condition for the sequence (q(n)) to be an averaging sequence of recurrence and this condition is the same as the hypothesis of our Proposition 2.11. In particular averaging sequences of recurrence in [Berg-Ha] (see page 106), provide examples of enhanced vdC sets. Here are two of these examples.

• For α 1 , α 2 , . . . , α k non zero real numbers and k ≥ 3,

{[α 1 n][α 2 n] . . . [α k n] : n ∈ N} is an enhanced vdC-set.
• For α a non zero real number, {[αn]n 2 : n ∈ N} is an enhanced vdC-set.

Van der Corput sets and sets of recurrence

In this section we discuss some links between the vdC property and recurrence in dynamical systems. One of the reasons to be interested in sets of strong recurrence is that they naturally appear in combinatorial applications. See for example Theorem 4.1 in [Berg.1].

Alan Forrest ([Fo]) gave an example of a set of recurrence which is not a set of strong recurrence. We know that we obtain an equivalent definition if we replace in the last sentence "any sequence (u n ) n∈N of complex numbers of modulus 1" by "any bounded sequence (u n ) n∈N of complex numbers". (This is a consequence of the generalized vdC inequality, as Corollary 1.31 follows from Proposition 1.30.) Using Theorem 3.1 (and more precisely the remark immediately following the theorem), we obtain that, almost surely, lim

N →+∞ 1 N N -1 n=0 f • T n = 0 .
The ergodic theorem gives f dµ = 0, hence σ f = 0.

3.3. Enhanced vdC sets and strong recurrence. The results in this subsection indicate that the link between enhanced van der Corput sets and sets of strong recurrence is parallel to the link between van der Corput sets and sets of recurrence. However, we don't know if there exists here any example of Bourgain's type ( [Bou]). Such an example would give a negative answer to the following question.

Question 5. (perhaps very difficult) Is every set of strong recurrence an FC + set (or, equivalently, an enhanced van der Corput set)?

The following question also comes naturally. Question 6. Is there any inclusion between the collection of sets of strong recurrence and the collection of van der Corput sets ?

The next theorem gives an equivalence between strong recurrence and strong intersectivity (which is defined by (SR2) below). u n = 0 .

Proof of Theorem 3.3. It is clear that properties (SR2) and (SR3) are the same. The fact that (SR1)⇒(SR2) follows directly from Furstenberg's correspondence principle. The following proof of (SR2)⇒(SR1) has been communicated to us by Anthony Quas . Let (X, A, µ, T ) be a m.p.s. and A ∈ A, with µ(A) > 0. Let (x n ) n≥1 be a sequence of random points in X chosen independently and with the law µ. We consider a new sequence in X defined by (y n ) := (x 1 , x 2 , T x 2 , x 3 , T x 3 , T 2 x 3 , x 4 , . . . , T 3 x 4 , x 5 , . . . , T 4 x 5 , . . .) , and the random set E of numbers n such that y n ∈ A. We claim that, almost surely, ( 16) lim

N →+∞ 1 N N n=1 1 E (n) = µ(A) .
This claim can be justified by the following law of large numbers, applied to the mutually independent random variables (The convergence ( 17) is a direct consequence of some easy L 2 estimates. It can be also deduced from the convergence of ordinary Cesàro averages. We omit the proof.)

Y k := 1 k k-1 j=0 1 A (T j x k ) -µ(A) .
Using the block structure of the sequence (y n ) a similar argument gives (almost surely) (18) lim

N →+∞ 1 N N n=1 1 E (n)1 E (n + d) = µ(A ∩ T -d A) .
Assume now that condition (SR2) is satisfied. From ( 16) we deduce that d(E) > 0, hence there exists ǫ > 0 and infinitely many d ∈ D such that

d (E ∩ (E + d)) > ǫ ,
which means (by ( 18)) that µ(A ∩ T -d A) > ǫ.

Proposition 3.5. Any enhanced vdC set is a set of strong recurrence.

Proof. Let D ⊂ Z be an enhanced vdC set, let (X, A, µ, T ) be a m.p.s. and A ∈ A, with µ(A) > 0. There exists a positive measure σ on the torus such that, for all n ∈ Z,

σ(n) = µ(A ∩ T n A) .
This measure has a point mass at zero : σ({0}) ≥ µ(A) 2 . Since the set D is FC + , this implies that there exists ǫ > 0 such that σ(d) > ǫ for infinitely many d ∈ D.

• lim M →+∞ 1 M M m=1 v(d m ) = 0, • There exists D ′ ⊂ D such that lim M →+∞ #D ′ ∩ [-M, M] #D ∩ [-M, M] = 1 and lim m→+∞,dm∈D ′ v(d m ) = 0. Definition 6. An infinite set of integers D is a density vdC set if for any sequence (u n ) n∈Z of complex numbers of modulus 1 such that lim M →+∞ 1 M M m=1 lim sup N →+∞ 1 N N -1 n=0 u n+dm u n = 0 , one has lim N →+∞ 1 N N -1 n=0 u n = 0 .
• If an increasing sequence of integers (d n ) satisfies hypotheses (i) and

(ii) of Proposition 2.11, then the set {d n } is a density vdC set. This leads to the "polynomial examples" presented in Subsection 2.5.2.

The following proposition establishes a link with recurrence.

Proposition 3.7. Any density vdC set is an averaging set of recurrence.

The proof of this proposition is similar to the proof of Proposition 3.5, and is omitted.

3.5. Nice vdC sets and nice recurrence. Another natural notion of recurrence is that of nice recurrence. Definition 9. A set D of integers is a set of nice recurrence if given any m.p.s. (X, A, µ, T ) and A ∈ A, with µ(A) > 0, given any ǫ > 0, we have

µ A ∩ T -d A ≥ µ(A) 2 -ǫ , for infinitely many d ∈ D.
The following proposition provides an equivalent definition for sets of nice recurrence. Proof. We have to prove that the integer d appearing in Condition (C) can be chosen arbitrarily large. We suppose that Condition (C) is satisfied. We consider a m.p.s. (X, A, µ, T ) and a set A ∈ A, with µ(A) > 0. Denote by (Y, B, ν, S) a Bernoulli scheme on two letters (Y is the set of sequences of 0's and 1's, ν is a non trivial product measure, and S is the shift). Let k be a positive integer and B be the cylinder set in Y of all sequences beginning by a 1 followed by k 0's. We have ν

(B) > 0, ν(B ∩S -d B) = 0 if |d| ≤ k, and ν(B ∩ S -d B) = ν(B) 2 if |d| > k.
Applying the hypothesis to the product T × S of the two dynamical systems, we affirm that there exists d ∈ D such that

µ ⊗ ν (A × B) ∩ (T × S) -d (A × B) ≥ µ ⊗ ν(A × B) 2 -ǫν(B) 2 ,
The map γ is the Fourier transform of a positive measure σ on the torus. Suppose that D is a nice vdC set. By Lemma 2.2 we have lim sup

N →+∞ 1 N N n=1 u n 2 ≤ σ({0}) ≤ lim sup |d|→∞,d∈D | σ(d)| ≤ M .
Claim (N3) can be proved using Lemmas 2.3 and 2.4. Following the method described in Subsection 2.2, we have lim

N →+∞ 1 N N n=1 Y n+h Y n = σ(h) and lim N →+∞ 1 N N n=1 Y n = σ({0}) .
Hence, if D is nice vdC, then,

σ({0}) 2 ≤ lim sup |d|→∞,d∈D | σ(d)| .
And the claim (N3) is verified.

One more natural question concerns the Ramsey property. Using product dynamical systems, it is easy to verify that the class of sets of recurrence and the class of sets of strong recurrence have the Ramsey property. We saw that the class of vdC sets and the class of enhanced vdC sets have this property. The other notions of vdC sets and of recurrence could be studied from this point of view.

Question 9. Do the class of sets of nice recurrence and the class of nice vdC sets have the Ramsey property ?

Note that the class of sets of nice recurrence has the Ramsey property if and only if the following property of simultaneous nice recurrence is valid : given any set D ⊂ Z \ {0} of nice recurrence, any m.p.s. (X, A, µ, T ), any sets A and B in A, and any ǫ > 0, there exists d ∈ D such that

µ A ∩ T -d A > µ(A) 2 -ǫ and µ B ∩ T -d B > µ(B) 2 -ǫ .

Variations on the averaging method

In this short final section we provide additional remarks on some of the possible variations on the vdC theme which are related to different notions of averaging which naturally appear in the theory of uniform distribution and ergodic theory. For simplicity and in order to be able to more easily stress the important points, we restrict our discussion to subsets of Z. We do want, however, to remark that many of the results in this paper can be extended to much a wider setup involving general groups and various methods of summation. (See for example [Pe], where some directions of extensions are indicated.) 4.1. Well distribution. Recall that a sequence (x n ) n∈N of real numbers is well distributed mod 1 if, for any continuous function f on the torus T, we have lim

N -M →+∞ 1 N -M N -1 n=M f (x n ) = T f (t) dt.
To this notion of well distribution is naturally associated a notion of van der Corput set. Let us call it w-vdC set: a set D of positive integers is a w-vdC set if, for any sequence (u n ) n∈N of complex numbers of modulus 1 such that ∀d ∈ D, γ(d) := lim The spectral characterization of vdC sets given in Theorem 1.8 immediately implies that any vdC set is a w-vdC set.

But the proof, coming from Ruzsa ([Ruz]), of the fact that spectral properties (S1) and (S2) are necessary for vdC sets cannot be applied to w-vdC. This comes from the fact that the law of large numbers fails dramatically when we replace averages 1/N 0≤n<N by moving averages 1/(N -M) M ≤n<N .

Question 10. Is every w-vdC set a vdC set ? 4.2. Følner sequences. Let F = (F N ) N ≥1 be a Følner sequence in the space of parameters (which in this section is Z). Let us say that a real sequence (x n ) n∈Z is F -u.d. mod 1 if, for any continuous function f on the torus T, we have (20) lim

N →+∞ 1 |F N | n∈F N f (x n ) = T f (x) dx .
(We say that the sequence (f (x n )) converges to the integral of f in the F -sense when (20) is satisfied.) One can naturally define also the notion of F -vdC. A set D of non zero integers is F -vdC set if any sequence (x n ) such that, for all d ∈ D, the sequence x n+dx n is F -u.d. mod 1, is itself F -u.d. mod 1.

In order to compare the notion of F -vdC set with the notion of vdC set, it would be of interest to obtain a spectral characterization of F -vdC sets similar to Theorem 1.8.

Note that the sequence of correlations γ(h) := lim sup

N →+∞ 1 |F N | n∈F N u n+h u n
is positive-definite, and the Følner property is exactly what is needed in order to prove a result similar to Lemma 1.9. An argument similar to the one used in the proof of implication (S2)⇒(S3) allows one to establish the fact that any vdC-set is an F -vdC set.

In the other direction we don't know any general result, but, keeping in mind the argument we used in the proof of Theorems 1.8 and 2.1, we can state the following sufficient condition : suppose that for any probability measure on the torus T there exists a sequence (Y n ) n∈N of complex numbers of modulus one such that, for all h ∈ Z, then any F -vdC set is a vdC set.

We have in particular the following result (and its multiparameter extensions).

Proposition 4.1. If a Følner sequence F is such that any bounded sequence which converges in the Cesàro sense also converges in the F -sense12 then the notions of vdC set and F -vdC set coincide.

Appendix. A remark on divisibility of polynomials

Definitions.

• A polynomial p ∈ Z[X] is divisible by an integer d if there exits n ∈ Z such that d divides p(n). (Trivial examples : if p(0) = 0 then p is divisible ; the polynomial 2X + 1 is not divisible ; polynomials X and X + 1 are divisible but not simultaneously divisible.) Known facts. Let p 1 , p 2 , . . . , p r ∈ Z[X]. There is equivalence between the following assertions

• The sequence (p 1 (n), p 2 (n), . . . , p r (n)) n∈N is a Poincaré recurrence sequence for finite measure preserving Z r actions;

• The sequence (p 1 (n), p 2 (n), . . . , p r (n)) n∈N is a van der Corput sequence in Z r ;

• p 1 , p 2 , . . . , p r are simultaneously divisible.

In [Berg-Lei-Les], we prove that the simultaneous divisibility of polynomials p 1 , p 2 , . . . , p r is also a necessary and sufficient condition for multiple recurrence of the type µ(A ∩ T p 1 (n) A ∩ T p 2 (n) A ∩ . . . ∩ T pr(n) A) > 0 .

Claim. The simultaneous divisibility of a family of polynomials is a property strictly stronger than the divisibility of any of their linear combinations. In other words, there exist two polynomials p and q in Z[X] such that, for any integers a and b, the polynomial ap + bq is divisible but the polynomials p and q are not simultaneously divisible.

Here are two facts which seem to go against the previous claim. Let p, q ∈ Z[X].

• Let d be a prime number. If for all pairs (a, b) of integers, the polynomial ap + bq is divisible by d, then p and q are simultaneously divisible by d. • Let d and e be two relatively prime integers. If p and q are simultaneously divisible by d and simultaneously divisible by e, then they are simultaneously divisible by de.

These facts indicate that the key to the distinction between the simultaneous divisibility and the divisibility of linear combinations of polynomials lies with the divisibility by d k where d is a prime number and k > 1.

Proof of the Claim. Let us show that the polynomials p(X) = (2 + X 2 + X 3 )(1 + 2X) and q(X) = X(1 + X)(1 + 2X)

are not simultaneously divisible by 4 although the polynomial ap + bq is divisible for all a, b in Z.

Modulo 4, we have p(0) = 2 and q(0) = 0, p(1) = 0 and q(1) = 2, p(2) = q(2) = 2, p(3) = 2 and q(3) = 0. This shows that p and q are not simultaneously divisible by 4.

Let us fix a and b in Z and show that ap + bq is divisible. It is of course enough to consider the case when a and b are relatively prime. The divisibility of ap + bq by odd integers is directly given by the presence of the common factor 1 + 2X. Let us examine divisibility by the powers of 2. We will distinguish the case when one of the two numbers a and b is even, and the case when both are odd.

First case : a or b is even (and the other is odd). Let us show by induction on k that, for all k ≥ 0, there exists an odd number n k such that 2 k | ap(n k ) + bq(n k ). We can choose any number n 0 , and n 1 = 1 is OK. Suppose that the result is true for an integer k ≥ 1. Define ℓ := max{i ≥ k : 2 i | ap(n k ) + bq(n k )}. We have ℓ ≥ k and ap(n k ) + bq(n k ) = 2 ℓ α, with α odd. Define a new odd number by n k+1 = n k + 2 ℓ . Using ap(X) + bq(X) = 2aX 4 + (3a + 2b)X 3 + (a + 3b)X 2 + (4a + b)X + 2a ,

2 1 N

 21 The subset S of N has positive upper density if d(S) := lim sup N →+∞ |S ∩ {1, 2, . . . , N }| > 0.

  The class of vdC sets has the Ramsey property. Namely, If D is a vdC set in Z d and if D = D 1 ∪ D 2 then at least one of the D i is a vdC set. • Let p 1 , p 2 , . . . , p d be a finite family of polynomials with integer coefficients, to which we associate the subset S = {(p 1 (n), p 2 (n), . . ., p d (n)) : n ∈ N} of Z d . The following properties are equivalent : -The set S is a set of recurrence for Z d -actions 5 . -The set S is a vdC set in Z d .

1. 1 . 1 .

 11 Van der Corput's inequality in Z 2 . For a, b, c, d ∈ Z, we write (a, b) ≤ (c, d) if a ≤ c and b ≤ d. (Similarly for <, ≥ and >.) We write 0 for (0

  3, or Corollary 1.4 applied to sets D = 0 × N and D = N × 0. 1.1.3. An abstract version of van der Corput's principle. Proposition 1.5. Let (G, •) be a group, and E, D two finite subsets of G.

Theorem 1 . 8 .

 18 Let D ⊂ Z 2 \ {0}. The following statements are equivalent (S1) D is a van der Corput set. (S2) If σ is a positive measure on the 2-torus T 2 such that, for all d ∈ D, σ(d) = 0, then σ ({(0, 0)}) = 0. (S3) If σ is a positive measure on the 2-torus T 2 such that, for all d ∈ D, σ(d) = 0, then σ is continuous.

Corollary 1 .

 1 15 (Linear transformations of vdC sets). Let d and e be positive integers, and let L be a linear transformation from Z d into Z e (i.e. an e × d matrix with integers entries).

( 1 )

 1 If D is a vdC set in Z d and if 0 / ∈ L(D), then L(D) is a vdC set in Z e . (2) Let D ⊂ Z d . If the linear map L is one to one, and if L(D) is a vdC set in Z e , then D is a vdC set in Z d . Proof. Let D be vdC set in Z d and σ a positive measure on the e-torus such that σ vanishes on L(D). Let us denote by t L the map from T e into T d defined by k • t L(x) = L(k) • x for k ∈ Z d and x ∈ T e . Denoting by σ ′ the image of σ under the linear transformation t L, we see that, for all k ∈ Z d , σ ′ (k) = σ(L(k)). Hence the Fourier transform σ ′ vanishes on the vdC set D. The measure σ ′ has no mass at zero, and hence σ also has no mass at zero. This proves the first assertion. Suppose now that L is one to one and that L(D) is a vdC set in Z e . Consider the lattice L(Z d ) in Z e . By a classical lemma (see for example [G], Exercise 8 of Chapter 31), there exist n 1 , n 2 , . . . , n e in Z e and positive integers p 1 , p 2 , . . . , p d such that Z e = Zn 1 + Zn 2 + . . . + Zn e and L(Z d ) = p 1 Zn 1 + p 2 Zn 2 + . . . + p d Zn d . This allows us to view L(D) as a vdC set in Z d ≃ Zn 1 + Zn 2 + . . . + Zn d and L as an endomorphism of Z d .

Corollary 1 .

 1 16 (Lattices are vdC*). If G is any d-dimensional lattice in Z d , and if D is a vdC set in Z d , then G ∩ D is a vdC set in Z d . Proof. To begin, we remark that if G is a lattice in Z d , and if z ∈ Z d , z / ∈ G, then the translate z + G is not a vdC set in Z d (test the definition of a vdC set on the indicator function of the set G). Since G is a d-dimensional lattice in Z d , there exist finitely many points z 1 , z 2 , . . . , z k in Z d and outside G such that

1. 3 . 2 .

 32 Application to polynomial sequences and sequences of shifted primes. The following proposition is the two-dimensional extension of Example 3 in [Kam-MF].

  It is not hard to verify that (10) is still true when d ∈ (-D) or e ∈ (-E). Let us fix ǫ > 0. By Remark 1.26, there exist two positive-definite families (a d ) and (b e ) indexed by Z 2 such that a d (resp. b e ) is zero whenever d (resp. e) is outside a finite subset of D ∪ (-D) ∪ {0} (resp. E ∪ (-E) ∪ {0}), with a 0 < ǫ, b 0 < ǫ and d a d = e b e = 1. It is clear from Proposition 1.25 (or from the Bochner-Herglotz Theorem) that the family (a d b e ) (d,e)∈Z 4 is positive definite. Let us denote P := N 1 N 2 M 1 M 2 and p := min{N 1 , N 2 , M 1 , M 2 }. The generalized vdC inequality (Theorem 1.27) applied to Z 4 gives

2 ≤

 2 d or e=0 a d b e . Since d or e=0 a d b e = a 0 e b e + b 0 d a da 0 b 0 ≤ 2ǫ, we conclude that the last limsup is zero.

2. 2 .(

 2 Definitions and a spectral characterization. Definition 3. An infinite set of integers D is enhanced van der Corput if, for any sequence (u n ) n∈Z of complex numbers of modulus 1 such that (12) ∀d ∈ D, γ(d) := lim Note that we obtain an equivalent definition if we replace lim by limsup in (12). See Proposition 2.5.) Definition 4. An infinite set of integers D is FC + if every positive measure σ on the torus T having the property that lim |d|→+∞,d∈D σ(d) = 0 is continuous.

Y

  n = E [e(hθ)]. Furthermore, the set of positive integers n such that Y n+h Y n = Z n has full density. Thus, almost surely, n+h Y n = E [e(hθ)] .

  Corollary 2.6 (Ramsey property). If D = D 1 ∪ D 2 is an enhanced vdC set, then at least one of the sets D 1 or D 2 is enhanced vdC.

Corollary 2 . 8 (

 28 Linear transformations). Let d and e be positive integers, and L be a linear transformation from Z d into Z e (i.e. an e × d matrix with integers entries).

( 1 )

 1 If D is an enhanced vdC set in Z d and if 0 / ∈ L(D), then L(D) is an enhanced vdC set in Z e . (2) Let D ⊂ Z d . If the linear map L is one to one, and if L(D) is an enhanced vdC set in Z e , then D is an enhanced vdC set in Z d . Corollary 2.9 (Lattices are (enhanced vdC)*). If G is any d-dimensional lattice in Z d , and if D is an enhanced vdC set in Z d , then G ∩ D is an enhanced vdC set in Z d .

  where b, d = 0, c ≥ 1, and a > 1.The paper[Bos-Ko-Q-Wi] contains also interesting examples of non ergodic sequences. For example the sequence [ √ 2n 3/2 + log n] is not ergodic, whereas sequences [ √ 2n 3/2 + (log n) 2 ] and [ √ 2n π/2 + log n] are ergodic. Is {[ √ 2n 3/2 + log n] : n ∈ N} an enhanced vdC set ? We leave this as an open question.

Corollary 2 .

 2 13. Let f be a (non zero) polynomial with integer coefficients and zero constant term. Sequences {(f (p -1)) : p ∈ P } and {(f (p + 1)) : p ∈ P } are enhanced vdC.

3. 1 .

 1 Sets of strong recurrence. Recall that a subset D of Z is a set of recurrence if, given any m.p.s. (X, A, µ, T ) and any subset A in A of positive µ-measure, there exists d ∈ D, d = 0 such that µ A ∩ T d A > 0. Definition 5. An infinite subset D of Z is a set of strong recurrence if, given any m.p.s. (X, A, µ, T ) and any subset A in A of positive µ-measure, lim sup d∈D,|d|→+∞ µ A ∩ T d A > 0 .

3. 2 .

 2 VdC sets and sets of recurrence. Recall once more the definition of a vdC set (cf. Definition 2).A set of non zero integers D is a van der Corput set if, for any sequence (u n ) n∈N of complex numbers of modulus 1 such that ∀d ∈ D, γ(d) := lim

Theorem 3 . 3 .

 33 Let D ⊂ Z. There is equivalence between the following assertions. (SR1) D is a set of strong recurrence. (SR2) For any E ⊂ N of upper density d(E) > 0, there exists ǫ > 0 and infinitely many d ∈ D such that d (E ∩ (E + d)) > ǫ .(SR3) For any sequence (u n ) n∈N of 0's and 1's such that lim

Lemma 3 .

 3 4 (law of large numbers). Let (Y k ) be a sequence of random variables such that sup k E(Y 2 k ) < +∞, E(Y k ) = 0, and E(Y k Y ℓ ) = 0 if k = ℓ. Almost surely we have

3. 4 .

 4 Density notions of vdC sets and sets of recurrence. A new natural notion of vdC-type set, which we will call density vdC can be obtained by replacing in Definition 3 the convergence of γ to zero along the set D by the convergence of γ to zero along a subset of D which has full density in D. We will associate to it a notion of density FC + set. These notions are related to averaging sets of recurrence, as we will see below. Here are the formal definitions.If D is an infinite set of integers, we will write D = {d m : m ∈ N} with the convention that the numbers d m are pairwise distinct and the sequence (|d m |) is nondecreasing. Let us recall that for any bounded sequence (v(d m )) m∈N of positive numbers the two following properties are equivalent:

Proposition 3 .

 3 8. A set D of integers is a set of nice recurrence if and only if the following is true: (C) given any m.p.s. (X, A, µ, T ) and A ∈ A, with µ(A) > 0, given any ǫ > 0, there exists d ∈ D, d = 0 such that µ A ∩ T -d A ≥ µ(A) 2ǫ .

  n∈F N Y n = σ({0}) and lim N →+∞ 1 |F N | n∈F N Y n+h Y n = σ(h);

  2 , . . . f d of polynomials with integer coefficients and with zero constant terms the set {f 1 (p-1), f 2 (p-1), . . . , f d (p-1) : p ∈ P } is a vdC set in Z d . (It can also be proved that it is an enhanced vdC set; see below.) • The Cartesian product of two vdC sets is a vdC set in the corresponding product of parameters space. • A subset D of Z is a vdC set if and only if any positive measure σ on the torus T such that d∈D | σ(d)| < +∞ is continuous. • We establish a generalized van der Corput inequality for multiparameter sequences in a Hilbert space (Proposition 1.30).

  Note that δ(D) is not the ordinary notion of density, which corresponds to lim sup min{H 1 ,H 2 }→+∞ .)

	Corollary 1.4. Let (x n ) n∈N 2 be a family of real numbers, and D ⊂ Z 2 \ {0}. If δ(D) = 1 and if, for any d ∈ D, the family (x n+d -x n ) is u.d. mod 1, then the family (x n ) is u.d. mod 1.

  Corollary 1.24 (Cf.[Ruz], Corollary 3). Any vdC set in Z 2 can be partitionned into infinitely many pairwise disjoint vdC sets.Proof. Let D be a vdC set in Z 2 . There exists a sequence (I k ) k≥1 of pairwise disjoint finite subsets of D, and for each k, a trigonometric polynomial P k with spectrum in I k and such that P k

mod 1. We conclude by Proposition 1.19.

Several other examples of vdC sets are presented in Subsection 2.5.

1.3.3

. One more corollary à la Ruzsa. Following

[Ruz]

, we deduce from Proposition 1.18 a new combinatorial property of vdC sets.

  1.5. A new spectral characterization. We work in this subsection with ordinary sequences indexed by Z. The extension to the multidimensional case is straightforward. We have the following spectral characterization of vdC sets, which completes the classical Theorem 1.8.

Theorem 1.32. Let D ⊂ Z. Then D is a van der Corput set if and only if any positive measure σ on the torus T such that d∈D | σ(d)| < +∞ is continuous.

  • A polynomial p ∈ Z[X] is divisible if it is divisible by any integer. • Polynomials p 1 , p 2 , . . . , p r ∈ Z[X] are simultaneously divisible by an integer d if there exists n ∈ Z such that d divides p i (n), 1 ≤ i ≤ r. • Polynomials p 1 , p 2 , . . . , p r ∈ Z[X] are simultaneously divisible if they are simultaneously divisible by any integer.

Ruzsa uses the name correlative set instead of van der Corput set.

This fact was first noticed and utilized by Khintchine in[Kh].

A subset S of Z d is called a set of recurrence for Z d -actions if, given any measure preserving Z d -action (T n ) n∈Z d on a probability space (X, A, µ) and any A ∈ A with µ(A) > 0, there exists n ∈ S, n = 0 such that µ (A ∩ T n A) > 0.

A subset S of Z d is called a set of multiple recurrence for Z-actions if, given any m.p.s. (X, A, µ, T ) and any A ∈ A with µ(A) > 0, there exists (n 1 , n 2 , . . . , n d ) ∈ S \ {(0, 0, . . . , 0)} such that µ (A ∩ T n1 A ∩ T n2 A ∩ . . . ∩ T n d A) > 0.

The class of polynomial functions is obtained, starting from the constants and the identity function x → x, by the use of addition and multiplication. To define the class of generalized polynomials just add the greatest integer function as an allowed operation.

If any bounded sequence which converges in the Cesàro sense also converges in the F -sense then the limits in the Cesàro sense and in the F -sense coincide (when they exist). This fact is left as an exercise for the reader.

The first author gratefully acknowledges the support of the NSF under grant DMS-0600042.

A set D is a set of recurrence if and only if it is intersective, namely satisfies the following condition: for any set of integers E of positive upper density, one has D ∩ (E -E) = ∅. This fact is well known (see [BM] and [Berg.1]). This fact is utilized in the proof of the following theorem. It is an exercise to verify that we obtain an equivalent statement if we replace in the preceding sentence "for any sequence (u n ) n∈N of 0's and 1's" by "for any bounded sequence (u n ) n∈N of positive real numbers".

As a consequence of Theorem 3.1, we obtain the well known fact that any van der Corput set is a set of recurrence ( [Kam-MF]). Answering a question of Ruzsa, Bourgain proved in [Bou] that there exist sets of recurrence which are not vdC.

Proof of Theorem 3.1. If D is not a set of recurrence, then there exists a set E ⊂ N such that

If we consider the sequence (u n ) defined by

This proves the "if" part of the Theorem. Suppose now that D is a set of recurrence. The fact that if E is a set of positive upper density, then there exists d ∈ D such that {n ∈ E : n + d ∈ E} = ∅ is a consequence of Furstenberg's correspondence principle.

But this principle gives more 11 : there exists d ∈ D such that the set {n ∈ E : n + d ∈ E} has positive upper density.

Hence if a sequence (u n ) is the indicator of a set E of positive upper density, then there exists d ∈ D such that lim sup

The similarity and the distinction between the recurrence property and the vdC property is also illustrated by the next proposition (to be compared with the spectral characterization of vdC sets -Theorem 1.8).

If (X, A, µ, T ) is a m.p.s. and if A ∈ A, we denote by σ A the spectral measure of A, which is defined by µ

The set D is a set of recurrence if and only if one of the two equivalent following properties is satisfied:

• In any ergodic m.p.s., if the Fourier transform σ A of a set A vanishes on D, then σ A = 0. • In any ergodic m.p.s., if the Fourier transform σ f of a bounded positive function f vanishes on D, then σ f = 0.

Proof. Suppose that D is not a set of recurrence. There exists an ergodic m.p.s. (X, A, µ, T ) and a set A in A, with positive measure such that, for

Suppose that D is a set of recurrence. Let σ f be the spectral measure of a bounded positive function f . Suppose that for all d ∈ D, σ f (d) = 0. By the ergodic theorem, we have almost surely, for all d ∈ D,

11 For a statement of Furstenberg's correspondence principle in the form we utilize here, see for example Theorem 1.1 in [Berg.3].

(Compare this definition with Proposition 2.5.) Definition 7. An infinite set of integers D is a density FC + set if every positive measure σ on the torus T such that lim

(Compare with Definition 4. Any density FC + set is a FC + set.) Definition 8. An infinite set of integers D is an averaging set of recurrence if for any m.p.s. (X, A, µ, T ) and A ∈ A, with µ(A) > 0, lim sup

Note that this definition differs slightly from the one given in [Berg-Ha] where the limsup is replaced by a lim.

Any averaging set of recurrence is a set of srong recurrence.

Theorem 3.6. The notions of a density vdC set and of a density FC + sets coincide.

The proof of this theorem is similar to the proof of Theorem 2.1 and is omitted.

From Theorem 3.6 one can deduce for example that the class of density vdC sets has the Ramsey property.

Of course every density vdC set is an enhanced vdC set. We do not know whether the reverse implication holds.

Question 7. Do the notions of density vdC set and enhanced vdC set coincide ? Questions 2, 3 and 4 that we asked about enhanced vdC sets have obvious density vdC sets analogues.

Note also that the examples described in Subsection 2.5 can also be utilized to illustrate the notion of density vdC set. In particular we have: hence there exists d ∈ D, |d| > k, such that

The notion of sets of nice recurrence seems to be naturally related to the following definitions.

Definition 10. An infinite set D of integers is a nice vdC set if, for any sequence (u n ) n∈N of complex numbers of modulus one, lim sup

Definition 11. A infinite set D of integers is a nice FC + set if, for any positive measure σ on the torus,

The following proposition is similar in spirit to Proposition 3.8. Proposition 3.9. A set D of integers is a nice FC + set if and only if the following is true:

(C') for any positive measure σ on the torus and any ǫ > 0, there exists

Proof. We have to prove that the integer d appearing in Condition (C') can be chosen arbitrarily large. We suppose that Condition (C') is satisfied. Let k be a positive integer. There exists a positive measure ρ on the torus such that ρ

(Choose the spectral measure of the indicator of the set B in the Bernoulli scheme considered in the proof of Proposition 3.8.) We apply our hypothesis to the measure σ ⋆ ρ. There exists d ∈ D such that

Question 8. What are the implications between the three properties : nice vdC, nice FC + and nice recurrence ?

Here is what we know: Here is what this last assertion means. Let D is a nice vdC set; for any probability measure σ on the torus,

and, consequently, we have the following recurrence property: given any m.p.s. (X, A, µ, T ) and A ∈ A, with µ(A) > 0, given any ǫ > 0, we have

for infinitely many d ∈ D.

(Note that the exponent 4 in ( 19) is not a typo. It would be "nice" to better understand the meaning of inequality ( 19).)

The proof of (N1) is a direct application of the spectral theorem : let (X, A, µ, T ) be a m.p.s. and A ∈ A. There exists a positive measure σ on the torus such that

The proof of (N2) follows the line of the spectral characterization described in Subsections 1.2.2 and 2.2. Let (u n ) be a sequence of complex numbers of modulus one and

There exists an increasing sequence (N j ) j≥0 of positive integers such that

we note that, modulo 2 ℓ+1 ,

Since α + an 2 k + b is even, this shows that 2 ℓ+1 | ap(n k+1 ) + bq(n k+1 ). We have ℓ + 1 ≥ k + 1, and n k+1 is odd. This concludes the induction.

Second case : a and b are odd. Let us show by induction on k that, for all k ≥ 0, there exists an even number n k such that 2 k | ap(n k ) + bq(n k ). We can choose any number n 0 , and n 1 = 2 is OK. Suppose that the result is true for an integer k ≥ 1. We define ℓ and n k+1 = n k + 2 ℓ as in the first case, but now the number n k is even, hence we have still ap(n k+1 ) + bq(n k+1 ) = 2 ℓ (α + an 2 k + b) = 0 modulo 2 ℓ+1 , and the induction process works.

In any case, we have proved that ap + bq is divisible by all the powers of 2. We know also that the polynomial ap + bq is divisible by any odd integer. Let us prove that it is divisible by any integer 2 k α, where α is odd. We write ap(X) + bq(X) = (2X + 1)r(X). We know that 2 k | r(n k ). By the Bézout identity, there exist integers u and v such that 2n k + 1 = -u2 k+1 + vα .

We have α | 2(n k + 2 k u) + 1 and 2 k | r(n k + 2 k u), hence 2 k α | ap(n k + 2 k u) + bq(n k + 2 k u) .

This proves that the polynomial ap + bq is divisible.