View source for 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 number]]s, 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====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Halberstam,   H.-E. Richert,   "Sieve methods" , Acad. Press  (1974)  {{ZBL|0298.10026}}</TD></TR>
</table>

{{TEX|done}}