= Solution
For a fixed <prime> $p\in[P,2P]$, the grid $a/p$ has <circular spacing> $1/p\geq1/(2P)$. Consequently an arc of length $\Delta=1/P$ contains at most three points of this grid, including endpoints. The standard <Chebyshev estimate> $\pi(t)\ll t/\log t$ for the <prime-counting function> gives
$$
K(1/P)\leq3\#\{p\in[P,2P]:p\text{ prime}\}\ll\frac P{\log P}.
$$
Since $N\leq P$, the <local-multiplicity large sieve> yields the <prime-denominator large sieve>:
$$
\boxed{\sum_{\substack{P\leq p\leq2P\\p\text{ prime}}}\sum_{a=1}^{p-1}|S(a/p)|^2\ll\frac{P^2}{\log P}E.}
$$
By contrast, distinct <reduced fractions> with denominators at most $2P$ have circular distance at least $1/(4P^2)$: their difference, even after subtraction of an <integer>, has a nonzero <integer> numerator over denominator $pp\prime$. Applying part (a) alone gives only $(4P^2+2\pi N)E\ll P^2E$. \b[The local-multiplicity argument saves a factor of $\log P$.]
Back to article page
