Selberg sieve (source code)

= Selberg sieve
{c}
{wiki}

The <Selberg sieve> constructs an <upper bound> for a <sifting function> using a square. Let $P$ be a <squarefree integer>, choose real weights $\lambda_d$ supported on selected <divisors> of $P$, and impose $\lambda_1=1$. Then
$$
\mathbf1_{\gcd(n,P)=1}\le\left(\sum_{d\mid\gcd(n,P)}\lambda_d\right)^2.
$$
When $n$ is coprime to $P$, the sum is exactly $1$; otherwise its square is nonnegative, which proves the inequality. Multiplying by nonnegative sequence weights and summing gives
$$
S(\mathcal A,P)\le\sum_{d,e}\lambda_d\lambda_e\,|\mathcal A_{[d,e]}|,
$$
where $[d,e]$ is the <least common multiple> and $|\mathcal A_l|$ is the weight of terms divisible by $l$.

A <sieve distribution> writes $|\mathcal A_l|=Xg(l)+r_l$. One then minimizes the main <quadratic form> $\sum_{d,e}\lambda_d\lambda_e g([d,e])$ subject to the support and normalization, while separately controlling the remainder. The <Selberg sieve diagonalization> explains the minimizing weights. This yields results such as the <prime-tuple upper bound from the Selberg sieve>, but the nonnegative-square construction by itself supplies only an <upper bound>.<Some sieve theory by Terence Tao (254A Notes 4)>[Selberg sieve: quadratic-weight construction]{ref}