Buchstab identity

A form of the Sylvester inclusion-and-exclusion principle specialized to sieve theory (cf. also Sieve method). Let $\mathcal{A}$ be a finite integer sequence and, for any integer $q$, denote by $\mathcal{A}_q$ the subsequence of elements of $\mathcal{A}$ that are multiples of $q$. Let $\mathcal{P}$ be a set of prime numbers, and, for $z \ge 2$, let $P(z) = \prod_{p\in\mathcal{P},\,p< z} p$. Finally, let $$ S(\mathcal{A}, \mathcal{P} ,z) = \sharp \{ a \in \mathcal{A} \ : \ (a,P(z)) = 1 \} $$ denote the "sifting function" associated with $\mathcal{A}$ and $\mathcal{P}$. The Buchstab identity asserts that, for $2 \le z_1 \le z$, \begin{equation}\label{eq:1} S(\mathcal{A}_q, \mathcal{P} ,z) = S(\mathcal{A}_q, \mathcal{P} ,z_1) - \sum_{p\in \mathcal{P},\,z_1 \le p < z} S(\mathcal{A}_{pq}, \mathcal{P} ,p) \ . \end{equation}

The identity is useful for deriving a lower-bound sieve estimate from an upper bound sieve estimate (or vice versa) as follows. If the parameter $z_1$ is sufficiently small, then the quantity $S(\mathcal{A}_q, \mathcal{P} ,z_1)$ on the right-hand side of (a1) usually can be estimated asymptotically. Thus, if an upper bound for each of the terms $S(\mathcal{A}_{pq}, \mathcal{P} ,p)$ on the right-hand side of \eqref{eq:1} is known, then a lower bound for the sifting function on the left-hand side of \eqref{eq:1} can be deduced.

References

[a1]	H. Halberstam, H.-E. Richert, "Sieve methods" , Acad. Press (1974) Zbl 0298.10026