We continue the discussion of sieve theory from Notes 4, but now specialise to the case of the linear sieve in which the sieve dimension is equal to , which is one of the best understood sieving situations, and one of the rare cases in which the precise limits of the sieve method are known. A bit more specifically, let be quantities with for some fixed , and let be a multiplicative function with
for all primes and some fixed (we allow all constants below to depend on ). Let , and for each prime , let be a set of integers, with for . We consider finitely supported sequences of non-negative reals for which we have bounds of the form
for all square-free and some , and some remainder terms . One is then interested in upper and lower bounds on the quantity
The fundamental lemma of sieve theory (Corollary 19 of Notes 4) gives us the bound
where we adopt the convention . Note that for each one has only finitely many non-zero summands in (6), (7). These functions are closely related to the Buchstab function from Exercise 28 of Supplement 4; indeed from comparing the definitions one has
for all .
Exercise 1 (Alternate definition of ) Show that is continuously differentiable except at , and is continuously differentiable except at where it is continuous, obeying the delay-differential equations
for , with the initial conditions
for . Show that these properties of determine completely.
We will show
if is sufficiently large depending on . Furthermore, this claim is sharp in the sense that the quantity cannot be replaced by any smaller quantity, and similarly cannot be replaced by any larger quantity.
Comparing the linear sieve with the fundamental lemma (and also testing using the sequence for some extremely large ), we conclude that we necessarily have the asymptotics
Exercise 3 Establish the integral identities
We will prove Theorem 2 below the fold. The optimality of is closely related to the parity problem obstruction discussed in Section 5 of Notes 4; a naive application of the parity arguments there only give the weak bounds and for , but this can be sharpened by a more careful counting of various sums involving the Liouville function .
As an application of the linear sieve (specialised to the ranges in (10), (11)), we will establish a famous theorem of Chen, giving (in some sense) the closest approach to the twin prime conjecture that one can hope to achieve by sieve-theoretic methods:
Theorem 5 (Chen’s theorem) There are infinitely many primes such that is the product of at most two primes.
The same argument gives the version of Chen’s theorem for the even Goldbach conjecture, namely that for all sufficiently large even , there exists a prime between and such that is the product of at most two primes.
The discussion in these notes loosely follows that of Friedlander-Iwaniec (who study sieving problems in more general dimension than ).
— 1. Optimality —
We argue for the optimality of ; the argument for is similar and is left as an exercise. Suppose that there is for which the claim in Theorem 2 is not optimal, thus there exists such that
for as in that theorem, with sufficiently large.
We will contradict this claim by specialising to a special case. Let be a large parameter going to infinity, and set . We set , then by Mertens’ theorem we have . We set to be the residue class , thus (3) becomes
and (14) becomes
Now let be a small fixed quantity to be chosen later, set , and let be the sequence
This is clearly finitely supported and non-negative. For any , we have
(say), annd hence the remainder term in (15) is of size
As such, the error term in (16) may be absorbed into the term, and so
Now we count the left-hand side. Observe that is supported on those numbers that are the product of an odd number of primes (possibly with repetition), in which case . To be coprime to , all these primes must be at least ; since we are restricting , we thus must have . The left-hand side of (18) may thus be written as
This expression may be computed using the prime number theorem:
Exercise 6 Show that the expression (19) is equal to .
Since is continuous for , we obtain a contradiction if is sufficiently small.
Exercise 7 Verify the optimality of in Theorem 2. (Hint: replace by in the above arguments.)
— 2. The linear sieve —
Fix . Morally speaking, the most natural sieve to use here is the (upper bound) beta sieve from Notes 4, with the optimal value of , which for the linear sieve turns out to be . Recall that this sieve is defined as the sum
where is the set of divisors of with , such that
for all odd . From Proposition 14 of Notes 4 this is indeed an upper bound sieve; indeed we have
for all odd . Now for the key heuristic point: if lies in the support of , then the sum in (20) mostly vanishes. Indeed, if is such that and for some and odd , then one has for some that is not divisible by any prime less than . On the other hand, from (21), (22) one has
which (morally) implies from the sieve of Erathosthenes that is prime, thus and so is not in the support of . As such, we expect the upper bound sieve to be extremely efficient on the support of , which when combined with the analysis of the previous section suggests that this sieve should produce the desired upper bound (12).
One can indeed use this sieve to establish the required bound (12); see Chapter 11 of Friedlander-Iwaniec for details. However, for various technical reasons it will be convenient to modify this sieve slightly, by increasing the parameter to be slightly greater than , and also by using the fundamental lemma to perform a preliminary sifting on the small primes.
We turn to the details. To prove (12) we may of course assume that is suitably small. It will be convenient to worsen the error in (12) a little to , since one can of course remove the logarithm by reducing appropriately.
Set and . By the fundamental lemma of sieve theory (Lemma 17 of Notes 4), one can find combinatorial upper and lower bound sieve coefficients at sifting level supported on divisors of , such that
for all .
We will use the upper bound sieve as a preliminary sieve to remove the for ; the lower bound sieve plays only a minor supporting role, mainly to control the difference between the upper bound sieve .
Next, we set , and let be the upper bound beta sieve with parameter on the primes dividing up to level of distribution . In other words, consists of those divisors of with such that
for all odd ; in particular, for all . By Proposition 14 of Notes 4, this is indeed an upper bound sieve for the primes dividing :
Multiplying this with the second inequality in (24) (this is the method of composition of sieves), we obtain an upper bound sieve for the primes up to :
Multiplying this by and summing in , we conclude that
Note that each product appears at most once in the above sum, and all such products are squarefree and at most . Applying (3), we thus have
Thus to prove (12), it suffices to show that
for sufficiently large depending on . Factoring out the summation using (23), it thus suffices to show that
for large enough. Also, if , then and all prime factors of are at least . Thus has at most prime factors, each of which are at least . From (1) we then have
One can proceed here by evaluating the left-hand side directly. However, we will proceed instead by using the weight function from the previous section. More precisely, we will evaluate the expression
in two different ways, where is as before (but with the role of now replaced by the function ). Firstly, since , we see from the argument used to establish (17) that
(say). Since each appears at least once, we can thus write (26) as
which upon factoring the sum using (23) and Mertens’ theorem
for sufficiently large.
To do this, we abbreviate (26) as
where are the sieves
By Proposition 14 of Notes 4, we can expand as
for all with the opposite parity as ; this follows from (30) when , but is an additional constraint when and is even, but in the above identity is odd, so this additional constraint is harmless. For similar reasons we impose the inequality
We first estimate . By(24), we can write as the sum of
plus an error of size at most
(where we bound by ). The error may be rearranged as
which by (23) is of size for small enough. As for the main term (33), we see from Exercise 6 (and the arguments preceding that exercise) that this term is equal to for sufficiently large. Thus, to obtain the desired approximation for (26), it will suffice to show that
Next, we establish an exponential decay estimate on the :
Lemma 8 For sufficiently large depending on , we have
for all and some absolute constant .
Proof: (Sketch) Note that if is in , then and all prime factors are at least , thus we may assume without loss of generality that .
Note that if lies in , then
By the prime number theorem, the left-hand side is bounded (Exercise!) by as , where
and is the set of points with ,
and such that
for all with the same parity as , and
for all and some absolute constant .
We use an argument from the book of Harman. Observe that vanishes for , which makes the claim (35) routine for (Exercise!) for sufficiently large. We will now inductively prove (35) for all odd . From the change of variables , we obtain the identity
where when is odd and when is even (Exercise!). In particular, if is odd and (35) was already proven for , then
One can check (Exercise!) that the quantity is maximised at , where its value is less than (in fact it is ) if is small enough. As such, we obtain (35) if is sufficiently close to .
Exercise 9 Fill in the steps marked (Exercise!) in the above proof.
In view of this lemma, the total contribution of with for some sufficiently large is acceptable. Thus it suffices to show that
whenever is odd.
By (24), we can write as
plus an error of size
Arguing as in the treatment of the term, we see from (23) that the error term is bounded by
If and appear in the above sum, then we have where has no prime factor less than , has an even number of prime factors, and obeys the bounds
thanks to (29). Note that (29) also gives , and thus (since and ) we see that if is small enough and is large enough. This forces to either equal , or be the product of two primes between and . The contribution of the case is bounded by , which is acceptable. As for the contribution of those that are the product of two primes, the prime number theorem shows that there are at most
values of that can contribute to the sum, and so this contribution to is at most
— 3. Chen’s theorem —
We now prove Chen’s theorem for twin primes, loosely following the treatment in Chapter 25 of Friedlander-Iwaniec. We will in fact show the slightly stronger statement that
for sufficiently large , where is the set of all numbers that are products of at most two primes, and . Indeed, after removing the (negligible) contribution of those that are powers of primes, this estimate would imply that there are infinitely many primes such that is the product of at most two primes, each of which is at least .
Chen’s argument begins with the following simple lower bound sieve for :
Lemma 11 If , then
Proof: If has no prime factors less than or equal to , then and the claim follows. If has two or more factors less than or equal to , then and the claim follows. Finally, if has exactly one factor less than or equal to , then (as ) it must be of the form for some , or it is divisible by for some , and the claim again follows.
for sufficiently large , where
We thus seek sufficiently good lower bounds on and sufficiently good upper bounds on and . As it turns out, the linear sieve, combined with the Bombieri-Vinogradov theorem, will give bounds on with numerical constants that are sufficient for this purpose.
We begin with . We use the lower bound linear sieve, with equal to the residue class for all , so that is the residue class . We approximate
where is the multiplicative function with and for . From the Bombieri-Vinogradov theorem (Theorem 17 of Notes 3) we have
(say) if for some small fixed . Applying the lower bound linear sieve (13), we conclude that
We can compute an asymptotic for :
as , where is the twin prime constant.
From (11) we have . Sending slowly to zero, we conclude that
Now we turn to . Here we use the upper bound linear sieve. Let be as before. For any dividing and , we have
where and are as previously. We apply the upper bound linear sieve (12) with level of distribution , to conclude that
We sum over . Since is at most , and each number less than or equal to has at most prime factors, we have
The error term is thanks to (39). Since , we thus have
which by (10) and sending slowly gives
A routine computation shows that
Finally, we consider , which is estimated by “switching” the sieve to sift out small divisors of , rather than small divisors of . Removing those with , as well as those that are powers of primes, and then shifting by , we have
Here we are sifting out the residue classes , so that .
The sequence has good distribution up to level :
Proposition 13 One has
where is as before, and
(say), with as before.
Proof: Observe that the quantity in (42) is bounded above by if the summand is to be non-zero. We now use a finer-than-dyadic decomposition trick similar to that used in the proof of the Bombieri-Vinogradov theorem in Notes 3 to approximate as a combination of Dirichlet convolutions. Namely, we set , and partition (plus possibly a little portion to the right of ) into consecutive intervals each of the form for some . We similarly split (plus possibly a tiny portion of ) into intervals each of the form for some . We can thus split as
Observe that for each there are only choices of for which the summand can be non-zero. As such, the contribution of the diagonal case can be easily seen to be absorbed into the error, as can those cases where the product set is not contained completely in . If we let be the set of triplets obeying these properties, we can thus approximate by , where is the Dirichlet convolution
This gives the claim with replaced by the quantity ; but by undoing the previous decomposition we see that this quantity is equal to up to an error of (say), and the claim follows.
Applying the upper bound sieve (12) (with sifting level ), we thus have
for sufficiently large.
From the prime number theorem and Exercise 37 of Notes 1, we thus have
(In fact one also has a matching lower bound, but we will not need it here.) We thus conclude that
The left-hand side of (38) is then at least
One can calculate that , and the claim follows.
Exercise 14 Establish Chen’s theorem for the even Goldbach conjecture.
Remark 15 If one is willing to use stronger distributional claims on the primes than is provided by the Bombieri-Vinogradov theorem, then one can use a simpler sieve than Chen’s sieve to establish Chen’s theorem, but then the required distributional theorem will then either be conjectural or more difficult to establish than the Bombieri-Vinogradov theorem. See Chapter 25 of Friedlander-Iwaniec for further discussion.