A question on the derivation of Selberg's sieve

71 Views Asked by At

I am currently reading An Introduction to Sieve Methods and Their Applications by Cojocaru and Murty. In section 7.1, I became stuck on the following derivation:

Let $\lambda_d$ be a real sequence such that $\lambda_d=1$ and $P_z=\prod_{p\le z}p$, so we have

$$ \Phi(x,z)=\sum_{\substack{n\le x\\(n,P_z)=1}}1\le x\sum_{d_1,d_2|P_z}{\lambda_{d_1}\lambda_{d_2}\over[d_1,d_2]}+\mathcal O\left(\sum_{d_1,d_2|P_z}|\lambda_{d_1}||\lambda_{d_2}|\right)\tag1 $$

However, in the later step, the authors introduce the constraint that $\lambda_d=0$ for $d>z$ and immediately convert the above inequality into

$$ \Phi(x,z)\le x\sum_{d_1,d_2\le z}{\lambda_{d_1}\lambda_{d_2}\over[d_1,d_2]}+\mathcal O\left(\sum_{d_1,d_2\le z}|\lambda_{d_1}||\lambda_{d_2}|\right)\tag2 $$

I know that under the new constraint for $\lambda_d$, $d_1,d_2|P_z$ means that $d_1,d_2$ are square-free numbers that do not exceed $P_z$, but this interpretation still does not allow me to deduce (2) from (1). I wonder could anyone give me a hint on how I should proceed from where I am stuck.