Brun sieve

Remarks

Example: let $\mathcal{A} = \set{1, \ldots, 10}$, let $\mathcal{P}$ be all primes and $z = 4$, so $P(z) = 6$. Then $S(\mathcal{A}, \mathcal{P}, 4) = \#\set{1, 5, 7} = 3$. Here $S_0 = 10$ and $S_1 = 10 - 5 - 3 = 2$, so $S_1 \le 3 \le S_0$; and $S_2 = 2 + \#\mathcal{A}_6 = 3$. The inequalities are the Bonferroni inequalities: for $m \ge 1$, the partial sums $\sum_{j \le k} (-1)^j \binom{m}{j}$ are $\ge 0$ for even $k$ and $\le 0$ for odd $k$. Non-example: the full Legendre sum $S_r$ with $r \ge \omega(P(z))$ is exact, but it is not a truncation. It has $2^{\omega(P(z))}$ terms, and the errors in approximating each $\#\mathcal{A}_d$ add up. Brun's later, more refined sieve replaces the condition $\omega(d) \le r$ by conditions on the sizes of the prime factors of $d$.