Basic ergodic theory

Consider a ''random'' process where the next state depends on the previous one but in a chaotic manner - say we consider a particle moving in a box. One would expect that as time passes, the trajectory of the particle fills the entire cube, and does so in a uniform way, so that different subsets are visited with frequency comparable to their volume. The path of the particle would then be called ergodic. Ergodic theory offers tools for analyzing dynamical systems, in particular as the time parameter of the system goes to infinity. Central questions are whether any subset of positive measure in our measure space is visited infinitely often, and whether the process is equidistributed, meaning that the measure of the subset tells the probability that the process lies in the subset at a given time.

In this post, we present the basics of ergodic theory, and use them to prove a strong version of Weyl's equidistribution result for the numbers $\gamma,2\gamma,3\gamma...$ modulo $1$ with $\gamma$ irrational. Another application of ergodic theory we present is the fact that almost all real numbers are normal in the sense that each finite sequence of digits occurs with the expected frequency, in each base. We also sketch a proof of the law of large numbers, assuming merely that the iid. random variables have an expectation. We require only the very basics of measure theory.

Schnirelmann density and Waring's problem

A central question in additive number theory is determining whether a given infinite set $A$ of positive integers is an asymptotic basis of finite order, meaning that every large enough integer is the sum of at most $C$ elements of $A$ for some constant $C$. Questions of this type of course cover the Goldbach conjectures, Waring's problem on representing numbers as sums of perfect $k$th powers, and Romanoff's theorem on writing an integer as the sum of $C$ primes and $C$ powers of two. A natural question is whether there is some relatively easily verifiable property of sets such that when this property holds, a set is an asymptotic basis. A natural candidate would be the positivity of the asymptotic density of the set, denoted by $d(A)$. This criterion could be used, but the asymptotic density fails to exist for some rather elementary sets, and even when it does exist, proving the existence can be hard for non-trivial sets. In 1930, L.G.Schnirelmann was able to define the right kind of density, called the Schnirelmann density and denoted by $\sigma(A)$, such that it always exists and any set with positive Schnirelmann density is an asymptotic basis of finite order. He went on to prove that every integer is the sum of $C$ primes for some $C$, and later Linnik used Schnirelmann's method to give a relatively simple solution to Waring's problem. It is also notable that Schnirelmann's and Linnik's proofs are quite elementary; the former one uses nothing more complicated than Brun's sieve (see this post), and the latter uses nothing more complicated than basic estimates for Weyl sums (see this post). We will prove in this post Schnirelmann's and Linnik's theorems, as well as Romanoff's theorem. We follow the book An Introduction to Sieve Methods and their Applications by Cojocaru and Murty and the book Not Always Buried Deep: A Second Course in Elementary Number Theory by Pollack.

Hales-Jewett theorem

We consider some classical theorems in arithmetic Ramsey theory, where one wants to find some monochromatic arithmetic structure (an arithmetic progression, for example) when a large set of integers or lattice points in $\mathbb{Z}^d$ is colored with several colors. Many such results follow from the Hales-Jewett theorem from 1963, stating that given any $k$ and $r$, there is a dimension $N$ such that when the lattice points of a cube of side length $k$ and dimension $N$ are colored with $r$ colors, there is a monochromatic combinatorial line. A combinatorial line is a line of length $k$ which is constant in some coordinates and increases with slope $1$ in the others.

We will prove the Hales-Jewett theorem, as its corollary the van der Waerden theorem, and a generalization of the latter, the Gallai-Witt theorem. The van der Waerden theorem from 1927 states that, given $k$ and $r$, there is $N$ such that if $\{1,2,...,N\}$ is colored with $r$ colors, there is a monochromatic arithmetic progression of length $k$. The smallest such $N$ is the van der Waerden number $W(k,r)$, and although they seem to grow fairly rapidly, the bounds given by the traditional double induction proofs are unimaginably large compared to what is expected. However, in 1988, Shelah found a one variable induction proof of the Hales-Jewett theorem in Primitive Recursive Bounds for Van Der Waerden Numbers, and this implied a bound that is still large but nothing compared to the previous bounds, which were functions that grow faster than any function defined by primitive recursion. We present in this post a proof of the Hales-Jewett theorem similar to Shelah's proof, and consider its consequences to the van der Waerden theorem and related results.

Geometric problems in Ramsey theory

In the previous post, we considered Ramsey theory for graphs. Graphs are however not the only combinatorial structures that are guaranteed to contain some regularity; another important example are sets of points in the plane or in a general Euclidean space. There are numerous theorems at the intersection of geometry and Ramsey theory, stating that such sets of points, whenever they are large enough, contain some geometrical structure. As examples of such results we consider the Erdös problem on the minimum number of distinct distances between $n$ points in the plane and the Hadwiger-Nelson problem on finding two points of the same color at unit distance when all points in $\mathbb{R}^2$ are colored with $k$ colors. We also give a more geometrical solution of the Happy Ending problem, which gives essentially the best known upper and lower bounds (the graph theoretic solution from the previous post gives very poor bounds).

Ramsey's theorem

Ramsey theory is a branch of combinatorics in which theorems typically state that any sufficiently large structure (e.g. a graph, a set of integers or a set of points in the plane) contains some large substructure (e.g. a complete graph, an arithmetic progression or a convex polygon). The starting point for this theory is Ramsey's theorem from 1930, stating that if the edges of a large enough graph are colored red and blue, there is a red clique of size $k$ or a blue clique of size $\ell$. The smallest size of a graph that guarantees this is the Ramsey number $R(k,\ell)$. The finiteness of the Ramsey numbers can be proved in an elementary way, but it is curious that the bounds given by simple arguments are almost the best that are known, despite that the upper and lower bounds are far from each other.

We will prove Ramsey's theorem, including its generalizations for multicolored graphs and hypergraphs. As corollaries we will prove Schur's theorem on the solvability of Fermat's equation $x^n+y^n=z^n, xyz\neq 0$ modulo any number, and the Happy Ending problem on finding convex polygons in an arbitrary set of points. We will also derive a lower bound due to Erdös for the Ramsey numbers. The bound is based on Erdös' probabilistic method, which has proved to be a very fruitful tool in combinatorics despite its simplicity. It is quite remarkable that the lower bound from 1947 that we are going to prove is the best one known up to a constant factor. Furthermore, so far all lower bounds that do not appeal to the probabilistic method (in particular constructive bounds) are considerably weaker than the probabilistic bound -- they do not even grow exponentially.

The Rosser-Iwaniec sieve

We derive the Rosser-Iwaniec sieve, which gives both upper and lower bounds for the linear sieve problem that are asymptotically optimal. Linearity of the sieve problem means that $v(p)$, the number of residue classes sifted modulo $p$, is on average $1$. The optimal examples are given by the sets of integers with odd or even number of prime factors. This reflects the parity problem of classical sieves, which states that one cannot distinguish between integers with odd and even number of prime factors by using merely type I sums, such as the error sum

\[\begin{eqnarray}\sum_{d\leq D}|R_d|; \quad \quad R_d=|A_d|-\frac{v(d)}{d}|A|\end{eqnarray}\]

that occurs also in the Rosser-Iwaniec sieve.

Obtaining lower bound sieves is often more challenging than obtaining upper bound sieves. One reason is that all the error terms must be of lower order than the main term, or our lower bound becomes zero. In addition, some sieves, such as the Selberg sieve, are fundamentally based on inequalities that have no clear lower bound counterpart (the Selberg sieve was based on the trivial observation that $1_{\{1\}}(n)\leq \left(\sum_{d\mid n}\lambda_d\right)^2$ for any $\lambda_i$ with $\lambda_1=1$). However, Buchstab's identity (from this post), which is just a number theoretic inclusion-exclusion principle, can be used to overcome this difficulty by making the signs of the terms we can upper bound negative. Buchstab's identity is also the basis of the Rosser-Iwaniec sieve (even for the upper bound sieve). In the course of deriving the Rosser-Iwaniec sieve, we will also prove the fundamental lemma of the sieve, which is rather elementary but gives optimal results when the sifting parameter is small. In the end, we apply the Rosser-Iwaniec sieve to prove that there are infinitely many primes $p$ such that $p+2$ is almost a prime; namely has no more than three prime factors. We follow Harman's book Prime Detecting Sieves.

The Siegel-Walfisz theorem

When considering primes in arithmetic progressions, one is naturally led to study the zeros of Dirichlet $L$-functions. As will be seen, one can prove the prime number theorem in arithmetic progressions, that is $\pi(x;a,q)=\frac{\text{Li}(x)}{\varphi(q)}+O_q(x\exp(-c_q\sqrt{\log x}))$, using arguments very analogous to proving the prime number theorem with the help of the zero free region of the Riemann zeta function $\zeta(s)$. However, things get much more complicated when uniformity in the modulus $q$ is required. Such uniformity was for example required in this post on the ternary Goldbach problem. The reason for increased complexity is that the location of the zeros of $L(s,\chi)$ may depend intricately on the modulus $q$ of $\chi$, as well as $\chi$ itself. For the $\zeta$ function no such problem exists, and given any finite rectangle in the plane, one can determine whether it contains zeros of $\zeta(s)$ just by calculating an integral arising from the principle of argument. For general $L$-functions, zeros lying too close to the line $\sigma=1$ could ruin all hope of uniformity in the prime number theorem for arithmetic progressions.

Fortunately, there is a classical theorem , which states that zeros of $L(s,\chi)$ close to the line $\sigma=1$, say with $\sigma>1-\frac{c}{\log q}$, with $c$ a suitable constant, must be exceptional in three different ways. First, $\chi$ must be a non-principal real primitive character; second, $s$ must be real, and third such a zero is at most unique. We shall prove this result and deduce Siegel's theorem, stating that $L(s,\chi)$ has no zeros with $s>1-C(\varepsilon)q^{-\varepsilon}$ for any fixed $\varepsilon>0$. This in turn implies the Siegel-Walfisz theorem, which gives a uniform error term from primes in arithmetic progressions up to $q\leq (\log x)^{M}$ for any fixed $M$. A defect of these theorems is that the constant $C(\varepsilon)$ is completely ineffective; the proof gives no bounds for it. Nevertheless, 80 years after Siegel's discovery, the result is essentially the best known. Already showing that the single real zero with $s>1-\frac{c}{\log q}$, known as the Landau-Siegel zero, never exists, would have profound consequences, including an improvement of the Brun-Titchmarsh theorem (see this post), an improved Siegel-Walfisz theorem, and better estimates for the class numbers of imaginary quadratic fields. We follow Davenport's Multiplicative Number Theory.

Harman's sieve

In this post, we will derive Harman's sieve, which enables one to show that a sparse set $A$ contains the expected proportion of primes compared to a bigger set $B$ (which is usually $[\frac{x}{2},x]$), provided that one can relate linear and bilinear sums over $A$ and $B$ in suitable ranges with a sufficiently small error term. The linear sums are called type I sums, and the bilinear sums are type II sums. As an application of the method, we show that given any irrational $\xi$ and real $\kappa$, there are infinitely many primes $p$ such that $\|\xi p+\kappa\|<p^{-\frac{1}{4}}\log^{C} p$ holds, where $\|\cdot\|$ stands for the distance to the nearest integer. We already showed in this post on prime exponential sums that the fractional parts of $\xi p$ are uniformly distributed, but this result gives even more uniformity. We follow Harman's book Prime Detecting Sieves.

Uncertainty principles in Fourier analysis

Uncertainty principles in Fourier analysis are formalizations of the following principle: A function $f$ and its Fourier transform $\hat{f}$ cannot both be sharply ''localized''. This of course allows many interpretations, and by interpreting localization in various ways, we get theorems (usually inequalities) about the simultaneous behavior of $f$ and $\hat{f}$. We will formalize and prove the following uncertainty principles.

• $|f|^2$ and $|\hat{f}|^2$ cannot both have small variance (Heisenberg uncertainty principle)
•  Two self-adjoint operators cannot both have small norms compared to the norm of their commutator (Heisenberg uncertainty principle for operators)
•  $f$ and $\hat{f}$ cannot both decay faster than gaussian functions (Hardy's uncertainty principle)
• Not both $f$ and $\hat{f}$ can be nonzero only in a set of finite measure (Benedick's inequality)
• The entropy of $f$ and $\hat{f}$ cannot both be positive (Hirschman's inequality)

The first hint that such principles might be true is that the Fourier transform ''spreads out'' a function the more it is concentrated: $\mathcal{F}(f(tx))=\frac{1}{t}\hat{f}(\frac{\xi}{t})$. We now proceed to formalize and prove the principles.

The large sieve and the Bombieri-Vinogradov inequality

In this post, we will derive the large sieve, which is one of the most classical sieves. The large sieve is quite different from combinatorial sieves, such as the sieve of Eratosthenes, Brun sieve and Selverg sieve (discussed in these posts 1, 2, 3, 4), in the sense that instead of combinatorial arguments, the large sieve stems from analytic inequalities that are not very far from harmonic analysis. Another important difference is that, as the name indicates, the large sieve is most useful when we are sifting a large proportion of the residue classes modulo primes, unlike the combinatorial sieves in which usually only a bounded amount of residue classes are sifted. The large sieve can, and will be, formulated as asserting square root cancellation in quadratic means of exponential sums, where the phase runs over rationals with denominator at most $z$, but we will also present an arithmetic version concerning the number of residue classes a set can occupy modulo each prime, given the size of the set (which is what combinatorial sieves are also about). One more formulation involves bilinear sums of Dirichlet characters, and we use it, together with Vaughan's identity (see this post) and the Pólya-Vinogradov inequality (see this post), to prove the Bombieri-Vinogradov theorem. Finally, we apply the Bombieri-Vinogradov theorem to the solution of the Titchmarsh divisor problem, which asks for the average number of prime divisors of $p+a$ for a given $a$, where $p$ runs through the primes up to $x$. We follow the book An Introduction to Sieve Methods and Their Applications by Cojocaru and Murty.

Ingham's Theorem on primes in short intervals

In ths post, we prove a theorem of Ingham, which states that there is always a prime on the short interval $[x,x+x^{\frac{5}{8}+\varepsilon}]$ when $x\geq M_{\varepsilon}$. More precisely, the theorem even gives an asymptotic formula for the number of such primes. It may seem a priori rather surprising that we are able to show the correct asymptotic for $\pi(x+x^{\theta})-\pi(x)$ for some numbers $\theta<1$ without being able to improve the error term in the prime number theorem to $x^{1-\varepsilon}$ for any $\varepsilon>0$. A crucial ingredient in the proof is relating the number of primes in short intervals to bounds for the number of zeros of the Riemann $\zeta$ function with real part at least $\sigma$ and imaginary part bounded by $T$. Even though we can by no means say that no zeros exist for $\sigma<1-\varepsilon$ for any $\varepsilon>0$, we still manage to prove that the number of zeros with real part at least $\sigma$ decays at least like $T^{A(1-\sigma)}\log^B T$ for some constants $A$ and $B$ so that zeros far from the critical line must be quite rare. The other crucial ingredient in the proof is in fact showing that bounds for $\zeta(\frac{1}{2}+it)$ lead to bounds for the number of zeros off from the critical line via the principle of argument, among other things. In particular, we will see that the truth of the Lindelöf hypothesis $\zeta(\frac{1}{2}+it)\ll t^{\varepsilon}$ for all $\varepsilon>0$ would imply that the intervals $[x,x+x^{\frac{1}{2}+\varepsilon}]$ contain primes for all $x\geq M_{\varepsilon}$. Of course, the truth of the Riemann hypothesis would imply that the shorter interval $[x,x+C\sqrt{x}\log^2 x]$ contains a prime for all large enough $x$, and Cramér's conjecture asserts that even intervals as short as $[x,x+K\log^2 x]$ contain primes for all $x$ when $K$ is large enough. The best unconditional result is due to Baker, Harman and Pintz, and says that the interval $[x,x+x^{0.525}]$ contains a prime for all large enough $x$.

Van der Corput's inequality and related bounds

In this post, we prove several bounds for rather general exponential sums, depending on the growth of the derivative of their phase functions. We already proved in this post Vinogradov's bound for such sums under the assumption that some derivative of order $k\geq 4$ is suitably small. Here we prove similar but better bounds when the first, second or third derivative of the phase function is suitably small. We follow Titchmarsh's book The Theory of the Riemann Zeta Function and the book Van der Corput's Method of Exponential Sums by S. W. Graham and G. Kolesnik. The bounds depending on the derivatives enable us to estimate long zeta sums and hence complete the proof of the error term in the prime number theorem from the previous post. As a byproduct, we also get the Hardy-Littlewood bound

\[\begin{eqnarray}\zeta\left(\frac{1}{2}+it\right)\ll t^{\frac{1}{6}}\log t,\end{eqnarray}\]

for the zeta function on the critical line, which will be utilized in the next post in proving Ingham's theorem on primes in short intervals. Two more consequences of the Weyl differencing method, which will be applied to bounding exponential sums based on their derivatives, are the van der Corput inequality and a related equidistribution test. This test easily gives the uniform distribution of the fractional parts of polynomials, as we shall see.

Error term in the prime number theorem

We prove here an improved prime number theorem of the form

\[\begin{eqnarray}\pi(x)=Li(x)+O(x\exp(-c\log^{\frac{4}{7}}x)),\quad Li(x):=\int_{2}^{x}\frac{dt}{\log t},\end{eqnarray}\]

for all $c>0$, a result which is essentially due to Chudakov. The proof is based on bounding the growth of the Riemann zeta function in the critical strip near $\Re(s)=1$, and achieving this in turn builds on bounds for the zeta sums

\[\begin{eqnarray}\sum_{M\leq n\leq N}n^{-it}.\end{eqnarray}\]

To bound these sums, we use a bound for exponential sums with slowly growing phase from this post (Theorem 5 (i)). The proof of that bound was based on Vinogradov's mean value theorem. When $M$ is large enough, however, the theorem from the previous post is no longer helpful, and we must follow a different approach based on Weyl differencing and van der Corput's inequality, which is quite useful by itself. That approach will be postponed to the next post, and here we concentrate on short zeta sums and on deducing the stronger prime number theorem. We follow Chandrasekharan's book Arithmetical functions.

We remark that without relying on exponential sums, one has not been able to prove anything significantly better than $\pi(x)=Li(x)+O(x\exp(-c\log^{\frac{1}{2}}x))$, which was proved by de la Valleé Poussin already in 1899. On the other hand, the best known form of the prime number theorem is due to Vinogradov and Korobov, and it states that 

\[\begin{eqnarray}\pi(x)=Li(x)+O(x\exp(-c_0\log^{\frac{3}{5}}x(\log \log x)^{-\frac{1}{5}}))\end{eqnarray}\] for some $c_0>0$; this was proved nearly 60 years ago in 1958.

Vinogradov's mean value theorem and Weyl sums

In this post, we consider Weyl sums, which are exponential sums with polynomial phases; a Weyl sum is defined by

\[\begin{eqnarray}f(\alpha,N):=\sum_{n\leq N}e(\alpha_kn^k+...+\alpha_1n),\quad \alpha\in \mathbb{R}^k.\end{eqnarray}\]

We also consider the closely related Vinogradov integrals

\[\begin{eqnarray}J_{s,k}(X):=\int_{[0,1]^k}|f(\alpha,X)|^{2s}d\alpha,\end{eqnarray}\]

which are moments of Weyl sums with respect to the coefficient vector $\alpha$. We derive an efficient estimate for the Vinogradov integrals, known as Vinogradov's mean value theorem and essentially due to Vinogradov, following a simple proof by Wooley. We then utilize this estimate to achieve significant cancellation in general exponential sums $\sum_{n\leq N}e(F(n))$, whose phase function $F$ is smooth and grows very slowly. In proving that estimate, we follow Chandrasekharan's book Arithmetical functions. In a later post, this general estimate, also due to Vinogradov, will be employed to bound the zeta sums

\[\begin{eqnarray}\sum_{M\leq n\leq N}n^{-it}.\end{eqnarray}\]

These estimates in turn give bounds for growth of the Riemann zeta function, and further a zero-free region, and eventually a much better error term for the prime number theorem than the classical $\pi(x)=Li(x)+O(x\exp(-c\log^{\frac{1}{2}} x))$ ($\log^{\frac{1}{2}}x$ will be replaced by $\log^{\frac{4}{7}} x$). With some effort, one could use the Vinogradov integrals to bound Weyl sums, but we instead put the method of Weyl differencing into use, obtaining usually weaker bounds but with less effort.

Prime exponential sums and Vaughan's identity

We prove in this post an estimate for the prime exponential sums \[\begin{eqnarray}S(N;\alpha):=\sum_{p\leq N}e(\alpha p)\end{eqnarray}\] using an identity of Vaughan that splits the von Magoldt function $\Lambda(n)$, which is a natural weighted version of the characteristic function of the primes, into pieces that are suited to efficient estimation of oscillating sums $\sum_{n\leq N}f(n)$ over primes. Vinogradov was the first to prove nontrivial cancellation in prime exponential sums in 1937, but the proof remained long and technical until Vaughan discovered in 1977 his formula that simplifies the estimation considerably, giving at the same time a much better bound of $N^{\frac{4}{5}}$ (times logarithmic factors) when $\alpha$ has bounded continued fraction coefficients. This estimate was also required in this post on the ternary Goldbach problem. We will also apply the derived bounds to show that the fractional parts $\{\alpha p\}$ are uniformly distributed for any irrational $\alpha$ as $p$ ranges through the primes.

Goldbach's ternary problem

The ternary Golbach problem is the assertion that every odd integer $N\geq 7$ is the sum of three primes. It was first proved for large enough integers by I. M. Vinogradov in 1937, and the proof is a good starting point for the study of the Hardy-Littlewood circle method and of Vinogradov's method for estimating exponential sums over prime numbers, such as

\[\begin{eqnarray}\sum_{p\leq N}e(\alpha p);\quad e(x):=e^{2\pi i x}.\quad \quad(1)\end{eqnarray}\]

The full ternary problem was solved only in 2013 in a paper by H. Helfgott. In this post, we present the circle method and show how it can be used to resolve the ternary Golbach problem for large enough integers, assuming an estimate for the prime exponential sum $(1)$. This estimate is due to R. C. Vaughan and is based on his refined version of Vinogradov's method. In a later post, we prove this estimate, so the results here serve as an illustration of the capability of Vinogradov's method. We follow Vinogradov's book Method of Trigonometrical Sums in the Theory of Numbers, but replacing the application of Page's theorem by Siegel's theorem allows us to avoid some technicalities and improve the error terms.

Character sums and Pólya-Vinogradov inequality

In this post, we consider character sums, which are one of the central objects in the discrete Fourier analysis of the integers modulo $q$. We will prove the Pólya-Vinogradov estimate, which we will observe to be the best possible estimate up to a logarithmic factor, despite being easy to prove. Character sums arise in many problems in number theory, and we utilize them to prove classical bounds for the least quadratic nonresidue and primitive root modulo $q$. We also show that the generalized Riemann hypothesis reduces the bounds for the least quadratic nonresidue and primitive root considerably.

Selberg's upper bound sieve

In this post, we derive Selberg's upper bound sieve. Selberg's sieve is a combinatorial sieve based  on the simple but immensely useful idea of introducing a large number of parameters into a combinatorial sieve inequality and optimizing them. We apply this sieve for example to prove the Brun-Titchmarsh inequality for primes in short intervals belonging to an arithmetic progression, as well as to prove good upper bounds for the number of representations of an integer as the sum of two primes, or the number of primes $ap+b$ where $p\leq x$ is prime (the bounds are conjectured to be sharp up to a constant factor). In a later post, we  establish a corresponding lower bound sieve. We follow the classical book of Halberstam and Richert.

Fourier transform and its mapping properties

We present some classical results about the Fourier transform in $\mathbb{R}^n$ in this post, and some of them will be applied in later posts to partial differential equations, additive number theory, and other topics. In particular, we consider the validity of the Fourier inversion theorem in various forms, the $L^2$ theory of the Fourier transform and the mapping properties of the Fourier transform in many spaces.

A refined Brun sieve

We improve the Brun sieve from the previous post to allow us to consider almost primes of various forms. We will prove for example the result that there are infinitely many $n$ such that $n$ and $n+2$ both have at most $7$ prime factors, and that every large enough even integer is the sum of two numbers both having at most $7$ prime factors.