You are currently browsing the category archive for the ‘math.CA’ category.

In the previous set of notes we saw that functions ${f: U \rightarrow {\bf C}}$ that were holomorphic on an open set ${U}$ enjoyed a large number of useful properties, particularly if the domain ${U}$ was simply connected. In many situations, though, we need to consider functions ${f}$ that are only holomorphic (or even well-defined) on most of a domain ${U}$, thus they are actually functions ${f: U \backslash S \rightarrow {\bf C}}$ outside of some small singular set ${S}$ inside ${U}$. (In this set of notes we only consider interior singularities; one can also discuss singular behaviour at the boundary of ${U}$, but this is a whole separate topic and will not be pursued here.) Since we have only defined the notion of holomorphicity on open sets, we will require the singular sets ${S}$ to be closed, so that the domain ${U \backslash S}$ on which ${f}$ remains holomorphic is still open. A typical class of examples are the functions of the form ${\frac{f(z)}{z-z_0}}$ that were already encountered in the Cauchy integral formula; if ${f: U \rightarrow {\bf C}}$ is holomorphic and ${z_0 \in U}$, such a function would be holomorphic save for a singularity at ${z_0}$. Another basic class of examples are the rational functions ${P(z)/Q(z)}$, which are holomorphic outside of the zeroes of the denominator ${Q}$.

Singularities come in varying levels of “badness” in complex analysis. The least harmful type of singularity is the removable singularity – a point ${z_0}$ which is an isolated singularity (i.e., an isolated point of the singular set ${S}$) where the function ${f}$ is undefined, but for which one can extend the function across the singularity in such a fashion that the function becomes holomorphic in a neighbourhood of the singularity. A typical example is that of the complex sinc function ${\frac{\sin(z)}{z}}$, which has a removable singularity at the origin ${0}$, which can be removed by declaring the sinc function to equal ${1}$ at ${0}$. The detection of isolated removable singularities can be accomplished by Riemann’s theorem on removable singularities (Exercise 35 from Notes 3): if a holomorphic function ${f: U \backslash S \rightarrow {\bf C}}$ is bounded near an isolated singularity ${z_0 \in S}$, then the singularity at ${z_0}$ may be removed.

After removable singularities, the mildest form of singularity one can encounter is that of a pole – an isolated singularity ${z_0}$ such that ${f(z)}$ can be factored as ${f(z) = \frac{g(z)}{(z-z_0)^m}}$ for some ${m \geq 1}$ (known as the order of the pole), where ${g}$ has a removable singularity at ${z_0}$ (and is non-zero at ${z_0}$ once the singularity is removed). Such functions have already made a frequent appearance in previous notes, particularly the case of simple poles when ${m=1}$. The behaviour near ${z_0}$ of function ${f}$ with a pole of order ${m}$ is well understood: for instance, ${|f(z)|}$ goes to infinity as ${z}$ approaches ${z_0}$ (at a rate comparable to ${|z-z_0|^{-m}}$). These singularities are not, strictly speaking, removable; but if one compactifies the range ${{\bf C}}$ of the holomorphic function ${f: U \backslash S \rightarrow {\bf C}}$ to a slightly larger space ${{\bf C} \cup \{\infty\}}$ known as the Riemann sphere, then the singularity can be removed. In particular, functions ${f: U \backslash S \rightarrow {\bf C}}$ which only have isolated singularities that are either poles or removable can be extended to holomorphic functions ${f: U \rightarrow {\bf C} \cup \{\infty\}}$ to the Riemann sphere. Such functions are known as meromorphic functions, and are nearly as well-behaved as holomorphic functions in many ways. In fact, in one key respect, the family of meromorphic functions is better: the meromorphic functions on ${U}$ turn out to form a field, in particular the quotient of two meromorphic functions is again meromorphic (if the denominator is not identically zero).

Unfortunately, there are isolated singularities that are neither removable or poles, and are known as essential singularities. A typical example is the function ${f(z) = e^{1/z}}$, which turns out to have an essential singularity at ${z=0}$. The behaviour of such essential singularities is quite wild; we will show here the Casorati-Weierstrass theorem, which shows that the image of ${f}$ near the essential singularity is dense in the complex plane, as well as the more difficult great Picard theorem which asserts that in fact the image can omit at most one point in the complex plane. Nevertheless, around any isolated singularity (even the essential ones) ${z_0}$, it is possible to expand ${f}$ as a variant of a Taylor series known as a Laurent series ${\sum_{n=-\infty}^\infty a_n (z-z_0)^n}$. The ${\frac{1}{z-z_0}}$ coefficient ${a_{-1}}$ of this series is particularly important for contour integration purposes, and is known as the residue of ${f}$ at the isolated singularity ${z_0}$. These residues play a central role in a common generalisation of Cauchy’s theorem and the Cauchy integral formula known as the residue theorem, which is a particularly useful tool for computing (or at least transforming) contour integrals of meromorphic functions, and has proven to be a particularly popular technique to use in analytic number theory. Within complex analysis, one important consequence of the residue theorem is the argument principle, which gives a topological (and analytical) way to control the zeroes and poles of a meromorphic function.

Finally, there are the non-isolated singularities. Little can be said about these singularities in general (for instance, the residue theorem does not directly apply in the presence of such singularities), but certain types of non-isolated singularities are still relatively easy to understand. One particularly common example of such non-isolated singularity arises when trying to invert a non-injective function, such as the complex exponential ${z \mapsto \exp(z)}$ or a power function ${z \mapsto z^n}$, leading to branches of multivalued functions such as the complex logarithm ${z \mapsto \log(z)}$ or the ${n^{th}}$ root function ${z \mapsto z^{1/n}}$ respectively. Such branches will typically have a non-isolated singularity along a branch cut; this branch cut can be moved around the complex domain by switching from one branch to another, but usually cannot be eliminated entirely, unless one is willing to lift up the domain ${U}$ to a more general type of domain known as a Riemann surface. As such, one can view branch cuts as being an “artificial” form of singularity, being an artefact of a choice of local coordinates of a Riemann surface, rather than reflecting any intrinsic singularity of the function itself. The further study of Riemann surfaces is an important topic in complex analysis (as well as the related fields of complex geometry and algebraic geometry), but unfortunately this topic will probably be postponed to the next course in this sequence (which I will not be teaching).

At the core of almost any undergraduate real analysis course are the concepts of differentiation and integration, with these two basic operations being tied together by the fundamental theorem of calculus (and its higher dimensional generalisations, such as Stokes’ theorem). Similarly, the notion of the complex derivative and the complex line integral (that is to say, the contour integral) lie at the core of any introductory complex analysis course. Once again, they are tied to each other by the fundamental theorem of calculus; but in the complex case there is a further variant of the fundamental theorem, namely Cauchy’s theorem, which endows complex differentiable functions with many important and surprising properties that are often not shared by their real differentiable counterparts. We will give complex differentiable functions another name to emphasise this extra structure, by referring to such functions as holomorphic functions. (This term is also useful to distinguish these functions from the slightly less well-behaved meromorphic functions, which we will discuss in later notes.)

In this set of notes we will focus solely on the concept of complex differentiation, deferring the discussion of contour integration to the next set of notes. To begin with, the theory of complex differentiation will greatly resemble the theory of real differentiation; the definitions look almost identical, and well known laws of differential calculus such as the product rule, quotient rule, and chain rule carry over verbatim to the complex setting, and the theory of complex power series is similarly almost identical to the theory of real power series. However, when one compares the “one-dimensional” differentiation theory of the complex numbers with the “two-dimensional” differentiation theory of two real variables, we find that the dimensional discrepancy forces complex differentiable functions to obey a real-variable constraint, namely the Cauchy-Riemann equations. These equations make complex differentiable functions substantially more “rigid” than their real-variable counterparts; they imply for instance that the imaginary part of a complex differentiable function is essentially determined (up to constants) by the real part, and vice versa. Furthermore, even when considered separately, the real and imaginary components of complex differentiable functions are forced to obey the strong constraint of being harmonic. In later notes we will see these constraints manifest themselves in integral form, particularly through Cauchy’s theorem and the closely related Cauchy integral formula.

Despite all the constraints that holomorphic functions have to obey, a surprisingly large number of the functions of a complex variable that one actually encounters in applications turn out to be holomorphic. For instance, any polynomial ${z \mapsto P(z)}$ with complex coefficients will be holomorphic, as will the complex exponential ${z \mapsto \exp(z)}$. From this and the laws of differential calculus one can then generate many further holomorphic functions. Also, as we will show presently, complex power series will automatically be holomorphic inside their disk of convergence. On the other hand, there are certainly basic complex functions of interest that are not holomorphic, such as the complex conjugation function ${z \mapsto \overline{z}}$, the absolute value function ${z \mapsto |z|}$, or the real and imaginary part functions ${z \mapsto \mathrm{Re}(z), z \mapsto \mathrm{Im}(z)}$. We will also encounter functions that are only holomorphic at some portions of the complex plane, but not on others; for instance, rational functions will be holomorphic except at those few points where the denominator vanishes, and are prime examples of the meromorphic functions mentioned previously. Later on we will also consider functions such as branches of the logarithm or square root, which will be holomorphic outside of a branch cut corresponding to the choice of branch. It is a basic but important skill in complex analysis to be able to quickly recognise which functions are holomorphic and which ones are not, as many of useful theorems available to the former (such as Cauchy’s theorem) break down spectacularly for the latter. Indeed, in my experience, one of the most common “rookie errors” that beginning complex analysis students make is the error of attempting to apply a theorem about holomorphic functions to a function that is not at all holomorphic. This stands in contrast to the situation in real analysis, in which one can often obtain correct conclusions by formally applying the laws of differential or integral calculus to functions that might not actually be differentiable or integrable in a classical sense. (This latter phenomenon, by the way, can be largely explained using the theory of distributions, as covered for instance in this previous post, but this is beyond the scope of the current course.)

Remark 1 In this set of notes it will be convenient to impose some unnecessarily generous regularity hypotheses (e.g. continuous second differentiability) on the holomorphic functions one is studying in order to make the proofs simpler. In later notes, we will discover that these hypotheses are in fact redundant, due to the phenomenon of elliptic regularity that ensures that holomorphic functions are automatically smooth.

In this blog post, I would like to specialise the arguments of Bourgain, Demeter, and Guth from the previous post to the two-dimensional case of the Vinogradov main conjecture, namely

Theorem 1 (Two-dimensional Vinogradov main conjecture) One has

$\displaystyle \int_{[0,1]^2} |\sum_{j=0}^N e( j x + j^2 y)|^6\ dx dy \ll N^{3+o(1)}$

as ${N \rightarrow \infty}$.

This particular case of the main conjecture has a classical proof using some elementary number theory. Indeed, the left-hand side can be viewed as the number of solutions to the system of equations

$\displaystyle j_1 + j_2 + j_3 = k_1 + k_2 + k_3$

$\displaystyle j_1^2 + j_2^2 + j_3^2 = k_1^2 + k_2^2 + k_3^2$

with ${j_1,j_2,j_3,k_1,k_2,k_3 \in \{0,\dots,N\}}$. These two equations can combine (using the algebraic identity ${(a+b-c)^2 - (a^2+b^2-c^2) = 2 (a-c)(b-c)}$ applied to ${(a,b,c) = (j_1,j_2,k_3), (k_1,k_2,j_3)}$) to imply the further equation

$\displaystyle (j_1 - k_3) (j_2 - k_3) = (k_1 - j_3) (k_2 - j_3)$

which, when combined with the divisor bound, shows that each ${k_1,k_2,j_3}$ is associated to ${O(N^{o(1)})}$ choices of ${j_1,j_2,k_3}$ excluding diagonal cases when two of the ${j_1,j_2,j_3,k_1,k_2,k_3}$ collide, and this easily yields Theorem 1. However, the Bourgain-Demeter-Guth argument (which, in the two dimensional case, is essentially contained in a previous paper of Bourgain and Demeter) does not require the divisor bound, and extends for instance to the the more general case where ${j}$ ranges in a ${1}$-separated set of reals between ${0}$ to ${N}$.

In this special case, the Bourgain-Demeter argument simplifies, as the lower dimensional inductive hypothesis becomes a simple ${L^2}$ almost orthogonality claim, and the multilinear Kakeya estimate needed is also easy (collapsing to just Fubini’s theorem). Also one can work entirely in the context of the Vinogradov main conjecture, and not turn to the increased generality of decoupling inequalities (though this additional generality is convenient in higher dimensions). As such, I am presenting this special case as an introduction to the Bourgain-Demeter-Guth machinery.

We now give the specialisation of the Bourgain-Demeter argument to Theorem 1. It will suffice to establish the bound

$\displaystyle \int_{[0,1]^2} |\sum_{j=0}^N e( j x + j^2 y)|^p\ dx dy \ll N^{p/2+o(1)}$

for all ${4, (where we keep ${p}$ fixed and send ${N}$ to infinity), as the ${L^6}$ bound then follows by combining the above bound with the trivial bound ${|\sum_{j=0}^N e( j x + j^2 x^2)| \ll N}$. Accordingly, for any ${\eta > 0}$ and ${4, we let ${P(p,\eta)}$ denote the claim that

$\displaystyle \int_{[0,1]^2} |\sum_{j=0}^N e( j x + j^2 y)|^p\ dx dy \ll N^{p/2+\eta+o(1)}$

as ${N \rightarrow \infty}$. Clearly, for any fixed ${p}$, ${P(p,\eta)}$ holds for some large ${\eta}$, and it will suffice to establish

Proposition 2 Let ${4, and let ${\eta>0}$ be such that ${P(p,\eta)}$ holds. Then there exists ${0 < \eta' < \eta}$ (depending continuously on $\eta$) such that ${P(p,\eta')}$ holds.

Indeed, this proposition shows that for ${4, the infimum of the ${\eta}$ for which ${P(p,\eta)}$ holds is zero.

We prove the proposition below the fold, using a simplified form of the methods discussed in the previous blog post. To simplify the exposition we will be a bit cavalier with the uncertainty principle, for instance by essentially ignoring the tails of rapidly decreasing functions.

Given any finite collection of elements ${(f_i)_{i \in I}}$ in some Banach space ${X}$, the triangle inequality tells us that

$\displaystyle \| \sum_{i \in I} f_i \|_X \leq \sum_{i \in I} \|f_i\|_X.$

However, when the ${f_i}$ all “oscillate in different ways”, one expects to improve substantially upon the triangle inequality. For instance, if ${X}$ is a Hilbert space and the ${f_i}$ are mutually orthogonal, we have the Pythagorean theorem

$\displaystyle \| \sum_{i \in I} f_i \|_X = (\sum_{i \in I} \|f_i\|_X^2)^{1/2}.$

For sake of comparison, from the triangle inequality and Cauchy-Schwarz one has the general inequality

$\displaystyle \| \sum_{i \in I} f_i \|_X \leq (\# I)^{1/2} (\sum_{i \in I} \|f_i\|_X^2)^{1/2} \ \ \ \ \ (1)$

for any finite collection ${(f_i)_{i \in I}}$ in any Banach space ${X}$, where ${\# I}$ denotes the cardinality of ${I}$. Thus orthogonality in a Hilbert space yields “square root cancellation”, saving a factor of ${(\# I)^{1/2}}$ or so over the trivial bound coming from the triangle inequality.

More generally, let us somewhat informally say that a collection ${(f_i)_{i \in I}}$ exhibits decoupling in ${X}$ if one has the Pythagorean-like inequality

$\displaystyle \| \sum_{i \in I} f_i \|_X \ll_\varepsilon (\# I)^\varepsilon (\sum_{i \in I} \|f_i\|_X^2)^{1/2}$

for any ${\varepsilon>0}$, thus one obtains almost the full square root cancellation in the ${X}$ norm. The theory of almost orthogonality can then be viewed as the theory of decoupling in Hilbert spaces such as ${L^2({\bf R}^n)}$. In ${L^p}$ spaces for ${p < 2}$ one usually does not expect this sort of decoupling; for instance, if the ${f_i}$ are disjointly supported one has

$\displaystyle \| \sum_{i \in I} f_i \|_{L^p} = (\sum_{i \in I} \|f_i\|_{L^p}^p)^{1/p}$

and the right-hand side can be much larger than ${(\sum_{i \in I} \|f_i\|_{L^p}^2)^{1/2}}$ when ${p < 2}$. At the opposite extreme, one usually does not expect to get decoupling in ${L^\infty}$, since one could conceivably align the ${f_i}$ to all attain a maximum magnitude at the same location with the same phase, at which point the triangle inequality in ${L^\infty}$ becomes sharp.

However, in some cases one can get decoupling for certain ${2 < p < \infty}$. For instance, suppose we are in ${L^4}$, and that ${f_1,\dots,f_N}$ are bi-orthogonal in the sense that the products ${f_i f_j}$ for ${1 \leq i < j \leq N}$ are pairwise orthogonal in ${L^2}$. Then we have

$\displaystyle \| \sum_{i = 1}^N f_i \|_{L^4}^2 = \| (\sum_{i=1}^N f_i)^2 \|_{L^2}$

$\displaystyle = \| \sum_{1 \leq i,j \leq N} f_i f_j \|_{L^2}$

$\displaystyle \ll (\sum_{1 \leq i,j \leq N} \|f_i f_j \|_{L^2}^2)^{1/2}$

$\displaystyle = \| (\sum_{1 \leq i,j \leq N} |f_i f_j|^2)^{1/2} \|_{L^2}$

$\displaystyle = \| \sum_{i=1}^N |f_i|^2 \|_{L^2}$

$\displaystyle \leq \sum_{i=1}^N \| |f_i|^2 \|_{L^2}$

$\displaystyle = \sum_{i=1}^N \|f_i\|_{L^4}^2$

giving decoupling in ${L^4}$. (Similarly if each of the ${f_i f_j}$ is orthogonal to all but ${O_\varepsilon( N^\varepsilon )}$ of the other ${f_{i'} f_{j'}}$.) A similar argument also gives ${L^6}$ decoupling when one has tri-orthogonality (with the ${f_i f_j f_k}$ mostly orthogonal to each other), and so forth. As a slight variant, Khintchine’s inequality also indicates that decoupling should occur for any fixed ${2 < p < \infty}$ if one multiplies each of the ${f_i}$ by an independent random sign ${\epsilon_i \in \{-1,+1\}}$.

In recent years, Bourgain and Demeter have been establishing decoupling theorems in ${L^p({\bf R}^n)}$ spaces for various key exponents of ${2 < p < \infty}$, in the “restriction theory” setting in which the ${f_i}$ are Fourier transforms of measures supported on different portions of a given surface or curve; this builds upon the earlier decoupling theorems of Wolff. In a recent paper with Guth, they established the following decoupling theorem for the curve ${\gamma({\bf R}) \subset {\bf R}^n}$ parameterised by the polynomial curve

$\displaystyle \gamma: t \mapsto (t, t^2, \dots, t^n).$

For any ball ${B = B(x_0,r)}$ in ${{\bf R}^n}$, let ${w_B: {\bf R}^n \rightarrow {\bf R}^+}$ denote the weight

$\displaystyle w_B(x) := \frac{1}{(1 + \frac{|x-x_0|}{r})^{100n}},$

which should be viewed as a smoothed out version of the indicator function ${1_B}$ of ${B}$. In particular, the space ${L^p(w_B) = L^p({\bf R}^n, w_B(x)\ dx)}$ can be viewed as a smoothed out version of the space ${L^p(B)}$. For future reference we observe a fundamental self-similarity of the curve ${\gamma({\bf R})}$: any arc ${\gamma(I)}$ in this curve, with ${I}$ a compact interval, is affinely equivalent to the standard arc ${\gamma([0,1])}$.

Theorem 1 (Decoupling theorem) Let ${n \geq 1}$. Subdivide the unit interval ${[0,1]}$ into ${N}$ equal subintervals ${I_i}$ of length ${1/N}$, and for each such ${I_i}$, let ${f_i: {\bf R}^n \rightarrow {\bf R}}$ be the Fourier transform

$\displaystyle f_i(x) = \int_{\gamma(I_i)} e(x \cdot \xi)\ d\mu_i(\xi)$

of a finite Borel measure ${\mu_i}$ on the arc ${\gamma(I_i)}$, where ${e(\theta) := e^{2\pi i \theta}}$. Then the ${f_i}$ exhibit decoupling in ${L^{n(n+1)}(w_B)}$ for any ball ${B}$ of radius ${N^n}$.

Orthogonality gives the ${n=1}$ case of this theorem. The bi-orthogonality type arguments sketched earlier only give decoupling in ${L^p}$ up to the range ${2 \leq p \leq 2n}$; the point here is that we can now get a much larger value of ${n}$. The ${n=2}$ case of this theorem was previously established by Bourgain and Demeter (who obtained in fact an analogous theorem for any curved hypersurface). The exponent ${n(n+1)}$ (and the radius ${N^n}$) is best possible, as can be seen by the following basic example. If

$\displaystyle f_i(x) := \int_{I_i} e(x \cdot \gamma(\xi)) g_i(\xi)\ d\xi$

where ${g_i}$ is a bump function adapted to ${I_i}$, then standard Fourier-analytic computations show that ${f_i}$ will be comparable to ${1/N}$ on a rectangular box of dimensions ${N \times N^2 \times \dots \times N^n}$ (and thus volume ${N^{n(n+1)/2}}$) centred at the origin, and exhibit decay away from this box, with ${\|f_i\|_{L^{n(n+1)}(w_B)}}$ comparable to

$\displaystyle 1/N \times (N^{n(n+1)/2})^{1/(n(n+1))} = 1/\sqrt{N}.$

On the other hand, ${\sum_{i=1}^N f_i}$ is comparable to ${1}$ on a ball of radius comparable to ${1}$ centred at the origin, so ${\|\sum_{i=1}^N f_i\|_{L^{n(n+1)}(w_B)}}$ is ${\gg 1}$, which is just barely consistent with decoupling. This calculation shows that decoupling will fail if ${n(n+1)}$ is replaced by any larger exponent, and also if the radius of the ball ${B}$ is reduced to be significantly smaller than ${N^n}$.

This theorem has the following consequence of importance in analytic number theory:

Corollary 2 (Vinogradov main conjecture) Let ${s, n, N \geq 1}$ be integers, and let ${\varepsilon > 0}$. Then

$\displaystyle \int_{[0,1]^n} |\sum_{j=1}^N e( j x_1 + j^2 x_2 + \dots + j^n x_n)|^{2s}\ dx_1 \dots dx_n$

$\displaystyle \ll_{\varepsilon,s,n} N^{s+\varepsilon} + N^{2s - \frac{n(n+1)}{2}+\varepsilon}.$

Proof: By the Hölder inequality (and the trivial bound of ${N}$ for the exponential sum), it suffices to treat the critical case ${s = n(n+1)/2}$, that is to say to show that

$\displaystyle \int_{[0,1]^n} |\sum_{j=1}^N e( j x_1 + j^2 x_2 + \dots + j^n x_n)|^{n(n+1)}\ dx_1 \dots dx_n \ll_{\varepsilon,n} N^{\frac{n(n+1)}{2}+\varepsilon}.$

We can rescale this as

$\displaystyle \int_{[0,N] \times [0,N^2] \times \dots \times [0,N^n]} |\sum_{j=1}^N e( x \cdot \gamma(j/N) )|^{n(n+1)}\ dx \ll_{\varepsilon,n} N^{n(n+1)+\varepsilon}.$

As the integrand is periodic along the lattice ${N{\bf Z} \times N^2 {\bf Z} \times \dots \times N^n {\bf Z}}$, this is equivalent to

$\displaystyle \int_{[0,N^n]^n} |\sum_{j=1}^N e( x \cdot \gamma(j/N) )|^{n(n+1)}\ dx \ll_{\varepsilon,n} N^{\frac{n(n+1)}{2}+n^2+\varepsilon}.$

The left-hand side may be bounded by ${\ll \| \sum_{j=1}^N f_j \|_{L^{n(n+1)}(w_B)}^{n(n+1)}}$, where ${B := B(0,N^n)}$ and ${f_j(x) := e(x \cdot \gamma(j/N))}$. Since

$\displaystyle \| f_j \|_{L^{n(n+1)}(w_B)} \ll (N^{n^2})^{\frac{1}{n(n+1)}},$

the claim now follows from the decoupling theorem and a brief calculation. $\Box$

Using the Plancherel formula, one may equivalently (when ${s}$ is an integer) write the Vinogradov main conjecture in terms of solutions ${j_1,\dots,j_s,k_1,\dots,k_s \in \{1,\dots,N\}}$ to the system of equations

$\displaystyle j_1^i + \dots + j_s^i = k_1^i + \dots + k_s^i \forall i=1,\dots,n,$

but we will not use this formulation here.

A history of the Vinogradov main conjecture may be found in this survey of Wooley; prior to the Bourgain-Demeter-Guth theorem, the conjecture was solved completely for ${n \leq 3}$, or for ${n > 3}$ and ${s}$ either below ${n(n+1)/2 - n/3 + O(n^{2/3})}$ or above ${n(n-1)}$, with the bulk of recent progress coming from the efficient congruencing technique of Wooley. It has numerous applications to exponential sums, Waring’s problem, and the zeta function; to give just one application, the main conjecture implies the predicted asymptotic for the number of ways to express a large number as the sum of ${23}$ fifth powers (the previous best result required ${28}$ fifth powers). The Bourgain-Demeter-Guth approach to the Vinogradov main conjecture, based on decoupling, is ostensibly very different from the efficient congruencing technique, which relies heavily on the arithmetic structure of the program, but it appears (as I have been told from second-hand sources) that the two methods are actually closely related, with the former being a sort of “Archimedean” version of the latter (with the intervals ${I_i}$ in the decoupling theorem being analogous to congruence classes in the efficient congruencing method); hopefully there will be some future work making this connection more precise. One advantage of the decoupling approach is that it generalises to non-arithmetic settings in which the set ${\{1,\dots,N\}}$ that ${j}$ is drawn from is replaced by some other similarly separated set of real numbers. (A random thought – could this allow the Vinogradov-Korobov bounds on the zeta function to extend to Beurling zeta functions?)

Below the fold we sketch the Bourgain-Demeter-Guth argument proving Theorem 1.

I thank Jean Bourgain and Andrew Granville for helpful discussions.

In the previous set of notes we established the central limit theorem, which we formulate here as follows:

Theorem 1 (Central limit theorem) Let ${X_1,X_2,X_3,\dots}$ be iid copies of a real random variable ${X}$ of mean ${\mu}$ and variance ${0 < \sigma^2 < \infty}$, and write ${S_n := X_1 + \dots + X_n}$. Then, for any fixed ${a < b}$, we have

$\displaystyle {\bf P}( a \leq \frac{S_n - n \mu}{\sqrt{n} \sigma} \leq b ) \rightarrow \frac{1}{\sqrt{2\pi}} \int_a^b e^{-t^2/2}\ dt \ \ \ \ \ (1)$

as ${n \rightarrow \infty}$.

This is however not the end of the matter; there are many variants, refinements, and generalisations of the central limit theorem, and the purpose of this set of notes is to present a small sample of these variants.

First of all, the above theorem does not quantify the rate of convergence in (1). We have already addressed this issue to some extent with the Berry-Esséen theorem, which roughly speaking gives a convergence rate of ${O(1/\sqrt{n})}$ uniformly in ${a,b}$ if we assume that ${X}$ has finite third moment. However there are still some quantitative versions of (1) which are not addressed by the Berry-Esséen theorem. For instance one may be interested in bounding the large deviation probabilities

$\displaystyle {\bf P}( |\frac{S_n - n \mu}{\sqrt{n} \sigma}| \geq \lambda ) \ \ \ \ \ (2)$

in the setting where ${\lambda}$ grows with ${n}$. Chebyshev’s inequality gives an upper bound of ${1/\lambda^2}$ for this quantity, but one can often do much better than this in practice. For instance, the central limit theorem (1) suggests that this probability should be bounded by something like ${O( e^{-\lambda^2/2})}$; however, this theorem only kicks in when ${n}$ is very large compared with ${\lambda}$. For instance, if one uses the Berry-Esséen theorem, one would need ${n}$ as large as ${e^{\lambda^2}}$ or so to reach the desired bound of ${O( e^{-\lambda^2/2})}$, even under the assumption of finite third moment. Basically, the issue is that convergence-in-distribution results, such as the central limit theorem, only really control the typical behaviour of statistics in ${\frac{S_n-n \mu}{\sqrt{n} \sigma}}$; they are much less effective at controlling the very rare outlier events in which the statistic strays far from its typical behaviour. Fortunately, there are large deviation inequalities (or concentration of measure inequalities) that do provide exponential type bounds for quantities such as (2), which are valid for both small and large values of ${n}$. A basic example of this is the Chernoff bound that made an appearance in Exercise 47 of Notes 4; here we give some further basic inequalities of this type, including versions of the Bennett and Hoeffding inequalities.

In the other direction, we can also look at the fine scale behaviour of the sums ${S_n}$ by trying to control probabilities such as

$\displaystyle {\bf P}( a \leq S_n \leq a+h ) \ \ \ \ \ (3)$

where ${h}$ is now bounded (but ${a}$ can grow with ${n}$). The central limit theorem predicts that this quantity should be roughly ${\frac{h}{\sqrt{2\pi n} \sigma} e^{-(a-n\mu)^2 / 2n \sigma^2}}$, but even if one is able to invoke the Berry-Esséen theorem, one cannot quite see this main term because it is dominated by the error term ${O(1/n^{1/2})}$ in Berry-Esséen. There is good reason for this: if for instance ${X}$ takes integer values, then ${S_n}$ also takes integer values, and ${{\bf P}( a \leq S_n \leq a+h )}$ can vanish when ${h}$ is less than ${1}$ and ${a}$ is slightly larger than an integer. However, this turns out to essentially be the only obstruction; if ${X}$ does not lie in a lattice such as ${{\bf Z}}$, then we can establish a local limit theorem controlling (3), and when ${X}$ does take values in a lattice like ${{\bf Z}}$, there is a discrete local limit theorem that controls probabilities such as ${{\bf P}(S_n = m)}$. Both of these limit theorems will be proven by the Fourier-analytic method used in the previous set of notes.

We also discuss other limit theorems in which the limiting distribution is something other than the normal distribution. Perhaps the most common example of these theorems is the Poisson limit theorems, in which one sums a large number of indicator variables (or approximate indicator variables), each of which is rarely non-zero, but which collectively add up to a random variable of medium-sized mean. In this case, it turns out that the limiting distribution should be a Poisson random variable; this again is an easy application of the Fourier method. Finally, we briefly discuss limit theorems for other stable laws than the normal distribution, which are suitable for summing random variables of infinite variance, such as the Cauchy distribution.

Finally, we mention a very important class of generalisations to the CLT (and to the variants of the CLT discussed in this post), in which the hypothesis of joint independence between the variables ${X_1,\dots,X_n}$ is relaxed, for instance one could assume only that the ${X_1,\dots,X_n}$ form a martingale. Many (though not all) of the proofs of the CLT extend to these more general settings, and this turns out to be important for many applications in which one does not expect joint independence. However, we will not discuss these generalisations in this course, as they are better suited for subsequent courses in this series when the theory of martingales, conditional expectation, and related tools are developed.

Let ${X_1,X_2,\dots}$ be iid copies of an absolutely integrable real scalar random variable ${X}$, and form the partial sums ${S_n := X_1 + \dots + X_n}$. As we saw in the last set of notes, the law of large numbers ensures that the empirical averages ${S_n/n}$ converge (both in probability and almost surely) to a deterministic limit, namely the mean ${\mu= {\bf E} X}$ of the reference variable ${X}$. Furthermore, under some additional moment hypotheses on the underlying variable ${X}$, we can obtain square root cancellation for the fluctuation ${\frac{S_n}{n} - \mu}$ of the empirical average from the mean. To simplify the calculations, let us first restrict to the case ${\mu=0, \sigma^2=1}$ of mean zero and variance one, thus

$\displaystyle {\bf E} X = 0$

and

$\displaystyle {\bf Var}(X) = {\bf E} X^2 = 1.$

Then, as computed in previous notes, the normalised fluctuation ${S_n/\sqrt{n}}$ also has mean zero and variance one:

$\displaystyle {\bf E} \frac{S_n}{\sqrt{n}} = 0$

$\displaystyle {\bf Var}(\frac{S_n}{\sqrt{n}}) = {\bf E} (\frac{S_n}{\sqrt{n}})^2 = 1.$

This and Chebyshev’s inequality already indicates that the “typical” size of ${S_n}$ is ${O(\sqrt{n})}$, thus for instance ${\frac{S_n}{\sqrt{n} \omega(n)}}$ goes to zero in probability for any ${\omega(n)}$ that goes to infinity as ${n \rightarrow \infty}$. If we also have a finite fourth moment ${{\bf E} |X|^4 < \infty}$, then the calculations of the previous notes also give a fourth moment estimate

$\displaystyle {\bf E} (\frac{S_n}{\sqrt{n}})^4 = 3 + O( \frac{{\bf E} |X|^4}{n} ).$

From this and the Paley-Zygmund inequality (Exercise 42 of Notes 1) we also get some lower bound for ${\frac{S_n}{\sqrt{n}}}$ of the form

$\displaystyle {\bf P}( |\frac{S_n}{\sqrt{n}}| \geq \varepsilon ) \geq \varepsilon$

for some absolute constant ${\varepsilon>0}$ and for ${n}$ sufficiently large; this indicates in particular that ${\frac{S_n \omega(n)}{\sqrt{n}}}$ does not converge in any reasonable sense to something finite for any ${\omega(n)}$ that goes to infinity.

The question remains as to what happens to the ratio ${S_n/\sqrt{n}}$ itself, without multiplying or dividing by any factor ${\omega(n)}$. A first guess would be that these ratios converge in probability or almost surely, but this is unfortunately not the case:

Proposition 1 Let ${X_1,X_2,\dots}$ be iid copies of an absolutely integrable real scalar random variable ${X}$ with mean zero, variance one, and finite fourth moment, and write ${S_n := X_1 + \dots + X_n}$. Then the random variables ${S_n/\sqrt{n}}$ do not converge in probability or almost surely to any limit, and neither does any subsequence of these random variables.

Proof: Suppose for contradiction that some sequence ${S_{n_j}/\sqrt{n_j}}$ converged in probability or almost surely to a limit ${Y}$. By passing to a further subsequence we may assume that the convergence is in the almost sure sense. Since all of the ${S_{n_j}/\sqrt{n_j}}$ have mean zero, variance one, and bounded fourth moment, Theorem 24 of Notes 1 implies that the limit ${Y}$ also has mean zero and variance one. On the other hand, ${Y}$ is a tail random variable and is thus almost surely constant by the Kolmogorov zero-one law from Notes 3. Since constants have variance zero, we obtain the required contradiction. $\Box$

Nevertheless there is an important limit for the ratio ${S_n/\sqrt{n}}$, which requires one to replace the notions of convergence in probability or almost sure convergence by the weaker concept of convergence in distribution.

Definition 2 (Vague convergence and convergence in distribution) Let ${R}$ be a locally compact Hausdorff topological space with the Borel ${\sigma}$-algebra. A sequence of finite measures ${\mu_n}$ on ${R}$ is said to converge vaguely to another finite measure ${\mu}$ if one has

$\displaystyle \int_R G(x)\ d\mu_n(x) \rightarrow \int_R G(x)\ d\mu(x)$

as ${n \rightarrow \infty}$ for all continuous compactly supported functions ${G: R \rightarrow {\bf R}}$. (Vague convergence is also known as weak convergence, although strictly speaking the terminology weak-* convergence would be more accurate.) A sequence of random variables ${X_n}$ taking values in ${R}$ is said to converge in distribution (or converge weakly or converge in law) to another random variable ${X}$ if the distributions ${\mu_{X_n}}$ converge vaguely to the distribution ${\mu_X}$, or equivalently if

$\displaystyle {\bf E}G(X_n) \rightarrow {\bf E} G(X)$

as ${n \rightarrow \infty}$ for all continuous compactly supported functions ${G: R \rightarrow {\bf R}}$.

One could in principle try to extend this definition beyond the locally compact Hausdorff setting, but certain pathologies can occur when doing so (e.g. failure of the Riesz representation theorem), and we will never need to consider vague convergence in spaces that are not locally compact Hausdorff, so we restrict to this setting for simplicity.

Note that the notion of convergence in distribution depends only on the distribution of the random variables involved. One consequence of this is that convergence in distribution does not produce unique limits: if ${X_n}$ converges in distribution to ${X}$, and ${Y}$ has the same distribution as ${X}$, then ${X_n}$ also converges in distribution to ${Y}$. However, limits are unique up to equivalence in distribution (this is a consequence of the Riesz representation theorem, discussed for instance in this blog post). As a consequence of the insensitivity of convergence in distribution to equivalence in distribution, we may also legitimately talk about convergence of distribution of a sequence of random variables ${X_n}$ to another random variable ${X}$ even when all the random variables ${X_1,X_2,\dots}$ and ${X}$ involved are being modeled by different probability spaces (e.g. each ${X_n}$ is modeled by ${\Omega_n}$, and ${X}$ is modeled by ${\Omega}$, with no coupling presumed between these spaces). This is in contrast to the stronger notions of convergence in probability or almost sure convergence, which require all the random variables to be modeled by a common probability space. Also, by an abuse of notation, we can say that a sequence ${X_n}$ of random variables converges in distribution to a probability measure ${\mu}$, when ${\mu_{X_n}}$ converges vaguely to ${\mu}$. Thus we can talk about a sequence of random variables converging in distribution to a uniform distribution, a gaussian distribution, etc..

From the dominated convergence theorem (available for both convergence in probability and almost sure convergence) we see that convergence in probability or almost sure convergence implies convergence in distribution. The converse is not true, due to the insensitivity of convergence in distribution to equivalence in distribution; for instance, if ${X_1,X_2,\dots}$ are iid copies of a non-deterministic scalar random variable ${X}$, then the ${X_n}$ trivially converge in distribution to ${X}$, but will not converge in probability or almost surely (as one can see from the zero-one law). However, there are some partial converses that relate convergence in distribution to convergence in probability; see Exercise 10 below.

Remark 3 The notion of convergence in distribution is somewhat similar to the notion of convergence in the sense of distributions that arises in distribution theory (discussed for instance in this previous blog post), however strictly speaking the two notions of convergence are distinct and should not be confused with each other, despite the very similar names.

The notion of convergence in distribution simplifies in the case of real scalar random variables:

Proposition 4 Let ${X_1,X_2,\dots}$ be a sequence of scalar random variables, and let ${X}$ be another scalar random variable. Then the following are equivalent:

• (i) ${X_n}$ converges in distribution to ${X}$.
• (ii) ${F_{X_n}(t)}$ converges to ${F_X(t)}$ for each continuity point ${t}$ of ${F_X}$ (i.e. for all real numbers ${t \in {\bf R}}$ at which ${F_X}$ is continuous). Here ${F_X(t) := {\bf P}(X \leq t)}$ is the cumulative distribution function of ${X}$.

Proof: First suppose that ${X_n}$ converges in distribution to ${X}$, and ${F_X}$ is continuous at ${t}$. For any ${\varepsilon > 0}$, one can find a ${\delta}$ such that

$\displaystyle F_X(t) - \varepsilon \leq F_X(t') \leq F_X(t) + \varepsilon$

for every ${t' \in [t-\delta,t+\delta]}$. One can also find an ${N}$ larger than ${|t|+\delta}$ such that ${F_X(-N) \leq \varepsilon}$ and ${F_X(N) \geq 1-\varepsilon}$. Thus

$\displaystyle {\bf P} (|X| \geq N ) = O(\varepsilon)$

and

$\displaystyle {\bf P} (|X - t| \leq \delta ) = O(\varepsilon).$

Let ${G: {\bf R} \rightarrow [0,1]}$ be a continuous function supported on ${[-2N, t]}$ that equals ${1}$ on ${[-N, t-\delta]}$. Then by the above discussion we have

$\displaystyle {\bf E} G(X) = F_X(t) + O(\varepsilon)$

and hence

$\displaystyle {\bf E} G(X_n) = F_X(t) + O(\varepsilon)$

for large enough ${n}$. In particular

$\displaystyle {\bf P}( X_n \leq t ) \geq F_X(t) - O(\varepsilon).$

A similar argument, replacing ${G}$ with a continuous function supported on ${[t,2N]}$ that equals ${1}$ on ${[t+\delta,N]}$ gives

$\displaystyle {\bf P}( X_n > t ) \geq 1 - F_X(t) - O(\varepsilon)$

for ${n}$ large enough. Putting the two estimates together gives

$\displaystyle F_{X_n}(t) = F_X(t) + O(\varepsilon)$

for ${n}$ large enough; sending ${\varepsilon \rightarrow 0}$, we obtain the claim.

Conversely, suppose that ${F_{X_n}(t)}$ converges to ${F_X(t)}$ at every continuity point ${t}$ of ${F_X}$. Let ${G: {\bf R} \rightarrow {\bf R}}$ be a continuous compactly supported function, then it is uniformly continuous. As ${F_X}$ is monotone increasing, it can only have countably many points of discontinuity. From these two facts one can find, for any ${\varepsilon>0}$, a simple function ${G_\varepsilon(t) = \sum_{i=1}^n c_i 1_{(t_i,t_{i+1}]}}$ for some ${t_1 < \dots < t_n}$ that are points of continuity of ${F_X}$, and real numbers ${c_i}$, such that ${|G(t) - G_\varepsilon(t)| \leq \varepsilon}$ for all ${t}$. Thus

$\displaystyle {\bf E} G(X_n) = {\bf E} G_\varepsilon(X_n) + O(\varepsilon)$

$\displaystyle = \sum_{i=1}^n c_i(F_{X_n}(t_{i+1}) - F_{X_n}(t)) + O(\varepsilon).$

Similarly for ${X_n}$ replaced by ${X}$. Subtracting and taking limit superior, we conclude that

$\displaystyle \limsup_{n \rightarrow \infty} |{\bf E} G(X_n) - {\bf E} G(X)| = O(\varepsilon),$

and on sending ${\varepsilon \rightarrow 0}$, we obtain that ${X_n}$ converges in distribution to ${X}$ as claimed. $\Box$

The restriction to continuity points of ${t}$ is necessary. Consider for instance the deterministic random variables ${X_n = 1/n}$, then ${X_n}$ converges almost surely (and hence in distribution) to ${0}$, but ${F_{X_n}(0) = 0}$ does not converge to ${F_X(0)=1}$.

Example 5 For any natural number ${n}$, let ${X_n}$ be a discrete random variable drawn uniformly from the finite set ${\{0/n, 1/n, \dots, (n-1)/n\}}$, and let ${X}$ be the continuous random variable drawn uniformly from ${[0,1]}$. Then ${X_n}$ converges in distribution to ${X}$. Thus we see that a continuous random variable can emerge as the limit of discrete random variables.

Example 6 For any natural number ${n}$, let ${X_n}$ be a continuous random variable drawn uniformly from ${[0,1/n]}$, then ${X_n}$ converges in distribution to the deterministic real number ${0}$. Thus we see that discrete (or even deterministic) random variables can emerge as the limit of continuous random variables.

Exercise 7 (Portmanteau theorem) Show that the properties (i) and (ii) in Proposition 4 are also equivalent to the following three statements:

• (iii) One has ${\limsup_{n \rightarrow \infty} {\bf P}( X_n \in K ) \leq {\bf P}(X \in K)}$ for all closed sets ${K \subset {\bf R}}$.
• (iv) One has ${\liminf_{n \rightarrow \infty} {\bf P}( X_n \in U ) \geq {\bf P}(X \in U)}$ for all open sets ${U \subset {\bf R}}$.
• (v) For any Borel set ${E \subset {\bf R}}$ whose topological boundary ${\partial E}$ is such that ${{\bf P}(X \in \partial E) = 0}$, one has ${\lim_{n \rightarrow \infty} {\bf P}(X_n \in E) = {\bf P}(X \in E)}$.

(Note: to prove this theorem, you may wish to invoke Urysohn’s lemma. To deduce (iii) from (i), you may wish to start with the case of compact ${K}$.)

We can now state the famous central limit theorem:

Theorem 8 (Central limit theorem) Let ${X_1,X_2,\dots}$ be iid copies of a scalar random variable ${X}$ of finite mean ${\mu := {\bf E} X}$ and finite non-zero variance ${\sigma^2 := {\bf Var}(X)}$. Let ${S_n := X_1 + \dots + X_n}$. Then the random variables ${\frac{\sqrt{n}}{\sigma} (\frac{S_n}{n} - \mu)}$ converges in distribution to a random variable with the standard normal distribution ${N(0,1)}$ (that is to say, a random variable with probability density function ${x \mapsto \frac{1}{\sqrt{2\pi}} e^{-x^2/2}}$). Thus, by abuse of notation

$\displaystyle \frac{\sqrt{n}}{\sigma} (\frac{S_n}{n} - \mu) \rightarrow N(0,1).$

In the normalised case ${\mu=0, \sigma^2=1}$ when ${X}$ has mean zero and unit variance, this simplifies to

$\displaystyle \frac{S_n}{\sqrt{n}} \rightarrow N(0,1).$

Using Proposition 4 (and the fact that the cumulative distribution function associated to ${N(0,1)}$ is continuous, the central limit theorem is equivalent to asserting that

$\displaystyle {\bf P}( \frac{\sqrt{n}}{\sigma} (\frac{S_n}{n} - \mu) \leq t ) \rightarrow \frac{1}{\sqrt{2\pi}} \int_{-\infty}^t e^{-x^2/2}\ dx$

as ${n \rightarrow \infty}$ for any ${t \in {\bf R}}$, or equivalently that

$\displaystyle {\bf P}( a \leq \frac{\sqrt{n}}{\sigma} (\frac{S_n}{n} - \mu) \leq b ) \rightarrow \frac{1}{\sqrt{2\pi}} \int_{a}^b e^{-x^2/2}\ dx.$

Informally, one can think of the central limit theorem as asserting that ${S_n}$ approximately behaves like it has distribution ${N( n \mu, n \sigma^2 )}$ for large ${n}$, where ${N(\mu,\sigma^2)}$ is the normal distribution with mean ${\mu}$ and variance ${\sigma^2}$, that is to say the distribution with probability density function ${x \mapsto \frac{1}{\sqrt{2\pi} \sigma} e^{-(x-\mu)^2/2\sigma^2}}$. The integrals ${\frac{1}{\sqrt{2\pi}} \int_{-\infty}^t e^{-x^2/2}\ dx}$ can be written in terms of the error function ${\hbox{erf}}$ as ${\frac{1}{2} + \frac{1}{2} \hbox{erf}(t/\sqrt{2})}$.

The central limit theorem is a basic example of the universality phenomenon in probability – many statistics involving a large system of many independent (or weakly dependent) variables (such as the normalised sums ${\frac{\sqrt{n}}{\sigma}(\frac{S_n}{n}-\mu)}$) end up having a universal asymptotic limit (in this case, the normal distribution), regardless of the precise makeup of the underlying random variable ${X}$ that comprised that system. Indeed, the universality of the normal distribution is such that it arises in many other contexts than the fluctuation of iid random variables; the central limit theorem is merely the first place in probability theory where it makes a prominent appearance.

We will give several proofs of the central limit theorem in these notes; each of these proofs has their advantages and disadvantages, and can each extend to prove many further results beyond the central limit theorem. We first give Lindeberg’s proof of the central limit theorem, based on exchanging (or swapping) each component ${X_1,\dots,X_n}$ of the sum ${S_n}$ in turn. This proof gives an accessible explanation as to why there should be a universal limit for the central limit theorem; one then computes directly with gaussians to verify that it is the normal distribution which is the universal limit. Our second proof is the most popular one taught in probability texts, namely the Fourier-analytic proof based around the concept of the characteristic function ${t \mapsto {\bf E} e^{itX}}$ of a real random variable ${X}$. Thanks to the powerful identities and other results of Fourier analysis, this gives a quite short and direct proof of the central limit theorem, although the arguments may seem rather magical to readers who are not already familiar with Fourier methods. Finally, we give a proof based on the moment method, in the spirit of the arguments in the previous notes; this argument is more combinatorial, but is straightforward and is particularly robust, in particular being well equipped to handle some dependencies between components; we will illustrate this by proving the Erdos-Kac law in number theory by this method. Some further discussion of the central limit theorem (including some further proofs, such as one based on Stein’s method) can be found in this blog post. Some further variants of the central limit theorem, such as local limit theorems, stable laws, and large deviation inequalities, will be discussed in the next (and final) set of notes.

The following exercise illustrates the power of the central limit theorem, by establishing combinatorial estimates which would otherwise require the use of Stirling’s formula to establish.

Exercise 9 (De Moivre-Laplace theorem) Let ${X}$ be a Bernoulli random variable, taking values in ${\{0,1\}}$ with ${{\bf P}(X=0)={\bf P}(X=1)=1/2}$, thus ${X}$ has mean ${1/2}$ and variance ${1/4}$. Let ${X_1,X_2,\dots}$ be iid copies of ${X}$, and write ${S_n := X_1+\dots+X_n}$.

• (i) Show that ${S_n}$ takes values in ${\{0,\dots,n\}}$ with ${{\bf P}(S_n=i) = \frac{1}{2^n} \binom{n}{i}}$. (This is an example of a binomial distribution.)
• (ii) Assume Stirling’s formula

$\displaystyle n! = (1+o(1)) \sqrt{2\pi n} n^n e^{-n} \ \ \ \ \ (1)$

where ${o(1)}$ is a function of ${n}$ that goes to zero as ${n \rightarrow \infty}$. (A proof of this formula may be found in this previous blog post.) Using this formula, and without using the central limit theorem, show that

$\displaystyle {\bf P}( a \leq 2\sqrt{n} (\frac{S_n}{n} - \frac{1}{2}) \leq b ) \rightarrow \frac{1}{\sqrt{2\pi}} \int_{a}^b e^{-x^2/2}\ dx$

as ${n \rightarrow \infty}$ for any fixed real numbers ${a.

The above special case of the central limit theorem was first established by de Moivre and Laplace.

We close this section with some basic facts about convergence of distribution that will be useful in the sequel.

Exercise 10 Let ${X_1,X_2,\dots}$, ${Y_1,Y_2,\dots}$ be sequences of real random variables, and let ${X,Y}$ be further real random variables.

• (i) If ${X}$ is deterministic, show that ${X_n}$ converges in distribution to ${X}$ if and only if ${X_n}$ converges in probability to ${X}$.
• (ii) Suppose that ${X_n}$ is independent of ${Y_n}$ for each ${n}$, and ${X}$ independent of ${Y}$. Show that ${X_n+iY_n}$ converges in distribution to ${X+iY}$ if and only if ${X_n}$ converges in distribution to ${X}$ and ${Y_n}$ converges in distribution to ${Y}$. (The shortest way to prove this is by invoking the Stone-Weierstrass theorem, but one can also proceed by proving some version of Proposition 4.) What happens if the independence hypothesis is dropped?
• (iii) If ${X_n}$ converges in distribution to ${X}$, show that for every ${\varepsilon>0}$ there exists ${K>0}$ such that ${{\bf P}( |X_n| \geq K ) < \varepsilon}$ for all sufficiently large ${n}$. (That is to say, ${X_n}$ is a tight sequence of random variables.)
• (iv) Show that ${X_n}$ converges in distribution to ${X}$ if and only if, after extending the probability space model if necessary, one can find copies ${Z_1,Z_2,\dots}$ and ${Z}$ of ${X_1,X_2,\dots}$ and ${X}$ respectively such that ${Z_n}$ converges almost surely to ${Z}$. (Hint: use the Skorohod representation, Exercise 29 of Notes 0.)
• (v) If ${X_1,X_2,\dots}$ converges in distribution to ${X}$, and ${F: {\bf R} \rightarrow {\bf R}}$ is continuous, show that ${F(X_1),F(X_2),\dots}$ converges in distribution to ${F(X)}$. Generalise this claim to the case when ${X}$ takes values in an arbitrary locally compact Hausdorff space.
• (vi) (Slutsky’s theorem) If ${X_n}$ converges in distribution to ${X}$, and ${Y_n}$ converges in probability to a deterministic limit ${Y}$, show that ${X_n+Y_n}$ converges in distribution to ${X+Y}$, and ${X_n Y_n}$ converges in distribution to ${XY}$. (Hint: either use (iv), or else use (iii) to control some error terms.) This statement combines particularly well with (i). What happens if ${Y}$ is not assumed to be deterministic?
• (vii) (Fatou lemma) If ${G: {\bf R} \rightarrow [0,+\infty)}$ is continuous, and ${X_n}$ converges in distribution to ${X}$, show that ${\liminf_{n \rightarrow \infty} {\bf E} G(X_n) \geq {\bf E} G(X)}$.
• (viii) (Bounded convergence) If ${G: {\bf R} \rightarrow {\bf R}}$ is continuous and bounded, and ${X_n}$ converges in distribution to ${X}$, show that ${\lim_{n \rightarrow \infty} {\bf E} G(X_n) = {\bf E} G(X)}$.
• (ix) (Dominated convergence) If ${X_n}$ converges in distribution to ${X}$, and there is an absolutely integrable ${Y}$ such that ${|X_n| \leq Y}$ almost surely for all ${n}$, show that ${\lim_{n \rightarrow \infty} {\bf E} X_n = {\bf E} X}$.

For future reference we also mention (but will not prove) Prokhorov’s theorem that gives a partial converse to part (iii) of the above exercise:

Theorem 11 (Prokhorov’s theorem) Let ${X_1,X_2,\dots}$ be a sequence of real random variables which is tight (that is, for every ${\varepsilon>0}$ there exists ${K>0}$ such that ${{\bf P}(|X_n| \geq K) < \varepsilon}$ for all sufficiently large ${n}$). Then there exists a subsequence ${X_{n_j}}$ which converges in distribution to some random variable ${X}$ (which may possibly be modeled by a different probability space model than the ${X_1,X_2,\dots}$.)

The proof of this theorem relies on the Riesz representation theorem, and is beyond the scope of this course; but see for instance Exercise 29 of this previous blog post. (See also the closely related Helly selection theorem, covered in Exercise 30 of the same post.)

In the previous set of notes, we constructed the measure-theoretic notion of the Lebesgue integral, and used this to set up the probabilistic notion of expectation on a rigorous footing. In this set of notes, we will similarly construct the measure-theoretic concept of a product measure (restricting to the case of probability measures to avoid unnecessary techncialities), and use this to set up the probabilistic notion of independence on a rigorous footing. (To quote Durrett: “measure theory ends and probability theory begins with the definition of independence.”) We will be able to take virtually any collection of random variables (or probability distributions) and couple them together to be independent via the product measure construction, though for infinite products there is the slight technicality (a requirement of the Kolmogorov extension theorem) that the random variables need to range in standard Borel spaces. This is not the only way to couple together such random variables, but it is the simplest and the easiest to compute with in practice, as we shall see in the next few sets of notes.

In Notes 0, we introduced the notion of a measure space ${\Omega = (\Omega, {\mathcal F}, \mu)}$, which includes as a special case the notion of a probability space. By selecting one such probability space ${(\Omega,{\mathcal F},\mu)}$ as a sample space, one obtains a model for random events and random variables, with random events ${E}$ being modeled by measurable sets ${E_\Omega}$ in ${{\mathcal F}}$, and random variables ${X}$ taking values in a measurable space ${R}$ being modeled by measurable functions ${X_\Omega: \Omega \rightarrow R}$. We then defined some basic operations on these random events and variables:

• Given events ${E,F}$, we defined the conjunction ${E \wedge F}$, the disjunction ${E \vee F}$, and the complement ${\overline{E}}$. For countable families ${E_1,E_2,\dots}$ of events, we similarly defined ${\bigwedge_{n=1}^\infty E_n}$ and ${\bigvee_{n=1}^\infty E_n}$. We also defined the empty event ${\emptyset}$ and the sure event ${\overline{\emptyset}}$, and what it meant for two events to be equal.
• Given random variables ${X_1,\dots,X_n}$ in ranges ${R_1,\dots,R_n}$ respectively, and a measurable function ${F: R_1 \times \dots \times R_n \rightarrow S}$, we defined the random variable ${F(X_1,\dots,X_n)}$ in range ${S}$. (As the special case ${n=0}$ of this, every deterministic element ${s}$ of ${S}$ was also a random variable taking values in ${S}$.) Given a relation ${P: R_1 \times \dots \times R_n \rightarrow \{\hbox{true}, \hbox{false}\}}$, we similarly defined the event ${P(X_1,\dots,X_n)}$. Conversely, given an event ${E}$, we defined the indicator random variable ${1_E}$. Finally, we defined what it meant for two random variables to be equal.
• Given an event ${E}$, we defined its probability ${{\bf P}(E)}$.

These operations obey various axioms; for instance, the boolean operations on events obey the axioms of a Boolean algebra, and the probabilility function ${E \mapsto {\bf P}(E)}$ obeys the Kolmogorov axioms. However, we will not focus on the axiomatic approach to probability theory here, instead basing the foundations of probability theory on the sample space models as discussed in Notes 0. (But see this previous post for a treatment of one such axiomatic approach.)

It turns out that almost all of the other operations on random events and variables we need can be constructed in terms of the above basic operations. In particular, this allows one to safely extend the sample space in probability theory whenever needed, provided one uses an extension that respects the above basic operations; this is an important operation when one needs to add new sources of randomness to an existing system of events and random variables, or to couple together two separate such systems into a joint system that extends both of the original systems. We gave a simple example of such an extension in the previous notes, but now we give a more formal definition:

Definition 1 Suppose that we are using a probability space ${\Omega = (\Omega, {\mathcal F}, \mu)}$ as the model for a collection of events and random variables. An extension of this probability space is a probability space ${\Omega' = (\Omega', {\mathcal F}', \mu')}$, together with a measurable map ${\pi: \Omega' \rightarrow \Omega}$ (sometimes called the factor map) which is probability-preserving in the sense that

$\displaystyle \mu'( \pi^{-1}(E) ) = \mu(E) \ \ \ \ \ (1)$

for all ${E \in {\mathcal F}}$. (Caution: this does not imply that ${\mu(\pi(F)) = \mu'(F)}$ for all ${F \in {\mathcal F}'}$ – why not?)

An event ${E}$ which is modeled by a measurable subset ${E_\Omega}$ in the sample space ${\Omega}$, will be modeled by the measurable set ${E_{\Omega'} := \pi^{-1}(E_\Omega)}$ in the extended sample space ${\Omega'}$. Similarly, a random variable ${X}$ taking values in some range ${R}$ that is modeled by a measurable function ${X_\Omega: \Omega \rightarrow R}$ in ${\Omega}$, will be modeled instead by the measurable function ${X_{\Omega'} := X_\Omega \circ \pi}$ in ${\Omega'}$. We also allow the extension ${\Omega'}$ to model additional events and random variables that were not modeled by the original sample space ${\Omega}$ (indeed, this is one of the main reasons why we perform extensions in probability in the first place).

Thus, for instance, the sample space ${\Omega'}$ in Example 3 of the previous post is an extension of the sample space ${\Omega}$ in that example, with the factor map ${\pi: \Omega' \rightarrow \Omega}$ given by the first coordinate projection ${\pi(i,j) := i}$. One can verify that all of the basic operations on events and random variables listed above are unaffected by the above extension (with one caveat, see remark below). For instance, the conjunction ${E \wedge F}$ of two events can be defined via the original model ${\Omega}$ by the formula

$\displaystyle (E \wedge F)_\Omega := E_\Omega \cap F_\Omega$

or via the extension ${\Omega'}$ via the formula

$\displaystyle (E \wedge F)_{\Omega'} := E_{\Omega'} \cap F_{\Omega'}.$

The two definitions are consistent with each other, thanks to the obvious set-theoretic identity

$\displaystyle \pi^{-1}( E_\Omega \cap F_\Omega ) = \pi^{-1}(E_\Omega) \cap \pi^{-1}(F_\Omega).$

Similarly, the assumption (1) is precisely what is needed to ensure that the probability ${\mathop{\bf P}(E)}$ of an event remains unchanged when one replaces a sample space model with an extension. We leave the verification of preservation of the other basic operations described above under extension as exercises to the reader.

Remark 2 There is one minor exception to this general rule if we do not impose the additional requirement that the factor map ${\pi}$ is surjective. Namely, for non-surjective ${\pi}$, it can become possible that two events ${E, F}$ are unequal in the original sample space model, but become equal in the extension (and similarly for random variables), although the converse never happens (events that are equal in the original sample space always remain equal in the extension). For instance, let ${\Omega}$ be the discrete probability space ${\{a,b\}}$ with ${p_a=1}$ and ${p_b=0}$, and let ${\Omega'}$ be the discrete probability space ${\{ a'\}}$ with ${p'_{a'}=1}$, and non-surjective factor map ${\pi: \Omega' \rightarrow \Omega}$ defined by ${\pi(a') := a}$. Then the event modeled by ${\{b\}}$ in ${\Omega}$ is distinct from the empty event when viewed in ${\Omega}$, but becomes equal to that event when viewed in ${\Omega'}$. Thus we see that extending the sample space by a non-surjective factor map can identify previously distinct events together (though of course, being probability preserving, this can only happen if those two events were already almost surely equal anyway). This turns out to be fairly harmless though; while it is nice to know if two given events are equal, or if they differ by a non-null event, it is almost never useful to know that two events are unequal if they are already almost surely equal. Alternatively, one can add the additional requirement of surjectivity in the definition of an extension, which is also a fairly harmless constraint to impose (this is what I chose to do in this previous set of notes).

Roughly speaking, one can define probability theory as the study of those properties of random events and random variables that are model-independent in the sense that they are preserved by extensions. For instance, the cardinality ${|E_\Omega|}$ of the model ${E_\Omega}$ of an event ${E}$ is not a concept within the scope of probability theory, as it is not preserved by extensions: continuing Example 3 from Notes 0, the event ${E}$ that a die roll ${X}$ is even is modeled by a set ${E_\Omega = \{2,4,6\}}$ of cardinality ${3}$ in the original sample space model ${\Omega}$, but by a set ${E_{\Omega'} = \{2,4,6\} \times \{1,2,3,4,5,6\}}$ of cardinality ${18}$ in the extension. Thus it does not make sense in the context of probability theory to refer to the “cardinality of an event ${E}$“.

On the other hand, the supremum ${\sup_n X_n}$ of a collection of random variables ${X_n}$ in the extended real line ${[-\infty,+\infty]}$ is a valid probabilistic concept. This can be seen by manually verifying that this operation is preserved under extension of the sample space, but one can also see this by defining the supremum in terms of existing basic operations. Indeed, note from Exercise 24 of Notes 0 that a random variable ${X}$ in the extended real line is completely specified by the threshold events ${(X \leq t)}$ for ${t \in {\bf R}}$; in particular, two such random variables ${X,Y}$ are equal if and only if the events ${(X \leq t)}$ and ${(Y \leq t)}$ are surely equal for all ${t}$. From the identity

$\displaystyle (\sup_n X_n \leq t) = \bigwedge_{n=1}^\infty (X_n \leq t)$

we thus see that one can completely specify ${\sup_n X_n}$ in terms of ${X_n}$ using only the basic operations provided in the above list (and in particular using the countable conjunction ${\bigwedge_{n=1}^\infty}$.) Of course, the same considerations hold if one replaces supremum, by infimum, limit superior, limit inferior, or (if it exists) the limit.

In this set of notes, we will define some further important operations on scalar random variables, in particular the expectation of these variables. In the sample space models, expectation corresponds to the notion of integration on a measure space. As we will need to use both expectation and integration in this course, we will thus begin by quickly reviewing the basics of integration on a measure space, although we will then translate the key results of this theory into probabilistic language.

As the finer details of the Lebesgue integral construction are not the core focus of this probability course, some of the details of this construction will be left to exercises. See also Chapter 1 of Durrett, or these previous blog notes, for a more detailed treatment.

Starting this week, I will be teaching an introductory graduate course (Math 275A) on probability theory here at UCLA. While I find myself using probabilistic methods routinely nowadays in my research (for instance, the probabilistic concept of Shannon entropy played a crucial role in my recent paper on the Chowla and Elliott conjectures, and random multiplicative functions similarly played a central role in the paper on the Erdos discrepancy problem), this will actually be the first time I will be teaching a course on probability itself (although I did give a course on random matrix theory some years ago that presumed familiarity with graduate-level probability theory). As such, I will be relying primarily on an existing textbook, in this case Durrett’s Probability: Theory and Examples. I still need to prepare lecture notes, though, and so I thought I would continue my practice of putting my notes online, although in this particular case they will be less detailed or complete than with other courses, as they will mostly be focusing on those topics that are not already comprehensively covered in the text of Durrett. Below the fold are my first such set of notes, concerning the classical measure-theoretic foundations of probability. (I wrote on these foundations also in this previous blog post, but in that post I already assumed that the reader was familiar with measure theory and basic probability, whereas in this course not every student will have a strong background in these areas.)

Note: as this set of notes is primarily concerned with foundational issues, it will contain a large number of pedantic (and nearly trivial) formalities and philosophical points. We dwell on these technicalities in this set of notes primarily so that they are out of the way in later notes, when we work with the actual mathematics of probability, rather than on the supporting foundations of that mathematics. In particular, the excessively formal and philosophical language in this set of notes will not be replicated in later notes.

The equidistribution theorem asserts that if ${\alpha \in {\bf R}/{\bf Z}}$ is an irrational phase, then the sequence ${(n\alpha)_{n=1}^\infty}$ is equidistributed on the unit circle, or equivalently that

$\displaystyle \frac{1}{N} \sum_{n=1}^N F(n\alpha) \rightarrow \int_{{\bf R}/{\bf Z}} F(x)\ dx$

for any continuous (or equivalently, for any smooth) function ${F: {\bf R}/{\bf Z} \rightarrow {\bf C}}$. By approximating ${F}$ uniformly by a Fourier series, this claim is equivalent to that of showing that

$\displaystyle \frac{1}{N} \sum_{n=1}^N e(hn\alpha) \rightarrow 0$

for any non-zero integer ${h}$ (where ${e(x) := e^{2\pi i x}}$), which is easily verified from the irrationality of ${\alpha}$ and the geometric series formula. Conversely, if ${\alpha}$ is rational, then clearly ${\frac{1}{N} \sum_{n=1}^N e(hn\alpha)}$ fails to go to zero when ${h}$ is a multiple of the denominator of ${\alpha}$.

One can then ask for more quantitative information about the decay of exponential sums of ${\frac{1}{N} \sum_{n=1}^N e(n \alpha)}$, or more generally on exponential sums of the form ${\frac{1}{|Q|} \sum_{n \in Q} e(P(n))}$ for an arithmetic progression ${Q}$ (in this post all progressions are understood to be finite) and a polynomial ${P: Q \rightarrow \/{\bf Z}}$. It will be convenient to phrase such information in the form of an inverse theorem, describing those phases for which the exponential sum is large. Indeed, we have

Lemma 1 (Geometric series formula, inverse form) Let ${Q \subset {\bf Z}}$ be an arithmetic progression of length at most ${N}$ for some ${N \geq 1}$, and let ${P(n) = n \alpha + \beta}$ be a linear polynomial for some ${\alpha,\beta \in {\bf R}/{\bf Z}}$. If

$\displaystyle \frac{1}{N} |\sum_{n \in Q} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there exists a subprogression ${Q'}$ of ${Q}$ of size ${|Q'| \gg \delta^2 N}$ such that ${P(n)}$ varies by at most ${\delta}$ on ${Q'}$ (that is to say, ${P(n)}$ lies in a subinterval of ${{\bf R}/{\bf Z}}$ of length at most ${\delta}$).

Proof: By a linear change of variable we may assume that ${Q}$ is of the form ${\{0,\dots,N'-1\}}$ for some ${N' \geq 1}$. We may of course assume that ${\alpha}$ is non-zero in ${{\bf R}/{\bf Z}}$, so that ${\|\alpha\|_{{\bf R}/{\bf Z}} > 0}$ (${\|x\|_{{\bf R}/{\bf Z}}}$ denotes the distance from ${x}$ to the nearest integer). From the geometric series formula we see that

$\displaystyle |\sum_{n \in Q} e(P(n))| \leq \frac{2}{|e(\alpha) - 1|} \ll \frac{1}{\|\alpha\|_{{\bf R}/{\bf Z}}},$

and so ${\|\alpha\|_{{\bf R}/{\bf Z}} \ll \frac{1}{\delta N}}$. Setting ${Q' := \{ n \in Q: n \leq c \delta^2 N \}}$ for some sufficiently small absolute constant ${c}$, we obtain the claim. $\Box$

Thus, in order for a linear phase ${P(n)}$ to fail to be equidistributed on some long progression ${Q}$, ${P}$ must in fact be almost constant on large piece of ${Q}$.

As is well known, this phenomenon generalises to higher order polynomials. To achieve this, we need two elementary additional lemmas. The first relates the exponential sums of ${P}$ to the exponential sums of its “first derivatives” ${n \mapsto P(n+h)-P(n)}$.

Lemma 2 (Van der Corput lemma, inverse form) Let ${Q \subset {\bf Z}}$ be an arithmetic progression of length at most ${N}$, and let ${P: Q \rightarrow {\bf R}/{\bf Z}}$ be an arbitrary function such that

$\displaystyle \frac{1}{N} |\sum_{n \in Q} e(P(n))| \geq \delta \ \ \ \ \ (1)$

for some ${\delta > 0}$. Then, for ${\gg \delta^2 N}$ integers ${h \in Q-Q}$, there exists a subprogression ${Q_h}$ of ${Q}$, of the same spacing as ${Q}$, such that

$\displaystyle \frac{1}{N} |\sum_{n \in Q_h} e(P(n+h)-P(n))| \gg \delta^2. \ \ \ \ \ (2)$

Proof: Squaring (1), we see that

$\displaystyle \sum_{n,n' \in Q} e(P(n') - P(n)) \geq \delta^2 N^2.$

We write ${n' = n+h}$ and conclude that

$\displaystyle \sum_{h \in Q-Q} \sum_{n \in Q_h} e( P(n+h)-P(n) ) \geq \delta^2 N^2$

where ${Q_h := Q \cap (Q-h)}$ is a subprogression of ${Q}$ of the same spacing. Since ${\sum_{n \in Q_h} e( P(n+h)-P(n) ) = O(N)}$, we conclude that

$\displaystyle |\sum_{n \in Q_h} e( P(n+h)-P(n) )| \gg \delta^2 N$

for ${\gg \delta^2 N}$ values of ${h}$ (this can be seen, much like the pigeonhole principle, by arguing via contradiction for a suitable choice of implied constants). The claim follows. $\Box$

The second lemma (which we recycle from this previous blog post) is a variant of the equidistribution theorem.

Lemma 3 (Vinogradov lemma) Let ${I \subset [-N,N] \cap {\bf Z}}$ be an interval for some ${N \geq 1}$, and let ${\theta \in{\bf R}/{\bf Z}}$ be such that ${\|n\theta\|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ for at least ${\delta N}$ values of ${n \in I}$, for some ${0 < \varepsilon, \delta < 1}$. Then either

$\displaystyle N < \frac{2}{\delta}$

or

$\displaystyle \varepsilon > 10^{-2} \delta$

or else there is a natural number ${q \leq 2/\delta}$ such that

$\displaystyle \| q \theta \|_{{\bf R}/{\bf Z}} \ll \frac{\varepsilon}{\delta N}.$

Proof: We may assume that ${N \geq \frac{2}{\delta}}$ and ${\varepsilon \leq 10^{-2} \delta}$, since we are done otherwise. Then there are at least two ${n \in I}$ with ${\|n \theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$, and by the pigeonhole principle we can find ${n_1 < n_2}$ in ${Q}$ with ${\|n_1 \theta \|_{{\bf R}/{\bf Z}}, \|n_2 \theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ and ${n_2-n_1 \leq \frac{2}{\delta}}$. By the triangle inequality, we conclude that there exists at least one natural number ${q \leq \frac{2}{\delta}}$ for which

$\displaystyle \| q \theta \|_{{\bf R}/{\bf Z}} \leq 2\varepsilon.$

We take ${q}$ to be minimal amongst all such natural numbers, then we see that there exists ${a}$ coprime to ${q}$ and ${|\kappa| \leq 2\varepsilon}$ such that

$\displaystyle \theta = \frac{a}{q} + \frac{\kappa}{q}. \ \ \ \ \ (3)$

If ${\kappa=0}$ then we are done, so suppose that ${\kappa \neq 0}$. Suppose that ${n < m}$ are elements of ${I}$ such that ${\|n\theta \|_{{\bf R}/{\bf Z}}, \|m\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ and ${m-n \leq \frac{1}{10 \kappa}}$. Writing ${m-n = qk + r}$ for some ${0 \leq r < q}$, we have

$\displaystyle \| (m-n) \theta \|_{{\bf R}/{\bf Z}} = \| \frac{ra}{q} + (m-n) \frac{\kappa}{q} \|_{{\bf R}/{\bf Z}} \leq 2\varepsilon.$

By hypothesis, ${(m-n) \frac{\kappa}{q} \leq \frac{1}{10 q}}$; note that as ${q \leq 2/\delta}$ and ${\varepsilon \leq 10^{-2} \delta}$ we also have ${\varepsilon \leq \frac{1}{10q}}$. This implies that ${\| \frac{ra}{q} \|_{{\bf R}/{\bf Z}} < \frac{1}{q}}$ and thus ${r=0}$. We then have

$\displaystyle |k \kappa| \leq 2 \varepsilon.$

We conclude that for fixed ${n \in I}$ with ${\|n\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$, there are at most ${\frac{2\varepsilon}{|\kappa|}}$ elements ${m}$ of ${[n, n + \frac{1}{10 |\kappa|}]}$ such that ${\|m\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$. Iterating this with a greedy algorithm, we see that the number of ${n \in I}$ with ${\|n\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ is at most ${(\frac{N}{1/10|\kappa|} + 1) 2\varepsilon/|\kappa|}$; since ${\varepsilon < 10^{-2} \delta}$, this implies that

$\displaystyle \delta N \ll 2 \varepsilon / \kappa$

and the claim follows. $\Box$

Now we can quickly obtain a higher degree version of Lemma 1:

Proposition 4 (Weyl exponential sum estimate, inverse form) Let ${Q \subset {\bf Z}}$ be an arithmetic progression of length at most ${N}$ for some ${N \geq 1}$, and let ${P: {\bf Z} \rightarrow {\bf R}/{\bf Z}}$ be a polynomial of some degree at most ${d \geq 0}$. If

$\displaystyle \frac{1}{N} |\sum_{n \in Q} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there exists a subprogression ${Q'}$ of ${Q}$ with ${|Q'| \gg_d \delta^{O_d(1)} N}$ such that ${P}$ varies by at most ${\delta}$ on ${Q'}$.

Proof: We induct on ${d}$. The cases ${d=0,1}$ are immediate from Lemma 1. Now suppose that ${d \geq 2}$, and that the claim had already been proven for ${d-1}$. To simplify the notation we allow implied constants to depend on ${d}$. Let the hypotheses be as in the proposition. Clearly ${\delta}$ cannot exceed ${1}$. By shrinking ${\delta}$ as necessary we may assume that ${\delta \leq c}$ for some sufficiently small constant ${c}$ depending on ${d}$.

By rescaling we may assume ${Q \subset [0,N] \cap {\bf Z}}$. By Lemma 3, we see that for ${\gg \delta^2 N}$ choices of ${h \in [-N,N] \cap {\bf Z}}$ such that

$\displaystyle \frac{1}{N} |\sum_{n \in I_h} e(P(n+h) - P(n))| \gg \delta^2$

for some interval ${I_h \subset [0,N] \cap {\bf Z}}$. We write ${P(n) = \sum_{i \leq d} \alpha_i n^i}$, then ${P(n+h)-P(n)}$ is a polynomial of degree at most ${d-1}$ with leading coefficient ${h \alpha_d n^{d-1}}$. We conclude from induction hypothesis that for each such ${h}$, there exists a natural number ${q_h \ll \delta^{-O(1)}}$ such that ${\|q_h h \alpha_d \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N^{d-1}}$, by double-counting, this implies that there are ${\gg \delta^{O(1)} N}$ integers ${n}$ in the interval ${[-\delta^{-O(1)} N, \delta^{-O(1)} N] \cap {\bf Z}}$ such that ${\|n \alpha_d \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N^{d-1}}$. Applying Lemma 3, we conclude that either ${N \ll \delta^{-O(1)}}$, or that

$\displaystyle \| q \alpha_d \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N^d. \ \ \ \ \ (4)$

In the former case the claim is trivial (just take ${Q'}$ to be a point), so we may assume that we are in the latter case.

We partition ${Q}$ into arithmetic progressions ${Q'}$ of spacing ${q}$ and length comparable to ${\delta^{-C} N}$ for some large ${C}$ depending on ${d}$ to be chosen later. By hypothesis, we have

$\displaystyle \frac{1}{|Q|} |\sum_{n \in Q} e(P(n))| \geq \delta$

so by the pigeonhole principle, we have

$\displaystyle \frac{1}{|Q'|} |\sum_{n \in Q'} e(P(n))| \geq \delta$

for at least one such progression ${Q'}$. On this progression, we may use the binomial theorem and (4) to write ${\alpha_d n^d}$ as a polynomial in ${n}$ of degree at most ${d-1}$, plus an error of size ${O(\delta^{C - O(1)})}$. We thus can write ${P(n) = P'(n) + O(\delta^{C-O(1)})}$ for ${n \in Q'}$ for some polynomial ${P'}$ of degree at most ${d-1}$. By the triangle inequality, we thus have (for ${C}$ large enough) that

$\displaystyle \frac{1}{|Q'|} |\sum_{n \in Q'} e(P'(n))| \gg \delta$

and hence by induction hypothesis we may find a subprogression ${Q''}$ of ${Q'}$ of size ${|Q''| \gg \delta^{O(1)} N}$ such that ${P'}$ varies by most ${\delta/2}$ on ${Q''}$, and thus (for ${C}$ large enough again) that ${P}$ varies by at most ${\delta}$ on ${Q''}$, and the claim follows. $\Box$

This gives the following corollary (also given as Exercise 16 in this previous blog post):

Corollary 5 (Weyl exponential sum estimate, inverse form II) Let ${I \subset [-N,N] \cap {\bf Z}}$ be a discrete interval for some ${N \geq 1}$, and let ${P(n) = \sum_{i \leq d} \alpha_i n^i}$ polynomial of some degree at most ${d \geq 0}$ for some ${\alpha_0,\dots,\alpha_d \in {\bf R}/{\bf Z}}$. If

$\displaystyle \frac{1}{N} |\sum_{n \in I} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there is a natural number ${q \ll_d \delta^{-O_d(1)}}$ such that ${\| q\alpha_i \|_{{\bf R}/{\bf Z}} \ll_d \delta^{-O_d(1)} N^{-i}}$ for all ${i=0,\dots,d}$.

One can obtain much better exponents here using Vinogradov’s mean value theorem; see Theorem 1.6 this paper of Wooley. (Thanks to Mariusz Mirek for this reference.) However, this weaker result already suffices for many applications, and does not need any result as deep as the mean value theorem.

Proof: To simplify notation we allow implied constants to depend on ${d}$. As before, we may assume that ${\delta \leq c}$ for some small constant ${c>0}$ depending only on ${d}$. We may also assume that ${N \geq \delta^{-C}}$ for some large ${C}$, as the claim is trivial otherwise (set ${q=1}$).

Applying Proposition 4, we can find a natural number ${q \ll \delta^{-O(1)}}$ and an arithmetic subprogression ${Q}$ of ${I}$ such that ${|Q| \gg \delta^{O(1)}}$ and such that ${P}$ varies by at most ${\delta}$ on ${Q}$. Writing ${Q = \{ qn+r: n \in I'\}}$ for some interval ${I' \subset [0,N] \cap {\bf Z}}$ of length ${\gg \delta^{O(1)}}$ and some ${0 \leq r < q}$, we conclude that the polynomial ${n \mapsto P(qn+r)}$ varies by at most ${\delta}$ on ${I'}$. Taking ${d^{th}}$ order differences, we conclude that the ${d^{th}}$ coefficient of this polynomial is ${O(\delta^{-O(1)} / N^d)}$; by the binomial theorem, this implies that ${n \mapsto P(qn+r)}$ differs by at most ${O(\delta)}$ on ${I'}$ from a polynomial of degree at most ${d-1}$. Iterating this, we conclude that the ${i^{th}}$ coefficient of ${n \mapsto P(qn+r)}$ is ${O(\delta N^{-i})}$ for ${i=0,\dots,d}$, and the claim then follows by inverting the change of variables ${n \mapsto qn+r}$ (and replacing ${q}$ with a larger quantity such as ${q^d}$ as necessary). $\Box$

For future reference we also record a higher degree version of the Vinogradov lemma.

Lemma 6 (Polynomial Vinogradov lemma) Let ${I \subset [-N,N] \cap {\bf Z}}$ be a discrete interval for some ${N \geq 1}$, and let ${P: {\bf Z} \rightarrow {\bf R}/{\bf Z}}$ be a polynomial ${P(n) = \sum_{i \leq d} \alpha_i n^i}$ of degree at most ${d}$ for some ${d \geq 1}$ such that ${\|P(n)\|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ for at least ${\delta N}$ values of ${n \in I}$, for some ${0 < \varepsilon, \delta < 1}$. Then either

$\displaystyle N \ll_d \delta^{-O_d(1)} \ \ \ \ \ (5)$

or

$\displaystyle \varepsilon \gg_d \delta^{O_d(1)} \ \ \ \ \ (6)$

or else there is a natural number ${q \ll_d \delta^{-O_d(1)}}$ such that

$\displaystyle \| q \alpha_i \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^i}$

for all ${i=0,\dots,d}$.

Proof: We induct on ${d}$. For ${d=1}$ this follows from Lemma 3 (noting that if ${\|P(n)\|_{{\bf R}/{\bf Z}}, \|P(n_0)\|_{{\bf R}/Z} \leq \varepsilon}$ then ${\|P(n)-P(n_0)\|_{{\bf R}/{\bf Z}} \leq 2\varepsilon}$), so suppose that ${d \geq 2}$ and that the claim is already proven for ${d-1}$. We now allow all implied constants to depend on ${d}$.

For each ${h \in [-2N,2N] \cap {\bf Z}}$, let ${N_h}$ denote the number of ${n \in [-N,N] \cap {\bf Z}}$ such that ${\| P(n+h)\|_{{\bf R}/{\bf Z}}, \|P(n)\|_{{\bf R}/{\bf Z}} \leq \varepsilon}$. By hypothesis, ${\sum_{h \in [-2N,2N] \cap {\bf Z}} N_h \gg \delta^2 N^2}$, and clearly ${N_h = O(N)}$, so we must have ${N_h \gg \delta^2 N}$ for ${\gg \delta^2 N}$ choices of ${h}$. For each such ${h}$, we then have ${\|P(n+h)-P(n)\|_{{\bf R}/{\bf Z}} \leq 2\varepsilon}$ for ${\gg \delta^2 N}$ choices of ${n \in [-N,N] \cap {\bf Z}}$, so by induction hypothesis, either (5) or (6) holds, or else for ${\gg \delta^{O(1)} N}$ choices of ${h \in [-2N,2N] \cap {\bf Z}}$, there is a natural number ${q_h \ll \delta^{-O(1)}}$ such that

$\displaystyle \| q_h \alpha_{i,h} \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^i}$

for ${i=1,\dots,d-1}$, where ${\alpha_{i,h}}$ are the coefficients of the degree ${d-1}$ polynomial ${n \mapsto P(n+h)-P(n)}$. We may of course assume it is the latter which holds. By the pigeonhole principle we may take ${q_h= q}$ to be independent of ${h}$.

Since ${\alpha_{d-1,h} = dh \alpha_d}$, we have

$\displaystyle \| qd h \alpha_d \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^{d-1}}$

for ${\gg \delta^{O(1)} N}$ choices of ${h}$, so by Lemma 3, either (5) or (6) holds, or else (after increasing ${q}$ as necessary) we have

$\displaystyle \| q \alpha_d \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^d}.$

We can again assume it is the latter that holds. This implies that ${q \alpha_{d-2,h} = (d-1) h \alpha_{d-1} + O( \delta^{-O(1)} \varepsilon / N^{d-2} )}$ modulo ${1}$, so that

$\displaystyle \| q(d-1) h \alpha_{d-1} \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^{d-2}}$

for ${\gg \delta^{O(1)} N}$ choices of ${h}$. Arguing as before and iterating, we obtain the claim. $\Box$

The above results also extend to higher dimensions. Here is the higher dimensional version of Proposition 4:

Proposition 7 (Multidimensional Weyl exponential sum estimate, inverse form) Let ${k \geq 1}$ and ${N_1,\dots,N_k \geq 1}$, and let ${Q_i \subset {\bf Z}}$ be arithmetic progressions of length at most ${N_i}$ for each ${i=1,\dots,k}$. Let ${P: {\bf Z}^k \rightarrow {\bf R}/{\bf Z}}$ be a polynomial of degrees at most ${d_1,\dots,d_k}$ in each of the ${k}$ variables ${n_1,\dots,n_k}$ separately. If

$\displaystyle \frac{1}{N_1 \dots N_k} |\sum_{n \in Q_1 \times \dots \times Q_k} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there exists a subprogression ${Q'_i}$ of ${Q_i}$ with ${|Q'_i| \gg_{k,d_1,\dots,d_k} \delta^{O_{k,d_1,\dots,d_k}(1)} N_i}$ for each ${i=1,\dots,k}$ such that ${P}$ varies by at most ${\delta}$ on ${Q'_1 \times \dots \times Q'_k}$.

A much more general statement, in which the polynomial phase ${n \mapsto e(P(n))}$ is replaced by a nilsequence, and in which one does not necessarily assume the exponential sum is small, is given in Theorem 8.6 of this paper of Ben Green and myself, but it involves far more notation to even state properly.

Proof: We induct on ${k}$. The case ${k=1}$ was established in Proposition 5, so we assume that ${k \geq 2}$ and that the claim has already been proven for ${k-1}$. To simplify notation we allow all implied constants to depend on ${k,d_1,\dots,d_k}$. We may assume that ${\delta \leq c}$ for some small ${c>0}$ depending only on ${k,d_1,\dots,d_k}$.

By a linear change of variables, we may assume that ${Q_i \subset [0,N_i] \cap {\bf Z}}$ for all ${i=1,\dots,k}$.

We write ${n' := (n_1,\dots,n_{k-1})}$. First suppose that ${N_k = O(\delta^{-O(1)})}$. Then by the pigeonhole principle we can find ${n_k \in I_k}$ such that

$\displaystyle \frac{1}{N_1 \dots N_{k-1}} |\sum_{n' \in Q_1 \times \dots \times Q_{k-1}} e(P(n',n_k))| \geq \delta$

and the claim then follows from the induction hypothesis. Thus we may assume that ${N_k \geq \delta^{-C}}$ for some large ${C}$ depending only on ${k,d_1,\dots,d_k}$. Similarly we may assume that ${N_i \geq \delta^{-C}}$ for all ${i=1,\dots,k}$.

By the triangle inequality, we have

$\displaystyle \frac{1}{N_1 \dots N_k} \sum_{n_k \in Q_k} |\sum_{n' \in Q_1 \times \dots \times Q_{k-1}} e(P(n',n_k))| \geq \delta.$

The inner sum is ${O(N_k)}$, and the outer sum has ${O(N_1 \dots N_{k-1})}$ terms. Thus, for ${\gg \delta N_1 \dots N_{k-1}}$ choices of ${n' \in Q_1 \times \dots \times Q_{k-1}}$, one has

$\displaystyle \frac{1}{N_k} |\sum_{n_k \in Q_k} e(P(n',n_k))| \gg \delta. \ \ \ \ \ (7)$

We write

$\displaystyle P(n',n_k) = \sum_{i_k \leq d_k} P_{i_k}(n') n_k^i$

for some polynomials ${P_{i_k}: {\bf Z}^{k-1} \rightarrow {\bf R}/{\bf Z}}$ of degrees at most ${d_1,\dots,d_{k-1}}$ in the variables ${n_1,\dots,n_{k-1}}$. For each ${n'}$ obeying (7), we apply Corollary 5 to conclude that there exists a natural number ${q_{n'} \ll \delta^{-O(1)}}$ such that

$\displaystyle \| q_{n'} P_{i_k}(n') \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N_k^{i_k}$

for ${i_k=1,\dots,d_k}$ (the claim also holds for ${i_k=0}$ but we discard it as being trivial). By the pigeonhole principle, there thus exists a natural number ${q \ll \delta^{-O(1)}}$ such that

$\displaystyle \| q P_{i_k}(n') \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N_k^{i_k}$

for all ${i_k=1,\dots,d_k}$ and for ${\gg \delta^{O(1)} N_1 \dots N_{k-1}}$ choices of ${n' \in Q_1 \times \dots \times Q_{k-1}}$. If we write

$\displaystyle P_{i_k}(n') = \sum_{i_{k-1} \leq d_{k-1}} P_{i_{k-1},i_k}(n_1,\dots,n_{k-2}) n_{k-1}^{i_{k-1}},$

where ${P_{i_{k-1},i_k}: {\bf Z}^{k-2} \rightarrow {\bf R}/{\bf Z}}$ is a polynomial of degrees at most ${d_1,\dots,d_{k-2}}$, then for ${\gg \delta^{O(1)} N_1 \dots N_{k-2}}$ choices of ${(n_1,\dots,n_{k-2}) \in Q_1 \times \dots \times Q_{k-2}}$ we then have

$\displaystyle \| \sum_{i_{k-1} \leq d_{k-1}} q P_{i_{k-1},i_k}(n_1,\dots,n_{k-2}) n_{k-1}^{i_{k-1}} \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N_k^{i_k}.$

Applying Lemma 6 in the ${n_{k-1}}$ and the largeness hypotheses on the ${N_i}$ (and also the assumption that ${i_k \geq 1}$) we conclude (after enlarging ${q}$ as necessary, and pigeonholing to keep ${q}$ independent of ${n_1,\dots,n_{k-2}}$) that

$\displaystyle \| q P_{i_{k-1},i_k}(n_1,\dots,n_{k-2}) \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)}}{N_{k-1}^{i_{k-1}} N_k^{i_k}}$

for all ${i_{k-1}=0,\dots,d_{k-1}}$ (note that we now include that ${i_{k-1}=0}$ case, which is no longer trivial) and for ${\gg \delta^{O(1)} N_1 \dots N_{k-2}}$ choices of ${(n_1,\dots,n_{k-2}) \in Q_1 \times \dots \times Q_{k-2}}$. Iterating this, we eventually conclude (after enlarging ${q}$ as necessary) that

$\displaystyle \| q \alpha_{i_1,\dots,i_k} \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)}}{N_1^{i_1} \dots N_k^{i_k}} \ \ \ \ \ (8)$

whenever ${i_j \in \{0,\dots,d_j\}}$ for ${j=1,\dots,k}$, with ${i_k}$ nonzero. Permuting the indices, and observing that the claim is trivial for ${(i_1,\dots,i_k) = (0,\dots,0)}$, we in fact obtain (8) for all ${(i_1,\dots,i_k) \in \{0,\dots,d_1\} \times \dots \times \{0,\dots,d_k\}}$, at which point the claim easily follows by taking ${Q'_j := \{ qn_j: n_j \leq \delta^C N_j\}}$ for each ${j=1,\dots,k}$. $\Box$

An inspection of the proof of the above result (or alternatively, by combining the above result again with many applications of Lemma 6) reveals the following general form of Proposition 4, which was posed as Exercise 17 in this previous blog post, but had a slight misprint in it (it did not properly treat the possibility that some of the ${N_j}$ could be small) and was a bit trickier to prove than anticipated (in fact, the reason for this post was that I was asked to supply a more detailed solution for this exercise):

Proposition 8 (Multidimensional Weyl exponential sum estimate, inverse form, II) Let ${k \geq 1}$ be an natural number, and for each ${j=1,\dots,k}$, let ${I_j \subset [0,N_j]_{\bf Z}}$ be a discrete interval for some ${N_j \geq 1}$. Let

$\displaystyle P(n_1,\dots,n_k) = \sum_{i_1 \leq d_1, \dots, i_k \leq d_k} \alpha_{i_1,\dots,i_k} n_1^{i_1} \dots n_k^{i_k}$

be a polynomial in ${k}$ variables of multidegrees ${d_1,\dots,d_k \geq 0}$ for some ${\alpha_{i_1,\dots,i_k} \in {\bf R}/{\bf Z}}$. If

$\displaystyle \frac{1}{N_1 \dots N_k} |\sum_{n \in I_1 \times \dots \times I_k} e(P(n))| \geq \delta \ \ \ \ \ (9)$

for some ${\delta > 0}$, then either

$\displaystyle N_j \ll_{k,d_1,\dots,d_k} \delta^{-O_{k,d_1,\dots,d_k}(1)} \ \ \ \ \ (10)$

for some ${1 \leq j \leq d_k}$, or else there is a natural number ${q \ll_{k,d_1,\dots,d_k} \delta^{-O_{k,d_1,\dots,d_k}(1)}}$ such that

$\displaystyle \| q\alpha_{i_1,\dots,i_k} \|_{{\bf R}/{\bf Z}} \ll_{k,d_1,\dots,d_k} \delta^{-O_d(1)} N_1^{-i_1} \dots N_k^{-i_k} \ \ \ \ \ (11)$

whenever ${i_j \leq d_j}$ for ${j=1,\dots,k}$.

Again, the factor of ${N_1^{-i_1} \dots N_k^{-i_k}}$ is natural in this bound. In the ${k=1}$ case, the option (10) may be deleted since (11) trivially holds in this case, but this simplification is no longer available for ${k>1}$ since one needs (10) to hold for all ${j}$ (not just one ${j}$) to make (11) completely trivial. Indeed, the above proposition fails for ${k \geq 2}$ if one removes (10) completely, as can be seen for instance by inspecting the exponential sum ${\sum_{n_1 \in \{0,1\}} \sum_{n_2 \in [1,N] \cap {\bf Z}} e( \alpha n_1 n_2)}$, which has size comparable to ${N}$ regardless of how irrational ${\alpha}$ is.