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 istotally 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-trivialhorizontal 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.

## 22 comments

Comments feed for this article

16 June, 2008 at 10:07 am

AIt’s a nitpick, but the statement of corollary 2 isn’t parsing correctly.

16 June, 2008 at 12:13 pm

Terence TaoThanks 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 SinhaA 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 EberhardDear 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 TaoUnfortunately, 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 EberhardI 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 TaoUnfortunately 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

CyrilHello. 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 TaoNo, 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.

2 July, 2014 at 8:51 am

Eytan PaldiIt is not clear why this argument is working for but not for .

2 July, 2014 at 9:31 am

CyrilThat’s why I’m asking the reference of the theorem.

1 July, 2014 at 11:32 pm

CyrilThank 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 TaoYes.

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 2:47 pm

Eytan PaldiThanks! 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 12:23 pm

CyrilOuawww I got it !!!! Thank you very much ! I love this trick.

3 July, 2014 at 4:14 am

AnonymousIn 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

AnonymousI 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 […]