Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 27 / 1

Let $L=\sqrt{D}$. Regroup the finite divisor sum using the least common multiple:This is nonnegative. If $n$ has no prime factor in $\mathcal{P}$, only $d=1$ can contribute to the inner sum, so it equals ${\rho }_1=1$. This proves the required pointwise upper-bound sieve inequality. Whenever a term defining ${\lambda }_d$ is nonzero, $u,v\le L$ and their prime factors lie in $\mathcal{P}$. Hence $d=[u,v]\le uv\le L^2=D$, and every prime factor of $d$ lies in $\mathcal{P}$. Thus these are upper-bound sieve weights of level $D$, as described by the Selberg least-common-multiple weights.

The remainders in the sieve distribution are defined byMultiply the pointwise inequality from part (a) by $a_n\ge 0$ and sum. Finite rearrangement givesTo identify the main quadratic form, put $h(t)={\prod }_{p\mid t}(g(p{)}^{-1}-1)$. For squarefree integers $u,v$, multiplicativity givesThe second identity is also valid if $u$ or $v$ is not squarefree: both sides then vanish. Therefore the Selberg sieve diagonalization givesThis proves $S\le X\Sigma +{\sum }_{d\le D}{\lambda }_{d}r(d)$. Notice that the hypotheses do not force ${\rho }_m$ to vanish on non-squarefree integers; those coefficients simply make no contribution to this main quadratic form because $g(m)=0$.

For coefficients $b_n$ supported on an interval of length $H$, write $B=\sum b_n$ and $B_p(a)={\sum }_{n\equiv a(\mathrm{mod}p)}{b}_n$. The variance form of the large sieve statesThe constant is absolute. One may take the explicit right side $(Q^2+2\pi H)\sum |b_n{|}^2$, by orthogonality of roots of unity and the exponential-sum large sieve proved in Question 2.

Take $H=\lfloor N^2\rfloor$, $Q=N$, and $b_n$ the indicator function of the $N^{\epsilon }$-smooth numbers up to $N^2$. Applying the given smooth-number density with parameter $\epsilon /2$ giveswith a harmless adjustment of the constant for integer endpoints. If an odd prime $p\le N$ has least quadratic nonresidue $n(p)>N^{\epsilon }$, then $p>N^{\epsilon }$: a quadratic nonresidue always occurs among $1,\dots ,p-1$. Every prime factor of every selected smooth number is thus a nonzero quadratic residue modulo $p$. By the multiplicativity of the Legendre symbol, every selected number is a nonzero quadratic residue modulo $p$.

There are $(p-1)/2$ nonzero quadratic nonresidue classes, and $B_p(a)=0$ on all of them. Their contribution to the variance is at leastIf $R$ denotes the number of exceptional primes, the variance form of the large sieve, with $\sum |b_n{|}^2=B$, yields $R{B}^2\ll N^{2}B$. ConsequentlyThis is the bounded exceptional primes for least quadratic nonresidues argument. Using an interval of length $N^2$ is what matches the $Q^2$ term; an interval of length $N$ would not give a bounded exceptional set.