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.

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.

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.

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.