Sieve theory

Sieve theory estimates the number of integers that avoid specified residue classes modulo primes.

Divisibility information by small primes cannot by itself reliably distinguish integers with an odd or even total number of prime factors. Consequently an upper-bound Selberg sieve can bound prime pairs and related sifted sets but does not supply a positive lower bound or the conjectured twin-prime asymptotic. This limitation concerns the information available to the sieve, not merely a choice of weight normalization.

// Target: number-theory.bigb

A positive integer in this set has no prime factor equal to two or congruent to three modulo four. Its prime factors all lie in the residue class one modulo four. For example $5\cdot 13=65$ belongs, while $3^2=9$ does not, even though $9$ itself is congruent to one modulo four. A half-dimensional interval sieve bounds the count in an interval of length $z$ by $O(z/\sqrt{\log z})$.

The large sieve bounds how much an exponential sum can concentrate at separated points of the circle group. Its variance form of the large sieve also bounds simultaneous concentration in residue classes modulo many primes.

For an interval set avoiding one residue at each sieving prime, the Ramanujan sum at the forbidden Chinese remainder theorem residue gives a linear combination of Fourier samples equal to $\mu (d)|S|$. Cauchy-Schwarz inequality gives sample energy at least $|S{|}^2/\phi (d)$ for each squarefree modulus. Summing these energies and applying the analytic large sieve inequality gives the bound. If primes dividing $q$ are excluded, restrict the denominator to $(d,q)=1$; it is uniformly at least a constant times $(\phi (q)/q)\log (2Q)$.

For coefficients supported on $N$ consecutive integers,The star restricts to primitive Dirichlet characters. Their finite Fourier transform of a primitive Dirichlet character has normalization of absolute value $\sqrt{q}$. Orthogonality of Dirichlet characters therefore bounds the weighted contribution for one modulus by ${\sum }_{\begin{array}{c}a\mathrm{mod}q\\ (a,q)=1\end{array}}|{\sum }_n{a}_{n}e(an/q){|}^2$. Sum over $q$ and use the exponential-sum large sieve on the distinct reduced fractions of denominators at most $Q$.

For coefficients $b_n$ supported on an interval of $H$ consecutive integers, set $B=\sum b_n$ and $B_p(a)={\sum }_{n\equiv a(\mathrm{mod}p)}{b}_n$. ThenThe orthogonality of roots of unity gives $p{\sum }_a|B_p(a)-B/p{|}^2={\sum }_{r=1}^{p-1}|{\sum }_n{b}_{n}e(rn/p){|}^2$. The distinct fractions $r/p$ have circular spacing at least $Q^{-2}$; now apply the exponential-sum large sieve.

If ${\theta }_r$ have circular spacing at least $\delta$, thenMultiply the exponential sum by $e(-Mt)$, apply the Sobolev–Gallagher inequality on disjoint arcs of length $\delta$, and sum. The finite-interval Parseval identities and Cauchy-Schwarz inequality bound the derivative contribution by $2\pi N\sum |a_n{|}^2$.

A triangular taper majorizes a fixed fraction of the summation interval. Its Fourier kernel is the Fejér kernel, bounded by $C\min (m,(m\Vert \theta {\Vert }^2{)}^{-1})$. For separated sample points, split each row sum at distance $1/m$: the plateau and square-decay tail each contribute $O({\delta }^{-1})$, while the diagonal contributes $O(m)$. Bounding the resulting quadratic form proves the dual sieve with constant $C(N+{\delta }^{-1})$. Operator norm duality gives the primal sieve.

Let $K(\Delta )={\max }_t\#\{r:\Vert {\theta }_r-t\Vert \le \Delta /2\}$. Without a separation assumption,For $0<\Delta \le 1$, each point belongs to at most $K(\Delta )$ integration arcs in the Sobolev–Gallagher inequality. For $\Delta \ge 1$, $K(\Delta )$ is the total number of points, and the Cauchy-Schwarz inequality bound $|S{|}^2\le N\sum |a_n{|}^2$ suffices.

When $N\le P$,An arc of length $1/P$ contains at most three points of each grid of denominator $p\le 2P$. The Chebyshev estimate gives $O(P/\log P)$ such primes. Apply the local-multiplicity large sieve. Using only the separation of distinct reduced fractions gives the weaker $O(P^2)\sum |a_n{|}^2$.

Points ${\theta }_r$ have circular spacing at least $\delta$ when $\Vert {\theta }_r-{\theta }_s\Vert \ge \delta$ for distinct $r,s$, where $\Vert t\Vert ={\min }_{k\in \mathbb{Z}}|t-k|$. The distance is measured on the circle group $\mathbb{R}/\mathbb{Z}$, so points near zero and one can be close.

The continuous Buchstab function satisfies $w(u)=1/u$ for $1\le u\le 2$ and $\frac{d}{du}(uw(u))=w(u-1)$ for $u>2$. It describes the density of rough numbers.

The Buchstab function takes values both above and below $e^{-\gamma }$ on every interval of length one in $[1,\infty )$. The equation $\frac{d}{du}(u(w(u)-e^{-\gamma }))=w(u-1)-e^{-\gamma }$ propagates any fixed sign forwards; the rapid decay to zero then forces an impossible identically zero tail.

For each fixed $u>1$, the number $\Phi (z^u,z)$ of z-sieved numbers at most $z^u$ satisfies $\Phi (z^u,z)\sim z^{u}w(u)/\log z$ as $z\to \infty$. The fixed-$u$ asymptotic does not extend to $u=1$.

A $z$-rough integer has no prime factor below $z$; $1$ is included. Some authors instead exclude prime factors at most $z$, so the endpoint convention should be stated.

For a finite integer set $A$ and a set of primes $\mathcal{P}$, the sifting function counts elements of $A$ divisible by no prime in $\mathcal{P}$ below $z$:

For a nonnegative weighted sequence $\mathcal{A}=(a_n)$, the same notation means $S(\mathcal{A},\mathcal{P},z)={\sum }_{(n,P(z))=1}{a}_n$.

Put $|{\mathcal{A}}_d|={\sum }_{d\mid n}{a}_n$. A nonnegative sequence has distribution $(X,P(z),g,(r_d))$ when $g$ is multiplicative on the squarefree divisors of $P(z)$, $0\le g(p)<1$, andfor every $d\mid P(z)$.

If $w<z$, ordering the least prime factor giveswhere $({\mathcal{A}}_p{)}_n=a_{pn}$ in a set formulation, or equivalently ${\mathcal{A}}_p$ restricts the original sequence to terms divisible by $p$.

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