Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 28 / 4 / Solution

The Selberg upper-bound sieve replaces a difficult coprimality indicator by a nonnegative square whose coefficients can be optimized. Let $P(z)={\prod }_{p\le z}p$, and suppose a finite sequence has divisibility countswhere $g$ is multiplicative on squarefree integers and $0<g(p)<1$. Choose real Selberg sieve weights ${\lambda }_1=1$ supported on $d\mid P(z)$ with $d\le R$. If an entry has no prime factor in $P(z)$, its only weighted divisor is $1$, so its indicator is bounded above by the square of the divisor sum. Summing giveswhere $Q(\lambda )={\sum }_{d,e}{\lambda }_d{\lambda }_{e}g([d,e])$. This is an upper bound regardless of the signs of the weights.

Here is the optimization. On the permitted squarefree integers putThe identitycan be checked one prime at a time: a prime in both $d$ and $e$ gives the factor $1+h(p)=1/g(p)$. ThusFinite Möbius inversion gives ${\lambda }_{d}g(d)={\sum }_{d\mid r}\mu (r/d)Y_r$, and in particular the condition ${\lambda }_1=1$ becomes ${\sum }_r\mu (r)Y_r=1$. The Cauchy-Schwarz inequality now yieldsEquality is attained by $Y_r=\mu (r)k(r)/J$. Inverting again gives the explicit optimizing weightsThey satisfy $|{\lambda }_d|\le 1$. To see this, multiply out ${\prod }_{p\mid d}(1-g(p){)}^{-1}={\sum }_{e\mid d}k(e)$. The numerator becomes the sum of $k(ev)$ over distinct permitted integers $ev\le R$ with $e\mid d$ and $(v,d)=1$, a subset of the terms in $J$. We therefore have a main term $X/J$ and a controllable remainder. This proves the basic Selberg sieve diagonalization and the useful bound on the weights, rather than merely asserting an optimized density.

Apply it to the polynomial $F(n)=n(n+2)$ for $1\le n\le N$. If $\omega (d)$ is the number of roots of $F$ modulo squarefree $d$, the Chinese remainder theorem givesUse $g(d)=\omega (d)/d$, $R=z=N^{1/8}$, and sieve the indices for which $F(n)$ has no prime factor at most $z$. The local weights areWe claim $J(z,z)\gg (\log z{)}^2$. The following truncated-product argument supplies the necessary lower bound. Put $w=z^{1/8}$, and consider all squarefree integers on the primes at most $w$, with total weightGive such an integer $d$ probability $k(d)/W$. Prime inclusion is independent with probability $g(p)$, soby the Mertens first theorem, absorbing the prime $2$ separately. For sufficiently large $z$, this is at most $\frac{1}{2}\log z$. The Markov inequality shows that at least half of $W$ lies on $d\le z$, all of which are terms in $J(z,z)$.

Moreover, partial summation applied to the Mertens first theorem givesIndeed it is $A(w)/\log w+{\int }_2^{w}A(t)/(t(\log t{)}^2)dt$, and the contribution of $A(t)-\log t=O(1)$ has a finite limiting constant with tail $O(1/\log w)$. Expanding the logarithm of $W$ now givesThe error is bounded since ${\sum }_p{p}^{-2}<\infty$. Consequently $W\asymp (\log w{)}^2\asymp (\log z{)}^2$, proving the claim. The exponent two reflects the two forbidden classes at almost every prime.

For the remainder use $|{\lambda }_d|\le 1$ and the simple bound $\omega ([d,e])\le [d,e]\le de$. HenceThe number of surviving indices is thereforeEvery pair of primes $p,p+2$ with $p>z$ survives, since both its prime factors exceed $z$. The exceptional pairs with $p\le z$ number at most $z$. With $z=N^{1/8}$ we obtainThis is the twin-prime upper bound from a quadratic sieve. The method constructs a majorant and bounds the sifted set; it does not give a positive lower bound for twin primes.