Help needed in deducing an inequality in a lemma in the proof of linnik's theorem.

Question

I have been reading Sieve theory from notes of Zeev Rudnick here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html and I have a question on page 5 of lecture 14 here: http://www.math.tau.ac.il/~rudnick/courses/sieves2015/LargeSieve1.pdf

In the proof of lemma 3.3 in the same theorem I am nota able to understand how Z(p,h)=0 if $h \in \Omega_p$ and how does it implies that $\sum_{ h (mod p), Z(p,h)\neq 0} 1 \leq p -w(p)$

Can you please help me deducing this inequality? I am not able to understand it despite thinking a lot.

Thanks!

Answer 1

So if $h\in \Omega_p$ that means $h$ is a part of one of the excluded residue classes mod $p$. By definition of $S$, any $n\in S$ will not be a part of $\Omega_p$ and thus we can never have $n\equiv h\mod p$. The summation of $0$ terms is defined to be $0$. So $Z(p,h)=0$ if $h\in \Omega_p$

$\Sigma_{Z(p,h)\neq 0}1\leq p$ since if $Z(p,h)$ is never $0$ there are $p$ equivalence classes. We can improve this inequality using the previous fact that $Z(p,h)=0$ whenever $h\in \Omega_p$. $\omega(p):=\#\Omega_p$ so this eliminates $\omega(p)$ cases out of $p$ where we know that $Z(p,h)=0$. $$\Sigma_{Z(p,h)\neq 0}1\leq p-\omega(p)$$