This question is from course notes in sieve theory and I am struck on this assertion in the proof of Linnik's theorem.
Consider Page 4 of lecture 14 here: http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html.
Link of lecture 14:http://www.math.tau.ac.il/~rudnick/courses/sieves2015/LargeSieve1.pdf
I have question in Last line of the proof on page 4: I am not able to deduce how did the author wrote #{ $ p \leq N^{1/2} : n_p > N^{\epsilon} $} equals $\sum_{p\in P}1 $ and how does that is also $\ll_{\epsilon}$ 1.
Maybe $S(A, P ,\Omega) \gg_{\epsilon} N$ and $S(A,P, \Omega) \leq 2 N/ S(z)$have to be used but using $S(A, P ,\Omega) \geq C_{\epsilon} N$ for some constant $C_{\epsilon}$, I am not getting that $N/ S(z) \ll_{\epsilon} 1$. Instead I am getting : $(C_{\epsilon } N) /2 \leq N/(S(z))$
Can you please help with this ?
$\mathcal{P}$ is by definition the set of prime numbers smaller than $N^{1/2}$ such that all positive integers smaller than $N^\epsilon$ are quadratic residues. While $n_p$ is the smallest positive integer smaller than p which is NOT a quadratic residue.
The first equality holds because an element in $\{p \leq N^{1/2} : n_p > N^{\epsilon}\}$ is a prime smaller than $N^{1/2}$ such that the smalelst positive non-quadratic residue is bigger than $N^{\epsilon},$ so it is in $\mathcal{P}.$ And conversely, an element in $\mathcal{P}$ is prime such that all non-quadratic residues are bigger than $N^{\epsilon},$ in particular the smallest one.
I think there's a typo in the last line of the proof.(The denominator should be $S(\mathcal{A},\mathcal{P},\Omega).$) However, you can argue as follows:
$$\#\{p \leq N^{1/2} : n_p > N^{\epsilon}\} = \sum_{p\in\mathcal{P}} 1 \ \le 2 \sum_{p\in\mathcal{P}}\left(1-\frac{1}{p}\right)\le 4S(z) \le \frac{8N}{S(\mathcal{A},\mathcal{P},\Omega)} <<_{\epsilon} 1.$$
The first inequality follows from the fact that for all $p\ge 2,$ $1-1/p \ge 1/2.$ The second inequality is in page 3, which follows from the Sieve. The third inequality also follows from the Sieve.