Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 117 (Five Ways to Think About Primes)

For a positive integer $d$, defineThe sequence $\mathcal{A}$ has sieve distribution $(X,P_z,g,(r_d))$ when $g$ is a multiplicative arithmetic function on the squarefree divisors of $P_z$, with $0\le g(p)<1$, andfor every $d\mid P_z$. The function $g(d)$ models the local density of divisibility by $d$, while $r_d$ is the remainder.

The weighted sifting function isLet ${\lambda }_1=1$ and let the real Selberg sieve weights ${\lambda }_d$ vanish unless $d\mid P_z$ and $d\le D$. Sinceexpansion and the distribution hypothesis giveFor the optimizing Selberg weights, the main quadratic form is $G(D,z{)}^{-1}$, whereThus the general upper bound isIf the sieve level is instead defined as the largest possible least common multiple, one supports the individual weights on $d\le \sqrt{D}$; this is the same statement after replacing $D$ by $\sqrt{D}$.

Put $F(m)=m(m+2)(m+6)$ and let $\rho (d)$ be the number of roots of $F$ modulo $d$. For squarefree $d$, the Chinese remainder theorem givesIndeed, for $p\ge 5$ the three roots $0,-2,-6$ are distinct. Counting $m\le X$ in each of the $\rho (d)$ residue classes givesConsequently a suitable sieve distribution isThis is the polynomial root density in a sieve calculation.

Write $L=\log D$. By the Prime number theorem and partial summation, the sum is at most a constant timesMake the substitution $v=L/\log t$. Since $dt/t=-L{v}^{-2}dv$, this becomesFor $u>0$, the final integral is $O(e^{-cu})$ after decreasing the absolute constant $c>0$; any polynomial factor in $u$ is absorbed by the exponential, and bounded $u$ causes no problem. Taking $u=L/\log z$ provesthe exponentially damped reciprocal-prime sum estimate.

Take $\mathcal{P}$ to contain the primes at least $5$; the exceptional local behavior at $2$ and $3$ is then harmless. Fix a sufficiently large constant $w$ and later choosewith fixed small $0<\delta <\eta$. The Buchstab identity givesThe first term is $c_{w}X+O_w(1)$ for a positive constant $c_w$, by direct counting in the finitely many permitted residue classes modulo $P_w$.

For each term in the sum, part c supplies the local factor $g(p)=3/p$ and remainders bounded by powers of $3^{\omega (d)}$. Apply the Selberg upper-bound sieve to the remaining prime conditions. Mertens theorem gives the dimension-three densityso the main terms in the Buchstab sum are bounded byThis convergent tail can be made smaller than $c_{w}X/4$ by taking $w$ large. The weighted remainder terms are $o(X)$: the estimate $k^{\omega (n)}{\ll }_{k,\epsilon }{n}^{\epsilon }$ controls the summed remainders, while part d controls uniformly the loss caused by the finite sieve level. Choosing $\delta$ sufficiently small relative to $\eta$, and then taking $X$ large, therefore givesfor some absolute $c>0$.

For every counted $m$, the distinct prime divisors of $F(m)$ are either below the fixed $w$ or at least $X^{\delta }$. The first class contains at most $\pi (w)$ primes, while $F(m)\ll X^3$ makes the second class contain at mostprimes. Since every prime divisor of $m$, $m+2$, or $m+6$ divides $F(m)$,after enlarging an absolute constant $C$. A positive proportion occurs for arbitrarily large $X$, so infinitely many such $m$ exist. This is the almost-primes from an upper-bound sieve and Buchstab identity method.

Replace $F(m)$ by $m(m+1)(m+2)$. The only change is at the locally obstructing primes: every value is divisible by $2$, and every value is divisible by $3$, so omit both primes from $\mathcal{P}$. For every $p\ge 5$, the three roots $0,-1,-2$ are distinct and again give $g(p)=3/p$ and $r_d=O(3^{\omega (d)})$. All Selberg upper-bound sieve, Buchstab identity, and large-prime-factor estimates from part e are unchanged, proving the analogous result.

The Mellin transform of $F$ isBecause the support is a compact subset of $(0,\infty )$, the integral defines an entire function of $s$. The Mellin inversion formula says that, for every real $\sigma$ and every $y>0$,

Apply this with $y=n/X$ and initially $\sigma =2$. Absolute convergence of the Dirichlet series for the logarithmic derivative permits interchange of sum and integral, givingTruncate at height $T=(\log X{)}^A$, where $A$ is a sufficiently large fixed constant. The assumed bound on $\tilde{F}$ makes the discarded tails smaller than the required error. The classical Zero-free region of the Riemann zeta function and the standard bound ${\zeta }^{\prime }(s)/\zeta (s)\ll (\log (|t|+3){)}^{O(1)}$ there allow the truncated contour to move toThe only singularity crossed is the simple pole of $-{\zeta }^{\prime }/\zeta$ at $s=1$, whose residue is $1$. Its contribution isOn the new contour, $|X^s|=X^{1-c/\log \log X}$; the zeta bounds, contour length, and exponential decay of $\tilde{F}$ absorb into a slight decrease of $c$. ThereforeThis is the smoothed prime number theorem from a zero-free region.

PutIf $Y<n\le Y+X$ is prime, then $n>D=X^{1/10}$. Since $f$ is supported on $[-1,1]$, the only divisor of $n$ contributing to $W(n)$ is $d=1$, and $W(n)=f(0)=1$. Every summand $W(n{)}^2$ is nonnegative, so

LetSince $g$ is the Fourier transform of $x\mapsto e^{x}f(x)$, the Fourier inversion theorem gives the Fourier representation of a smooth Selberg weightExpanding the square, interchanging the absolutely convergent sums and integrals, and usingwe obtainThe error is $O(D^2)$ because the support of $f$ restricts both divisors to $d_j\le D$. The main factor isand its Euler product is

It remains to estimate the integral using the assumed zeta-factor bound. The transform $g$ is a Schwartz function, since $e^{x}f(x)$ is smooth and compactly supported. We may therefore truncate to $|t_1|,|t_2|\le T$, losing an arbitrarily large negative power of $T$. Uniformly in the needed truncated range, the standard estimates near the pole of the Riemann zeta function giveandAfter multiplication, one net factor $(\log D{)}^{-1}$ remains. The polynomial factors in $t_1,t_2$ are integrable against the rapidly decreasing $g(t_1)g(t_2)$, and choosing $T$ as a sufficiently large power of $\log D$ makes the tails negligible. HenceSince $D=X^{1/10}$ and $D^2=X^{1/5}\ll X/\log X$,This proves the short-interval prime upper bound from a smooth divisor weight.

With ${\mu }_{\le U}(d)=\mu (d)1_{d\le U}$ and analogous notation for ${\Lambda }_{\le V}$, Vaughan identity isThus, when $UV\le N$,The first term is short, the next two are Type I sums, and the last becomes a Type II bilinear sum after grouping variables and applying a dyadic decomposition.

Write $\alpha =a/q+\beta$, where $|\beta |\le q^{-2}$. Split the $m$-interval into $O(M/q+1)$ consecutive blocks of length at most $q/2$. If distinct integers $m,n$ lie in one block, then $0<|m-n|<q/2$. Since $(a,q)=1$,whereas $|\beta (m-n)|\le 1/(2q)$. Hence $\Vert \alpha m-\alpha n\Vert \ge 1/(2q)$.

The points $\alpha m$ in one block are therefore $1/(2q)$-separated modulo one. Order them by distance from the nearest integer. Apart from a bounded number of endpoints, the $j$th closest point has distance $\gg j/q$, and consequentlyMultiplying by $O(M/q+1)$ givesThis is the reciprocal fractional-part sum near a rational estimate.

LetApplying the Cauchy-Schwarz inequality in $t$ givesTake absolute values and apply Cauchy-Schwarz to $(r_1,r_2)$. Since ${\sum }_{r_1,r_2}|c_{r_1}{c}_{r_2}{|}^2=\Vert c{\Vert }_2^4$, expanding the remaining square givesTaking fourth roots proves the claimed bilinear quadratic exponential sum fourth-moment bound.

In the fourth moment from part c, putThen the phase is $e(\alpha s_1{s}_2{u}_1{u}_2)$. The contribution with $s_1=0$ is $O(R{T}^2)$, because $r_1=r_2$; the contribution with $u_1=0$ is $O(T{R}^2)$. Their fourth roots are respectively $R^{1/4}{T}^{1/2}$ and $R^{1/2}{T}^{1/4}$.

Off the diagonals, fix $s_2,u_1,u_2$. The variable $s_1$ ranges over an interval of length $O(R)$, subject only to harmless parity and range restrictions. The exponential geometric sum bound givesPut $m=|s_2{u}_1{u}_2|$. We have $m\le CR{T}^2$, and the number of representations of a fixed $m$ by the three factors, including signs and range restrictions, is $O({\tau }_4(m))$. Hence the fourth moment isUsing $(A+B+C{)}^{1/4}\le A^{1/4}+B^{1/4}+C^{1/4}$ in part c provesThis is the factorized fourth moment for a bilinear quadratic exponential sum.

Write $M_0=CR{T}^2$ and split the last sum in part d according as ${\tau }_4(m)<X$ or ${\tau }_4(m)\ge X$. For the first part, the reciprocal fractional-part sum near a rational givesFor the second part, use the supplied second-moment estimate and truncation of a divisor weight by its second moment:Substitute $M_0\asymp R{T}^2$, take fourth roots, and factor out $R^{1/2}{T}^{1/2}$. The four terms from the bounded-weight estimate become, after harmless enlargement by $(\log q)(\log RT{)}^{O(1)}$,with the smaller $XR$ term absorbed by $X{M}_0$. The large-weight part contributes $X^{-1/4}$. Finally, the two diagonal terms from part d contribute $R^{-1/4}$ and $T^{-1/4}$; since $X\ge 1$, the first is absorbed by $X^{1/4}{R}^{-1/4}$. Therefore

Assume $RT=N$. To beat the trivial bound $\Vert b{\Vert }_2\Vert c{\Vert }_2{N}^{1/2}$ by $(\log N{)}^{-A}$, it is enough to make every term in the parentheses of part e smaller than a sufficiently larger negative power of $\log N$, allowing for the prefactor $(\log q)(\log N{)}^{O(1)}$.

Choose the splitting parameter $X=(\log N{)}^B$ with $B$ large in terms of $A$. It then suffices, for a still larger constant $C=C(A,B)$, thatIndeed, these four conditions control respectively the last, third, second, and fourth terms, while the choice of $X$ controls the first. Equivalently, away from polylogarithmic neighborhoods of the endpoints, the estimate gives a logarithmic saving wheneverare all sufficiently large powers of $\log N$, with $R$ also larger than the chosen divisor cutoff $X$ by such a power. This is the Type II range used after Vaughan identity.

For $g\in {\mathcal{H}}_N$, writeThe orthogonality of complex exponentials converts the linear configuration count intoExpand the difference between the products for $g_1$ and $g_2$ by changing one factor at a time. A typical term iswhere each $h_j$ is either $g_1$ or $g_2$. The assumed uniform norm bound controls the first factor by $\epsilon N$. The substitution $\alpha \mapsto k\alpha$ preserves an integral over the circle group, so Hölder's inequality and the three supplied $L^3$ bounds giveEach of the four terms is therefore $O(\epsilon N^3)$, and henceThis is Fourier stability of a linear configuration count.

Use the normalized inner productThe test-function seminorm generated by $\mathcal{F}$ and its dual test-function norm areThe first quantity may only be a seminorm if $\mathcal{F}$ does not separate all functions in ${\mathcal{H}}_N$; correspondingly, the second may be infinite outside the linear span detected by $\mathcal{F}$.

Put $\delta =\exp (-{\epsilon }^{-C})$, with the absolute constant $C$ chosen sufficiently large below, and suppose for a contradiction that no $g_2$ with $0\le g_2\le 1$ satisfies $\Vert g_1-g_2{\Vert }_{\mathcal{F}}\le \epsilon$.

LetThe set $K$ is compact and convex, while $B$ is closed and convex, so $K+B$ is closed and convex. We use the following finite-dimensional form of the Hahn-Banach separation theorem: if a point lies outside a nonempty closed convex set, there is a linear functional whose value at the point is strictly greater than its supremum over that set. Identifying linear functionals on ${\mathcal{H}}_N$ through the inner product, there is therefore a function $\psi$ such thatThe separating functional cannot have zero dual norm, so rescale it to make $\Vert \psi {\Vert }_{\mathcal{F}}^{\ast }=1$. Because $\mathcal{F}$ is closed, convex, and symmetric, the finite-dimensional Bipolar theorem for a dual pair says that the unit ball of $\Vert \cdot {\Vert }_{\mathcal{F}}^{\ast }$ is precisely $\mathcal{F}$. Thus $\psi \in \mathcal{F}$ and $|\psi (n)|\le 1$.

The support function of $K$ is obtained by choosing $g(n)=1$ where $\psi (n)>0$ and $g(n)=0$ where $\psi (n)<0$. In terms of the positive part of a real-valued function ${\psi }_{+}=\max (0,\psi )$, the separating inequality becomesSince $0\le g_1\le \nu$, pointwise we have $g_1\psi \le \nu {\psi }_{+}$, and hence

Apply the supplied polynomial approximation of the positive part to $\psi$. If $P_{\epsilon }(t)={\sum }_{i=0}^m{a}_i{t}^i$, then its uniform approximation error and $\mathbb{E}\nu \le 1$ implyThe constant function $1$ and $\psi$ belong to the dual unit ball. By the assumed submultiplicativity, $\Vert {\psi }^i{\Vert }_{\mathcal{F}}^{\ast }\le 1$ for every $i\ge 0$. Dual seminorm therefore givesThe stated coefficient bound, with $C$ in $\delta$ chosen larger than the absolute constant in that bound, makes this last quantity at most $\epsilon /50$. Together with the polynomial-approximation error, this contradicts $⟨\nu -1,{\psi }_{+}⟩>\epsilon$. The required $g_2$ consequently exists. This proves the dense model theorem for a multiplicative test family.