= Lower-bound sieve
A lower-bound sieve constructs a computable lower estimate for the <sifting function>, the number or weight of objects avoiding specified local exclusions. For positive integers in a finite set $A$, put $P(z)=\prod_{p<z}p$. Coefficients $\lambda_d^-$ supported on <divisors> of $P(z)$ are suitable when
$$
\sum_{d\mid\gcd(n,P(z))}\lambda_d^-\leq\mathbf1_{\gcd(n,P(z))=1}.
$$
Summing over $n\in A$ then gives
$$
|\{n\in A:\gcd(n,P(z))=1\}|\geq\sum_{d\mid P(z)}\lambda_d^-|\{n\in A:d\mid n\}|.
$$
This separates the desired survival count from more accessible divisibility counts. The weights need not be nonnegative.
For example, deleting multiples of $2$ and $3$ from $1,\ldots,N$ leaves at least $N-\lfloor N/2\rfloor-\lfloor N/3\rfloor$ numbers, by the <union bound>. Including intersections sharpens this elementary <inclusion-exclusion> estimate. Effective lower-bound sieves truncate much larger exclusion families while controlling their error; the <fundamental lemma of sieve theory> makes the main term positive when the distribution information is sufficiently strong.<Some sieve theory by Terence Tao (254A Notes 4)>[Combinatorial upper and lower sieve coefficients; Lemma 17]{ref}
Back to article page
