This week I was in Columbus, Ohio, attending a conference on equidistribution on manifolds. I talked about my recent paper with Ben Green on the quantitative behaviour of polynomial sequences in nilmanifolds, which I have blogged about previously. During my talk (and inspired by the immediately preceding talk of Vitaly Bergelson), I stated explicitly for the first time a generalisation of the van der Corput trick which morally underlies our paper, though it is somewhat buried there as we specialised it to our application at hand (and also had to deal with various quantitative issues that made the presentation more complicated). After the talk, several people asked me for a more precise statement of this trick, so I am presenting it here, and as an application reproving an old theorem of Leon Green that gives a necessary and sufficient condition as to whether a linear sequence on a nilmanifold
is equidistributed, which generalises the famous theorem of Weyl on equidistribution of polynomials.
UPDATE, Feb 2013: It has been pointed out to me by Pavel Zorin that this argument does not fully recover the theorem of Leon Green; to cover all cases, one needs the more complicated van der Corput argument in our paper.
— The classical van der Corput trick —
The classical van der Corput trick (first used implicitly by Weyl) gives a means to establish the equidistribution of a sequence in a torus
(e.g. a sequence
in the unit circle
for some function P, such as a polynomial.) Recall that such a sequence is said to be equidistributed if one has
(1)
as for every continuous function
; an equivalent formulation of equidistribution is that
for every box B in the torus . (The equivalence can be deduced easily from Urysohn’s lemma.) Equidistribution is an important phenomenon to study in ergodic theory and number theory, but also arises in applications such as Monte Carlo integration and pseudorandom number generation.
The fundamental equidistribution theorem of Weyl states that a sequence is equidistributed if and only if the exponential sums
(2)
converge to zero for every non-trivial character , i.e. a non-zero continuous homomorphism to the unit cicle. Indeed, it is clear that (2) is a special case of (1), and conversely the general case of (1) can be deduced from (2) and either the Weierstrass approximation theorem or basic Fourier analysis.
The significance of the equidistribution theorem is that it reduces the study of equidistribution to the question of estimating exponential sums, which is a problem in analysis and number theory. For instance, from the equidistribution theorem and the geometric series formula we immediately obtain the following result (stronger than Kronecker’s approximation theorem):
Corollary 1. (Equidistribution of linear sequences in torii) Let
. Then the sequence
is equidistributed in
if and only if
is totally irrational, which means that
for all non-zero characters
.
For instance, the linear sequence is equidistributed in the two-torus
, since
is totally irrational, but the linear sequence
is not (the character
annihilates
and thus obstructs equidistribution). [Of course, in the latter case, the orbit is still equidistributed in a smaller torus, namely the kernel of the character
mentioned above; this is an extremely simple case of a much more general result known as Ratner’s theorem, which I will not talk further about here.]
One elementary but very useful tool for estimating exponential sums is Weyl’s differencing trick, that ultimately rests on the humble Cauchy-Schwarz inequality. One formulation of this trick can be phrased as the following inequality:
Lemma 1. (van der Corput inequality) Let
be a sequence of complex numbers bounded in magnitude by 1. Then for any
we have
. (3)
Proof. Observe that
for every . Averaging this in h we obtain
and hence by the Cauchy-Schwarz inequality
Expanding out the square and rearranging a bit, we soon obtain the upper bound (3) (in fact one can sharpen the constants slightly here, though this will not be important for this discussion).
The significance of this inequality is that it replaces the task of bounding a sum of coefficients by that of bounding a sum of “differentiated” coefficients
. This trick is thus useful in “polynomial” type situations when the differentiated coefficients are often simpler than the original coefficients. One particularly clean application of this inequality is as follows:
Corollary 2. (Van der Corput’s difference theorem) Let
be a sequence in a torus
such that the difference sequences
are equidistributed for every non-zero h. Then
is itself equidistributed.
Proof. By Weyl’s equidistribution theorem, it suffices to show that (2) holds for every non-trivial character . But by Lemma 1, we can bound the magnitude of the left-hand side of (2) by
(4)
for any fixed H.
Now we use the fact that is a character to simplify
as
. By hypothesis and the equidistribution theorem, the inner sum
goes to zero as
for any fixed non-zero h; when instead h is zero, this sum is of course just 1. We conclude that for fixed H, the expression (4) is bounded by O(1/H) in the limit
. Thus the limit (or limit superior) of the magnitude of (2) is bounded in magnitude by O(1/H) for every H, and is thus zero. The claim follows.
By iterating this theorem, and using the observation that the difference sequence of a polynomial sequence
of degree d becomes a polynomial sequence of degree d-1 for any non-zero h, we can conclude by induction the following famous result of Weyl, generalising Corollary 1:
Theorem 1. (Equidistribution of polynomial sequences in torii) Let
be a polynomial sequence taking values in a torus. Then the sequence
is equidistributed in
if and only if
is non-constant for all non-zero characters
.
In the one-dimensional case d=1, this theorem asserts that a polynomial with real coefficients is equidistributed modulo one if and only if it has at least one irrational non-constant coefficient; thus for instance the sequence
is equidistributed.
— A variant of the trick —
It turns out that van der Corput’s difference theorem (Corollary 2) can be generalised to deal not just on torii, but on more general measure spaces with a torus action. Given a topological probability space (which one should probably take to be a Polish space to avoid various technicalities) and a sequence
in X, we say that such a sequence is equidistributed with respect to
if we have
(5)
for all continuous compactly supported functions . This clearly generalises the previous notion of equidistribution, in which X was a torus and
was uniform probability measure.
To motivate our generalised version of Corollary 2, we observe that the hypothesis “the sequence is equidistributed in
” can be phrased in a more dynamical fashion (eliminating the subtraction operation, which is algebraic) as the equivalent assertion that the sequence of pairs
in
, after quotienting out by the action of the diagonal subgroup
, becomes equidistributed on the quotient space
. This convoluted reformulation is necessary for generalisations, in which we do not have a good notion of subtraction, but we still have a good notion of group action and quotient spaces.
We can now prove
Proposition 1. (Generalised van der Corput difference theorem) Let
be a (Polish) probability space with a continuous (right-)action of a torus
, and let
be the projection map onto the quotient space (which then has the pushforward measure
. Let
be a sequence in X obeying the following properties:
- (Horizontal equidistribution) The projected sequence
in
is equidistributed with respect to
.
- (Vertical differenced equidistribution) For every non-zero h, the sequence
in the quotiented product space
is equidistributed with respect to some measure
which is invariant under the action of the torus
.
Then
is equidistributed with respect to
.
Note that Corollary 2 is the special case of Proposition 1 in which X is itself the torus with the usual translation action and uniform measure (so that the quotient space is a point).
Proof. We need to verify the property (1). If the function f was invariant under the action of the torus , then we could push it down to the quotient space
and the claim would follow from hypothesis 1. We may therefore subtract off the invariant component
from our function and assume instead that f has zero vertical mean in the sense that
for all x. A Fourier expansion in the vertical variable (or the Weierstrass approximation theorem) then allows us to reduce to the case when f has a vertical frequency given by some non-zero character
of the torus, in the sense that
for all
and
.
Now we apply van der Corput’s inequality as in the proof of Corollary 2. Using these arguments, we find that it suffices to show that
for each non-zero h. But the summand here is just the tensor product function applied to the pair
. The fact that f has a vertical frequency implies that
is invariant with respect to the diagonal action
, and thus this function descends to the quotient space
. On the other hand, as the vertical frequency is non-trivial, the latter function also has zero mean on every orbit of
and thus vanishes when integrated against
. The claim then follows from hypothesis 2.
As an application, let us prove the following result, first established by (Leon) Green:
Theorem 2. (Equidistribution of linear sequences in nilmanifolds) Let
be a nilmanifold (where we take the nilpotent group G to be connected for simplicity, although this is not strictly necessary), and let
and
. Then
is equidistributed with respect to Haar measure on
if and only if
is non-constant in n for every non-trivial horizontal character
, where a horizontal character is any continuous homomorphism
that vanishes on
(and thus descends to
).
This statement happens to contain Weyl’s result (Theorem 1) as a special case, because polynomial sequences can be encoded as linear sequences in nilmanifolds; but it is actually stronger, allowing extensions to generalised polynomials that involve the floor function or the fractional part function
. For instance, if we take
and
for some real numbers then a computation shows that
and then Green’s theorem asserts that the triple
is equidistributed in the unit cube if and only if the pair
is totally irrational (the rationality of
turns out to be irrelevant). Even for concrete values such as
, it is not obvious how to establish this fact directly; for instance a direct application of Corollary 2 does not obviously simplify the situation.
Proof of Theorem 2. (Sketch) It is clear that if is constant for some non-trivial character, then the orbit
is trapped on a level set of
and thus cannot equidistribute. Conversely, suppose that
is never constant. We induct on the step s of the nilmanifold. The case s=0 is trivial, and the case s=1 follows from Corollary 1, so suppose inductively that
and that the claim has already been proven for smaller s. We then look at the vertical torus
, where
is the last non-trivial group in the lower central series (and thus central). The quotient of the nilmanifold
by this torus action turns out to be a nilmanifold of one lower step (in which G is replaced by
) and so the projection of the orbit
is then equidistributed by induction hypothesis. Applying Proposition 1, it thus suffices to check that for each non-zero h, the sequence of pairs
in
, after quotienting out by the diagonal action of the torus, is equidistributed with respect to some measure which is invariant under the residual torus
.
We first pass to the abelianisation (or horizontal torus) of the nilmanifold, and observe that the projections
of the coefficients of the pair
to this torus only differ by a constant
. Thus the pair
does not range freely in
, but is instead constrained to a translate of a smaller nilmanifold
, defined as the space of pairs (x,y) with
. After quotienting out also by the diagonal vertical torus, we obtain a nilmanifold coming from the group
, where
is the space of pairs
of group elements
whose projections to the abelianisation
agree, and
is the vertical diagonal group. But a short computation shows that this new group is at most s-1 step nilpotent. One can then apply the induction hypothesis to show the required equidistribution properties of
, thus closing the induction by Proposition 1. [UPDATE, Feb 2013: This doesn’t work in all cases, because sometimes the orbit
is not equidistributed in the abelianisation of this nilmanifold.]
There are many further generalisations of these results, including a polynomial version of Theorem 2 due to Leibman (that also permits G to be disconnected), and quantitative versions of all of these results in my paper with Ben Green that I discuss in my earlier blog post.
24 comments
Comments feed for this article
16 June, 2008 at 10:07 am
A
It’s a nitpick, but the statement of corollary 2 isn’t parsing correctly.
16 June, 2008 at 12:13 pm
Terence Tao
Thanks for the correction!
18 November, 2008 at 12:46 pm
Marker lectures II, “Linear equations in primes” « What’s new
[…] turns out to be somewhat unpleasant; the standard technology of Weyl differencing and the van der Corput lemma eventually works (see this paper of Ben Green and myself), but does not scale well to bracket […]
25 October, 2009 at 1:02 am
ERT2: Polynomial Von Neumann’s Theorem « Disquisitiones Mathematicae
[…] true, by the induction hypothesis). This is done with the use of Van der Corput’s Trick (see this lecture of Terry Tao for a broader discussion on this trick). Theorem 3 (Van der Corput Trick) If is a bounded sequence […]
2 March, 2010 at 11:55 am
ERT9: Weak Mixing implies Weak Mixing of all orders « Disquisitiones Mathematicae
[…] van der Corput trick allows an inductive […]
24 October, 2010 at 7:30 am
Nilotpal Sinha
A remark on Corollary 1.
Reading this post reminded me of an old observation of mine of which I thought would be fit to share in this post on equidistribution.
Let u(n) be any sequence such that for every in (0,1), u(nt) ~ t u(n). If α is any real such that αu(n) and n are linearly independent then the sequence αu(n) is equidistributed mod 1.
Applications:
Eg 1. Take u(n) = n and α irrational. Then the above remark implies that the sequence αn is equidistributed mod 1. This was the original equidistribution theorem of Weyl in 1909.
Eg 2. Take u(n) = p(n) where p(n) is the n-th prime. Then our remark implies that the sequence α p(n) is equidistributed mod 1. This was the result of I.M. Vinogradov, 1935.
Taking advantage of the liner independence condition in the remark, we have have similar results for rational numbers too.
Eg 3. Taking α = 1 and u(n) ~ 2Πn/log(n) we see that the imaginary parts of the non-trivial zeta zeros are equidistributed mod 1. This was the result of Hlawka.
In short the remark looks very powerful and if applied in the right places, it can yield many interesting results.
25 October, 2012 at 10:11 am
Walsh’s ergodic theorem, metastability, and external Cauchy convergence « What’s new
[…] for . (We will see why these particular functions arise in the argument shortly.) The key step in proving Theorem 8 is then the following result, reminiscent of the van der Corput lemma in ergodic theory (see e.g. this blog post). […]
4 October, 2013 at 4:02 am
Sean Eberhard
Dear Prof Tao,
I’m trying to understand the proof of Theorem 2, whether the sketch you give here or a proof in the literature somewhere. I thought I understood the proof until I read your update from Feb 2013. It suffices to check that
equidistributes in the nilmanifold coming from
: it would then follow that
is equidistributed in a translate of this nilmanifold. Since this nilmanifold has step
, if this fails it follows by induction that there is a nontrivial horizontal character
of
such that
is constant. But then by precomposing with the diagonal embedding
we get a nontrivial character
of
such that
is constant, contradicting our hypothesis. Doesn’t this work?
4 October, 2013 at 8:08 am
Terence Tao
Unfortunately, the non-triviality of
does not imply the non-triviality of
,and in any event
is clearly trapped in the diagonal
of
and so cannot equidistribute. (A similar problem was pointed out to me by Pavel Zorin in https://terrytao.wordpress.com/2010/05/29/254b-notes-6-the-inverse-conjecture-for-the-gowers-norm-ii-the-integer-case/#comment-217771 , which prompted the above correction.)
4 October, 2013 at 8:56 am
Sean Eberhard
I see. The point that was getting me is that
typically has abelianisation larger than just
. Where is the best place to find the missing details?
4 October, 2013 at 9:12 am
Terence Tao
Unfortunately I do not know of a quick way to make the strategy outlined in this blog post to work in full generality; one either has to work in a fully quantitative setting (as in my paper with Ben, http://arxiv.org/abs/0709.3562 ) or else work in an ergodic theory setting (taking full advantage of the ergodic theorem) as in the original paper of Leibman, http://www.ams.org/mathscinet-getitem?mr=2122919 .
1 July, 2014 at 3:52 am
Cyril
Hello. I am a beginner in the theory you are dealing with. However I think there is a link with an old problem I have for a long time:
Is the sequence
bounded ?
1 July, 2014 at 4:22 pm
Terence Tao
No, it is unbounded. If it were bounded, then the sequence
would be bounded uniformly in
, but from Weyl’s theorem and the irrationality of
, the asymptotic mean of this sequence is comparable to
, a contradiction.
1 July, 2014 at 11:32 pm
Cyril
Thank you very much but I don’t really understand. Can you give me a link to the Weyl’s theorem you are talking about ?
When you say “bounded uniformly in K” you mean that it exists a constant C such that for all K, for all n, the sequence is bounded by C ?
2 July, 2014 at 12:08 pm
Terence Tao
Yes.
Weyl’s theorem can be found for instance in Corollary 6 of my notes https://terrytao.wordpress.com/2010/03/28/254b-notes-1-equidistribution-of-polynomial-sequences-in-torii/ . The point is that when one expands out the square in the indicated sequence in terms of complex exponentials, one gets terms such as
for various
. For
, the phase here contains an irrational nonconstant coefficient and so has asymptotic mean zero in n. If one worked with
instead of
then
would instead be constant in
and Weyl’s theorem would not apply.
2 July, 2014 at 12:23 pm
Cyril
Ouawww I got it !!!! Thank you very much ! I love this trick.
2 July, 2014 at 2:47 pm
Eytan Paldi
Thanks! I expected this question to be much more difficult – because it seems related to the complicated behavior of the (theta) function
near the irrational point
on the unit circle – its natural boundary!
The function
(defined e.g. in page 36, Entry 22(i) in Berndt's book "Ramanujan Notebooks" Part III, 1991)
From the proof of Entry 23(i) (page 38 in this book) it follows that
Where
is the generating function for the partition function
.
Therefore,
behavior near the unit circle may be studied via the well known complicated behavior of
there (in particular, it follows that
has the unit circle as its natural boundary!)
2 July, 2014 at 8:51 am
Eytan Paldi
It is not clear why this argument is working for
but not for
.
2 July, 2014 at 9:31 am
Cyril
That’s why I’m asking the reference of the theorem.
3 July, 2014 at 4:14 am
Anonymous
In your paper, I think there is a typo in line 2 in the introduction. Shouldn’t it be “role” rather than “rôle”? (English is not my first language.)
3 July, 2014 at 6:07 am
Anonymous
I see that I’m wrong. (Please delete this and the previous comment.)
24 September, 2015 at 8:47 am
Frogs and Lily Pads and Discrepancy | Gödel's Lost Letter and P=NP
[…] The connection with products of the form is analyzed by an old trick which Tao once discussed here. There is finally an important use of Andrew Granville’s notion of pretending, which we once […]
14 September, 2017 at 12:51 pm
Anonymous
Dear Prof. Tao,
I am trying to understand the proof of Proposition 1. I got stuck in the first part of the proof, where you claim that we can assume the continuous function
has the property that
for all
and
, where
is some non-zero character of the torus. I assume this is true because functions of this kind generate an algebra that separates points and hence, by Stone-Weierstrass (like you suggested in the proof), this algebra is dense in
. However, I am stuck on proving that this family actually separates points. Can you please clarify the argument that I am missing here. Thank you very much!
14 September, 2017 at 1:53 pm
Terence Tao
If
do not lie in the same
-orbit, one can take a bump function
supported in a small neighbourhood of
and average it along the action to obtain a suitable function
to separate
. If instead
lies in the orbit of
, then the set
is a non-trivial coset
of some closed subgroup
of
. One can then locate a frequency
which annihilates
but not
(because the characters on
separate points, by Plancherel’s theorem), and then the modulated average
will work if the support of
is small enough.