(Linear) Fourier analysis can be viewed as a tool to study an arbitrary function on (say) the integers , by looking at how such a function correlates with *linear phases* such as , where is the fundamental character, and is a frequency. These correlations control a number of expressions relating to , such as the expected behaviour of on arithmetic progressions of length three.

In this course we will be studying higher-order correlations, such as the correlation of with quadratic phases such as , as these will control the expected behaviour of on more complex patterns, such as arithmetic progressions of length four. In order to do this, we must first understand the behaviour of exponential sums such as

Such sums are closely related to the distribution of expressions such as in the unit circle , as varies from to . More generally, one is interested in the distribution of polynomials of one or more variables taking values in a torus ; for instance, one might be interested in the distribution of the quadruplet as both vary from to . Roughly speaking, once we understand these types of distributions, then the general machinery of quadratic Fourier analysis will then allow us to understand the distribution of the quadruplet for more general classes of functions ; this can lead for instance to an understanding of the distribution of arithmetic progressions of length in the primes, if is somehow related to the primes.

More generally, to find arithmetic progressions such as in a set , it would suffice to understand the equidistribution of the quadruplet in as and vary. This is the starting point for the fundamental connection between *combinatorics* (and more specifically, the task of finding patterns inside sets) and *dynamics* (and more specifically, the theory of equidistribution and recurrence in measure-preserving dynamical systems, which is a subfield of ergodic theory). This connection was explored in one of my previous classes; it will also be important in this course (particularly as a source of motivation), but the primary focus will be on finitary, and Fourier-based, methods.

The theory of equidistribution of polynomial orbits was developed in the linear case by Dirichlet and Kronecker, and in the polynomial case by Weyl. There are two regimes of interest; the (qualitative) *asymptotic regime* in which the scale parameter is sent to infinity, and the (quantitative) *single-scale regime* in which is kept fixed (but large). Traditionally, it is the asymptotic regime which is studied, which connects the subject to other asymptotic fields of mathematics, such as dynamical systems and ergodic theory. However, for many applications (such as the study of the primes), it is the single-scale regime which is of greater importance. The two regimes are not directly equivalent, but are closely related: the single-scale theory can be usually used to derive analogous results in the asymptotic regime, and conversely the arguments in the asymptotic regime can serve as a simplified model to show the way to proceed in the single-scale regime. The analogy between the two can be made tighter by introducing the (qualitative) *ultralimit regime*, which is formally equivalent to the single-scale regime (except for the fact that explicitly quantitative bounds are abandoned in the ultralimit), but resembles the asymptotic regime quite closely.

We will view the equidistribution theory of polynomial orbits as a special case of Ratner’s theorem, which we will study in more generality later in this course.

For the finitary portion of the course, we will be using *asymptotic notation*: , , or denotes the bound for some absolute constant , and if we need to depend on additional parameters then we will indicate this by subscripts, e.g. means that for some depending only on . In the ultralimit theory we will use an analogue of asymptotic notation, which we will review later in these notes.

** ā 1. Asymptotic equidistribution theory ā **

Before we look at the single-scale equidistribution theory (both in its finitary form, and its ultralimit form), we will first study the slightly simpler, and much more classical, asymptotic equidistribution theory.

Suppose we have a sequence of points in a compact metric space . For any finite , we can define the probability measure

which is the average of the Dirac point masses on each of the points , where we use as shorthand for (with ). *Asymptotic equidistribution theory* is concerned with the limiting behaviour of these probability measures in the limit , for various sequences of interest. In particular, we say that the sequence is *asymptotically equidistributed* on with respect to a reference Borel probability measure on if the converge in the vague topology to , or in other words that

for all continuous scalar-valued functions . Note (from the Riesz representation theorem) that any sequence is asymptotically equidistributed with respect to at most one Borel probability measure .

It is also useful to have a slightly stronger notion of equidistribution: we say that a sequence is *totally asymptotically equidistributed* if it is asymptotically equidistributed on every infinite arithmetic progression, i.e. that the sequence is asymptotically equidistributed for all integers and .

A doubly infinite sequence , indexed by the integers rather than the natural numbers, is said to be asymptotically equidistributed relative to if both halves of the sequence and are asymptotically equidistributed relative to . (This omits entirely, but it is easy to see that any individual element of the sequence has no impact on the asymptotic equidistribution.) Similarly, one can define the notion of a doubly infinite sequence being totally asymptotically equidistributed relative to .

Example 1If , and whenever for some natural number and otherwise, show that the sequence is not asymptotically equidistributed with respect to any measure. Thus we see that asymptotic equidistribution requires all scales to behave “the same” in the limit.

Exercise 1If is a sequence into a compact metric space , and is a probability measure on , show that is asymptotically equidistributed with respect to if and only if one hasfor all open sets in whose boundary has measure zero. (

Hint:for the “only if” part, use Urysohn’s lemma. For the “if” part, reduce (1) to functions taking values between and , and observe that almost all of the level sets have a boundary of measure zero.) What happens if the requirement that have measure zero is omitted?

Exercise 2Let be a sequence in a compact metric space which is equidistributed relative to some probability measure . Show that for any open set in with , the set is infinite, and furthermore has positive lower density in the sense thatIn particular, if the support of is equal to , show that the set is dense in .

Exercise 3Let be a sequence into a compact metric space which is equidistributed relative to some probability measure . Let be a compactly supported, piecewise continuous function with only finitely many pieces. Show that for any one hasand for any open whose boundary has measure zero, one has

In this set of notes, will be a torus (i.e. a compact connected abelian Lie group), which from the theory of Lie groups is isomorphic to the standard torus , where is the dimension of the torus. This torus is then equipped with Haar measure, which is the unique Borel probability measure on the torus which is translation-invariant. One can identify the standard torus with the standard fundamental domain , in which case the Haar measure is equated with the usual Lebesgue measure. We shall call a sequence in (asymptotically) *equidistributed* if it is (asymptotically) equidistributed with respect to Haar measure.

We have a simple criterion for when a sequence is asymptotically equidistributed, that reduces the problem to that of estimating exponential sums:

Proposition 1 (Weyl equidistribution criterion)Let . Then is asymptotically equidistributed if and only if

for all , where . Here we use the dot product

which maps to .

*Proof:* The “only if” part is immediate from (1). For the “if” part, we see from (2) that (1) holds whenever is a plane wave for some (checking the case separately), and thus by linearity whenever is a trigonometric polynomial. But by Fourier analysis (or from the Stone-Weierstrass theorem), the trigonometric polynomials are dense in in the uniform topology. The claim now follows from a standard limiting argument.

As one consequence of this proposition, one can reduce multidimensional equidistribution to single-dimensional equidistribution:

Corollary 2Let . Then is asymptotically equidistributed in if and only if, for each , the sequence is asymptotically equidistributed in .

Exercise 4Show that a sequence is totally asymptotically equidistributed if and only if one has

This quickly gives a test for equidistribution for linear sequences, sometimes known as the equidistribution theorem:

Exercise 5Let . By using the geometric series formula, show that the following are equivalent:

- The sequence is asymptotically equidistributed on .
- The sequence is totally asymptotically equidistributed on .
- The sequence is totally asymptotically equidistributed on .
- is
irrational, in the sense that for any non-zero .

Remark 1One can view Exercise 5 as an assertion that a linear sequence will equidistribute itself unless there is an “obvious” algebraic obstruction to it doing so, such as being constant for some non-zero . This theme of algebraic obstructions being the “only” obstructions to uniform distribution will be present throughout the course.

Exercise 5 shows that linear sequences with irrational shift are equidistributed. At the other extreme, if is *rational* in the sense that for some positive integer , then the sequence is clearly periodic of period , and definitely not equidistributed.

In the one-dimensional case , these are the only two possibilities. But in higher dimensions, one can have a mixture of the two extremes, that exhibits irrational behaviour in some directions and periodic behaviour in others. Consider for instance the two-dimensional sequence . The first coordinate is totally asymptotically equidistributed in , while the second coordinate is periodic; the shift is neither irrational nor rational, but is a mixture of both. As such, we see that the two-dimensional sequence is equidistributed with respect to Haar measure on the group .

This phenomenon generalises:

Proposition 3 (Ratner’s theorem for abelian linear sequences)Let be a torus, and let for some . Then there exists a decomposition , where is totally asymptotically equidistributed on in a subtorus of (with , of course), and is periodic (or equivalently, that is rational).

*Proof:* We induct on the dimension of the torus . The claim is vacuous for , so suppose that and that the claim has already been proven for tori of smaller dimension. Without loss of generality we may identify with .

If is irrational, then we are done by Exercise 5, so we may assume that is not irrational; thus for some non-zero . We then write , where is a positive integer and is *irreducible* (i.e. is not a proper multiple of any other element of ); thus is rational. We may thus write , where is rational, and . Thus, we can split , where and . Clearly is periodic, while takes values in the subtorus of . The claim now follows by applying the induction hypothesis to (and noting that the sum of two periodic sequences is again periodic).

As a corollary of the above proposition, we see that any linear sequence in a torus is equidistributed in some union of finite cosets of a subtorus . It is easy to see that this torus is uniquely determined by , although there is a slight ambiguity in the decomposition because one can add or subtract a periodic linear sequence taking values in from and add it to (or vice versa).

Having discussed the linear case, we now consider the more general situation of *polynomial* sequences in tori. To get from the linear case to the polynomial case, the fundamental tool is

Lemma 4 (van der Corput inequality)Let be a sequence of complex numbers of magnitude at most . Then for every , we have

*Proof:* For each , we have

and hence on averaging

Applying Cauchy-Schwarz, we conclude

We expand out the left-hand side as

The diagonal contribution is . By symmetry, the off-diagonal contribution can be dominated by the contribution when . Making the change of variables , (accepting a further error of ), we obtain the claim.

Corollary 5 (van der Corput lemma)Let be such that the derivative sequence is asymptotically equidistributed on for all positive integers . Then is asymptotically equidistributed on . Similarly with replaced by .

*Proof:* We just prove the claim for , as the claim for is analogous (and can in any case be deduced from the case.)

By Proposition 1, we need to show that for each non-zero , the exponential sum

goes to zero as . Fix an . By Lemma 4, this expression is bounded by

On the other hand, for each fixed positive integer , we have from hypothesis and Proposition 1 that goes to zero as . Taking limit superior as , we conclude that

Since is arbitrary, the claim follows.

Remark 2There is another famous lemma by van der Corput concerning oscillatory integrals, but it is not directly related to the material discussed here.

Corollary 5 has the following immediate corollary:

Corollary 6 (Weyl equidistribution theorem for polynomials)Let be an integer, and let be a polynomial of degree with . If is irrational, then is asymptotically equidistributed on .

*Proof:* We induct on . For this follows from Exercise 5. Now suppose that , and that the claim has already been proven for smaller values of . For any positive integer , we observe that is a polynomial of degree in with leading coefficient . As is irrational, is irrational also, and so by the induction hypothesis, is asymptotically equidistributed. The claim now follows from Corollary 5.

Exercise 6Let be a polynomial of degree in . Show that the following are equivalent:

- is asymptotically equidistributed on .
- is totally asymptotically equidistributed on .
- is totally asymptotically equidistributed on .
- There does not exist a non-zero such that .
(

Hint:it is convenient to first use Corollary 2 to reduce to the one-dimensional case.)

This gives a polynomial variant of Ratner’s theorem:

Exercise 7 (Ratner’s theorem for abelian polynomial sequences)Let be a torus, and let be a polynomial map from to of some degree . Show that there exists a decomposition , where are polynomials of degree , is totally asymptotically equidistributed in a subtorus of on , and is periodic (or equivalently, that all non-constant coefficients of are rational).

In particular, we see that polynomial sequences in a torus are equidistributed with respect to a finite combination of Haar measures of cosets of a subtorus. Note that this finite combination can have multiplicity; for instance, when considering the polynomial map , it is not hard to see that this map is equidistributed with respect to times the Haar probability measure on , plus times the Haar probability measure on .

Exercise 7 gives a satisfactory description of the asymptotic equidistribution of arbitrary polynomial sequences in tori. We give just one example of how such a description can be useful:

Exercise 8 (Recurrence)Let be a torus, let be a polynomial map from to , and let be an integer. Show that there exists a sequence of positive integers going to infinity such that .

We discussed recurrence for one-dimensional sequences . It is also of interest to establish an analogous theory for multi-dimensional sequences, as follows.

Definition 7A multidimensional sequence isasymptotically equidistributedrelative to a probability measure if, for every continuous, compactly supported function and every function , one hasas . The sequence is

totally asymptotically equidistributedrelative to if the sequence is asymptotically equidistributed relative to for all positive integers and all .

Exercise 9Show that this definition of equidistribution on coincides with the preceding definition of equidistribution on in the one-dimensional case .

Exercise 10 (Multidimensional Weyl criterion)Let be a multidimensional sequence. Show that is asymptotically equidistributed if and only if

for all and all rectangular boxes in . Then show that is totally asymptotically equidistributed if and only if

Exercise 11Let , and let be the linear sequence . Show that the following are equivalent:

- The sequence is asymptotically equidistributed on .
- The sequence is totally asymptotically equidistributed on .
- We have for any non-zero .

Exercise 12 (Multidimensional van der Corput lemma)Let be such that the sequence is asymptotically equidistributed on for all outside of a hyperplane in . Show that is asymptotically equidistributed on .

Exercise 13Letbe a polynomial map from to of degree , where are coefficients. Show that the following are equivalent:

- is asymptotically equidistributed on .
- is totally asymptotically equidistributed on .
- There does not exist a non-zero such that for all .

Exercise 14 (Ratner’s theorem for abelian multidimensional polynomial sequences)Let be a torus, and let be a polynomial map from to of some degree . Show that there exists a decomposition , where are polynomials of degree , is totally asymptotically equidistributed in a subtorus of on , and is periodic with respect to some finite index sublattice of (or equivalently, that all non-constant coefficients of are rational).

We give just one application of this multidimensional theory, that gives a hint as to why the theory of equidistribution of polynomials may be relevant:

Exercise 15 (SzemerĆ©di’s theorem for polynomial Bohr sets)Let be a torus, let be a polynomial map from to , and let be an open ball of . Let be the set . Show that if the set has positive upper density in the sense that , then contains arbitrarily long arithmetic progressions. (Hint:consider the polynomial map from to that maps to . One can also use the one-dimensional theory by freezing and only looking at the equidistribution in .)

** ā 2. Single-scale equidistribution theory ā **

We now turn from the asymptotic equidistribution theory to the equidistribution theory at a single scale . Thus, instead of analysing the qualitative distribution of infinite sequence , we consider instead the quantitative distribution of a finite sequence , where is a (large) natural number and . To make everything quantitative, we will replace the notion of a continuous function by that of a Lipschitz function. Recall that the (inhomogeneous) Lipschitz norm of a function on a metric space is defined by the formula

We also define the homogeneous Lipschitz seminorm

Definition 8Let be a compact metric space, let , let be a probability measure on . A finite sequence is said to be-equidistributedrelative to if one has

We say that the sequence is

totally -equidistributedrelative to if one hasfor all Lipschitz functions and all arithmetic progressions in of length at least .

In these notes, we will only apply this concept to the torus with the Haar measure and the metric inherited from the Euclidean metric. However, in subsequent notes we will also consider equidistribution in other spaces, most notably on nilmanifolds.

Exercise 16Let be a sequence in a metric space , and let be a probability measure on . Show that the sequence is asymptotically equidistributed relative to if and only if, for every , is -equidistributed relative to whenever is sufficiently large depending on , or equivalently if is -equidistributed relative to for all , where as . (Hint:You will need the ArzelĆ”-Ascoli theorem.)Similarly, show that is totally asymptotically equidistributed relative to if and only if, for every , is totally -equidistributed relative to whenever is sufficiently large depending on , or equivalently if is totally -equidistributed relative to for all , where as .

Remark 3More succinctly, (total) asymptotic equidistribution of is equivalent to (total) -equidistribution of as , where denotes a quantity that goes to zero as . (Thus we see that asymptotic notation such as can efficiently conceal a surprisingly large number of quantifiers.)

Exercise 17Let be a large integer, and let be a sequence in the standard torus with Haar measure. Show that whenever is a positive multiple of , then the sequence is -equidistributed. What happens if is not a multiple of ?If furthermore , show that is -equidistributed. Why is a condition such as necessary?

Note that the above exercise does not specify the exact relationship between and when one is given an asymptotically equidistributed sequence ; this relationship is the additional piece of information provided by single-scale equidistribution that is not present in asymptotic equidistribution.

It turns out that much of the asymptotic equidistribution theory has a counterpart for single-scale equidistribution. We begin with the Weyl criterion.

Proposition 9 (Single-scale Weyl equidistribution criterion)Let be a sequence in , and let .

- If is -equidistributed, and has magnitude , then one has
if is a small enough absolute constant.

- Conversely, if is
not-equidistributed, then there exists with magnitude , such thatfor some depending on .

*Proof:* The first claim is immediate as the function has mean zero and Lipschitz constant , so we turn to the second claim. By hypothesis, (6) fails for some Lipschitz . We may subtract off the mean and assume that ; we can then normalise the Lipschitz norm to be one; thus we now have

We introduce a summation parameter , and consider the FejĆ©r partial Fourier series

where are the Fourier coefficients

and is the Fourier multiplier

Standard Fourier analysis shows that we have the convolution representation

where is the FejĆ©r kernel

Using the kernel bounds

and

where is the distance from to the nearest integer, and the Lipschitz nature of , we see that

Thus, if we choose to be a sufficiently small multiple of (depending on ), one has

and thus by the pigeonhole principle (and the trivial bound and ) we have

for some non-zero of magnitude , and the claim follows.

There is an analogue for total equidistribution:

Exercise 18Let be a sequence in , and let .

- If is totally -equidistributed, has magnitude , and is a rational of height at most , then one has
if is a small enough constant depending only on .

- Conversely, if is
nottotally -equidistributed, then there exists with magnitude , and a rational of height , such thatfor some depending on .

This gives a version of Exercise 5:

Exercise 19Let , let , and let . Suppose that the linear sequence is not totally -equidistributed. Show that there exists a non-zero with such that .

Next, we give an analogue of Corollary 5:

Exercise 20 (Single-scale van der Corput lemma)Let be a sequence which is not totally -equidistributed for some . Let for some sufficiently large depending only on . Then there exists at least integers such that the sequence is not totally -equidistributed (where we extend by zero outside of ). (Hint:apply Lemma 4.)

Just as in the asymptotic setting, we can use the van der Corput lemma to extend the linear equidistribution theory to polynomial sequences. To get satisfactory results, though, we will need an additional input, namely the following classical lemma:

Lemma 10 (Vinogradov lemma)Let , , , and . Suppose that for at least values of . Then there exists a positive integer such that .

The key point here is that one starts with many multiples of being somewhat close () to an integer, but concludes that there is a single multiple of which is *very* close (, ignoring factors of ) to an integer.

*Proof:* By the pigeonhole principle, we can find two distinct integers with such that . Setting , we thus have . We may assume that since we are done otherwise. Since , we have (say).

Now partition into arithmetic progressions for some . By the pigeonhole principle, there must exist an for which the set

has cardinality at least . On the other hand, since , we see that this set consists of intervals of length at most , punctuated by gaps of length at least (say). Since the gaps are at least times as large as the intervals, we see that if two or more these intervals appear in the set, then the cardinality of the set is at most , a contradiction. Thus at most one interval appears in the set, which implies that , and the claim follows.

Remark 4The numerical constants can of course be improved, but this is not our focus here.

Exercise 21Let be a polynomial sequence , let , and let . Suppose that the polynomial sequence is not totally -equidistributed on . Show that there exists a non-zero with such that . (Hint:Induct on starting with Exercise 19 for the base case, and then using Exercise 20 and Lemma 10 to continue the induction.)

Note the denominator; the higher-degree coefficients of a polynomial need to be *very* rational in order not to cause equidistribution.

The above exercise only controls the top degree coefficient, but we can in fact control all coefficients this way:

Lemma 11With the hypotheses of Exercise 21, we can in fact find a non-zero with such that for all .

*Proof:* We shall just establish the one-dimensional case , as the general dimensional case then follows from Exercise 18.

The case follows from Exercise 19, so assume inductively that and that the claim has already been proven for smaller values of . We allow all implied constants to depend on . From Exercise 21, we already can find a positive with such that . We now partition into arithmetic progressions of spacing and length for some sufficiently large ; then by the pigeonhole principle, we see that fails to be totally -equidistributed on one of these progressions. But on one such progression (which can be identified with ) the degree component of is essentially constant (up to errors much smaller than ) if is large enough; if one then applies the induction hypothesis to the remaining portion of on this progression, we can obtain the claim.

This gives us the following analogue of Exercise 7. We say that a subtorus of some dimension of a standard torus has *complexity* at most if there exists an invertible linear transformation with integer coefficients (which can thus be viewed as a homeomorphism of that maps to the standard torus , and such that all coefficients have magnitude at most .

Exercise 22Show that every subtorus (i.e. compact connected Lie subgroup) of has finite complexity. (Hint:Let be the Lie algebra of , then identify with a subspace of and with . Show that is a full rank sublattice of , and is thus generated by independent generators.)

Proposition 12 (Single-scale Ratner’s theorem for abelian polynomial sequences)Let be a polynomial map from to of some degree , and let be an increasing function. Then there exists an integer and a decompositioninto polynomials of degree , where

- ( is smooth) The coefficient of has size . In particular, on the interval , is Lipschitz with homogeneous norm .
- ( is equidistributed) There exists a subtorus of of complexity at most and some dimension , such that takes values in and is totally -equidistributed on in this torus (after identifying this torus with using an invertible linear transformation of complexity at most ).
- ( is rational) The coefficients of are such that for some and all . In particular, and is periodic with period .
If furthermore is of polynomial growth, and more precisely for some , then one can take .

Example 2Consider the linear flow in on . This flow can be decomposed into a smooth flow with a homogeneous Lipschitz norm of , an equidistributed flow which will be -equidistributed on the subtorus for a reasonably small (in fact one can take as small as for some small absolute constant ), and a rational flow , which is periodic with period . This example illustrates how all three components of this decomposition arise naturally in the single-scale case.

Remark 5Comparing this result with the asymptotically equidistributed analogue in Example 7, we notice several differences. Firstly, we now have the smooth component , which did not previously make an appearance (except implicitly, as the constant term in ). Secondly, the equidistribution of the component is not infinite, but is the next best thing, namely it is given by an arbitrary function of the quantity , which controls the other components of the decomposition.

*Proof:* The case is trivial, so suppose inductively that , and that the claim has already been proven for lower degrees. Then for fixed degree, the case is vacuously true, so we make a further inductive assumption and the claim has already been proven for smaller dimensions (keeping fixed).

If is already totally -equidistributed then we are done (setting and and ), so suppose that this is not the case. Applying Exercise 21, we conclude that there is some non-zero with such that

for all . We split where is irreducible and is a positive integer. We can therefore split where , for some positive integer , and . This then gives a decomposition , with taking values in the subtorus , which can be identified with after an invertible linear transformation with integer coefficients of size . If one applies the induction hypothesis to (with replaced by a suitably larger function ) one then obtains the claim.

The final claim about polynomial bounds can be verified by a closer inspection of the argument (noting that all intermediate steps are polynomially quantitative, and that the length of the induction is bounded by ).

Remark 6It is instructive to see how this smooth-equidistributed-rational decomposition evolves as increases. Roughly speaking, the torus that the component is equidistributed on is stable at most scales, but there will be a finite number of times in which a “growth spurt” occurs and jumps up in dimension. For instance, consider the linear flow on the two-dimensional torus. At scales (and with fixed, and assumed to be sufficiently large depending on ), consists entirely of the smooth component. But as increases past , the first component of no longer qualifies as smooth, and becomes equidistributed instead; thus in the range , we have and (with remaining trivial), with the torus increasing from the trivial torus to . A second transition occurs when exceeds , at which point encompasses all of . Evolving things in a somewhat different direction, if one then increases so that is much larger than , then will now entirely consist of a rational component . These sorts of dynamics are not directly seen if one only looks at the asymptotic theory, which roughly speaking is concerned with the limit after taking , andthentaking a second limit by making the growth function go to infinity.

There is a multidimensional version of Proposition 12, but we will not describe it here; see this paper of Ben Green and myself for a statement (and also see the next section for the ultralimit counterpart of this statement).

Remark 7These single-scale abelian Ratner theorems are a special case of a more general single-scalenilpotentRatner theorem, which will play an important role in later aspects of the theory, and which was the main result of the aforementioned paper of Ben Green and myself.

As an example of this theorem in action, we give a single-scale strengthening of Exercise 8 (and Exercise 15):

Exercise 23 (Recurrence)Let be a polynomial map from to of degree , and let be an integer. Show that for every and , and every integer , we have

Exercise 24 (Multiple recurrence)With the notation of Exercise 23, establish thatfor any .

Exercise 25 (Syndeticity)A set of integers issyndeticif it has bounded gaps (or equivalently, if a finite number of translates of this set can cover all of ). Let be a polynomial and let . Show that the set is syndetic. (Hint:first reduce to the case when is (totally) asymptotically equidistributed. Then, if is large enough, show (by inspection of the proof of Exercise 21) that the translates are -equidistributed on uniformly for all , for any fixed . Note how the asymptotic theory and the single-scale theory need to work together to obtain this result.)

** ā 3. Ultralimit equidistribution theory ā **

The single-scale theory was somewhat more complicated than the asymptotic theory, in part because one had to juggle parameters such as , and (for the Ratner-type theorems) as well. However, one can clean up this theory somewhat (especially if one does not wish to quantify the dependence of bounds on the equidistribution parameter ) by using an ultralimit, which causes the and parameters to disappear, at the cost of converting the finitary theory to an infinitary one. Ultralimit analysis was discussed in this previous blog post; we give a quick review here.

We first fix a non-principal ultrafilter . A property pertaining to a natural number is said to hold *for all sufficiently close to * if the set of for which holds lies in the ultrafilter . Two sequences of objects are *equivalent* if one has for all sufficiently close to , and we define the *ultralimit* to be the equivalence class of all sequences equivalent to , with the convention that is identified with its own ultralimit . Given any sequence of sets, the ultraproduct is the space of all ultralimits , where for all sufficiently close to . The ultraproduct of a single set is the *ultrapower* of and is denoted .

Ultralimits of real numbers (i.e. elements of ) will be called *limit real numbers*; similarly one defines limit natural numbers, limit complex numbers, etc. Ordinary numbers will be called *standard* numbers to distinguish them from limit numbers, thus for instance a limit real number is an ultralimit of standard real numbers. All the usual arithmetic operations and relations on standard numbers are inherited by their limit analogues; for instance, a limit real number is larger than another if one has for all sufficiently close to . The axioms of a non-principal ultrafilter ensure that these relations and operations on limit numbers obey the same axioms as their standard counterparts (the formalisation of this principle is Los’s theorem).

Ultraproducts of sets will be called *limit sets*; they are roughly analogous to “measurable sets” in measure theory. Ultraproducts of finite sets will be called *limit finite sets*. Thus, for instance, if is a limit natural number, then is a limit finite set, and can be identified with the set of limit natural numbers between and .

Given a sequence of functions , we can form the *ultralimit* by the formula

one easily verifies that this is a well-defined function between the two ultraproducts. We refer to ultralimits of functions as *limit functions*; they are roughly analogous to “measurable functions” in measurable theory. We identify every standard function with its ultralimit , which extends the original function .

Given two limit numbers , we write , , or if we have for some standard . We also write if we have for every standard ; thus for any limit numbers with , exactly one of and is true. A limit real is said to be *bounded* if it is of the form , and *infinitesimal* if it is of the form ; similarly for limit complex numbers. Note that the bounded limit reals are a subring of the limit reals, and the infinitesimal limit reals are an ideal of the bounded limit reals.

Exercise 26Show that every bounded limit real number has a unique decomposition , where is a standard real (called thestandard partof ) and is infinitesimal.

We now give the analogue of single-scale equidistribution in the ultralimit setting.

Definition 13 (Ultralimit equidistribution)Let be a standard compact metric space, let be an unbounded limit natural number, and let be a limit function. We say that isequidistributedwith respect to a (standard) Borel probability measure on if one hasfor all standard continuous functions . Here, we define the expectation of a limit function in the obvious limit manner, thus

if and .

We say that is

totally equidistributedrelative to if the sequence is equidistributed on for every standard and (extending arbitrarily outside if necessary).

Remark 8One could just as easily replace the space of continuous functions by any dense subclass in the uniform topology, such as the space of Lipschitz functions.

The ultralimit notion of equidistribution is closely related to that of both asymptotic equidistribution and single-scale equidistribution, as the following exercises indicate:

Exercise 27 (Asymptotic equidistribution vs. ultralimit equidistribution)Let be a sequence into a standard compact metric space (which can then be extended from a map from to as usual), let be a Borel probability measure on . Show that is asymptotically equidistributed on with respect to if and only if is equidistributed on for every unbounded natural number and every choice of non-principal ultrafilter .

Exercise 28 (Single-scale equidistribution vs. ultralimit equidistribution)For every , let be a natural number that goes to infinity as , let be a map to a standard compact metric space. Let be a Borel probability measure on . Write and for the ultralimits. Show that is equidistributed with respect to if and only if, for every standard , is -equidistributed with respect to for all sufficiently close to .

In view of these correspondences, it is thus not surprising that one has ultralimit analogues of the asymptotic and single-scale theory. These analogues tend to be *logically equivalent* to the single-scale counterparts (once one concedes all quantitative bounds), but are *formally similar* (though not identical) to the asymptotic counterparts, thus providing a bridge between the two theories, which we can summarise by the following three statements:

- Asymptotic theory is analogous to ultralimit theory (in particular, the statements and proofs are formally similar);
- ultralimit theory is logically equivalent to qualitative finitary theory; and
- quantitative finitary theory is a strengthening of qualitative finitary theory.

For instance, here is the ultralimit version of the Weyl criterion:

Exercise 29 (Ultralimit Weyl equidistribution criterion)Let be a limit function for some unbounded and standard . Then is equidistributed if and only if

for all standard . {

Hint:mimic the proof of Proposition 1.}

Exercise 30Use Exercise 29 to recover a weak version of Proposition 9, in which the quantities , are replaced by (ineffective) functions of that decay to zero as . Conversely, use this weak version to recover Exercise 29. (Hint:see this previous blog post for further examples of this type of logical equivalence between ultralimit statements and qualitative finitary statements.)

Exercise 31With the notation of Exercise 29, show that is totally equidistributed if and only iffor all standard and standard rational .

Exercise 32With the notation of Exercise 29, show that is equidistributed in on if and only if is equidistributed in on for every non-zero standard .

Now we establish the ultralimit version of the linear equidistribution criterion:

Exercise 33Let , and let be an unbounded integer. Show that the following are equivalent:

- The sequence is equidistributed on .
- The sequence is totally equidistributed on .
- is
irrational to scale, in the sense that for any non-zero standard .

Note that in the ultralimit setting, assertions such as make perfectly rigorous sense (it means that for every standard ), but when using finitary asymptotic big-O notation

Next, we establish the analogue of the van der Corput lemma:

Exercise 34 (van der Corput lemma, ultralimit version)Let be an unbounded integer, and let be a limit sequence. Let be unbounded, and suppose that the derivative sequence is equidistributed on for values of (extending by arbitrarily outside of ). Show that is equidistributed on . Similarly “equidistributed” replaced by “totally equidistributed”.

Here is the analogue of the Vinogradov lemma:

Exercise 35 (Vinogradov lemma, ultralimit version)Let , be unbounded, and be infinitesimal. Suppose that for values of . Show that there exists a positive standard integer such that .

These two lemmas allow us to establish the ultralimit polynomial equidistribution theory:

Exercise 36Let be a polynomial sequence with standard, and . Let be an unbounded natural number. Suppose that is not totally equidistributed on . Show that there exists a non-zero standard with .

Exercise 37With the hypotheses of Exercise 36, show in fact that there exists a non-zero standard such that for all .

Exercise 38 (Ultralimit Ratner’s theorem for abelian polynomial sequences)Let be a polynomial map from to of some standard degree . Let be an unbounded natural number. Then there exists a decompositioninto polynomials of degree , where

- ( is smooth) The coefficient of has size . In particular, on the interval , is Lipschitz with homogeneous norm .
- ( is equidistributed) There exists a standard subtorus of , such that takes values in and is totally equidistributed on in this torus.
- ( is rational) The coefficients of are standard rational elements of . In particular, there is a standard positive integer such that and is periodic with period .

Exercise 39Show that the torus is uniquely determined by , and decomposition in Exercise 38 is unique up to expressions taking values in (i.e. if one is given another decomposition , then and differ by expressions taking values in ).

Exercise 40 (Recurrence)Let be a polynomial map from to of some standard degree , and let be an unbounded natural number. Show that for every standard and every , we haveand more generally

for any standard .

As before, there are also multidimensional analogues of this theory. We shall just state the main results without proof:

Definition 14 (Multidimensional equidistribution)Let be a standard compact metric space, let be an unbounded limit natural number, let be standard, and let be a limit function. We say that isequidistributedwith respect to a (standard) Borel probability measure on if one hasfor every standard box and for all standard continuous functions .

We say that is

totally equidistributedrelative to if the sequence is equidistributed on for every standard and (extending arbitrarily outside if necessary).

Remark 9One can replace the indicators by many other classes, such as indicators of standard convex sets, or standard open sets whose boundary has measure zero, or continuous or Lipschitz functions.

Theorem 15 (Multidimensional ultralimit Ratner’s theorem for abelian polynomial sequences)Let be standard integers, and let be a polynomial map from to of degree . Let be an unbounded natural number. Then there exists a decompositioninto polynomials of degree , where

- ( is smooth) The coefficient of has size for every multi-index . In particular, on the interval , is Lipschitz with homogeneous norm .
- ( is equidistributed) There exists a standard subtorus of , such that takes values in and is totally equidistributed on in this torus.
- ( is rational) The coefficients of are standard rational elements of . In particular, there is a standard positive integer such that and is periodic with period .

*Proof:* This is implicitly in this paper of Ben Green and myself; the result is phrased using the language of single-scale equidistribution, but this easily implies the ultralimit version.

*Update, Apr 5:* Another exercise added; some corrections.

## 44 comments

Comments feed for this article

29 March, 2010 at 10:53 am

DiegoDear Terry,

Will there be applications to, say, dispersive PDEs in this course, or only number-theoretic oriented applications?

Thanks!

29 March, 2010 at 12:48 pm

Terence TaoAn overview of the course can be found at

https://terrytao.wordpress.com/2010/03/09/course-announcement-254b-higher-order-fourier-analysis/

The focus will be primarily on applications in additive combinatorics. There are tantalising hints that higher order Fourier analysis could also be useful in some aspects of harmonic analysis, such as the theory of the trilinear Hilbert transform, or the Lambda(p) problem for sets such as the square numbers, but there has been little concrete progress in this direction so far.

29 March, 2010 at 4:04 pm

DiegoThanks Terry, I’ll try to keep up.

30 March, 2010 at 4:10 am

VincentThank you for the interesting notes! A stupid notational question though: what is the meaning of the dot in the Weyl Criterion for equidistribution? Does it take values in the ordinary torus T?

[Corrected, thanks – T.]30 March, 2010 at 7:25 am

SujitSmall typo. \Phi should be U in Exercise 3.

[Corrected, thanks – T.]1 April, 2010 at 12:14 pm

Josh“…it is not hard to see that this map is equidistributed with respect to 1/3 times the Haar probability measure on (T)\times {0 mod Z}, plus 2/3 times the Haar probability measure on (T)\times {1 mod Z}”

Perhaps the last statement should be “(T)\times {1/3 mod Z}” ?

[Corrected, thanks – T.]5 April, 2010 at 9:10 am

EckhardFirst, thank you for the notes and the whole blog, which I find very interesting to read.

Second, I think the plural of ‘torus’ is ‘tori’, not ‘torii’.

[Corrected, thanks – T.]5 April, 2010 at 9:50 am

JasonIn the definition of totally delta-equidistributed, I think f(n) should read f(x(n)).

Thanks for the great notes–Jason

[Corrected, thanks – T.]5 April, 2010 at 10:20 am

bradPerhaps I’m missing something, but for the Fejer kernel estimates, I think one has only 1/(R \|x_j\|^2) rather than 1/(R\|x_j\|)^2; and to get the O(1/R) bound I think one has to resort to the full force of a \min(R,1/(R\|x_j\|^2)) estimate (at any rate I did).

More pedantically, the expression involving a product of sines should have x_j multiplied by 2\pi, I think.

[Corrected, thanks – T.]9 April, 2010 at 3:00 am

Sungjin KimOne minor thing, the error term H/N in the proof of corollary 5 should be changed to sqrt(H/N) too.

[Corrected, thanks – T.]9 April, 2010 at 9:50 am

JasonSmall detail: In Exercise 21, should “the linear sequence P” read “the polynomial sequence P” ?

[Corrected, thanks – T.]12 April, 2010 at 10:41 am

mmailliw/williamIn the beginning of Section 3, you say

“thus for any limit numbers {X, Y} with {Y>0}, exactly one of {X=O(Y)} and {X=o(Y)} is true”.

Doesn’t X=o(Y) imply X=O(Y) by your definition? Maybe it should be changed to “exactly one of {Y=O(|X|)} and {X=o(Y)} is true”.

[Corrected, thanks -T.]21 April, 2010 at 3:13 pm

bradThere’s a classical metric theory of asymptotic equidistribution; for example, for any increasing sequence of integers , the sequence is equidistributed mod 1 for almost all . Is their any analogue of these results in the single scale case? For instance, one might make the following guess:

For a fixed sequence of increasing integers and any , for almost all , there is a sequence (depending on ) so that and is -equidistributed for all N.

If I'm not mistaken this is true in the case that , but there might be other obstructions for less canonical sequences. (There is also another motivation, by analogy to Carleson's theorem, using partial summation.)

21 April, 2010 at 8:56 pm

Terence TaoIt seems quite likely that most of the classical results of asymptotic equidistribution have more quantitative single-scale counterparts, but the literature of the latter is much sparser currently than that of the former. A very rough rule of thumb is that as long as one avoids the use of the ergodic theorem (which is perhaps the first genuinely asymptotic result that utilises multiple scales), or the use of infinitary topological tools such as closures and compactifications, then asymptotic equidistribution arguments are usually fairly easy to make quantitative (and the bounds are then usually “polynomial” in nature in some sense).

Note though that the exact value of here will be somewhat sensitive to the precise definition of equidistribution. In my notes here, I used a notion based on the Lipschitz norm, but this is not the only possible choice, and if one uses a different quantitative measure of equidistribution, then one might get a different power of showing up. But I would guess that a polynomially quantitative version of the above theorem should probably exist.

23 April, 2010 at 12:19 pm

254B, Notes 3: Linear patterns « What’s new[…] for any cyclic group and any subset of that group (analogues of this identity also exist for other finite abelian groups, and to a lesser extent to non-abelian groups also, although that is not the focus of my current discussion). As it turns out, linear Fourier analysis is not able to discern higher order patterns, such as arithmetic progressions of length four; we give some demonstrations of this below the fold, taking advantage of the polynomial recurrence theory from Notes 1. […]

8 May, 2010 at 1:48 pm

254B, Lecture Notes 4: Equidistribution of polynomials over finite fields « What’s new[…] starting point for this course (Notes 1) was the study of equidistribution of polynomials from the integers to the unit circle. We now […]

29 May, 2010 at 2:15 pm

254B, Notes 6: The inverse conjecture for the Gowers norm II. The integer case « What’s new[…] theory (which generalises the equidistribution theory of polynomial flows on tori from Notes 1) and show that they are indeed obstructions to the Gowers norm being small. This leads to the […]

20 August, 2010 at 10:54 am

ICM2010 — Lindenstrauss laudatio « Gowers's Weblog[…] on it. (That is not the only post of Terry’s on that topic: another I would recommend is this one. More generally, you can click on promising tags such as “Ratner’s theorems” and […]

30 April, 2012 at 3:44 am

Waring’s Problem: Lecture 2 « Theorem of the week[…] Tao has some notes about equidistribution and Weyl’s inequality on his blog, which give another […]

6 November, 2013 at 8:26 am

Joel MoreiraWhy is Exercise 15 called Szemeredi’s theorem for polynomials? Does it imply Szemeredi’s theorem (or polynomial Szemeredi) in some sense? Thank you.

[Exercise reworded to make the connection to Szemeredi’s theorem clearer – T.]25 December, 2014 at 4:09 pm

How do you prove that $p(n xi)$ for $xi$ irrational and $p$ a polynomial is uniformly distributed modulo 1? | CL-UAT[…] is a fairly good exposition in Terry Tao’s post, see Corollaries 4-6. Here is a […]

28 December, 2014 at 9:50 pm

Convergence of $sum limits_{n=1}^{infty}sin(n^k)/n$ | CL-UAT[…] So this is $$sum_{n=1}^N S_n/(n(n+1)) + S_N/(N+1).$$ The second term goes to zero by Weyl’s polynomial equidistribution theorem. So your question is equivalent to the question of whether $sum s_n/(n(n+1))$ converges. We may as […]

16 April, 2015 at 3:05 pm

MrCactu5 (@MonsieurCactus)Can you go through the second-to-last sentence in the proof of Lemma 10 more slowly. Why do you get ?

I reasoned set has size at most and we need to fit two intervals + a gap which is about 50 times larger.

Then I reasons the set is at most but that might be false.

16 April, 2015 at 3:25 pm

Terence TaoThe length of each gap is at least as long as either of the neighbouring intervals, each of which have length at least 1, so the number of integers in each gap is at least times the number of integers in the neighbouring intervals (one can tighten the factor of 10 a bit if needed, but this is certainly enough of a safety margin to deal with roundoff error). Summing, this shows that the total number of integers in the gaps is at least times the total number of integers in the intervals, which gives the claim since there are only about integers in all.

12 June, 2017 at 12:55 pm

AnonymousI’m having a little trouble with exercise 4: total asymptotic equidistribution seems to be equivalent to

for any non-zero , and any . Not sure how to connect this to the statement

for rational without some sort of structural assumption on the sequence …

12 June, 2017 at 1:00 pm

AnonymousBelow remark 1:

“…if {\alpha} is rational in the sense that {m\alpha = 0} for some positive integer {m}…”

Do you mean that {m\alpha = 0 \mod 1}?

is an element of a torus here, not a Euclidean space. -T]22 June, 2017 at 5:10 pm

Terence TaoWrite . Each natural number can be uniquely expressed as for some . This can be used to break up sums of the second type into sums of the first type. To go in the reverse direction, one needs to perform a Fourier expansion in .

13 June, 2017 at 10:03 am

AnonymousIn the second half of exercise 17, should the sequence be equidistributed rather that equidistributed?

[Corrected, thanks – T.]15 June, 2017 at 8:50 am

AnonymousIn exercise 20, should the condition

$$ 1 \leq H \leq \delta^{-C_d} N $$

be replaced with

$$ 1 \leq H \leq \delta^{C_d} N $$

instead?

[Corrected, thanks – T.]2 October, 2017 at 5:46 am

farlabbI am trying to understand the proof of proposition 1 (Weyls equidistribution criterion) and I don’t understand the “if” part. I think I am missing something silly, but here it goes: If then we have that for , so assuming equation (2) we indeed have that (1) holds for such functions. In general, if is any function, then by linearity I get that . So I get that integral of any function on the torus is just 0, which seems weird to me. Could you explain in more detail the limiting argument to me? A lot of thanks in advance!

2 October, 2017 at 9:23 am

Terence TaoThe contribution of has to be treated separately. If (1) holds for a sequence of functions that tend uniformly to a limit , then it is not hard to show that (1) also holds for .

13 October, 2017 at 4:54 am

farlabbDear prof. Tao, I am having trouble with exercise 4. I do not understand how to show that if is totally asymptotically equidistributed, then . Using your hint I could prove the converse to this, but I do not understand how to use your hint (fourier expansion in ) to prove this case.

17 October, 2017 at 10:51 am

Terence TaoFourier expansion is not needed for the converse direction. If , split up the summation into sums over arithmetic progressions modulo by making a change of variables .

27 March, 2019 at 4:26 am

Maths studentI believe that the uniqueness of the asymptotic equidistribution needs only the easy implication of Riesz’ representation theorem.

29 August, 2019 at 11:51 pm

Extreme Events Modeling Using Continued Fractions - Data Science Central[…] being the n-th prime number, or h(n) being an integer power of n (see hereĀ and corollary 6 in this tutorial). Then the distribution of the sequenceĀ z(n), including its limiting median SQRT(2)/2, is […]

12 October, 2021 at 5:59 am

AnonymousIn Lemma 11, I’m having a hard time figuring out how to identify the pigeon-holed arithmetic progression , which lives inside , with the progression , where is the length of . My concern is that we are translating by a constant on the order of ,

but identifying with seems to discount the effect of the shift by , which would change the coefficients of the relevant polynomial

has different coefficients that .

20 October, 2021 at 1:19 pm

Terence TaoThe stated conclusion of Lemma 11 is invariant with respect to these shifts (the powers of that show up cancel each other out).

26 November, 2021 at 8:51 pm

NoviceDear Prof Tao,

In the statement of the Proposition 3, we have that is totally asymptotically equidistributed on in a **subtorus** of . How is this **subtorus** defined?

In the proof of proposition we have defined the subtorus and then we apply induction hypothesis, but no where it is described how subtorus is defined?

Can you please elaborate on this? Thankyou!

28 November, 2021 at 10:51 am

Terence TaoThe subtorus is constructed recursively. After identifying with , there are two cases. If is irrational, then Exercise 5 lets us take . Otherwise, we take to be whatever subtorus was recursively assigned to .

29 November, 2021 at 9:01 pm

NoviceDear Prof Tao,

Also, can you please explain how are we able to apply induction hypothesis to the subtorus ?

To apply induction hypothesis we need to have dimension less than the dimension of since we assumed that such a decomposition exists for tori of smaller dimension.

But I donāt see why the subtorus of has dimension less than d (=dimension of )

4 December, 2021 at 11:45 am

Terence TaoThe dimension of a torus is equal to the dimension of its tangent space at the origin. The tangent space of at the origin is a linear subspace of the tangent space of that cannot be all of (since the exponential map would then make equal to ), so it has dimension at most .

15 December, 2021 at 11:22 pm

AnonymousCan I get a hint with Exercises 23/24? I can approximate the set by a Fejer kernel argument, so it looks like Iām interested in analyzing quantities like

(or take the expectation of arithmetic progressions). I can see an upper bound in terms of a maximum of

where

is the minimal āstopping timeā that using a polynomial growth function

.

But, Iām having trouble with the lower bound. Any hints?

16 December, 2021 at 1:54 am

AnonymousAh, a single AP does the job

3 January, 2022 at 8:57 pm

NoviceDear Prof. Tao,

Can you please give some explaination on how to proceed for exercise 17? I am unable to bound the difference by for the case when is a multiple of (from the definition of -equidistribution) . Similarly I am not unable to bound the difference for the case when .

[Try the case first. Think about why a Riemann sum of a Lipschitz function is close to the Riemann integral. -T]