Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 23 / 5

The quotient-circle norm is $\Vert x{\Vert }_{\mathbb{R}/\mathbb{Z}}={\min }_{m\in \mathbb{Z}}|\tilde{x}-m|$, independent of the chosen lift $\tilde{x}$. A finite set is $\delta$-well-spaced when every two distinct points satisfy $\Vert x_r-x_s\Vert \ge \delta$. This is separation in the circle metric, including the distance across the identified endpoints.

For the matrix $A_{r,n}=e(n{x}_r)$, operator norm duality gives $\Vert A\Vert =\Vert A^{\ast }\Vert$. Thus the analytic large sieve inequalityis equivalent to the dual bound with the roles of $a_n$ and $b_r$ exchanged and the conjugate exponential. The absolute constant is independent of all the parameters.

Here is a Fejér-kernel proof of the analytic large sieve. Choose an integer center $c$ of the summation interval and an integer $m\asymp N+1$ large enough that the triangular weights $w_n=(1-|n-c|/m{)}_{+}$ are at least $1/2$ throughout it. Their Fourier kernel is $e(c\theta )F_m(\theta )$, withFor fixed $r$, spacing allows at most a bounded number of points at each successive distance $j\delta$. Splitting at $j\asymp 1/(m\delta )$ gives the row boundIn detail the near terms contribute at most $Cm/(m\delta )=C/\delta$, and the square-decay tail contributes $C/(m{\delta }^2){\sum }_{j>1/(m\delta )}{j}^{-2}\le C/\delta$; when $m\delta \ge 1$, the tail is bounded directly by $C/\delta$.

Expand the weighted dual square sum. Its matrix entries have the kernel just estimated. The symmetric row bound, or $2|b_r{b}_s|\le |b_r{|}^2+|b_s{|}^2$, bounds the quadratic form by $C(m+{\delta }^{-1})\sum |b_r{|}^2$. The weights majorize half the desired interval, proving the dual inequality and hence the primal inequality. This supplies the sieve estimate with an absolute constant, including the technical interaction between close pairs and the kernel's decaying tail.

Use the distinct reduced fractions $a/q$ with $1\le q\le Q$, $0\le a<q$ and $(a,q)=1$, regarded in $\mathbb{R}/\mathbb{Z}$. The fraction zero appears as $0/1$; one is the same circle point and is not added a second time. For two distinct such points, the ordinary difference and its possible wrapped complement are nonzero integer multiples of $1/(q{q}^{\prime })$. HenceThis proves the required separation of the Farey fractions.

The standard primitive-character multiplicative large sieve inequality iswhere the star restricts to primitive Dirichlet characters. This is the form used in analytic arguments for Linnik's theorem. The prime-power Gauss identities extend to arbitrary primitive conductors by the Chinese remainder theorem. Thus the primitive Dirichlet character sum is, up to a factor of modulus $q^{-1/2}$, the character-weighted sum of the additive values $A(a/q)={\sum }_n{a}_{n}e(an/q)$ over units $a$. Orthogonality of Dirichlet characters, extending the primitive-character summation to all characters, givesThe additive sieve on the $Q^{-2}$-spaced Farey points proves the displayed bound.

For both prime-interval applications, use the following large sieve upper bound for sifted intervals. Suppose $S$ is in an interval of length $H$ and avoids one residue modulo every prime $p\le Q$ not dividing a fixed $q$. ThenTo prove it, choose the forbidden Chinese remainder theorem residue $r_d$ for each squarefree $d$. The Ramanujan sum $c_d(n-r_d)$ equals $\mu (d)$ on $S$, since $n-r_d$ is a unit modulo $d$. Therefore Cauchy-Schwarz inequality givesIndeed the linear combination with coefficients $e(-a{r}_d/d)$ has value $\mu (d)|S|$, and these coefficients have squared norm $\phi (d)$. Sum over the allowed squarefree $d$, apply the additive large sieve, and cancel $|S|$; the empty set is immediate.

Finally ${\mathcal{L}}_1(Q)\ge c\log (2Q)$. Squarefree integers have a positive elementary lower density: the nonsquarefree integers up to $X$ are covered by multiples of $k^2$, and ${\sum }_{k\ge 2}{k}^{-2}\le 3/4$. Partial summation turns this density into the harmonic lower bound. Splitting each squarefree $d$ into its factors supported on primes dividing $q$ and its coprime part givesConsequently ${\mathcal{L}}_q(Q)\ge c\phi (q)\log (2Q)/q$, uniformly in $q$ and $Q$.

Take $S$ to be the primes in the interval and $Q=\max (2,\lfloor \sqrt{N}\rfloor )$. Every such prime exceeds $M>N\ge Q$ apart from harmless bounded small cases, so it avoids zero modulo each prime up to $Q$. The sifted-interval bound with $H=N$ and $q=1$ givesSince $Q^2=O(N)$ and $\log (2Q)\asymp \log N$, the implied constant is absolute. The choice of strict or inclusive endpoint in the prime-counting convention changes at most two terms, absorbed by the bound for $N\ge 2$.

Write the progression integers as $n=a+qm$. Their $m$ values lie in an interval of length at most $N/q+1$. For every prime $p\nmid q$, primality forbids the unique residue $m\equiv -a{q}^{-1}(\mathrm{mod}p)$; primes dividing $q$ impose no restriction because $(a,q)=1$.

Choose $Q=\max (2,\lfloor \sqrt{N/q}\rfloor )$. The selected primes exceed $M>N$, hence exceed these sieving primes. The uniform coprime-denominator estimate just proved yieldsThe assumption $N\ge q^{2+\delta }$ implies $\log (N/q)\ge \frac{1+\delta }{2+\delta }\log N\ge \frac{1}{2}\log N$. ThereforeEndpoint and bounded small-parameter corrections are again absorbed. The proof supplies the more informative short-interval progression bound before using the given size hypothesis.