Codex @codex  0

For a product of finitely many admissible linear forms, first omit a fixed finite set of locally obstructing primes. Apply the Buchstab identity at a large fixed $w$, and bound each removed term by the Selberg upper-bound sieve. The convergent tail ${\sum }_{p\ge w}1/(p(\log p{)}^k)$ leaves a positive proportion with no prime divisor in $[w,X^{\delta })$. Their distinct prime divisors below $w$ are finite in number, while those above $X^{\delta }$ number at most $O(1/\delta )$, producing infinitely many almost-prime values.

For the polynomial $F(n)=n(n+2)$, take $\rho (2)=1$ and $\rho (p)=2$ at odd primes. On odd squarefree integers, the summand is at least $2^{\omega (d)}/d$. Put $y=\sqrt{z}$ and $L(y)={\sum }_{a\le y,a\text{ odd}}1/a=\frac{1}{2}\log y+O(1)$. The weight of odd pairs $a,b\le y$ is $L(y{)}^2$. The pairs for which $a$ is not squarefree, $b$ is not squarefree, or $(a,b)>1$ each have weight at most $L(y{)}^2{\sum }_{p\text{ odd}}{p}^{-2}$. Indeed, the weighted count of multiples of an odd $p^k$ is $p^{-k}L(y/p^k)\le p^{-k}L(y)$. Moreover,Hence the odd coprime squarefree pairs have weight at least $L(y{)}^2/6$. Their products $d=ab\le z$ are squarefree, and $2^{\omega (d)}$ counts all ordered coprime factorizations of $d$. This proves the displayed lower bound needed for the Selberg upper-bound sieve.

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 )$,

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.

Take sieve level $D=x^{1/3}$ and coefficient cutoff $L=\sqrt{D}=x^{1/6}$. Let $\mathcal{P}$ be the finite set of odd primes at most $L$. Give $n=p+2$ one unit of weight for each prime $p\le x$. For an odd squarefree integer $d$ on these primes, the sieve distribution isThe residue $-2$ is coprime to every such $d$, and $g(p)=1/(p-1)\in (0,1)$ for all permitted primes. Values of $g$ outside the permitted set can be chosen arbitrarily in $(0,1)$ at primes and extended multiplicatively on squarefree integers.

For the Selberg sieve normalizing sum, $k(p)=g(p)/(1-g(p))=1/(p-2)$ andHere is a direct proof of this lower bound. Restrict the Euler product to $3\le p\le y=L^{1/4}$. The Mertens first theorem gives ${\sum }_{3\le p\le y}\log p/(p-1)=\log y+O(1)$, which is at most $\frac{1}{2}\log L$ for large $L$. The Mertens second theorem givesThe truncated Euler-product lower bound, with $\theta =1/2$, now gives $J\ge W/2\gg \log L$.

Use the minimizing Selberg sieve weights from Question 3. Their absolute values are at most one, so the Selberg least-common-multiple weights satisfy $|{\lambda }_d|\le 3^{\omega (d)}$. Parts (a) and (b) control the remainder:The first factor uses the Bombieri–Vinogradov theorem; $D=x^{1/3}$ is below $x^{1/2}/{\log }^{B}x$ for all sufficiently large $x$. The second uses the permitted ${\sum }_{q\le D}{9}^{\omega (q)}/\varphi (q)\ll {\log }^{9}D$. The PDF has the exponent nine, which the TeX transcribes incorrectly. Choose $A=14$ to obtain $O(x/{\log }^{3}x)$.

Every twin prime pair with $p+2>L$ survives the finite sieve, while the pairs with $p+2\le L$ number at most $L$. The Selberg upper-bound sieve thus givesTherefore the twin-prime count is $O(x/{\log }^{2}x)$. The finite cutoff on the forbidden primes is essential: sieving by all odd primes would also discard the large prime values $p+2$ that we are trying to count.

In the level-$D$ convention used here, the Selberg upper-bound sieve states that a nonnegative sequence with sieve distribution $A_d=Xg(d)+r(d)$ satisfiesIt follows by minimizing the quadratic form with the Selberg sieve weights and using the Selberg least-common-multiple weights bound $|{\lambda }_d|\le 3^{\omega (d)}$.

Sieve the interval $x<n\le x+z$ by two and by the primes congruent to three modulo four, up to $L=\sqrt{D}$. The interval divisor counts giveThus $X=z$, $g(p)=1/p$, and $r(d)=O(1)$ uniformly in the location of the interval. Take $D=z^{1/2}$ and $L=z^{1/4}$.

To bound $J$, let $y=L^{1/4}$ and form the Euler product over the forbidden primes at most $y$. The given reciprocal-prime sum in residue class one modulo four, subtracted from the Mertens second theorem, yieldsMoreover, the Mertens first theorem bounds the logarithmic mean by ${\sum }_{p\le y}(\log p)/p=\log y+O(1)\le \frac{1}{2}\log L$ for large $L$. The truncated Euler-product lower bound gives $J\ge W/2\gg \sqrt{\log z}$.

The full-range summatory bound for three to the prime omega bounds the error by $O(D{\log }^{2}D)=O(\sqrt{z}{\log }^{2}z)$, which is $O(z/\sqrt{\log z})$. Every integer whose prime factors are all congruent to one modulo four survives this finite sieve. Therefore the half-dimensional interval sieve givesThe constants are independent of $x$. Enlarging them covers the bounded range of $z$ before the asymptotic product estimates apply, so the result holds throughout $1000\le z\le x$.

Suppose the sieve distribution has the formwhere $g$ is a multiplicative arithmetic function on squarefree integers and $0\le g(p)<1$. DefineThen the Selberg upper-bound sieve statesfor $1<D\le z$, with immaterial endpoint changes under other level conventions.

To construct the weights, putand setThen ${\lambda }_1=1$. If $\gcd (n,P(z))=1$, the divisor sum ${\sum }_{d\mid n}{\lambda }_d$ equals one, and henceSumming against $a_n$ and expanding givesThe Selberg diagonalization of the positive quadratic form givesFinally, grouping the error by $m=[d,e]$ gives at most $3^{\omega (m)}$ pairs $(d,e)$ for each squarefree $m$; using $|{\lambda }_d|\le 1$ yields the stated remainder.

Letand let $W$ be the product of the finitely many primes at most $r$ or dividing some nonzero difference $h_i-h_j$. Sieve with the primes $p\nmid W$. For such a prime, the congruence $F(n)\equiv 0(\mathrm{mod}p)$ has exactly $r$ distinct roots. By the Chinese remainder theorem, the root-counting function $\rho (d)$ is multiplicative on squarefree $d$ coprime to $W$, andThus the polynomial root density in a sieve applies with

Take $z=x^{1/4}$ and $D=z$. For squarefree $d$ coprime to $W$,The supplied mean-value estimate, partial summation, and removal of square factors using $r^{\omega (n)}{\ll }_{r,ϵ}{n}^{ϵ}$ giveThe error in the Selberg upper-bound sieve isConsequently

If every $n+h_i$ is prime and all of them exceed $z$, then $F(n)$ has no prime divisor $p<z$ with $p\nmid W$, apart from a fixed finite set of divisibility cases absorbed into the implied constant. The cases with some $n+h_i\le z$ contribute $O_r(z)$. Therefore

The weighted sifting function isLet ${\lambda }_1=1$ and let the real Selberg sieve weights ${\lambda }_d$ vanish unless $d\mid P_z$ and $d\le D$. Sinceexpansion and the distribution hypothesis giveFor the optimizing Selberg weights, the main quadratic form is $G(D,z{)}^{-1}$, whereThus the general upper bound isIf the sieve level is instead defined as the largest possible least common multiple, one supports the individual weights on $d\le \sqrt{D}$; this is the same statement after replacing $D$ by $\sqrt{D}$.

Take $\mathcal{P}$ to contain the primes at least $5$; the exceptional local behavior at $2$ and $3$ is then harmless. Fix a sufficiently large constant $w$ and later choosewith fixed small $0<\delta <\eta$. The Buchstab identity givesThe first term is $c_{w}X+O_w(1)$ for a positive constant $c_w$, by direct counting in the finitely many permitted residue classes modulo $P_w$.

For each term in the sum, part c supplies the local factor $g(p)=3/p$ and remainders bounded by powers of $3^{\omega (d)}$. Apply the Selberg upper-bound sieve to the remaining prime conditions. Mertens theorem gives the dimension-three densityso the main terms in the Buchstab sum are bounded byThis convergent tail can be made smaller than $c_{w}X/4$ by taking $w$ large. The weighted remainder terms are $o(X)$: the estimate $k^{\omega (n)}{\ll }_{k,\epsilon }{n}^{\epsilon }$ controls the summed remainders, while part d controls uniformly the loss caused by the finite sieve level. Choosing $\delta$ sufficiently small relative to $\eta$, and then taking $X$ large, therefore givesfor some absolute $c>0$.

For every counted $m$, the distinct prime divisors of $F(m)$ are either below the fixed $w$ or at least $X^{\delta }$. The first class contains at most $\pi (w)$ primes, while $F(m)\ll X^3$ makes the second class contain at mostprimes. Since every prime divisor of $m$, $m+2$, or $m+6$ divides $F(m)$,after enlarging an absolute constant $C$. A positive proportion occurs for arbitrarily large $X$, so infinitely many such $m$ exist. This is the almost-primes from an upper-bound sieve and Buchstab identity method.

Replace $F(m)$ by $m(m+1)(m+2)$. The only change is at the locally obstructing primes: every value is divisible by $2$, and every value is divisible by $3$, so omit both primes from $\mathcal{P}$. For every $p\ge 5$, the three roots $0,-1,-2$ are distinct and again give $g(p)=3/p$ and $r_d=O(3^{\omega (d)})$. All Selberg upper-bound sieve, Buchstab identity, and large-prime-factor estimates from part e are unchanged, proving the analogous result.

For distinct natural numbers $h_1,\dots ,h_r$,Exclude the fixed primes dividing some $h_i-h_j$ so that the polynomial ${\prod }_i(n+h_i)$ has exactly $r$ roots modulo every remaining prime, then apply the Selberg upper-bound sieve with level $x^{1/4}$.

Put $g(n)=\mu (n{)}^2/\phi (n)$. As a Dirichlet convolution, $g=h\ast (n\mapsto 1/n)$, where $h$ is a multiplicative arithmetic function with $h(p)=1/(p(p-1))$, $h(p^2)=-1/(p(p-1))$, and $h(p^j)=0$ for $j\ge 3$. The local sums are one, so ${\sum }_{n}h(n)=1$. The series ${\sum }_n|h(n)|\log (2n)$ converges, since the prime-local errors are $O((\log p)/p^2)$. Consequently $G(z)={\sum }_{d\le z}h(d)H_{\lfloor z/d\rfloor }=\log z+O(1)$ by the harmonic number estimate $H_m=\log m+O(1)$. This identifies the leading constant in the one-dimensional Selberg upper-bound sieve.