[proofplan]
The proof is the basic linearization argument behind combinatorial sieves. Let $S(\mathcal A,\mathcal P,z)$ denote the sifted counting function from the statement, and for each positive integer $d$ let $A_d := \#\{a \in \mathcal A : d \mid a\}$ denote the divisor-counting quantity, with multiplicity inherited from the finite multiset $\mathcal A$. We sum the pointwise upper and lower sieve-weight inequalities over the elements of $\mathcal A$, then interchange the finite order of summation. The resulting inner sums are exactly the quantities $A_d$, so the sieve axiom separates each expression into a main term and a remainder term. The level condition and the bound $|\lambda_d^\pm| \le 1$ then control the total remainder by the displayed error sum.
[/proofplan]
[step:Sum the upper weight inequality over the multiset $\mathcal A$]
For each positive integer $d$, define
\begin{align*}
A_d := \#\{a \in \mathcal A : d \mid a\},
\end{align*}
where the count uses the multiplicity of $a$ in the finite multiset $\mathcal A$. For each $a \in \mathcal A$, the defining upper sieve-weight inequality applied to $n=a$ gives
\begin{align*}
\mathbb{1}_{\gcd(a,P(z)) = 1} \le \sum_{d \mid \gcd(a,P(z))} \lambda_d^+.
\end{align*}
Summing over $a \in \mathcal A$ with multiplicity gives
\begin{align*}
S(\mathcal A,\mathcal P,z) \le \sum_{a \in \mathcal A} \sum_{d \mid \gcd(a,P(z))} \lambda_d^+.
\end{align*}
Because $\mathcal A$ is finite and $P(z)$ has finitely many positive divisors, the double sum is finite, so we may interchange the order of summation:
\begin{align*}
\sum_{a \in \mathcal A} \sum_{d \mid \gcd(a,P(z))} \lambda_d^+ = \sum_{d \mid P(z)} \lambda_d^+ \#\{a \in \mathcal A : d \mid a\}.
\end{align*}
By the definition of $A_d$, this becomes
\begin{align*}
S(\mathcal A,\mathcal P,z) \le \sum_{d \mid P(z)} \lambda_d^+ A_d.
\end{align*}
[guided]
The role of the upper weights is to replace the condition $\gcd(a,P(z))=1$ by a divisor sum. Recall that, for each positive integer $d$, the divisor-counting quantity is
\begin{align*}
A_d := \#\{a \in \mathcal A : d \mid a\},
\end{align*}
with multiplicity inherited from the finite multiset $\mathcal A$. For each element $a \in \mathcal A$, the upper sieve-weight hypothesis says that the indicator of being sifted is bounded above by
\begin{align*}
\sum_{d \mid \gcd(a,P(z))} \lambda_d^+.
\end{align*}
Thus
\begin{align*}
\mathbb{1}_{\gcd(a,P(z)) = 1} \le \sum_{d \mid \gcd(a,P(z))} \lambda_d^+.
\end{align*}
Summing this inequality over the finite multiset $\mathcal A$ gives
\begin{align*}
S(\mathcal A,\mathcal P,z) = \sum_{a \in \mathcal A} \mathbb{1}_{\gcd(a,P(z)) = 1} \le \sum_{a \in \mathcal A} \sum_{d \mid \gcd(a,P(z))} \lambda_d^+.
\end{align*}
Now we reorganize the finite double sum by grouping terms according to the divisor $d$. This is legitimate because there are only finitely many $a \in \mathcal A$ and only finitely many divisors $d$ of $P(z)$. The condition $d \mid \gcd(a,P(z))$ is equivalent to the two conditions $d \mid P(z)$ and $d \mid a$. Hence
\begin{align*}
\sum_{a \in \mathcal A} \sum_{d \mid \gcd(a,P(z))} \lambda_d^+ = \sum_{d \mid P(z)} \lambda_d^+ \#\{a \in \mathcal A : d \mid a\}.
\end{align*}
The counting factor is precisely $A_d$ by definition, so the upper bound becomes
\begin{align*}
S(\mathcal A,\mathcal P,z) \le \sum_{d \mid P(z)} \lambda_d^+ A_d.
\end{align*}
This is the key reduction: the sifted counting problem has been converted into a linear combination of the divisor-counting quantities governed by the sieve axiom.
[/guided]
[/step]
[step:Insert the sieve axiom and bound the upper remainder]
For every $d \mid P(z)$, the sieve axiom gives
\begin{align*}
A_d = X\frac{\omega(d)}{d} + r_d.
\end{align*}
Substituting this identity into the previous upper bound yields
\begin{align*}
S(\mathcal A,\mathcal P,z) \le X\sum_{d \mid P(z)} \lambda_d^+\frac{\omega(d)}{d} + \sum_{d \mid P(z)} \lambda_d^+ r_d.
\end{align*}
Since $\lambda_d^+ = 0$ whenever $d \ge D$, the remainder sum is supported on the divisors $d \mid P(z)$ with $d < D$. Since $|\lambda_d^+| \le 1$, the triangle inequality gives
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^+ r_d \le \left|\sum_{d < D,\ d \mid P(z)} \lambda_d^+ r_d\right| \le \sum_{d < D,\ d \mid P(z)} |\lambda_d^+| |r_d| \le \sum_{d < D,\ d \mid P(z)} |r_d|.
\end{align*}
Therefore
\begin{align*}
S(\mathcal A,\mathcal P,z) \le X\sum_{d \mid P(z)} \lambda_d^+\frac{\omega(d)}{d} + \sum_{d < D,\ d \mid P(z)} |r_d|.
\end{align*}
[guided]
We now use the sieve axiom to convert the divisor-counting quantities into a main term plus an error term. For each divisor $d \mid P(z)$, the axiom states
\begin{align*}
A_d = X\frac{\omega(d)}{d} + r_d.
\end{align*}
Substituting this equality into
\begin{align*}
S(\mathcal A,\mathcal P,z) \le \sum_{d \mid P(z)} \lambda_d^+ A_d
\end{align*}
gives
\begin{align*}
S(\mathcal A,\mathcal P,z) \le X\sum_{d \mid P(z)} \lambda_d^+\frac{\omega(d)}{d} + \sum_{d \mid P(z)} \lambda_d^+ r_d.
\end{align*}
The only remaining task is to control the error sum. The level condition for the upper weights says that $\lambda_d^+ = 0$ for $d \ge D$, so the error sum has no contribution from those divisors. Hence
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^+ r_d = \sum_{d < D,\ d \mid P(z)} \lambda_d^+ r_d.
\end{align*}
Taking absolute values and applying the triangle inequality gives
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^+ r_d \le \left|\sum_{d < D,\ d \mid P(z)} \lambda_d^+ r_d\right| \le \sum_{d < D,\ d \mid P(z)} |\lambda_d^+| |r_d|.
\end{align*}
Finally the sieve-weight bound $|\lambda_d^+| \le 1$ yields
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^+ r_d \le \sum_{d < D,\ d \mid P(z)} |r_d|.
\end{align*}
Combining this with the main-term identity proves the asserted upper sieve inequality.
[/guided]
[/step]
[step:Sum the lower weight inequality and identify the same divisor sums]
For each $a \in \mathcal A$, the defining lower sieve-weight inequality applied to $n=a$ gives
\begin{align*}
\sum_{d \mid \gcd(a,P(z))} \lambda_d^- \le \mathbb{1}_{\gcd(a,P(z)) = 1}.
\end{align*}
Summing over $a \in \mathcal A$ and interchanging the finite sums as in the upper-bound argument gives
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^- A_d \le S(\mathcal A,\mathcal P,z).
\end{align*}
Thus
\begin{align*}
S(\mathcal A,\mathcal P,z) \ge \sum_{d \mid P(z)} \lambda_d^- A_d.
\end{align*}
[guided]
The lower weights give the reverse pointwise comparison. For each $a \in \mathcal A$, the lower sieve-weight hypothesis gives
\begin{align*}
\sum_{d \mid \gcd(a,P(z))} \lambda_d^- \le \mathbb{1}_{\gcd(a,P(z)) = 1}.
\end{align*}
We sum this inequality over the finite multiset $\mathcal A$. Since both $\mathcal A$ and the divisor set of $P(z)$ are finite, no convergence theorem is involved; this is only a finite rearrangement of terms. We obtain
\begin{align*}
\sum_{a \in \mathcal A} \sum_{d \mid \gcd(a,P(z))} \lambda_d^- \le \sum_{a \in \mathcal A} \mathbb{1}_{\gcd(a,P(z)) = 1}.
\end{align*}
The sum on the right is $S(\mathcal A,\mathcal P,z)$ by the definition of the sifted counting function. On the left, the condition $d \mid \gcd(a,P(z))$ is equivalent to requiring both $d \mid P(z)$ and $d \mid a$. Grouping the finite sum by $d$ gives
\begin{align*}
\sum_{a \in \mathcal A} \sum_{d \mid \gcd(a,P(z))} \lambda_d^- = \sum_{d \mid P(z)} \lambda_d^- \#\{a \in \mathcal A : d \mid a\}.
\end{align*}
By the definition of $A_d$, this becomes
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^- A_d \le S(\mathcal A,\mathcal P,z).
\end{align*}
Equivalently,
\begin{align*}
S(\mathcal A,\mathcal P,z) \ge \sum_{d \mid P(z)} \lambda_d^- A_d.
\end{align*}
This is the lower-bound analogue of the upper linearization step.
[/guided]
[/step]
[step:Insert the sieve axiom and bound the lower remainder]
Using the sieve axiom again,
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^- A_d = X\sum_{d \mid P(z)} \lambda_d^-\frac{\omega(d)}{d} + \sum_{d \mid P(z)} \lambda_d^- r_d.
\end{align*}
Since $\lambda_d^- = 0$ whenever $d \ge D$, and since $|\lambda_d^-| \le 1$, we have
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^- r_d \ge -\left|\sum_{d < D,\ d \mid P(z)} \lambda_d^- r_d\right| \ge -\sum_{d < D,\ d \mid P(z)} |\lambda_d^-| |r_d| \ge -\sum_{d < D,\ d \mid P(z)} |r_d|.
\end{align*}
Combining this estimate with the lower divisor-sum inequality gives
\begin{align*}
S(\mathcal A,\mathcal P,z) \ge X\sum_{d \mid P(z)} \lambda_d^-\frac{\omega(d)}{d} - \sum_{d < D,\ d \mid P(z)} |r_d|.
\end{align*}
Together with the upper estimate already proved, this establishes both combinatorial sieve inequalities.
[guided]
We now convert the lower divisor sum into the lower main term and an error. The sieve axiom states that, for every divisor $d \mid P(z)$,
\begin{align*}
A_d = X\frac{\omega(d)}{d} + r_d.
\end{align*}
Substituting this identity into the lower divisor-sum expression gives
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^- A_d = X\sum_{d \mid P(z)} \lambda_d^-\frac{\omega(d)}{d} + \sum_{d \mid P(z)} \lambda_d^- r_d.
\end{align*}
Because the lower weights have level $D$, the support condition gives $\lambda_d^- = 0$ for every $d \ge D$. Therefore the remainder term is supported only on divisors $d \mid P(z)$ with $d < D$:
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^- r_d = \sum_{d < D,\ d \mid P(z)} \lambda_d^- r_d.
\end{align*}
For a lower bound, we need to control how negative this error can be. Any real number $u$ satisfies $u \ge -|u|$, so with
\begin{align*}
u := \sum_{d < D,\ d \mid P(z)} \lambda_d^- r_d,
\end{align*}
we get
\begin{align*}
\sum_{d \mid P(z)} \lambda_d^- r_d \ge -\left|\sum_{d < D,\ d \mid P(z)} \lambda_d^- r_d\right|.
\end{align*}
Applying the triangle inequality to the finite sum and then using $|\lambda_d^-| \le 1$ gives
\begin{align*}
-\left|\sum_{d < D,\ d \mid P(z)} \lambda_d^- r_d\right| \ge -\sum_{d < D,\ d \mid P(z)} |\lambda_d^-| |r_d| \ge -\sum_{d < D,\ d \mid P(z)} |r_d|.
\end{align*}
Combining this lower bound for the remainder with
\begin{align*}
S(\mathcal A,\mathcal P,z) \ge \sum_{d \mid P(z)} \lambda_d^- A_d
\end{align*}
therefore yields
\begin{align*}
S(\mathcal A,\mathcal P,z) \ge X\sum_{d \mid P(z)} \lambda_d^-\frac{\omega(d)}{d} - \sum_{d < D,\ d \mid P(z)} |r_d|.
\end{align*}
Together with the upper estimate, this proves both stated combinatorial sieve inequalities.
[/guided]
[/step]
