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 whenSumming over $n\in A$ then givesThis 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,\dots ,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.^[ref]