In the early twenty century Hardy and Littlewood gave an answer to the following problem: given a polynomial with real coefficients, when do we have that the set is dense in the interval ?. Today we have a much shorter answer, the difficulty was that being dense is a property too weak to bootstrap.
In 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 , if is a map that preserves the measure and is a set of positive measure, then there is some such that .
More recently, in the late ‘s, Sárközy proved the following combinatorial result: if a subset has positive upper density (the upper density is defined by ) then there is some and such that .
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 is proved.)
Then, for any set with positive upper density there exists some integer such that and is non-empty.
Furthermore, if fails condition (1) for some , then the set is such that is empty for every . We also note that if has an integer root (i.e. if for some integer ) then automatically satisfies condition (1), however having an integer root is not necessary, as shown by the example .
— 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 we will write to denote the fractional part of , i.e. . We can also think of as being the image of under the canonical projection , where, as usual, stands for the circle group, i.e. the quotient of by the subgroup . We now prove the following:
Proposition 2 Let be a polynomial. Then the set is dense in if and only if has an irrational coefficient (or in other words if there is a coefficient of 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 . Next we note that if all coefficients are rational and is a common denominator, then the set is contained in the set and thus it is not dense.
To prove the other implication, the natural idea is to use induction on the degree of . If has degree this means that is of the form for some irrational number . By the definition of “irrational” and the pigeonhole principle we can see that is indeed dense in .
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 is not only dense but actually equidistributed in . Now we are going to prove:
Proposition 3 Let be a polynomial with real coefficients such that and has at least one irrational coefficient. Then the projection modulo of the sequence is equidistributed in the quotient . (Here, as usual, the projection modulo is the natural quotient map ).
Clearly this theorem implies theorem 2. Again we prove this by induction on the degree of . When has degree it is of the form for some irrational 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:
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 and is a polynomial of degree , then for each , the function is a polynomial of degree at most which is then equidistributed modulo . By van der Corput trick we conclude that is also equidistributed modulo .
Proof: (of proposition 4) Fix an arbitrary non-zero integer and . By Weyl criterion it suffices to prove that
The idea of the proof is to replace the average on (2) with a double average. For each , if is large enough then
On the other hand
By (3) we have that also goes to when . We do this with , and then choose large enough so that the last equation is also less than . Thus we get
— 2. Recurrence sequences —
As mentioned in the introduction, Poincaré obtained a very useful result on recurrence:
Theorem 5 (Poincaré Recurrence) Let be a probability space and an invertible measure preserving (measurable) map (i.e., for any we have ). Then for any with positive measure there exists some positive integer such that .
Proof: Let . Then the sets can’t be all disjoint, since the measure of their union is no more than and thus less than the sum of their measures. Assume that with . Then applying we get that .
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 can be bounded by . We can also require that the set has not only positive measure but has actually measure bigger than for any . Analyzing the proof deeper we see that we actually proved the following: “for any set of positive integers with size we can find in the difference set “.
Rewriting this last sentence we obtain the following: The set intersects for any with . So for instance when only has even numbers, also only has even numbers, and so we have some even . Thus the intersection is non-empty, no matter what’s the space , the map or the set ! This property of the even numbers is satisfied for many other sets, which we will call recurrent sets:
Definition 6 (Recurrent sets) A set of non-zero integers is a recurrent set if for any probability space , any invertible measure preserving map and for any with positive measure, has non-empty intersection with .
So for instance the set of all positive integers is a recurrent set, and so is the set of even numbers. One surprising feature of recurrent sets is that there are so many. This means that the sets 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 , which implies that they have always positive upper density (recall that we define the upper density of a set of positive integers by ).
Actually satisfies a stronger property, usually called IP*, but which I will not develop in this post.
Proof: Suppose otherwise. Then for each there is some such that is disjoint from . Then let be some integer not in and for each let . Then for any we have and so is not in . However, the set has elements, and so some number in must be in . This contradiction implies the proposition.
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:
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:
To explain the name intersective, we note that a set is intersective if and only if for any set of positive density, there is some , such that , or in other words, if has non-empty intersection with .
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 be an intersective set. Then is also a recurrent set. In particular, the set of perfect squares is a recurrent set.
Proof: Let be an intersective set, a probability space, a measure preserving map and have positive measure. For denote by and let .
Suppose . Then for each there are such that . Thus and so . For each choose some pair . Thus we are coloring with countably many colors, and so one of those colors have positive measure, say . Call the subset of such that for . Thus has positive measure, and so has , so also has positive measure. This implies that and thus the intersection in non-empty.
To prove that , define, for each and , . We can rewrite it as , which proves that these functions are measurable. Also, as , so, by Fatou’s lemma, . But we see easily that for any , and so the function can’t be -a.e., so the set where it is positive has positive measure.
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 —
It turns out that with this conditions the set satisfies a stronger condition, namely that of being a van der Corput set.
Definition 11 A set of positive integers is a van der Corput set if it satisfies the following property: Any sequence taking values on such that is equidistributed for each must be itself equidistributed.
Thus a set 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 for ; 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.
Proof: Let be a set of positive integers such that . We want to prove that the density of is . Let be a sequence in such that for each . We also want that the sequences be equidistributed for each , so we want to construct a sequence such that for each and each non-zero integer , the Cesàro limit
We will see that indeed almost every sequence satisfies (5); we need to call the Law of Large numbers: For a fixed and , we construct the sequence of random variables by , where . Now we are in the subset (which happens to be a subgroup with a natural Haar measure) , and we restrict the random variables to this subgroup. Since is disjoint from by hypothesis on , we have that if then and if then . In any case for , the variables and are not correlated (they are orthogonal as elements of ) and have mean , so the Law of Large numbers apply and we conclude that (5) is true for almost every . Since we only have countable many and , there must exist some sequence which satisfies (5) for any and .
We then conclude that is itself equidistributed, and so the density of the set must be , and so in particular . This implies that is an intersective set.
Now, in order to prove theorem 1 it suffices to show that the set is a van der Corput set, for any polynomial satisfying (1). For this we will need a different characterization of van der Corput sets. For an integer we use the notation to denote the character defined by . We recall that for a measure on we define its Fourier transform as being the sequence for . Also, a trigonometric polynomial in is a finite linear combination of characters, and it’s support is the set of characters which are not orthogonal to the polynomial.
- a. is a van der Corput set
- b. Any measure on whose Fourier transform vanishes on (i.e. for any ) has no atom at (meaning that ).
- c. For each there is a real valued trigonometric polynomial supported on and such that and for all .
Implications cba 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 ac 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.
- c’.There is a sequence of real valued trigonometric polynomials supported on with and such that for each , the limit exists and is non-negative.
Then 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 be a polynomial satisfying 1. Fix positive integers and and denote by the set . Define the sequence of functions . Note that each is a real valued trigonometric polynomial, with and supported in (recall that ). Thus in order to apply proposition 14 it suffices to find a pointwise limit of some 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 then (because is an ideal of the ring ) and so the set is the union of some arithmetic progressions with step . Thus, for an irrational , the sequence is equidistributed in , by proposition 3.
Also, since there are only countably many rational numbers we can choose a sequence such that the function converges when for any . Let be the limit function. Furthermore let . Then for any irrational and if is rational, then for all large enough for any , and so . Thus for any rational number .
We can now use proposition 14, since is the pointwise limit of trigonometric polynomials with the desired conditions, and conclude that is, indeed, a van der Corput set. To finish we call the proposition 12 which assures us that 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.a. in that theorem.
To prove c’.a. we need a technical lemma. We recall the notion of positive definite sequence:
Definition 15 (Positive Definite Sequence) A sequence is positive definite if for any positive integer and any complex numbers we have
In particular, the expression in the left must be real.
This definition is equivalent to say that all the Toeplitz matrices with for and for 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 .
Lemma 16 Let be a bounded complex valued sequence. Then there is some increasing sequence of positive integers such that the limit of the averages of the discrete derivatives over that sequence exist:
Furthermore, the sequence thus defined is positive definite.
Proof: The existence of the sequence is achieved by the usual trick of the diagonal argument. To prove that is a positive definite sequence, let be complex numbers. Then
We now prove the proposition 14. Let be a set of positive integers satisfying condition c’. Let be a sequence in such that the discrete derivatives are equidistributed for each . We will use Weyl’s criterion to prove equidistribution of , so we want to prove that converges to as in the Cesàro sense for any non-zero integer .
Fix an arbitrary . Define for positive and otherwise. Now let (and thus we want to prove that ) and define . Apply lemma 16 with , let be the corresponding positive definite sequence and let be the non-negative measure on with as its Fourier transform (the existence of is guaranteed by Bochner-Herglotz theorem). Then apply again lemma 16 for , let be the positive sequence and let be the non-negative measure on with as its Fourier transform.
Notice that the Cesàro limit of is , and also
so we get that . Since the measure with constant Fourier transform equal to is the atomic measure at , denoted by , we then have , so in particular, . Thus if we can prove that , we conclude that as desired.
On the other hand, by construction we have for each
because by hypothesis, the sequence is equidistributed. Also, since is a real valued measure, and so also vanishes for . Let be the sequence of trigonometric polynomials given by condition c’ and let be the pointwise limit of that sequence. Since and is non-negative, we have . On the other hand, since and have disjoint spectrum, the integral , and by the dominated convergence theorem, also . This proves that and since was arbitrary this implies that is equidistributed and thus is a van der Corput set.