Equidistribution of polynomials, recurrence and van der Corput trick

In the early twenty century Hardy and Littlewood gave an answer to the following problem: given a polynomial {f\in {\mathbb R}[x]} with real coefficients, when do we have that the set {\{f(n)-\lfloor f(n)\rfloor,n\in {\mathbb Z}\}} is dense in the interval {[0,1]}?. Today we have a much shorter answer, the difficulty was that being dense is a property too weak to bootstrap.

In {1890} Poincaré obtained an important result which today can be given as an easy exercise; this is called Poincaré recurrence theorem. It states that in a probability space {(X,\mu)}, if {T:X\rightarrow X} is a map that preserves the measure {\mu} and {A\subset X} is a set of positive measure, then there is some {n\in {\mathbb Z}} such that {\mu(A\cap T^n A)>0}.

More recently, in the late {1970}‘s, Sárközy proved the following combinatorial result: if a subset {A\subset {\mathbb Z}} has positive upper density (the upper density is defined by {\displaystyle\overline d(A):=\limsup_{n\rightarrow \infty} \frac1n|A\cap[1,n]|}) then there is some {n\in {\mathbb Z}} and {a\in A} such that {a+n^2\in A}.

This three seemingly different topics are entangled together, with the so-called van der Corput trick in the center. In this post I want to make this relation clear by proving the following theorem (I believe this theorem as stated here was only completely solved by Kamae and Mendes France in this paper). (Update: Actually there is another way to prove this that was probably known before. Ideas in that line go as back as this Furstenberg’s paper where the case when p(x)=x^2 is proved.)

Theorem 1 Let {p\in {\mathbb Z}[x]} be a polynomial with integer coefficients and assume that

\displaystyle \text{for all positive integer }k\text{ there is some }n\in {\mathbb Z}\text{ such that }k|p(n).\ \ \ \ \ (1)

Then, for any set {A\subset {\mathbb Z}} with positive upper density there exists some integer {m} such that p(m)\neq0 and {A\cap (A-p(m))} is non-empty.

Furthermore, if {p} fails condition (1) for some {k}, then the set {A=k{\mathbb Z}} is such that {A\cap (A-p(m))} is empty for every {m}. We also note that if {p} has an integer root (i.e. if {p(n)=0} for some integer {n}) then {p} automatically satisfies condition (1), however having an integer root is not necessary, as shown by the example {p(x)=(x^2-13)(x^2-17)(x^2-221)}.

— 1. van der Corput Trick —

In this section we give a different solution of the problem solved by Hardy and Littlewood, which I believe was first found by Weyl. To simplify the notation, for non-negative real {x} we will write {x \mod 1} to denote the fractional part of {x}, i.e. {x\mod 1:=x-\lfloor x\rfloor}. We can also think of {x\mod 1} as being the image of {x} under the canonical projection {\pi:{\mathbb R}\rightarrow {\mathbb T}}, where, as usual, {\mathbb T} stands for the circle group, i.e. the quotient {{\mathbb T}:={\mathbb R}/{\mathbb Z}} of {{\mathbb R}} by the subgroup {{\mathbb Z}}. We now prove the following:

Proposition 2 Let {f\in {\mathbb R}[x]} be a polynomial. Then the set {\{f(n)\mod 1,n\in {\mathbb Z}\}} is dense in {[0,1]} if and only if {f(x)-f(0)} has an irrational coefficient (or in other words if there is a coefficient of {f} different from the constant term which is irrational).

First we note that changing the constant term only shifts the set, and so the property of being dense doesn’t change. Therefore we can assume that {f(0)=0}. Next we note that if all coefficients are rational and {a} is a common denominator, then the set {\{f(n)\mod 1\ ,n\in {\mathbb Z}\}} is contained in the set {\left\{\frac ia,0\leq i\leq a\right\}} and thus it is not dense.

To prove the other implication, the natural idea is to use induction on the degree of {f}. If {f} has degree {1} this means that {f} is of the form {f(x)=\alpha x} for some irrational number {\alpha}. By the definition of “irrational” and the pigeonhole principle we can see that {\{f(n)\mod1\ ,n\in {\mathbb Z}\}} is indeed dense in {[0,1]}.

The problem is with the induction step. As in many other problems solved by induction, we need here to strengthen the conclusion of the theorem, so that we also have stronger conditions to perform the induction step. In this case, we prove that the sequence {\{f(n)\mod1\}_n} is not only dense but actually equidistributed in {[0,1]}. Now we are going to prove:

Proposition 3 Let {f\in {\mathbb R}[x]} be a polynomial with real coefficients such that {f(0)=0} and {f} has at least one irrational coefficient. Then the projection modulo {1} of the sequence {\{f(n),n=1,2,...\}} is equidistributed in the quotient {{\mathbb T}:={\mathbb R}/{\mathbb Z}}. (Here, as usual, the projection modulo {1} is the natural quotient map {\pi:{\mathbb R}\rightarrow {\mathbb T}}).

Clearly this theorem implies theorem 2. Again we prove this by induction on the degree of {f}. When {f} has degree {1} it is of the form {f(x)=\alpha x} for some irrational {\alpha} and the result can be obtained by an improved version of the density case. One can also use the Weyl criterion together with the sum of geometric series.

The advantage in improving to equidistribution is that we now have the van der Corput trick which does the induction step:

Proposition 4 (van der Corput trick) Let {\{x_n\}} be a sequence in {\mathbb T} such that for each {h=1,2,...}, the sequence {\{x_{n+h}-x_n\}} is equidistributed. Then the sequence {\{x_n\}} is itself equidistributed.

Before we prove this fact let’s see how it finishes the proof of proposition 3: recall we are proving it by induction, if we assume the result valid for polynomials of degree at most {d-1} and {f} is a polynomial of degree {d}, then for each {h}, the function {g(n)=f(n+h)-f(n)} is a polynomial of degree at most {d-1} which is then equidistributed modulo {1}. By van der Corput trick we conclude that {f(n)} is also equidistributed modulo {1}.

Proof: (of proposition 4) Fix {m\in {\mathbb Z}\setminus\{0\}} an arbitrary non-zero integer and {\epsilon>0}. By Weyl criterion it suffices to prove that

\displaystyle  \left|\lim_{N\rightarrow \infty}\frac1N\sum_{n=0}^{N-1}e^{2\pi i m x_n}\right|<3\epsilon \ \ \ \ \ (2)

To simplify the notation, call {u_n:=e^{2\pi i m x_n}}, so that {e^{2\pi im(x_{n+h}-x_n)}=u_{n+h}\overline{u_n}}. Using again the Weyl criterion, the hypothesis implies that, for each positive integer {h}, we have

\displaystyle \displaystyle\lim_{N\rightarrow \infty}\frac1N\sum_{n=0}^{N-1}u_{n+h}\overline{u_n}=0\ \ \ \ \ (3)

The idea of the proof is to replace the average on (2) with a double average. For each {H}, if {N} is large enough then

\displaystyle  \left|\frac1N\sum_{n=0}^{N-1}u_n-\frac1H\sum_{h=1}^H\frac1N\sum_{n=0}^{N-1}u_{n+h}\right|<\epsilon \ \ \ \ \ (4)

On the other hand

\displaystyle  \begin{array}{rcl} \left|\frac1H\sum_{h=1}^H\frac1N\sum_{n=0}^{N-1}u_{n+h}\right|^2&\leq & \displaystyle\frac1N\sum_{n=0}^{N-1}\left|\frac1H\sum_{h=1}^Hu_{n+h}\right|^2\\&=& \displaystyle\frac1N\sum_{n=0}^{N-1}\frac1{H^2}\sum_{h_1=1}^H\sum_{h_2=1}^Hu_{n+h_1}\overline{u_{n+h_2}}\\&=& \displaystyle\frac1N\sum_{n=0}^{N-1}\frac1H\sum_{h_1=1}^H|u_{n+h_1}|^2+ \frac1{H^2}\sum_{h_1=1}^H\sum_{h_2\neq h_1}\frac1N\sum_{n=h_2}^{N-1+h_2}u_{n+h_1-h_2}\overline{u_n} \end{array}

By (3) we have that also {\displaystyle\frac1N\sum_{n=h_2}^{N-1+h_2}u_{n+h_1-h_2}\overline{u_n}} goes to {0} when {n\rightarrow \infty}. We do this with {H>1/\epsilon}, and then choose {N} large enough so that the last equation is also less than {\epsilon}. Thus we get

\displaystyle \left|\frac1H\sum_{h=1}^H\frac1N\sum_{n=0}^{N-1}u_{n+h}\right|^2\leq 2\epsilon

Putting this together with (4) we obtain (2), thus finishing the proof.\Box

— 2. Recurrence sequences —

As mentioned in the introduction, Poincaré obtained a very useful result on recurrence:

Theorem 5 (Poincaré Recurrence) Let {(X,{\cal B},\mu)} be a probability space and {T:X\rightarrow X} an invertible measure preserving (measurable) map (i.e., for any {B\in {\cal B}} we have {\mu(TB)=\mu(B)}). Then for any {B\in {\cal B}} with positive measure there exists some positive integer {n} such that {\mu(B\cap T^nB)>0}.

Proof: Let {N>\frac1{\mu(B)}}. Then the sets {B,TB,...,T^NB} can’t be all disjoint, since the measure of their union is no more than {1} and thus less than the sum of their measures. Assume that {\mu(T^kB\cap T^lB)>0} with {k>l}. Then applying {T^{-l}} we get that {\mu(T^{k-l}B\cap B)>0}. \Box

There are several improvements that can be made to the proof to obtain better results. For instance, it is not hard to see from the proof that {n} can be bounded by {1/\mu(B)}. We can also require that the set {B\cap T^{-n}B} has not only positive measure but has actually measure bigger than {\lambda \mu(B)^2} for any {\lambda<1}. Analyzing the proof deeper we see that we actually proved the following: “for any set {K} of positive integers with size {|K|>\frac1{\mu(B)}} we can find {n} in the difference set {K-K:=\{k_1-k_2:k_1,k_2\in K\}}“.

Rewriting this last sentence we obtain the following: The set {R_B:=\{n\in {\mathbb Z}: \mu(T^nB\cap B)>0\}} intersects {K-K} for any {K\subset {\mathbb Z}} with {|K|>\frac1{\mu(B)}}. So for instance when {K} only has even numbers, also {K-K} only has even numbers, and so we have some even {n\in R_B}. Thus the intersection {2{\mathbb Z}\cap R_B} is non-empty, no matter what’s the space {X}, the map {T} or the set {B}! This property of the even numbers is satisfied for many other sets, which we will call recurrent sets:

Definition 6 (Recurrent sets) A set {R} of non-zero integers is a recurrent set if for any probability space {(X,{\cal B},\mu)}, any invertible measure preserving map {T:X\rightarrow X} and for any {B\in {\cal B}} with positive measure, {R} has non-empty intersection with {R_B:=\{n\in {\mathbb Z}:\mu(T^nB\cap B)>0\}}.

So for instance the set of all positive integers is a recurrent set, and so is the set {2{\mathbb Z}} of even numbers. One surprising feature of recurrent sets is that there are so many. This means that the sets {R_B} are always “large” and “well spread” over the integers in some sense. Before further discussion on recurrent sets, I will prove a nice property of the sets {R_B}, which implies that they have always positive upper density (recall that we define the upper density of a set {A} of positive integers by {\displaystyle\overline d(A):=\limsup_{n\rightarrow \infty} \frac1n|A\cap[1,n]|}).

Proposition 7 With the hypothesis of theorem 5, the set {R_B:=\{n\in {\mathbb Z}:\mu(T^nB\cap B)>0\}} is a syndetic set (i.e. there is some {M} such that the interval {[l,l+M]} contains an element of {R_B} for any {l}), and thus has positive upper density.

Actually {R_B} satisfies a stronger property, usually called IP*, but which I will not develop in this post.

Proof: Suppose otherwise. Then for each {k} there is some {l_k} such that {[l_k,l_k+k]} is disjoint from {R_B}. Then let {k_1} be some integer not in {R_B} and for each {j=1,2,...} let {k_{j+1}:=l_{k_j}+k_j}. Then for any {i\leq j} we have {k_{j+1}-k_i=l_{k_j}+(k_j-k_i)\in [l_{k_j},l_{k_j}+k_j]} and so {k_{j+1}-k_i} is not in {R_B}. However, the set {K:=\{k_1,...,k_N\}} has {N} elements, and so some number in {K-K} must be in {R_B}. This contradiction implies the proposition. \Box

We ask now the question of whether the set of perfect squares is a set of recurrence. The answer turns out to be yes (the first appearance of this result is, I believe, due to Furstenberg), and it can be deduced from Sárközy’s theorem mentioned in the introduction:

Theorem 8 (Sárközy) Let {A\subset {\mathbb Z}} be a set with positive upper density. Then there is some {n\in {\mathbb Z}}, n\neq0 and some {a\in A} such that {a+n^2\in A}.

We now deduce the fact that the set of perfect squares is a recurrent set using Sárközy’s theorem. This turns out to be a particular case of a more general result, which establishes a relation between recurrent sets and sets that “satisfy Sárközy’s theorem”, which we call intersective sets:

Definition 9 (Intersective Sets) A set {I} of non-zero integers is said to be an intersective set if for any {A\subset {\mathbb Z}} with positive upper density there exist some {a\in A} and {i\in I} such that {a+i\in A}.

To explain the name intersective, we note that a set {I} is intersective if and only if for any set {A} of positive density, there is some {i\in I}, {a,b\in A} such that {b-a=i}, or in other words, if {I} has non-empty intersection with {A-A=\{a_1-a_2: a_1,a_2\in A\}}.

Thus Sárközy’s theorem asserts that the set of perfect squares is an intersective set. The general result mentioned is that intersective sets are also recurrent sets:

Theorem 10 Let {I} be an intersective set. Then {I} is also a recurrent set. In particular, the set of perfect squares is a recurrent set.

Proof: Let {I} be an intersective set, {(X,{\cal B},\mu)} a probability space, {T:X\rightarrow X} a measure preserving map and {B\subset X} have positive measure. For {x\in X} denote by {x_B:=\{n\in {\mathbb Z}:T^nx\in B\}} and let {C:=\{x\in X: \overline{d}(x_B)>0\}}.

Suppose {\mu(C)>0}. Then for each {x\in C} there are {n_1>n_2\in x_B} such that {n_1-n_2\in I}. Thus {x\in T^{n_1}B\cap T^{n_2}B} and so {T^{-n_2}x\in T^{n_1-n_2}B\cap B}. For each {x\in C} choose some pair {(n_1,n_2)}. Thus we are coloring {C} with countably many colors, and so one of those colors have positive measure, say {(m_1,m_2)}. Call {D} the subset of {C} such that {T^{-m_2}x\in T^{m_1-m_2}B\cap B} for {x\in D}. Thus {D} has positive measure, and so has {T^{-m_2}D}, so {T^{m_1-m_2}B\cap B} also has positive measure. This implies that {m_1-m_2\in I\cap R_B} and thus the intersection in non-empty.

To prove that {\mu(C)>0}, define, for each {x\in X} and {n\in {\mathbb Z}^{>0}}, {f_n(x):=\frac1n|\{k\leq n:T^kx\in B\}|}. We can rewrite it as {f_n=\frac1n\sum_{k=1}^n 1_{T^{-k}B}}, which proves that these functions are measurable. Also, {\bar d(x_B)=\limsup f_n(x)} as {n\rightarrow \infty}, so, by Fatou’s lemma, {\int \bar d(x_B)d\mu(x)\geq \limsup \int f_nd\mu}. But we see easily that {\int f_nd\mu=\mu(B)} for any {n}, and so the function {\bar d(x_B)} can’t be {0} {\mu}-a.e., so the set {C} where it is positive has positive measure. \Box

I have to say that this can also be done in the other direction: a recurrent set is also an intersective set. Using this fact (which is an instance of Furstenberg’s correspondence principle, I plan to write a post about that in the near future) one can prove directly that the set of squares is a recurrent set and get for free Sárközy’s theorem. This is done in this Furstenberg’s book, which unfortunately I believe to be currently out of print.

— 3. van der Corput sets —

Recalling the definition of intersective sets (cf. Definition 9), we can now reformulate theorem 1: “For a polynomial {p\in {\mathbb Z}[x]} satisfying (1), the set {p({\mathbb Z})} is intersective”.

It turns out that with this conditions the set {p({\mathbb Z})} satisfies a stronger condition, namely that of being a van der Corput set.

Definition 11 A set {H} of positive integers is a van der Corput set if it satisfies the following property: Any sequence {\{u_n\}} taking values on {{\mathbb T}={\mathbb R}/{\mathbb Z}} such that {\{u_{n+h}-u_n\}} is equidistributed for each {h\in H} must be itself equidistributed.

Thus a set {H} is a van der Corput set if to apply the van der Corput trick (proposition 4) it suffices to check equidistribution of the discrete derivatives {u_{n+h}-u_h} for {h\in H}; proposition 4 itself says that the set of all positive integers is a van der Corput set.

The most surprising property of van der Corput sets is that they are also intersective sets (and thus also recurrent sets). It should be mentioned that an example of an intersective set which is not a van der Corput set was constructed by J. Bourgain in this paper.

Proposition 12 Let {H} be a van der Corput set. Then {H} is an intersective set.

Proof: Let {A} be a set of positive integers such that {H\cap (A-A)=\emptyset}. We want to prove that the density of {A} is {0}. Let {u_n} be a sequence in {\mathbb T} such that {u_a=0} for each {a\in A}. We also want that the sequences {\{u_{n+h}-u_n\}} be equidistributed for each {h\in H}, so we want to construct a sequence {\{u_n\}} such that for each {h\in H} and each non-zero integer {k}, the Cesàro limit

\displaystyle  \lim_{N\rightarrow \infty}\frac1N\sum_{n=0}^{N-1}e^{2\pi i k(u_{n+h}-u_n)}=0 \ \ \ \ \ (5)

We will see that indeed almost every sequence satisfies (5); we need to call the Law of Large numbers: For a fixed {h\in H} and {k\in {\mathbb Z}\setminus\{0\}}, we construct the sequence of random variables {\{X_n:{\mathbb T}^\infty\rightarrow{\mathbb C}|n\geq0\}} by {X_n(u)=e^{2\pi i k(u_{n+h}-u_n)}}, where {u=\{u_n\}\in {\mathbb T}^\infty}. Now we are in the subset (which happens to be a subgroup with a natural Haar measure) {{\mathbb T}_A:=\{u\in {\mathbb T}^\infty|\forall a\in A,\ u_a=0\}}, and we restrict the random variables to this subgroup. Since {A-h} is disjoint from {A} by hypothesis on {A}, we have that if {n\in A} then {X_n=e^{2\pi i ku_{n+h}}} and if {n\in A-h} then {X_n=e^{-2\pi i ku_n}}. In any case for {n\neq m}, the variables {X_n} and {X_m} are not correlated (they are orthogonal as elements of {L^2({\mathbb T}_A)}) and have mean {0}, so the Law of Large numbers apply and we conclude that (5) is true for almost every {u\in {\mathbb T}_A}. Since we only have countable many {h} and {k}, there must exist some sequence {u\in {\mathbb T}_A} which satisfies (5) for any {h\in H} and {k\in {\mathbb Z}\setminus{0}}.

We then conclude that {u} is itself equidistributed, and so the density of the set {\{n|u_n=0\}} must be {0}, and so in particular {\overline d(A)=0}. This implies that {H} is an intersective set. \Box

Now, in order to prove theorem 1 it suffices to show that the set {p({\mathbb Z})} is a van der Corput set, for any polynomial {p\in {\mathbb Z}[x]} satisfying (1). For this we will need a different characterization of van der Corput sets. For an integer {n} we use the notation {e_n} to denote the character {e_n:{\mathbb T}\rightarrow {\mathbb C}} defined by {e_n(x)=e^{2\pi i n x}}. We recall that for a measure {\mu} on {\mathbb T} we define its Fourier transform {\hat \mu} as being the sequence {\hat\mu(n)=\int_{\mathbb T} e_nd\mu} for {n\in {\mathbb Z}}. Also, a trigonometric polynomial in {\mathbb T} is a finite linear combination of characters, and it’s support is the set of characters which are not orthogonal to the polynomial.

Theorem 13 Let {H} be a set of non-zero integers. Then the following are equivalent:

  1. a. {H} is a van der Corput set
  2. b. Any measure {\mu} on {\mathbb T} whose Fourier transform {\hat \mu} vanishes on {H} (i.e. {\hat\mu(h)=0} for any {h\in H}) has no atom at {0} (meaning that {\mu(\{0\})=0}).
  3. c. For each {\epsilon>0} there is a real valued trigonometric polynomial {P} supported on {H\cup(-H)} and such that {P(0)=1} and {P(x)>-\epsilon} for all {x\in {\mathbb T}}.

Implications c{\Rightarrow}b{\Rightarrow}a were proved in the same paper where van der Corput sets were first defined, this is the paper by Kamae and Mendes France mentioned in the introduction. The implication a{\Rightarrow}c was proved later by Ruzsa. For our purposes we need to get the van der Corput property with a slightly weaker condition than condition c.

Proposition 14 Let {H} be a set of non-zero integers satisfying the following:

  1. c’.There is a sequence {\{P_n\}} of real valued trigonometric polynomials supported on {H\cup(-H)} with {P_n(0)=1} and such that for each {x\in {\mathbb T}}, the limit {\displaystyle \lim_{n\rightarrow \infty}P_n(x)} exists and is non-negative.

Then {H} is a van der Corput set.

We postpone the technical proof of this proposition to the next section, we now see how we can use it to conclude the proof of theorem 1. Let {p\in {\mathbb Z}[x]} be a polynomial satisfying 1. Fix positive integers {q} and {N} and denote by {A_{q,N}} the set {A_{q,N}:=\{n\in {\mathbb Z}: q!|p(n), 1\leq n\leq N\}}. Define the sequence of functions {f_{q,N}(y):=\frac1{|A_{q,N}|}\sum_{n\in A_{q,N}}\cos(2\pi p(n)y)}. Note that each {f_{q,N}} is a real valued trigonometric polynomial, with {f_{q,N}(0)=1} and supported in {p({\mathbb Z})\cup(-p({\mathbb Z}))} (recall that {e_n(y)+e_{-n}(y)=2\cos(2\pi ny)}). Thus in order to apply proposition 14 it suffices to find a pointwise limit of some {f_{q,N}} which is positive.

We will now make use of proposition 3 (which was proved using the van der Corput trick, or in other words, the fact that the positive integers are a van der Corput set). Note that if {n\equiv m\mod k} then {p(n)\equiv p(m)\mod k} (because {k{\mathbb Z}} is an ideal of the ring {{\mathbb Z}}) and so the set {A_q:=\{n\geq1:q!|p(n)\}} is the union of some arithmetic progressions with step {q!}. Thus, for an irrational {y}, the sequence {\{p(n)y\mod 1\}_{n\in A_q}} is equidistributed in {\mathbb T}, by proposition 3.

Using Weyl’s criterion we get that both {e_1(p(n)y)} and {e_{-1}(p(n)y)} converge (in Cesàro sense, discussed in my previous post) to {0}, so their average, i.e. {\cos(p(n)y)}, must converge as well. Thus we have {\displaystyle\lim_{N\rightarrow \infty} f_{N,q}(y)=0} for any irrational {y}.

Also, since there are only countably many rational numbers we can choose a sequence {\{N_k\}} such that the function {f_{N_k,q}(y)} converges when {N\rightarrow \infty} for any {y\in {\mathbb T}}. Let {g_q} be the limit function. Furthermore let {\displaystyle j(y):=\lim_{q\rightarrow \infty} g_q(y)}. Then {j(y)=0} for any irrational {y} and if {y} is rational, then for all {q} large enough {e_1(p(n)y)=1} for any {n\in A_{q,N}}, and so {f_{N,q}(y)=1}. Thus {j(y)=1} for any rational number {y}.

We can now use proposition 14, since {j} is the pointwise limit of trigonometric polynomials with the desired conditions, and conclude that {p({\mathbb Z})} is, indeed, a van der Corput set. To finish we call the proposition 12 which assures us that {p({\mathbb Z})} is also an intersective set.

— 4. Proof of proposition 14

In this a little more technical section we prove the proposition 14. Actually we prove that the condition c’. of that proposition imply condition b. in theorem 13, and then we prove that b.{\Rightarrow}a. in that theorem.

To prove c’.{\Rightarrow}a. we need a technical lemma. We recall the notion of positive definite sequence:

Definition 15 (Positive Definite Sequence) A sequence {\{\gamma_d\}_{d\in {\mathbb Z}}} is positive definite if for any positive integer {k} and any complex numbers {c_1,...,c_k} we have

\displaystyle \sum_{i,j=1}^k\gamma_{i-j}c_i\overline{c_j}\geq0

In particular, the expression in the left must be real.

This definition is equivalent to say that all the Toeplitz matrices with {a_{0d}=\gamma_d} for {d=0,1,...} and {a_{d0}=\gamma_{-d}} for {d=0,-1,...} are positive definite matrices. Furthermore, Bochner-Herglotz theorem states that a sequence is positive definite if and only if it is the Fourier transform of a non-negative measure on {\mathbb T}.

Lemma 16 Let {\{\alpha_n\}_{n\in {\mathbb Z}}} be a bounded complex valued sequence. Then there is some increasing sequence {\{N_t\}_{t=1}^\infty} of positive integers such that the limit of the averages of the discrete derivatives over that sequence exist:

\displaystyle \lim_{t\rightarrow \infty}\frac1{N_t}\sum_{n=1}^{N_t}\alpha_n\overline{\alpha_{n+d}}=\gamma(d)\qquad\forall d\in {\mathbb Z}

Furthermore, the sequence {\gamma(d)} thus defined is positive definite.

Proof: The existence of the sequence {\{N_t\}} is achieved by the usual trick of the diagonal argument. To prove that {\gamma} is a positive definite sequence, let {c_1,...,c_k} be complex numbers. Then

\begin{array}{rcl}  \displaystyle\sum_{i,j=1}^k\gamma_{i-j}c_i\overline{c_j}&=&\displaystyle\sum_{i,j=1}^k\lim_{t\rightarrow \infty}\frac1{N_t}\sum_{n=1}^{N_t}\alpha_n\overline{\alpha_{n+i-j}}c_i\overline{c_j}\\ &=&\displaystyle\sum_{i,j=1}^k\lim_{t\rightarrow \infty}\frac1{N_t}\sum_{n=1+i}^{N_t+i}\alpha_{n-i}\overline{\alpha_{n-j}}c_i\overline{c_j}\\ &=&\displaystyle\sum_{i,j=1}^k\lim_{t\rightarrow \infty}\frac1{N_t}\sum_{n=1}^{N_t}\alpha_{n-i}c_i\overline{\alpha_{n-j}c_j}\\ &=&\displaystyle\lim_{t\rightarrow \infty}\frac1{N_t}\sum_{n=1}^{N_t}\sum_{i,j=1}^k\alpha_{n-i}c_i\overline{\alpha_{n-j}c_j}\\ &=&\displaystyle\lim_{t\rightarrow \infty}\frac1{N_t}\sum_{n=1}^{N_t}\left|\sum_{i=1}^k\alpha_{n-i}c_i\right|^2\\ &\geq&0 \end{array}

We now prove the proposition 14. Let {H} be a set of positive integers satisfying condition c’. Let {\{u_n\}} be a sequence in {\mathbb T} such that the discrete derivatives {\{u_{n+h}-u_n\}} are equidistributed for each {h\in H}. We will use Weyl’s criterion to prove equidistribution of {\{u_n\}}, so we want to prove that {e_k(u_n)} converges to {0} as {n\rightarrow \infty} in the Cesàro sense for any non-zero integer {k}.

Fix an arbitrary {k\in {\mathbb Z}\setminus \{0\}}. Define {\alpha_n:=e_k(u_n)} for positive {n} and {\alpha_n=0} otherwise. Now let {C=\displaystyle\lim_{N\rightarrow \infty}\frac1N\sum_{n=1}^N\alpha_n} (and thus we want to prove that {C=0}) and define {\beta_n:=\alpha_n-C}. Apply lemma 16 with {\{\alpha_n\}}, let {\{\gamma_n\}} be the corresponding positive definite sequence and let {\mu} be the non-negative measure on {\mathbb T} with {\{\gamma\}} as its Fourier transform (the existence of {\mu} is guaranteed by Bochner-Herglotz theorem). Then apply again lemma 16 for {\{\beta_n\}}, let {\{\gamma'_n\}} be the positive sequence and let {\nu} be the non-negative measure on {\mathbb T} with {\{\gamma'\}} as its Fourier transform.

Notice that the Cesàro limit of {\{\beta_n\}} is {0}, and also

\displaystyle \alpha_n\overline{\alpha_{n+h}}=\beta_n\overline{\beta_{n+h}}+C\overline{\beta_{n+h}}+ \overline{C}\beta_n+|C|^2

so we get that {\gamma_n=\gamma'_n+|C|^2}. Since the measure with constant Fourier transform equal to {1} is the atomic measure at {0}, denoted by {\delta_0}, we then have {\mu=|C|^2\delta_0+\nu}, so in particular, {\mu(\{0\})=|C|^2+\nu(\{0\})\geq |C|^2}. Thus if we can prove that {\mu(\{0\})=0}, we conclude that {C=0} as desired.

On the other hand, by construction we have for each {h\in H}

\displaystyle  \begin{array}{rcl}  \hat\mu(h)&=&\gamma(h)=\lim_{t\rightarrow \infty}\frac1{N_t}\sum_{n=1}^{N_t}\alpha_n\overline{\alpha_{n+h}}\\ &=&\lim_{t\rightarrow \infty}\frac1{N_t}\sum_{n=1}^{N_t}e_k(u_n-u_{n+h})=0 \end{array}

because by hypothesis, the sequence {u_n-u_{n+h}} is equidistributed. Also, since {\mu} is a real valued measure, {\hat\mu(-n)=\overline{\hat\mu(n)}} and so {\hat\mu} also vanishes for {n\in -H}. Let {\{P_n\}} be the sequence of trigonometric polynomials given by condition c’ and let {P} be the pointwise limit of that sequence. Since {P(0)=1} and {P} is non-negative, we have {\int_{\mathbb T} P(x)d\mu(x)\geq\mu\{0\}\geq |C|^2}. On the other hand, since {P_n} and {\mu} have disjoint spectrum, the integral {\int_{\mathbb T} P_n(x)d\mu(x)=0}, and by the dominated convergence theorem, also {\int_{\mathbb T} P(x)d\mu(x)=0}. This proves that {C=0} and since {k} was arbitrary this implies that {u_n} is equidistributed and thus {H} is a van der Corput set.

This entry was posted in Classic results, Ergodic Theory. Bookmark the permalink.

9 Responses to Equidistribution of polynomials, recurrence and van der Corput trick

  1. Pingback: Furstenberg’s Correspondence Theorem | YAMB

  2. Pingback: YAMB

  3. Pingback: Recurrence theorems | YAMB

  4. Pingback: Proof of Roth’s Theorem using Ergodic Theory | YAMB

  5. Pingback: Weak Mixing | YAMB

  6. Pingback: Sets of nice recurrence | YAMB

  7. Pingback: YAMB

  8. Pingback: Applications of the coloring trick | I Can't Believe It's Not Random!

  9. Pingback: A viewpoint on Katai’s orthogonality criterion | I Can't Believe It's Not Random!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s