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.