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.

Basic Brun sieve

In this post, we derive a simple form of Brun's combinatorial sieve that is already superior to the Eratosthenes-Legendre sieve and is sufficient to prove for example that the sum of the reciprocals of twin prime converges. We will see, however, that this sieve gives upper bounds that are slightly weaker than the optimal ones, such as $\pi(x)\ll x\cdot \frac{\log \log x}{\log x}$. In a later post, we will derive a more powerful Brun sieve that enables us to get rid of the extra factors $\log \log x$ and allows us to choose the sieve parameter $z$ to be a fixed power of $x$.

Eratosthenes-Legendre sieve

In this post, we present the basic idea of sieve methods and derive the simple Eratosthenes-Legendre sieve. Subsequently, there will be posts about more advanced sieve topics and their applications in number theory. Sieve theory offers tools for estimating various quantities in number theory (and also other branches of mathematics), in particular ones related to primes. The first idea of sieve theory was already invented by Eratosthenes around 2200 years ago. He devised a simple but rather efficient algorithm for finding all the primes up to $x$. Unfortunately, Eratosthenes' algorithm is so famous that the generality of the idea behind it is often forgotten. The idea allows us to estimate theoretically the number of primes up to $x$, or more generally many other similar sets of numbers, instead of taking a fixed $x$ such as $10^{10}$ and doing a boring computation. The simple but important idea can be formulated as follows : If we want to compute the number of those elements of a set $A\subset \mathbb{Z_+}$ with $|A|=x$ that have no prime factors below $z$, we should first take all the $x$ numbers, then subtract the number of even ones, subtract the number of multiples of $3$, subtract the number of multiples of $5$, add the number of multiples of $6$ (they were discarded twice), and so forth. The process goes through all the numbers $d$ that divide the product of the primes up to $z$ and whether we subtract or add depends on the parity of the number of prime divisors of $d$. It was probably Legendre who first wrote down this observation as a formula $-$ around 2000 years after Eratosthenes' algorithm $-$ and it is essentially the principle of inclusion and exclusion from combinatorics. Below we briefly discuss sieve methods in general. Then we derive the Eratosthenes-Legendre sieve and present some applications of it.

Elementary estimates for prime sums

In this post, we prove several results about prime sums that are not much weaker than what follows from the prime number theorem, but the proofs are quite simple and use elementary methods (even the prime number theorem actually has a proof using elementary methods, by Selberg and Erdös, but the proof is not simple). One of the results we show is Chebychev's assertion that $\frac{\pi(x)\log x}{x}$ is bounded from below and above by positive constants (that are not very far from each other), and as a corollary we get Bertrand's postulate, telling that the interval $[n,2n]$ always contains a prime number. We also prove Mertens' three theorems about sums and products related to primes. These results are nearly as good as what the prime number theorem gives. We will need these results in later posts about sieve theory.

Roth's theorem on arithmetic progressions

In this post, we give an application of Fourier analysis to combinatorics, more precisely to Ramsey theory. In Ramsey theory, a typical result tells that certain large but otherwise arbitrary objects (sets of integers, graphs, collections of points, etc.) are forced to contain some structure in them, thus implying intuitively that there is no complete randomness. The desired structure in these objects could mean for example large cliques or independent sets of vertices in the case of graphs, or some arithmetic structure in the case of sets of integers. One of the most basic arithmetic structures is of course an arithmetic progression, and there are several Ramsey theoretic results about their occurrence. We mention the following two theorems.

Theorem 1 (van der Waerden). Let $k$ and $\ell$ be positive integers. Then there exists a number $W(k,\ell)$ such that whenever the numbers in $\{1,2,...,N\}$ with $N\geq W(k,\ell)$ are colored using $\ell$ colors, there is a monochromatic arithmetic progression of length $k$ .

Theorem 2 (Szemerédi). Let $\delta>0$, and let $k$ be a positive integer. Then, if $A$ is any subset of $\{1,2,...,N\}$ with $N\geq N(k,\delta)$ and having density at least $\delta$ (that is, $|A|\geq \delta N$), the set $A$ contains an arithmetic progression of length $k$.

The first result was proved by van der Waerden in 1927 (back then, the result was an open problem that many famous mathematicians attempted to resolve, but it was the young van der Waerden who solved it). The latter result is a very deep and important result of Szemerédi from 1975 (the proof was so complicated that Szemerédi refused to write it down himself). Szemerédi's proof was based on his graph regularity lemma, and virtually every proof of the theorem has started a fruitful new research direction. For instance, Furstenberg proved the theorem using ergodic theory in 1977, and Gowers using Fourier analytic methods and his uniformity norms in 2001, and the latter proof also improved bounds on $W(k,\ell)$ enormously.

It is easy to see that van der Waerden's theorem is a special case of Szemerédi's; indeed, if $\{1,2,...,N\}$ is colored with $\ell$ colors, there is at least one monochromatic subset of density at least $\frac{1}{\ell}$. In addition, both theorems allow immediately an infinite version. For Szemerédi's theorem, the infinite version is that any subset of the natural numbers with a positive lower density contains arbitrarily long arithmetic progressions. In fact, there is a nice compactness argument that can be used to deduce the finite versions of the theorems from their infinite versions, but that is a different story.

We will not try to prove Szemerédi's theorem in this post, but we will prove its special case $k=3$ due to Roth from 1953. This case is an elegant and relatively short application of Fourier analysis into combinatorics. For convenience, we also formulate this claim.

Quadratic reciprocity via discrete Fourier analysis

In this post, we give a proof of the law of quadratic reciprocity based on discrete Fourier analysis and more precisely Gauss sums. This celebrated theorem has numerous proofs, but the most elementary ones usually boil down to some tedious combinatorial computations. In particular, after one has derived Gauss' lemma or some similar statement that is usually used in the proof, the big picture may become unclear, and one is left with some combinatorial counting problem. On the other hand, if one uses discrete Fourier analysis to prove the reciprocity law, the structure of the proof is simple, and one works in the context of trigonometric sums instead of solving an isolated combinatorial problem. Moreover, this method generalizes to higher reciprocity laws as well, and similar ideas as in what follows can be applied for example in proving the functional equation of the $L$-functions, the class number formula or the Pólya-Vinogradov inequality. Some of these results will be discussed in later posts.

Lacunary trigonometric series

In this post, we consider trigonometric series that do not necessarily arise from Fourier series. In particular, we consider lacunary trigonometric series

\[\begin{eqnarray}\sum_{n=0}^{\infty}(a_k\cos(2\pi n_k x)+b_k\sin(2\pi n_k x)),\quad\frac{n_{k+1}}{n_k}\geq \lambda >1\quad \text{for all}\quad k. \quad \quad (1)\end{eqnarray}\]

(It turns out that the sine and cosine form is more convenient than the complex exponential form in what follows). In other words, the frequencies of the trigonometric functions always grow by at least a factor of $\lambda$. It turns out that for such series, one can formulate some interesting convergence and integrability results that are not generally valid for trigonometric series. For example, Zygmund showed in 1930 that a lacunary series converges in a set of positive measure iff the sum of squares of its coefficients converges iff the lacunary series converges almost everywhere. This answers very broadly the question of convergence of such a series, while for a general trigonometric series the task of finding such a convergence criterion is hopeless. In the same paper, Zygmund proved that a lacunary series always converges in a dense set that even has the cardinality of the real numbers, unless the series is trivially divergent, that is $a_k^2+b_k^2\not \to 0$.

Another intriguing property of lacunary trigonometric series is that if such a series converges pointwise almost everywhere, its value distribution is random; in fact, the value distribution of its partial sums approaches the normal distribution. This was shown by Salem and Zygmund in 1947. It is also interesting to study whether a lacunary series is the Fourier series of some integrable function. Kolmogorov proved in 1924 that if this is the case, then this lacunary Fourier series converges almost everywhere, so for lacunary Fourier series, there are no problems with convergence (this of course follows from Carleson's result about pointwise almost everywhere convergence of $L^2$-functions, but the proof for lacunary series is much simpler, though not trivial).

It must also be mentioned that lacunary trigonometric series, whose frequencies grow too fast compared to the decay of the coefficients, are a good way to construct continuous nowhere differentiable functions, and indeed Weierstrass' example is a lacunary series.

The study of trigonometric series is also closely related to complex analysis, since the boundary values of an analytic function $f(z)=\sum_{n=0}^{\infty}a_nz^n$, defined in the unit disc, are given by the series $\sum_{n=0}^{\infty}a_ne^{in x}$, and conversely, a trigonometric series gives rise to an analytic function in the unit disc, whose boundary values are given by the trigonometric series, unless the coefficients grow too fast.

The above results (which are just a tiny proportion of what is known) should motivate the study of (lacunary) trigonometric series quite well. We will prove some of the mentioned results, following closely the original papers mentioned above.

Irreducibility of polynomials

In many contexts, it is important to know whether a polynomial is irreducible. In algebraic number theory, the properties of an algebraic number $\alpha$ are determined by its minimal polynomial, the irreducible monic polynomial of least degree having $\alpha$ as a root. In Galois theory, it is important to know whether a field extension arises from an irreducible polynomial. In algebraic geometry, one is interested in varieties arising from the zero set of a set of multivariate polynomials, and if some of the polynomials are reducible, the variety can be represented in simpler terms. There are many more examples as well.

By the fundamental theorem of algebra, polynomials with complex coefficients always factor into linear factors in $\mathbb{C}[x].$ From this it follows that real polynomials factor into at most quadratic factors in $\mathbb{R}[x]$. However, in $\mathbb{Q}[x]$ and $\mathbb{Z}[x]$, irreducibility is much more interesting. By Gauss' lemma, irreducibility in both of them is the same thing, so we consider only $\mathbb{Z}[x]$ (every polynomial in $\mathbb{Q}[x]$ becomes a polynomial with integer coefficients when multiplied by a suitable integer).

In what follows, by polynomials we mean polynomials with integer coefficients in one variable and irreducibility is considered in $\mathbb{Z}[x]$, unless otherwise noted. In this post, we present a few methods to determine whether a polynomial is irreducible. For some reason, it seems that the Eisenstein criterion is almost the only irreducibility criterion that is truly well-known, even though it fails for many polynomials.