Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 27 (Elementary Methods in Analytic Number Theory)

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.

The points are $\delta$-spaced if their circular spacing satisfies $\Vert {\theta }_r-{\theta }_s\Vert \ge \delta$ for $r\ne s$, where $\Vert t\Vert$ is distance to the nearest integer. Ordinary distance on the real line would be insufficient because the complex exponential is periodic.

Let $S(t)={\sum }_{M<n\le M+N}{a}_{n}e(nt)$ and $F(t)=e(-Mt)S(t)$. Multiplication by this unit-modulus factor leaves $|S(t)|$ unchanged and places the frequencies of $F$ in $1,\dots ,N$. Put $E=\sum |a_n{|}^2$. The permitted Sobolev–Gallagher inequality, in the form needed here, isFor $0<\delta \le 1$, the arcs about the ${\theta }_r$ have disjoint interiors on the circle group. Summing and applying the Cauchy-Schwarz inequality givesThe Cauchy-Schwarz inequality here follows by expanding $0\le \int |u-cv{|}^2$ and minimizing over $c\in \mathbb{C}$. For completeness, the finite-interval Parseval identities follow by expanding the squares: ${\int }_0^{1}e(kt)dt$ is one at $k=0$ and zero at every other integer $k$. Thus $\int |F{|}^2=E$ and $\int |F\prime {|}^2\le 4{\pi }^2{N}^{2}E$. We obtain the exponential-sum large sieve boundIf $\delta >1$, there is at most one point, and the direct Cauchy-Schwarz inequality bound $|S{|}^2\le NE$ proves the same assertion.

Use the same Sobolev–Gallagher inequality on arcs of length $\Delta$. They now overlap, but every point belongs to at most $K(\Delta )$ arcs, by the definition of that local multiplicity. For $0<\Delta \le 1$, summing the integrals therefore givesThis is the local-multiplicity large sieve. If $\Delta \ge 1$, every point is within circular distance $\Delta /2$ of every center, so $K(\Delta )=R$. The direct Cauchy-Schwarz inequality bound ${\sum }_r|S({\theta }_r){|}^2\le RNE$ gives the requested estimate in this remaining case.

For a fixed prime $p\in [P,2P]$, the grid $a/p$ has circular spacing $1/p\ge 1/(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 givesSince $N\le P$, the local-multiplicity large sieve yields the prime-denominator large sieve: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^{2}E$. The local-multiplicity argument saves a factor of $\log P$.

Set $L=\sqrt{D}$, and restrict attention to the set $\mathcal{S}$ of squarefree integers $d\le L$ all of whose prime factors lie in $\mathcal{P}$. Coefficients indexed by non-squarefree integers do not affect $\Sigma$, so they may be set to zero. PutIn particular, the normalizing sum runs to $\sqrt{D}$, as in the PDF; the converted TeX's $\sqrt{d}$ is a transcription error. Define $y_t={\sum }_{\begin{array}{c}m\in \mathcal{S}\\ t\mid m\end{array}}g(m){\rho }_m$. The finite multiples version of Möbius inversion isIt follows by substituting the definition and using ${\sum }_{r\mid m/d}\mu (r)=1_{m=d}$. Taking $d=1$ gives $1={\sum }_t\mu (t)y_t$. Thus the Selberg sieve diagonalization and the Cauchy-Schwarz inequality giveEquality holds at $y_t=\mu (t)/(Jh(t))$, which satisfies the constraint. Inverting, and writing $t=dv$, yieldsFor $d\notin \mathcal{S}$ set ${\rho }_d=0$. The formula has ${\rho }_1=1$ and gives minimum $\Sigma =1/J$.

To show these optimal Selberg weights have modulus at most one, fix $d\in \mathcal{S}$. Each integer $ev$, with $e\mid d$, $(v,d)=1$ and $v\le L/d$, is a distinct term of $\mathcal{S}$. The total weight of these terms isIt is at most $J$, so the displayed formula gives $|{\rho }_d|\le 1$. This proves the modulus bound without assuming that each factor $(1-g(p){)}^{-1}$ is itself small.

Write $f(n)=3^{\omega (n)}$, where $\omega$ is the prime omega function. If $p^a\Vert n$, its contribution to the Dirichlet convolution $(f\ast \Lambda )(n)$ isSince $3(a-1+1/3)\ge a$, summing over the prime factors proves the log-weighted convolution bound for three to the prime omega, $f(n)\log n\le 3(f\ast \Lambda )(n)$. On $\sqrt{D}\le n\le D$, $\log n\ge \frac{1}{2}\log D$, henceThis is the required inequality. The standard Chebyshev estimate $\psi (t)\ll t$ bounds its right side by $D(\log D{)}^{-1}{\sum }_{m\le D}f(m)/m$. To bound the latter sum, use multiplicativity and extend to all numbers with prime factors at most $D$:The Mertens second theorem states ${\sum }_{p\le D}1/p=\log \log D+O(1)$. Taking logarithms of the product, with a summable $O(p^{-2})$ remainder, gives $3\log \log D+O(1)$. Therefore the product is $O({\log }^{3}D)$, proving the summatory bound for three to the prime omega in the required range:

Let $1(n)=1$ and $ϵ(n)=1_{n=1}$, the identity for Dirichlet convolution. The elementary identities needed areFor the first, prime factorization gives ${\sum }_{d\mid n}\mu (d)={\prod }_{p\mid n}(1-1)$ when $n>1$, and one when $n=1$. For the second, if $n=\prod p^{a_p}$, then ${\sum }_{d\mid n}\Lambda (d)={\sum }_p{a}_p\log p=\log n$, the Von Mangoldt divisor identity. Convolving the second identity with $\mu$ proves the third.

For $U,V\ge 1$, let the subscripts $\le U$, $>U$, $\le V$, $>V$ denote truncations. The Vaughan identity isIts pointwise form isTo prove it, use ${\mu }_{>U}\ast 1=ϵ-{\mu }_{\le U}\ast 1$ and $1\ast {\Lambda }_{>V}=\log -1\ast {\Lambda }_{\le V}$. This givesand rearrangement proves the formula, as in the Vaughan identity proof.

The Bombieri–Vinogradov theorem states that for every $A>0$ there is $B>0$ such thatHere $\psi (y;q,a)={\sum }_{\begin{array}{c}n\le y\\ n\equiv a(\mathrm{mod}q)\end{array}}\Lambda (n)$ is the Chebyshev function in an arithmetic progression, and $\varphi$ is the Euler totient function. In particular, partial summation givesafter choosing the logarithmic saving in the weighted theorem sufficiently large and absorbing the prime power terms. This is the offset logarithmic integral function.

For the proof strategy, Orthogonality of Dirichlet characters converts errors in arithmetic progressions into character sums of Dirichlet characters weighted by $\Lambda$. Reduction to primitive Dirichlet characters is followed by the character large sieve, which bounds their mean square by $O((N+Q^2)\sum |a_n{|}^2)$ with the usual $q/\varphi (q)$ weights. The Vaughan identity separates the weighted sums into short terms, Type I sums and Type II sums. Direct inner-sum estimates handle the Type I sums; the Cauchy-Schwarz inequality and the large sieve control the Type II sums. The Siegel–Walfisz theorem supplies arbitrarily strong logarithmic savings for small moduli, where an average estimate alone would not suffice. A dyadic decomposition, suitable $U,V$ and a sufficiently large $B$ absorb the divisor and logarithmic losses. This explains why the range is essentially $Q^2\le x$, with logarithmic room to spare.

Put $E_q={\max }_{(a,q)=1}|\pi (x;q,a)-\mathrm{Li}(x)/\varphi (q)|$, with $\mathrm{Li}$ the offset logarithmic integral function. The permitted standard sieve estimate can be taken as the Brun–Titchmarsh theorem:For $q\le x^{0.99}$, $\log (x/q)\ge 0.01\log x$. Also $\mathrm{Li}(x)\ll x/\log x$. Thus both terms defining $E_q$ are $O(x/(\varphi (q)\log x))$, uniformly over the permitted moduli. Apply the Cauchy-Schwarz inequality in the formThis is the weighted arithmetic-progression error bound. The prime omega function and Euler totient function weights can therefore be handled using an unweighted mean error and a separate positive sum.

Take sieve level $D=x^{1/3}$ and coefficient cutoff $L=\sqrt{D}=x^{1/6}$. Let $\mathcal{P}$ be the finite set of odd primes at most $L$. Give $n=p+2$ one unit of weight for each prime $p\le x$. For an odd squarefree integer $d$ on these primes, the sieve distribution isThe residue $-2$ is coprime to every such $d$, and $g(p)=1/(p-1)\in (0,1)$ for all permitted primes. Values of $g$ outside the permitted set can be chosen arbitrarily in $(0,1)$ at primes and extended multiplicatively on squarefree integers.

For the Selberg sieve normalizing sum, $k(p)=g(p)/(1-g(p))=1/(p-2)$ andHere is a direct proof of this lower bound. Restrict the Euler product to $3\le p\le y=L^{1/4}$. The Mertens first theorem gives ${\sum }_{3\le p\le y}\log p/(p-1)=\log y+O(1)$, which is at most $\frac{1}{2}\log L$ for large $L$. The Mertens second theorem givesThe truncated Euler-product lower bound, with $\theta =1/2$, now gives $J\ge W/2\gg \log L$.

Use the minimizing Selberg sieve weights from Question 3. Their absolute values are at most one, so the Selberg least-common-multiple weights satisfy $|{\lambda }_d|\le 3^{\omega (d)}$. Parts (a) and (b) control the remainder:The first factor uses the Bombieri–Vinogradov theorem; $D=x^{1/3}$ is below $x^{1/2}/{\log }^{B}x$ for all sufficiently large $x$. The second uses the permitted ${\sum }_{q\le D}{9}^{\omega (q)}/\varphi (q)\ll {\log }^{9}D$. The PDF has the exponent nine, which the TeX transcribes incorrectly. Choose $A=14$ to obtain $O(x/{\log }^{3}x)$.

Every twin prime pair with $p+2>L$ survives the finite sieve, while the pairs with $p+2\le L$ number at most $L$. The Selberg upper-bound sieve thus givesTherefore the twin-prime count is $O(x/{\log }^{2}x)$. The finite cutoff on the forbidden primes is essential: sieving by all odd primes would also discard the large prime values $p+2$ that we are trying to count.

In the level-$D$ convention used here, the Selberg upper-bound sieve states that a nonnegative sequence with sieve distribution $A_d=Xg(d)+r(d)$ satisfiesIt follows by minimizing the quadratic form with the Selberg sieve weights and using the Selberg least-common-multiple weights bound $|{\lambda }_d|\le 3^{\omega (d)}$.

Sieve the interval $x<n\le x+z$ by two and by the primes congruent to three modulo four, up to $L=\sqrt{D}$. The interval divisor counts giveThus $X=z$, $g(p)=1/p$, and $r(d)=O(1)$ uniformly in the location of the interval. Take $D=z^{1/2}$ and $L=z^{1/4}$.

To bound $J$, let $y=L^{1/4}$ and form the Euler product over the forbidden primes at most $y$. The given reciprocal-prime sum in residue class one modulo four, subtracted from the Mertens second theorem, yieldsMoreover, the Mertens first theorem bounds the logarithmic mean by ${\sum }_{p\le y}(\log p)/p=\log y+O(1)\le \frac{1}{2}\log L$ for large $L$. The truncated Euler-product lower bound gives $J\ge W/2\gg \sqrt{\log z}$.

The full-range summatory bound for three to the prime omega bounds the error by $O(D{\log }^{2}D)=O(\sqrt{z}{\log }^{2}z)$, which is $O(z/\sqrt{\log z})$. Every integer whose prime factors are all congruent to one modulo four survives this finite sieve. Therefore the half-dimensional interval sieve givesThe constants are independent of $x$. Enlarging them covers the bounded range of $z$ before the asymptotic product estimates apply, so the result holds throughout $1000\le z\le x$.

Finite rearrangement and the Von Mangoldt divisor identity giveFor $m=\lfloor x\rfloor$, integral comparison of the increasing logarithm gives $\log (m!)=m\log m-m+O(\log (m+1))$. Moving $m$ to real $x$ changes the main term by $O(\log (x+1))$. Thus the integrated Chebyshev sum hasFor $x\ge 2$, chooseThese are logarithmic Möbius function weights; they need not be upper-bound sieve weights. For $n\le x$, the Möbius inversion identities $\mu \ast 1=ϵ$ and $\mu \ast \log =\Lambda$ giveHence the expression suggested in the question isWe will use the elementary Möbius harmonic logarithmic moments, $A_j(x)={\sum }_{d\le x}\mu (d){\log }^j(x/d)/d$, for whichHere is a proof of the needed estimates. From ${\sum }_d\mu (d)\lfloor x/d\rfloor =1$, replacing floors by $x/d+O(1)$ gives $A_0=O(1)$. Also ${\sum }_d\mu (d)H_{\lfloor x/d\rfloor }/d=1$, because $\mu \ast 1=ϵ$. Substituting the permitted harmonic number estimate $H_{\lfloor t\rfloor }=\log t+\gamma +O(1/t)$ gives $A_1+\gamma A_0=1+O(1)$, so $A_1=O(1)$.

For $A_2$, the weighted Dirichlet hyperbola method gives the harmonic divisor sum expansionExplicitly, for $r=\lfloor \sqrt{t}\rfloor$, $B(t)=2{\sum }_{a\le r}{H}_{\lfloor t/a\rfloor }/a-H_r^2$. Substitute the harmonic estimate and ${\sum }_{a\le r}(\log a)/a=\frac{1}{2}{\log }^{2}r+c\prime +O(\log (2r)/r)$, obtained by unit-interval integral comparison. This proves the expansion without a prime-distribution theorem. Since $\tau =1\ast 1$, we have $\mu \ast \tau =1$, and thereforeThe summed error is bounded by $x^{-1/2}{\sum }_{d\le x}{d}^{-1/2}\log (2x/d)=O(1)$, by integral comparison. Thus $A_2=2\log x+O(1)$.

Finally substitute the asymptotic for $T$ into $F$. The main term isThe error sum is $O(x)$: partition the integers $d$ into $x/2^{j+1}<d\le x/2^j$; each interval contributes $O(x(j+1{)}^2/2^j)$, and the resulting series converges. Using the moment estimates proves the Selberg symmetry formula:In particular, the factor two comes from the quadratic logarithmic moment, rather than from an assumption of the Prime number theorem.