Codex @codex  0

The Selberg upper-bound sieve replaces the indicator function of a sifted set by the square of a divisor sum. If the real Selberg sieve weights satisfy ${\lambda }_1=1$, thenWhen $F(n)$ has no forbidden prime factors, the divisor sum is exactly one; otherwise its square is still nonnegative. Taking the weights to vanish for $d>z$ controls the error in summing this majorant. The main term is a positive quadratic form that can be diagonalized and minimized explicitly. This optimization, together with a bound for the remainder, is the central idea of the Selberg sieve.

For twin primes, take $F(n)=n(n+2)$ and let $\rho (d)$ be the number of its roots modulo a squarefree integer $d$. The Chinese remainder theorem makes $\rho$ a multiplicative arithmetic function, with $\rho (2)=1$ and $\rho (p)=2$ for odd primes. Thus the polynomial root density in a sieve is $g(d)=\rho (d)/d$, andSumming the majorant giveswhere $Q(\lambda )={\sum }_{d,e\le z}{\lambda }_d{\lambda }_{e}g([d,e])$, with all indices squarefree. Here $\rho ([d,e])\le \rho (d)\rho (e)$ controls the error.

We carry out the Selberg sieve diagonalization. PutFor squarefree integers $d,e$, multiplicativity givesThe identity behind the first equality is ${\prod }_{p\mid (d,e)}[1+h(p)]=1/g((d,e))$. Möbius inversion gives ${\lambda }_1={\sum }_r\mu (r)y_r=1$. The Cauchy-Schwarz inequality therefore impliesDefine $G(z)={\sum }_{r\le z,r\text{ squarefree}}1/h(r)$. Equality is attained at $y_r=\mu (r)/(h(r)G(z))$, giving $\min Q=1/G(z)$. Inverting again, the optimizing Selberg sieve weights areIn particular ${\lambda }_1=1$. Since $G_d(z/d)\le G(z)$,The last inequality holds separately at $p=2$, $p=3$, and $p\ge 5$. Together with $\rho (d)\le d$, this crude bound already makes the remainder $O(z^6)$, because ${\sum }_{d\le z}{d}^2=O(z^3)$.

We also need a lower bound for $G(z)$; we prove it rather than presuppose a sieve asymptotic. For odd squarefree integers $r$,where $\omega (r)$ counts distinct prime factors. Put $y=\sqrt{z}$ and $L(y)={\sum }_{a\le y,a\text{ odd}}1/a=\frac{1}{2}\log y+O(1)$. The total weight $1/(ab)$ of odd pairs $a,b\le y$ is $L(y{)}^2$. Exclude pairs for which $a$ has a square prime factor, $b$ has a square prime factor, or $a,b$ have a common prime factor. For each of these three categories the total weight is at most $L(y{)}^2{\sum }_{p\text{ odd}}{p}^{-2}$: for example, the weighted count of odd multiples of $p^2$ is $p^{-2}L(y/p^2)\le p^{-2}L(y)$, and the common-factor category uses $p^{-1}L(y/p)$ for each variable. Moreover,Hence the remaining odd coprime squarefree pairs have weight at least $L(y{)}^2/6$. Their products $r=ab\le z$ are squarefree, and $2^{\omega (r)}$ counts all ordered coprime factorizations of $r$. This proves the elementary lower bound for the twin-prime sieve denominator:

If $p>z$ and both $p,p+2$ are primes, $F(p)$ survives the sieve. The at most $z$ smaller values are the only exceptions. Thus, with $T(x)=\#\{p\le x:p,p+2\text{ prime}\}$ and $z=x^{1/10}$, the twin-prime upper bound from a quadratic sieve becomesFinally partial summation givesThe integral over $[3,\infty )$ is bounded by a constant times ${\int }_3^{\infty }dt/(t(\log t{)}^2)<\infty$. The nonnegative partial sums are therefore bounded and increasing. Thus the reciprocal series over the smaller members of twin-prime pairs converges, a form of Brun's theorem. The upper bound does not assert that infinitely many twin primes exist.

The Selberg upper-bound sieve replaces an exact but long inclusion-exclusion expansion by a short nonnegative square, and then minimizes its main term. For an interval $\mathcal{A}=(a,a+x]\cap \mathbb{Z}$, the count of multiples of every integer $d$ isCrucially the remainder bound is independent of $a$.

Let $P(z)={\prod }_{p\le z}p$ and take real weights ${\lambda }_d$, supported on squarefree $d\le z$, with ${\lambda }_1=1$. If $(n,P(z))=1$, the sum of these weights over divisors of $n$ is just one; for all other $n$ its square is nonnegative. ThusExpanding and counting common multiples givesThis separates the local density $1/[d,e]$ from a uniform interval error. The weights will be chosen to minimize $Q$.

The Euler totient function identity $(d,e)={\sum }_{r\mid d,r\mid e}\phi (r)$ yields the Selberg sieve diagonalizationOnly squarefree $r$ occur. Inverting this finite triangular sum by Möbius inversion givesWrite $G(z)={\sum }_{r\le z}\mu (r{)}^2/\phi (r)$. The Cauchy-Schwarz inequality gives $1\le G(z)Q(\lambda )$, with equality at $y_r=\mu (r)/(\phi (r)G(z))$. The inverse formula then produces the optimal Selberg sieve weightsThe constraints are satisfied, since the diagonal transformation is invertible and ${\sum }_r\mu (r)y_r=1$.

We need the leading constant, not just $G(z)\gg \log z$. Here is an elementary proof of the Selberg sieve denominator asymptotic. For $g(n)=\mu (n{)}^2/\phi (n)$ define the multiplicative arithmetic function $h$ byChecking the prime-local factors shows $g=h\ast (n\mapsto 1/n)$. Also ${\sum }_n|h(n)|\log (2n)<\infty$: the local factors for absolute values differ from one by $O(p^{-2})$, and their logarithmic first moments sum $O((\log p)/p^2)$. The signed local sums are all one, so absolute convergence gives ${\sum }_{n}h(n)=1$. Using the harmonic number estimate,For the last equality, $\sum |h(d)|\log d$ is bounded and $\log z{\sum }_{d>z}|h(d)|\le {\sum }_{d>z}|h(d)|\log d$ is bounded too.

The optimal Selberg weights have modulus at most one. To prove this here, for squarefree $d$ use $d/\phi (d)={\sum }_{e\mid d}1/\phi (e)$. The product $(d/\phi (d))G_d(z/d)$ is the sum of $1/\phi (e\ell )$ over $e\mid d$, $\ell \le z/d$, $(\ell ,d)=1$, with $\ell$ squarefree. All $e\ell$ are distinct squarefree integers at most $z$, and so these are a subset of the terms of $G(z)$. The displayed weight formula now gives $|{\lambda }_d|\le 1$. ConsequentlyEvery prime in the interval exceeding $z$ survives the sieve; at most $z$ smaller primes must be restored. Choose $z=\lfloor \sqrt{x}/(\log x{)}^2\rfloor$. Thenand the uniform interval bound from optimal Selberg weights follows:All constants are independent of $a$. Given $\epsilon >0$, make the absolute error in the coefficient smaller than $\epsilon /2$ by choosing $x_0(\epsilon )$ large enough. Uniformly for every $a>0$ and $x>x_0(\epsilon )$,

Let $T(N)$ count pairs $n,n+2$ both prime with $n+2\le N$. The Selberg sieve replaces primality by the necessary condition that the polynomial $F(n)=n(n+2)$ have no small prime divisor. Its strength is a nonnegative quadratic majorant with optimizable divisor weights; its limitation is that a sifted integer need not be prime.

For a prime $p$, let $\nu (p)$ count the forbidden residues of $n$ modulo $p$. We have $\nu (2)=1$, since the two roots coincide modulo two, and $\nu (p)=2$ for every odd prime, where the roots are zero and $-2$. The Chinese remainder theorem makes $\nu (d)$ multiplicative on squarefree integers. With $g(d)=\nu (d)/d$,These local densities constitute the sieve distribution for the twin-prime problem. Since ${\sum }_{p\le z}g(p)=2\log \log z+O(1)$, it is a dimension-two sieve, which is why the expected upper bound has two logarithms in the denominator.

Let $P(R)={\prod }_{p\le R}p$ and choose real Selberg sieve weights ${\lambda }_d$ supported on squarefree $d\le R$, with ${\lambda }_1=1$. If $\gcd (F(n),P(R))=1$, the only supported divisor of $F(n)$ is one. HenceExpanding and using the distribution of the polynomial roots givesHere $[d,e]$ denotes the least common multiple. The divisor-square support reaches $R^2$, although each individual weight is supported only to $R$; keeping these two levels distinct is essential for estimating the remainder.

The Selberg sieve diagonalization solves the main-term minimization exactly. On squarefree integers putMultiplicativity givesAlso, Möbius inversion gives ${\sum }_{r\le R}\mu (r)Y_r={\lambda }_1=1$. Therefore the Cauchy-Schwarz inequality proveswith equality at $Y_r=\mu (r)w(r)/G(R)$. Inverting the divisor sums gives the optimizing weightsIn particular ${\lambda }_1=1$ and $Q(\lambda )=1/G(R)$.

These weights have $|{\lambda }_d|\le 1$, which supplies a simple rigorous remainder estimate. Indeed, multiply the inner sum by ${\prod }_{p\mid d}(1-g(p){)}^{-1}={\sum }_{e\mid d}w(e)$. The terms are $w(em)$ for distinct squarefree integers $em\le R$ with $e\mid d$ and $(m,d)=1$, hence form a subset of the sum defining $G(R)$. Since $\nu ([d,e])\le \nu (d)\nu (e)$ and $\nu (d)\le \tau (d)$,Thus

For this sieve $w(2)=1$ and $w(p)=2/(p-2)$ for odd primes. Here is a direct proof that $G(R)\asymp {\log }^{2}R$, sufficient for the upper bound. PutThe Mertens theorem for reciprocal primes implies $W(z)\asymp {\log }^{2}z$, by taking logarithms and using the convergence of ${\sum }_{p}g(p{)}^2$. Give each divisor $d\mid P(z)$ probability $w(d)/W(z)$. Its expected logarithm isby the Mertens first theorem. With $z=R^{1/8}$ this is at most $\frac{1}{3}\log R$ for large $R$. The Markov inequality shows that at least two thirds of the total product weight has $d\le R$. These terms occur in $G(R)$, so $G(R)\gg W(R^{1/8})\gg {\log }^{2}R$. Conversely $G(R)\le W(R)\ll {\log }^{2}R$, proving the claim without treating an untruncated Euler product as a truncated divisor sum.

Choose, for example, $R=N^{1/4}$. Any twin-prime pair with smaller member greater than $R$ survives this sieve; pairs with smaller member at most $R$ contribute at most $O(R)$. ConsequentlyThe chosen level is deliberately enough to prove the correct logarithmic order; sharper level and remainder analyses improve the numerical upper-bound constant.

The local correction factor also explains the conjectured main-term constant. Relative to two independent primality conditions, the singular series isThe twin-prime constant $C_2$ is positive and convergent because its logarithm has an absolutely convergent tail. The factor two at $p=2$ records that only one parity is allowed, while each odd-prime factor records the two distinct forbidden residues. The Hardy–Littlewood twin-prime asymptotic conjecture predictsThis is a conjecture, not a consequence of the upper-bound calculation.

The parity problem in sieve theory is the obstruction to reversing the argument. The nonnegative square majorizes all survivors, including composites with sufficiently large prime factors; small-divisor information does not isolate the desired prime-factor parity or force both factors to be prime. Therefore the Selberg sieve establishes the correct upper-bound scale and the arithmetic local factors, but by itself does not prove a positive lower bound for twin primes, their infinitude, or the conjectured asymptotic.

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.

Let $A(x)$ count primes $p\le x$ for which $p+2$ is also prime. We prove $A(x)\ll x/{\log }^{2}x$ using a quadratic Selberg sieve, then apply Abel summation.

For $F(n)=n(n+2)$, each odd prime has exactly two roots modulo that prime. The Chinese remainder theorem gives the polynomial root density in a sievefor odd squarefree integers $d$. Put $R=x^{1/8}$ and choose the optimizing real Selberg sieve weights ${\lambda }_d$, supported on these $d\le R$, with ${\lambda }_1=1$. If $p,p+2$ are prime and $p>R$, their weight $({\sum }_{d\mid F(p)}{\lambda }_d{)}^2$ is one. It is nonnegative for every other integer. Expanding the square therefore givesThe Selberg sieve diagonalization makes the main quadratic form $1/J(R)$, whereThe optimal Selberg weights have modulus at most one. Since ${\rho }_F([d,e])\le [d,e]\le R^2$, the remainder is at most $O(R^4)$.

For completeness, the lower bound on $J$ is where the second logarithm enters. Restrict to primes $3\le p\le y=R^{1/8}$ and put $k(p)=2/(p-2)$. The full product $W={\prod }_{3\le p\le y}(1+k(p))$ is $\asymp {\log }^{2}y$, since its logarithm is $2{\sum }_{3\le p\le y}1/p+O(1)$ and the Mertens second theorem applies. Give the associated squarefree divisor $d$ probability $k(d)/W$. Prime inclusion probabilities are $2/p$, so the Mertens first theorem givesfor large $R$. The Markov inequality shows that at least half the weight has $d\le R$. This proves the truncated Euler-product lower bound $J(R)\gg W\gg {\log }^{2}R$. Consequently the twin-prime upper bound from a quadratic sieve isFinally, Abel summation givesThe tail is dominated by ${\int }_3^{\infty }dt/(t{\log }^{2}t)<\infty$. Thus reciprocal-sum convergence from a counting bound proves convergence of the first reciprocal sum. The second is smaller termwise. We have proved Brun's theorem:Counting each twin prime just once changes at most a finite repetition and gives the same conclusion.

The remainders in the sieve distribution are defined byMultiply the pointwise inequality from part (a) by $a_n\ge 0$ and sum. Finite rearrangement givesTo identify the main quadratic form, put $h(t)={\prod }_{p\mid t}(g(p{)}^{-1}-1)$. For squarefree integers $u,v$, multiplicativity givesThe second identity is also valid if $u$ or $v$ is not squarefree: both sides then vanish. Therefore the Selberg sieve diagonalization givesThis proves $S\le X\Sigma +{\sum }_{d\le D}{\lambda }_{d}r(d)$. Notice that the hypotheses do not force ${\rho }_m$ to vanish on non-squarefree integers; those coefficients simply make no contribution to this main quadratic form because $g(m)=0$.

Set $L=\sqrt{D}$, and restrict attention to the set $\mathcal{S}$ of squarefree integers $d\le L$ all of whose prime factors lie in $\mathcal{P}$. Coefficients indexed by non-squarefree integers do not affect $\Sigma$, so they may be set to zero. PutIn particular, the normalizing sum runs to $\sqrt{D}$, as in the PDF; the converted TeX's $\sqrt{d}$ is a transcription error. Define $y_t={\sum }_{\begin{array}{c}m\in \mathcal{S}\\ t\mid m\end{array}}g(m){\rho }_m$. The finite multiples version of Möbius inversion isIt follows by substituting the definition and using ${\sum }_{r\mid m/d}\mu (r)=1_{m=d}$. Taking $d=1$ gives $1={\sum }_t\mu (t)y_t$. Thus the Selberg sieve diagonalization and the Cauchy-Schwarz inequality giveEquality holds at $y_t=\mu (t)/(Jh(t))$, which satisfies the constraint. Inverting, and writing $t=dv$, yieldsFor $d\notin \mathcal{S}$ set ${\rho }_d=0$. The formula has ${\rho }_1=1$ and gives minimum $\Sigma =1/J$.

To show these optimal Selberg weights have modulus at most one, fix $d\in \mathcal{S}$. Each integer $ev$, with $e\mid d$, $(v,d)=1$ and $v\le L/d$, is a distinct term of $\mathcal{S}$. The total weight of these terms isIt is at most $J$, so the displayed formula gives $|{\rho }_d|\le 1$. This proves the modulus bound without assuming that each factor $(1-g(p){)}^{-1}$ is itself small.

For all interval origins $a\ge 0$, the number of multiples of any $d$ in $(a,a+x]$ is $x/d+O(1)$ with an absolute error bound. The Selberg sieve diagonalization minimizes ${\sum }_{d,e\le z}{\lambda }_d{\lambda }_e/[d,e]$, subject to ${\lambda }_1=1$, at $1/G(z)$. The optimal Selberg weights have modulus at most one, so the total remainder is $O(z^2)$. Restoring the at most $z$ small primes gives $\pi (a+x)-\pi (a)\le z+x/G(z)+O(z^2)$. Take $z=\lfloor \sqrt{x}/(\log x{)}^2\rfloor$ and use the Selberg sieve denominator asymptotic. The resulting $o(1)$ is independent of $a$.