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 (g^n x)_{n=1}^\infty on a nilmanifold G/\Gamma 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 (x_n)_{n = 1}^\infty in a torus {\Bbb T}^d (e.g. a sequence (P(n) \hbox{ mod } 1)_{n=1}^\infty in the unit circle {\Bbb T} = {\Bbb R}/{\Bbb Z} for some function P, such as a polynomial.) Recall that such a sequence is said to be equidistributed if one has

\displaystyle \frac{1}{N} \sum_{n=1}^N f(x_n) \to \int_{{\Bbb T}^d} f (1)

as N \to \infty for every continuous function f: {\Bbb T}^d \to {\Bbb C}; an equivalent formulation of equidistribution is that

\displaystyle \frac{1}{N} | \{ 1 \leq n \leq N: x_n \in B \} | \to \hbox{vol}(B)

for every box B in the torus {\Bbb T}^d. (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

\displaystyle \frac{1}{N} \sum_{n=1}^N e^{2\pi i \chi(x_n)} (2)

converge to zero for every non-trivial character \chi: {\Bbb T}^d \to {\Bbb T}, 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 \alpha \in {\Bbb T}^d. Then the sequence (\alpha n)_{n =1}^\infty is equidistributed in {\Bbb T}^d if and only if \alpha is totally irrational, which means that \chi(\alpha) \neq 0 for all non-zero characters \chi.

For instance, the linear sequence (\sqrt{2} n \hbox{ mod } 1, \sqrt{3} n \hbox{ mod } 1) is equidistributed in the two-torus {\Bbb T}^2, since (\sqrt{2}, \sqrt{3}) is totally irrational, but the linear sequence (\sqrt{2} n \hbox{ mod } 1, \sqrt{8} n \hbox{ mod } 1) is not (the character \chi: (x,y) \mapsto y-2x annihilates (\sqrt{2}, \sqrt{8}) 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 \chi 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 a_1,a_2,\ldots be a sequence of complex numbers bounded in magnitude by 1. Then for any 1 \leq H \leq N we have

\displaystyle |\frac{1}{N} \sum_{n=1}^N a_n | \ll (\frac{1}{H} \sum_{h=0}^{H -1}|\frac{1}{N} \sum_{n=1}^N a_{n+h} \overline{a_n}| )^{1/2} + O( \frac{H}{N} ). (3)

Proof. Observe that

\displaystyle \frac{1}{N} \sum_{n=1}^N a_n = \frac{1}{N} \sum_{n=1}^N a_{n+h} + O( \frac{H}{N})

for every 0 \leq h \leq H-1. Averaging this in h we obtain

\displaystyle \frac{1}{N} \sum_{n=1}^N a_n = \frac{1}{N} \sum_{n=1}^N \frac{1}{H} \sum_{h=0}^{H-1} a_{n+h} + O( \frac{H}{N})

and hence by the Cauchy-Schwarz inequality

\displaystyle |\frac{1}{N} \sum_{n=1}^N a_n| \leq (\frac{1}{N} \sum_{n=1}^N |\frac{1}{H} \sum_{h=0}^{H-1} a_{n+h}|^2)^{1/2} + O( \frac{H}{N}).

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). \Box

The significance of this inequality is that it replaces the task of bounding a sum of coefficients a_n by that of bounding a sum of “differentiated” coefficients a_{n+h} \overline{a_n}. 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 (x_n)_{n=1}^\infty be a sequence in a torus {\Bbb T}^d such that the difference sequences (x_{n+h}-x_n)_{n=1}^\infty are equidistributed for every non-zero h. Then (x_n)_{n=1}^\infty is itself equidistributed.

Proof. By Weyl’s equidistribution theorem, it suffices to show that (2) holds for every non-trivial character \chi. But by Lemma 1, we can bound the magnitude of the left-hand side of (2) by

\displaystyle \ll (\frac{1}{H} \sum_{h=0}^{H -1}|\frac{1}{N} \sum_{n=1}^N e^{2\pi i \chi(x_{n+h})} e^{-2\pi i \chi(x_n)}| )^{1/2} + O( \frac{H}{N} ) (4)

for any fixed H.

Now we use the fact that \chi is a character to simplify e^{2\pi i \chi(x_{n+h})} e^{-2\pi i \chi(x_n)} as e^{2\pi i \chi(x_{n+h}-x_n)}. By hypothesis and the equidistribution theorem, the inner sum \frac{1}{N} \sum_{n=1}^N e^{2\pi i \chi(x_{n+h})} e^{-2\pi i \chi(x_n)} goes to zero as N \to \infty 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 N \to \infty. 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. \Box

By iterating this theorem, and using the observation that the difference sequence (P(n+h) - P(n))_{n=1}^\infty of a polynomial sequence (P(n))_{n=1}^\infty 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 P: {\Bbb Z} \to {\Bbb T}^d be a polynomial sequence taking values in a torus. Then the sequence (P(n))_{n =1}^\infty is equidistributed in {\Bbb T}^d if and only if \chi(P(\cdot)) is non-constant for all non-zero characters \chi.

In the one-dimensional case d=1, this theorem asserts that a polynomial P: {\Bbb Z} \to {\Bbb R} 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 (\pi n^3 + \sqrt{2} n^2 + \frac{1}{4} n \hbox{ mod } 1)_{n=1}^\infty 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 (X,\mu) (which one should probably take to be a Polish space to avoid various technicalities) and a sequence (x_n)_{n = 1}^\infty in X, we say that such a sequence is equidistributed with respect to \mu if we have

\displaystyle \frac{1}{N} \sum_{n=1}^N f(x_n) \to \int_X f\ d\mu (5)

for all continuous compactly supported functions f: X \to {\Bbb C}. This clearly generalises the previous notion of equidistribution, in which X was a torus and \mu was uniform probability measure.

To motivate our generalised version of Corollary 2, we observe that the hypothesis “the sequence (x_{n+h}-x_n)_{n=1}^\infty is equidistributed in {\Bbb T}^d” can be phrased in a more dynamical fashion (eliminating the subtraction operation, which is algebraic) as the equivalent assertion that the sequence of pairs ((x_{n+h},x_n))_{n=1}^\infty in {\Bbb T}^d \times {\Bbb T}^d, after quotienting out by the action of the diagonal subgroup ({\Bbb T})^d)^\Delta := \{ (y, y): y \in {\Bbb T}^d \}, becomes equidistributed on the quotient space {\Bbb T}^d \times {\Bbb T}^d / ({\Bbb T})^d)^\Delta. 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 (X,\mu) be a (Polish) probability space with a continuous (right-)action of a torus {\Bbb T}^d, and let \pi: X \to X/{\Bbb T}^d be the projection map onto the quotient space (which then has the pushforward measure \pi_* \mu. Let (x_n)_{n = 1}^\infty be a sequence in X obeying the following properties:

  1. (Horizontal equidistribution) The projected sequence (\pi(x_n))_{n =1}^\infty in X/{\Bbb T}^d is equidistributed with respect to \pi_* \mu.
  2. (Vertical differenced equidistribution) For every non-zero h, the sequence ( (x_{n+h},x_n) ({\Bbb T}^d)^\Delta )_{n=1}^\infty in the quotiented product space (X \times X)/({\Bbb T}^d)^\Delta is equidistributed with respect to some measure \nu_h which is invariant under the action of the torus {\Bbb T}^d \times {\Bbb T}^d / ({\Bbb T}^d)^\Delta.

Then (x_n)_{n=1}^\infty is equidistributed with respect to \mu.

Note that Corollary 2 is the special case of Proposition 1 in which X is itself the torus {\Bbb T}^d 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 {\Bbb T}^d, then we could push it down to the quotient space X/{\Bbb T}^d and the claim would follow from hypothesis 1. We may therefore subtract off the invariant component \int_{{\Bbb T}^d} f(\cdot y)\ dy from our function and assume instead that f has zero vertical mean in the sense that \int_{{\Bbb T}^d} f(x y)\ dy = 0 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 \chi: {\Bbb T}^d \to {\Bbb T} of the torus, in the sense that f(xy) = f(x) e^{2\pi i \chi(y)} for all x \in X and y \in {\Bbb T}^d.

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

\displaystyle \frac{1}{N} \sum_{n=1}^N f(x_{n+h}) \overline{f(x_n)} \to 0

for each non-zero h. But the summand here is just the tensor product function f \otimes \overline{f}: X \times X \to {\Bbb C} applied to the pair (x_{n+h},x_n). The fact that f has a vertical frequency implies that f \otimes \overline{f} is invariant with respect to the diagonal action ({\Bbb T}^d)^\Delta, and thus this function descends to the quotient space (X \times X)/({\Bbb T}^d)^\Delta. On the other hand, as the vertical frequency is non-trivial, the latter function also has zero mean on every orbit of {\Bbb T}^d \times {\Bbb T}^d / ({\Bbb T}^d)^\Delta and thus vanishes when integrated against \nu_h. The claim then follows from hypothesis 2. \Box

As an application, let us prove the following result, first established by (Leon) Green:

Theorem 2. (Equidistribution of linear sequences in nilmanifolds) Let G/\Gamma be a nilmanifold (where we take the nilpotent group G to be connected for simplicity, although this is not strictly necessary), and let g \in G and x \in G/\Gamma. Then (g^n x)_{n=1}^\infty is equidistributed with respect to Haar measure on G/\Gamma if and only if \chi(g^n x) is non-constant in n for every non-trivial horizontal character \chi: G/\Gamma \to {\Bbb T}, where a horizontal character is any continuous homomorphism \chi: G \to {\Bbb T} that vanishes on \Gamma (and thus descends to G/\Gamma).

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 \lfloor \cdot \rfloor or the fractional part function \{ \}. For instance, if we take

\displaystyle G := \begin{pmatrix} 1 & {\Bbb R} & {\Bbb R} \\ 0 & 1 & {\Bbb R} \\ 0 & 0 & 1 \end{pmatrix}; \Gamma := \begin{pmatrix} 1 & {\Bbb Z} & {\Bbb Z} \\ 0 & 1 & {\Bbb Z} \\ 0 & 0 & 1 \end{pmatrix}


\displaystyle g := \begin{pmatrix} 1 & \alpha & \beta \\ 0 & 1 & \gamma \\ 0 & 0 & 1 \end{pmatrix}; x = \Gamma

for some real numbers \alpha,\beta,\gamma then a computation shows that

\displaystyle g^n x = \begin{pmatrix} 1 & \{\alpha n\} & \{ \beta n + \alpha \frac{n(n-1)}{2} - \{ \alpha n \} \lfloor \gamma n \rfloor \} \\ 0 & 1 & \{ \gamma n \} \\ 0 & 0 & 1 \end{pmatrix} \Gamma

and then Green’s theorem asserts that the triple

\displaystyle ( \{ \alpha n\}, \{ \beta n + \alpha \frac{n(n-1)}{2} - \{ \alpha n \} \lfloor \gamma n \rfloor \}, \{ \gamma n \} )

is equidistributed in the unit cube {}[0,1]^3 if and only if the pair (\alpha, \gamma) is totally irrational (the rationality of \beta turns out to be irrelevant). Even for concrete values such as \alpha = \sqrt{2}, \beta = 0, \gamma = \sqrt{3}, 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 \chi(g^n x) is constant for some non-trivial character, then the orbit g^n x is trapped on a level set of \chi and thus cannot equidistribute. Conversely, suppose that \chi(g^n x) 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 s \geq 2 and that the claim has already been proven for smaller s. We then look at the vertical torus G_s / (\Gamma \cap G_s) \equiv {\Bbb T}^d, where G_s is the last non-trivial group in the lower central series (and thus central). The quotient of the nilmanifold G/\Gamma by this torus action turns out to be a nilmanifold of one lower step (in which G is replaced by G/G_s) and so the projection of the orbit (g^n x)_{n=1}^\infty is then equidistributed by induction hypothesis. Applying Proposition 1, it thus suffices to check that for each non-zero h, the sequence of pairs (g^{n+h} x, g^n x) in G/\Gamma \times G/\Gamma, after quotienting out by the diagonal action of the torus, is equidistributed with respect to some measure which is invariant under the residual torus {\Bbb T}^d \times {\Bbb T}^d / ({\Bbb T}^d)^\Delta.

We first pass to the abelianisation (or horizontal torus) G/G_2 \Gamma of the nilmanifold, and observe that the projections \pi(g^{n+h} x), \pi(g^n x) of the coefficients of the pair (g^{n+h} x, g^n x) to this torus only differ by a constant \pi(g^h). Thus the pair (g^{n+h} x, g^n x) does not range freely in G/\Gamma \times G/\Gamma, but is instead constrained to a translate of a smaller nilmanifold G/\Gamma \times_\pi G/\Gamma, defined as the space of pairs (x,y) with \pi(x)=\pi(y). After quotienting out also by the diagonal vertical torus, we obtain a nilmanifold coming from the group (G \times_{G_2} G) / G_s^\Delta, where G \times_{G_2} G is the space of pairs (g,h) of group elements g,h \in G whose projections to the abelianisation G/G_2 agree, and G_s^\Delta := \{ (g_s,g_s): g_s \in G_s \} 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 (x_{n+h},x_n), thus closing the induction by Proposition 1. [UPDATE, Feb 2013: This doesn’t work in all cases, because sometimes the orbit (g^{n+h} x, g^n x) is not equidistributed in the abelianisation of this nilmanifold.]  \Box

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.