Upper-bound sieve

An upper-bound sieve bounds the size of a sifted set from above. In a dimension-one problem with one forbidden class modulo each relevant prime $p$, its main density factor is comparable to ${\prod }_p(1-1/p)$.

For $x>q$ and $(a,q)=1$, the prime-counting function in an arithmetic progression satisfiesThe denominator involves the Euler totient function and the length-to-modulus ratio. In particular, for $q\le x^{1-\eta }$ with fixed $\eta >0$, this is $O_{\eta }(x/(\varphi (q)\log x))$.

The Selberg sieve uses optimized quadratic weights to bound the size of a sifted set.

Suppose $|{\mathcal{A}}_d|=Xg(d)+r_d$ for $d\mid P(z)$. If ${\lambda }_1=1$ and the real Selberg weights ${\lambda }_d$ vanish unless $d\mid P(z)$ and $d\le D$, thenOptimizing the main quadratic form gives $X/G(D,z)$, whereup to the harmless replacement of $D$ by $D^2$ under the alternative convention that $D$ denotes the level of the least common multiples.

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$.

Sieve an interval of length $z$ by the prime two and the primes congruent to three modulo four, with local densities $g(p)=1/p$. Take $D=z^{1/2}$ and $L=\sqrt{D}$. The truncated Euler-product lower bound, the Mertens first theorem and the reciprocal-prime sum in residue class one modulo four give $J\gg \sqrt{\log z}$. The interval counts have bounded remainders, whose sum is $O(D{\log }^{2}D)$ by the summatory bound for three to the prime omega. Hence the number surviving is $O(z/\sqrt{\log z})$, uniformly in the location of the interval.

FordefineThe optimizing Selberg weights arefor $d<D$ dividing $P(z)$, and zero otherwise. They satisfy ${\lambda }_1=1$ and diagonalize the main quadratic form to $1/G(D,z)$.

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.

Put $L=\sqrt{D}$, $h(t)={\prod }_{p\mid t}(g(p{)}^{-1}-1)$ and $y_t={\sum }_{\begin{array}{c}m\le L\\ t\mid m\end{array}}g(m){\rho }_m$, where $g$ is a multiplicative arithmetic function supported on squarefree integers. For squarefree integers $m,n$,Thus the quadratic form is $\Sigma ={\sum }_{t\le L}h(t)y_t^2$. Möbius inversion gives $g(d){\rho }_d={\sum }_{d\mid t\le L}\mu (t/d)y_t$. On the permitted squarefree integers, the constraint ${\rho }_1=1$ becomes ${\sum }_t\mu (t)y_t=1$. The Cauchy-Schwarz inequality yields $\Sigma \ge 1/J$, where $J={\sum }_{t}1/h(t)$ over those integers; equality holds at $y_t=\mu (t)/(Jh(t))$.

For real coefficients ${\rho }_1=1$ supported on permitted divisors up to $L$, put ${\lambda }_d={\sum }_{[u,v]=d}{\rho }_u{\rho }_v$. Then ${\sum }_{d\mid n}{\lambda }_d=({\sum }_{d\mid n}{\rho }_d{)}^2$ is an upper bound for the indicator function of numbers free of the forbidden prime factors. Its support has $d\le L^2$. If the coefficients vanish on non-squarefree integers and satisfy $|{\rho }_d|\le 1$, then $|{\lambda }_d|\le 3^{\omega (d)}$: each prime factor of $d$ occurs in $u$, in $v$, or in both.

Let $k(d)={\prod }_{p\mid d}g(p)/(1-g(p))$ on permitted squarefree integers. The Selberg sieve weights haveThe numerator is the total weight of the distinct integers $ev\le L$ with $e\mid d$ and $(v,d)=1$: multiplicativity gives ${\sum }_{e\mid d}k(e)={\prod }_{p\mid d}(1-g(p){)}^{-1}$. They are a subset of the terms in $J$.

For an integer polynomial $F$ and squarefree $d$, let ${\rho }_F(d)$ count the roots of $F$ modulo $d$. The Chinese remainder theorem makes ${\rho }_F$ multiplicative, andThus $g(d)={\rho }_F(d)/d$ and $r_d=O({\rho }_F(d))$ define a sieve distribution.

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.

For $F(n)=n(n+2)$, every odd prime has two forbidden residue classes. Use Selberg sieve weights supported on odd squarefree integers $d\le R=x^{1/8}$. Their main quadratic form is $1/J$, where $J={\sum }_{d\le R}{\prod }_{p\mid d}2/(p-2)$. The truncated Euler-product lower bound applied to primes up to $R^{1/8}$ gives $J\gg {\log }^{2}R$: the mean logarithmic divisor size is $2{\sum }_{3\le p\le R^{1/8}}(\log p)/p<\frac{1}{2}\log R$, by the Mertens first theorem, and the full product is $\asymp {\log }^{2}R$, by the Mertens second theorem. The optimal Selberg weights have modulus at most one, so the remainder is at most $O({\sum }_{d,e\le R}[d,e])=O(R^4)$. The finitely many possible pairs with $p\le R$ contribute $O(R)$. Thus the count is $O(x/J+R^4+R)$, proving the bound.

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}$.

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.

If $f$ is smooth and supported on $[-1,1]$ and $g(t)={\int }_{\mathbb{R}}{e}^{x}f(x)e(-tx)dx$, Fourier inversion givesExpanding the square of the resulting Möbius-weighted divisor sum turns its mean value into an Euler product controlled by zeta functions near their pole at one.

For a real smooth cutoff $\varphi$ supported on $[-1/3,1/3]$ with $\varphi (0)=1$, define $F_X(n)=({\sum }_{d\mid n}\mu (d)\varphi (\log d/\log X){)}^2$. Its sum over any interval of length $X$ is $c_{\varphi }X/\log X+O_{\varphi }(X/{\log }^{2}X+X^{2/3})$, uniformly in the interval location. Here $c_{\varphi }$ is the derivative energy constant for a smooth sieve cutoff. Expanding the square yields an interval-counting error $O(X^{2/3})$ and an Euler product for a smoothed divisor-square correlation; its zeta function pole provides the main term. Every prime exceeding $X^{1/3}$ has weight one, giving the short-interval prime upper bound from a smooth divisor weight.

For $\mathrm{Re}z,\mathrm{Re}{z}^{\prime }>0$, the series ${\sum }_{d,e}\mu (d)\mu (e)d^{-z}{e}^{-z^{\prime }}/[d,e]$ has local factor $1-p^{-1-z}-p^{-1-z^{\prime }}+p^{-1-z-z^{\prime }}$. Dividing by the displayed zeta function ratio leaves a holomorphic function $H$ near zero with $H(0,0)=1$. The local factor of $H$ is $(1-a-b+c)(1-c)/((1-a)(1-b))$, where $a=p^{-1-z}$, $b=p^{-1-z^{\prime }}$, $c=p^{-1-z-z^{\prime }}$, and equals one exactly at zero. With $z=(1+it)/\log X$, the zeta function poles produce the kernel $(1+it)(1+i{t}^{\prime })/((2+i(t+t^{\prime }))\log X)$ that determines the smooth divisor-square sieve asymptotic.

Write $e^u\varphi (u)=\int \psi (t)e^{-iut}dt$. The double integral $\iint \psi (t)\psi (t^{\prime })(1+it)(1+i{t}^{\prime })/(2+i(t+t^{\prime }))dtd{t}^{\prime }$ equals the displayed constant. Express the denominator as a Laplace integral and each differentiated Fourier factor as $-{\varphi }^{\prime }(u)$, then use Fubini's theorem. For a real cutoff the resulting square is positive even though the Fourier transform factors have no complex conjugation. The Cauchy-Schwarz inequality and $\varphi (0)=1$, $\varphi (1/3)=0$ give $c_{\varphi }\ge 3$.

For $Y\ge X\ge 2$, a smooth Selberg divisor weight of level $D=X^{1/10}$ equals one on every prime in $(Y,Y+X]$. Its second moment can be expressed through an Euler product $H$ whose zeta-factor bound contributes $O(1/\log D)$ after integration against rapidly decreasing Fourier transforms. Consequently

If three nonproportional linear forms exclude three distinct residue classes modulo every sufficiently large prime, the upper-bound sieve has dimension three and gives an upper bound of order $x/(\log x{)}^3$.