Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 28 (Prime Numbers)

Use the Fourier transform convention $\hat{f}(u)={\int }_{\mathbb{R}}f(x)e^{-2\pi iux}dx$. A version of the Poisson summation formula sufficient here isBoth sums converge absolutely. To prove it, form the periodization of a Schwartz function $P(x)={\sum }_{n\in \mathbb{Z}}f(x+n)$. The rapid decay of $f$ and all its derivatives makes this series and its differentiated series uniformly convergent on $[0,1]$, so $P$ is smooth and one-periodic. Its Fourier coefficients areRepeated integration by parts makes these coefficients rapidly decreasing. Thus ${\sum }_m\hat{f}(m)e^{2\pi imx}$ converges absolutely and uniformly and has the same coefficients as $P$. By uniqueness of Fourier series it equals $P$. Evaluation at zero proves the formula.

For $u>0$, the Gaussian $f(x)=e^{-\pi u{x}^2}$ has transform $u^{-1/2}{e}^{-\pi m^2/u}$. This follows from the Gaussian integral at frequency zero and integration by parts, which gives the differential equation ${\hat{f}}^{\prime }(v)=-(2\pi v/u)\hat{f}(v)$. Hence the Jacobi theta functionsatisfies $\Theta (u)=u^{-1/2}\Theta (1/u)$.

Use the normalization of the completed Riemann zeta functionInitially, for $\Re s>1$, the Gamma function integral and absolute convergence give its Mellin transform representationIndeed, the two equal terms for $n$ and $-n$ cancel the factor $1/2$, and the $n$th integral is ${\pi }^{-s/2}\Gamma (s/2)n^{-s}$.

Split at $u=1$ and use the theta transformation in the integral over $(0,1)$. Its elementary part isIn the remaining part substitute $v=1/u$. DefineThe pole-subtracted theta integral for the completed zeta function is thereforeSince $\Theta (u)-1=O(e^{-\pi u})$ for $u\ge 1$, both integrals and every derivative in $s$ converge uniformly on compact subsets of $\mathbb{C}$. Thus $J$ is an entire function. The boxed identity supplies the meromorphic continuation of $\Xi$ to the whole plane, with no other singularities. Its poles really are simple, because the residues of the displayed rational terms are nonzero:The identity also gives $\Xi (s)=\Xi (1-s)$, the completed functional equation of the Riemann zeta function.

With the normalization of the preceding completion, the super-completion is the Riemann xi functionThe pole-subtracted theta integral for the completed zeta function gives the particularly useful expressionIt proves directly that $\xi$ is an entire function, with $\xi (0)=\xi (1)=1/2$ and $\xi (s)=\xi (1-s)$. Here “integral function” means entire, not integer-valued.

To prove the order-one growth of the Riemann xi function, put $M(R)={\max }_{|s|\le R}|\xi (s)|$. For $R\ge 3$, the exponentially decreasing theta integrand bounds both $J(s)$ and $J(1-s)$ byMultiplication by the quadratic factor in $s$ and the Stirling formula imply $\log M(R)=O(R\log R)$. Hence the order of an entire function is at most one. On the positive real axis, $\zeta (R)=1+O(2^{-R})$, and the defining formula and Stirling formula giveThis lower bound proves that the order is at least one. Consequently $\xi$ is entire of order exactly one, generally not of finite exponential type.

Its zeros are precisely the Nontrivial zeros of the Riemann zeta function, counted with multiplicity. The values at zero and one are nonzero; the Gamma function has no zeros; and the completed functional equation together with the Euler product shows that there are no further completed zeros outside the closed critical strip. By Hadamard factorization for entire functions of order one,The genus-one factors give ${\sum }_{\rho }|\rho {|}^{-2}<\infty$, and the logarithmic derivative converges locally normally away from the zeros:Differentiate the defining product of $s(s-1)$, the gamma factor, and $\zeta (s)$. Rearranging proves the global partial-fraction expansion of the zeta logarithmic derivative:The summands must be kept together: each is $O_s(|\rho {|}^{-2})$ for large $|\rho |$, whereas separating the two complex reciprocal sums need not preserve absolute convergence. The gamma term accounts for the trivial zeros as well as cancellation at zero.

A precise endpoint version of the Perron formula is as follows. If $F(s)={\sum }_{n\ge 1}{a}_n{n}^{-s}$ converges absolutely on $\Re s=c>0$, then, for $x>0$,When $x$ is not an integer, the left side is simply the sum over $n\le x$.

Prove first the scalar kernel formula, with symmetric vertical limits:For $y>1$, close the contour to the left and apply the residue theorem at $s=0$; the exponential $e^{s\log y}$ makes the closing integral vanish. For $y<1$, close to the right, where there is no enclosed pole and the exponential decreases. The usual semicircle estimate, or integration by parts on the closing arcs, justifies these limits. At $y=1$ the truncated integral is ${\pi }^{-1}\arctan (T/c)$, tending to $1/2$.

One also needs a uniform bound to pass through the Dirichlet series. Pairing the two halves of the vertical integral gives, with $u=\log y$,The cosine term is absolutely bounded. The sine term is uniformly bounded by integration by parts against the bounded sine integral ${\int }_0^v\sin (tu)dt/t$, since $t^2/(c^2+t^2)$ is increasing from zero to one. Thus $|K_T(y)|\le C_c{y}^c$, independently of $T,y$.

For finite $T$, absolute convergence permits termwise integration, giving ${\sum }_n{a}_n{K}_T(x/n)$. The uniform bound dominates this by $C_c{x}^c{\sum }_n|a_n|n^{-c}<\infty$. The dominated convergence theorem and the scalar kernel formula now prove the boxed Perron formula, including its half-weight endpoint convention.

For the link with primes, the logarithmic derivative of the Euler product givesApplying Perron formula therefore expresses the second Chebyshev function ${\psi }_0(x)$, with half weight at a prime-power endpoint, as the vertical integral of $-{\zeta }^{\prime }/\zeta (s)x^s/s$. Shift this contour left, choosing heights away from zeros and using the partial-fraction expansion to control the integrand. The pole at one contributes $x$, a nontrivial zero $\rho$ of multiplicity $m$ contributes $-m{x}^{\rho }/\rho$, the trivial zeros contribute ${\sum }_{k\ge 1}{x}^{-2k}/(2k)$, and the pole from $1/s$ contributes $-{\zeta }^{\prime }(0)/\zeta (0)=-\log (2\pi )$. Thus the resulting Riemann–von Mangoldt explicit formula iswith zeros summed symmetrically in height. A truncated contour gives the corresponding truncated formula and remainder. The pole at one gives the main term for primes; zeros farther left give smaller oscillating corrections. Zero-free regions therefore translate into error bounds for $\psi (x)$ and, by partial summation, for the prime-counting function.

Put $F(s)=-{\zeta }^{\prime }(s)/\zeta (s)$. The Euler product gives $F(s)={\sum }_{n\ge 1}\Lambda (n)n^{-s}$ for $\Re s>1$. The elementary nonnegative polynomialtherefore gives the three-four-one zero-free-region argument:The coefficients $\Lambda (n)$ are nonnegative; applying the identity with $u=t\log n$ justifies the inequality term by term.

Take real parts in the global partial-fraction expansion of the zeta logarithmic derivative. For $1<\sigma \le 2$, the digamma function bounds yieldAll terms in the zero sum are nonnegative, because the Euler product and completed functional equation locate the nontrivial zeros in the closed critical strip. The constant terms are bounded: in particular ${\sum }_{\rho }\Re (1/\rho )={\sum }_{\rho }\beta /|\rho {|}^2$ converges. Near the real pole, $F(\sigma )=1/(\sigma -1)+O(1)$.

First exclude zeros on the line one. If $1+it$, $t\ne 0$, were a zero of multiplicity $m\ge 1$, the selected zero term would giveInserted into the positivity inequality, this yields $0\le (3-4m)/(\sigma -1)+O_t(1)$, impossible as $\sigma \downarrow 1$. At $t=0$, zeta has a pole, with a punctured neighbourhood containing no zeros. Thus the line one has no zeros.

Now let $\rho =\beta +i\gamma$ with $|\gamma |\ge 1$ and put $L=\log (|\gamma |+2)$. Select this zero in the formula at $t=\gamma$ and discard every other nonnegative zero kernel. The pole terms at heights $\gamma ,2\gamma$ are bounded. ConsequentlyChoose a fixed positive $a$ small enough that $C_{1}a\le 1/2$ and $1+a/L\le 2$, and set $\sigma =1+a/L$, $h=1-\beta$. Rearranging givesThis is the required logarithmic gap at large height.

For $|\gamma |\le 1$, zeros with $\beta \le 1/2$ already have a fixed gap. The remaining compact region contains finitely many zeros, none on the line one; the pole at one cannot be an accumulation point of zeros. Hence those zeros also have a fixed positive distance from that line. Reduce the absolute constant to cover this bounded-height region and to make the preceding weak inequality strict. The zero-free region of the Riemann zeta function is thereforeThis proof has established boundary nonvanishing as well as the quantitative gap, rather than assuming the former implicitly.

The permitted zero-count bound $N(T)\ll T\log (T+2)$ implies, by partial summation,Indeed, the zeros with $|\rho |\le 1$ contribute a bounded amount since $\xi (0)\ne 0$; the rest contribute $N(T)/T+{\int }_1^{T}N(u)u^{-2}du$. For every zero in the sum, the preceding zero-free region of the Riemann zeta function givesThe supplied truncated explicit formula for the second Chebyshev function therefore impliesChoose $T=\exp (a\sqrt{\log x})$, with any fixed positive $a$ and then, for example, $a=\sqrt{c}$. Both terms have exponential decay in $\sqrt{\log x}$, and the logarithmic factors can be absorbed by slightly decreasing its coefficient. Hence, for some absolute $b>0$,If the truncated formula is taken only at admissible heights and non-prime-power endpoints, choose such heights of the same size and first apply it at half-integers. Monotonicity and the $O(\log x)$ jump of $\psi$ at an integer transfer this bound to all $x$; these convention choices do not change the conclusion.

To pass from prime powers to primes, let $\vartheta (x)={\sum }_{p\le x}\log p$. The higher prime-power contribution satisfiesThus $\vartheta (x)\sim x$. Apply partial summation again:The integral is $O(x/{\log }^{2}x)$: use $\vartheta (t)\ll t$ and split at $\sqrt{x}$. It is therefore smaller than the first term, which is asymptotic to $x/\log x$. This proves the Prime number theorem in the requested form

A fixed zero-free strip changes the zero contribution qualitatively. If every nontrivial zero satisfies $\beta <1-c$, with fixed $0<c<1/2$, the same zero-count estimate and partial summation giveThe truncated explicit formula for the second Chebyshev function then yieldsTake $T=x^c$, or an admissible height of this size. The two contributions are bounded by the same order, proving the prime number theorem error from a fixed zero-free strip:In particular this is $O_{\epsilon }(x^{1-c+\epsilon })$ for every $\epsilon >0$. It is a power saving, stronger than the decay obtained from the logarithmic zero-free region. The triangle-inequality estimate of the zero sum explains the two logarithms; removing them would require additional information or cancellation, not merely the asserted zero-free strip.

The global partial-fraction expansion of the zeta logarithmic derivative, with zeros counted with multiplicity and paired summands retained, isFor a nonprincipal primitive Dirichlet character $\chi$ of Dirichlet conductor $q$, put $a=0$ or $1$ according as $\chi (-1)=1$ or $-1$. Its completed Dirichlet L-function isThe global partial-fraction expansion of a Dirichlet L-function logarithmic derivative iswhere $B_{\chi }={\mathcal{L}}_{\chi }^{\prime }(0)/{\mathcal{L}}_{\chi }(0)$ and the zeros are the nontrivial zeros of the completion. These expansions follow from genus-one Hadamard factorization; the combined terms converge locally normally. The primitive principal Dirichlet character has Dirichlet conductor one and gives the zeta formula. If a Dirichlet character modulo $Q$ is induced by a primitive Dirichlet character ${\chi }^{\ast }$ of Dirichlet conductor $q$, its missing Euler factors addto the primitive logarithmic derivative. This correction is $O(\log Q)$ on the real interval $1<\sigma \le 2$.

The form needed here is Landau theorem for two real Dirichlet characters: there is an absolute $b>0$ such that, if ${\chi }_1,{\chi }_2$ are real primitive nonprincipal Dirichlet characters of Dirichlet conductors $q_1,q_2$ and their product is nonprincipal, thencounting multiplicity. In particular, two distinct primitive real Dirichlet characters cannot each have a zero in that interval.

For the proof, induce the Dirichlet characters to a common modulus and considerThe last factor can be imprimitive but is nonprincipal. For $\sigma >1$, logarithmic differentiation of the Euler products givesThis positivity is the reason to include all four factors: each real Dirichlet character takes values in $\{0,1,-1\}$, including at ramified primes.

The real partial-fraction identity for a primitive completion has no residual real constant. Indeed, after taking real parts in its Hadamard derivative, the constant is determined to be zero by the functional-equation symmetry of its modulus across the critical line; the zero kernels there cancel in reflected pairs. ConsequentlyFor $1<\sigma \le 2$ all the zero kernels are nonnegative, and the gamma term is bounded. The missing Euler factors have the previously bounded correction. Combining the four logarithmic derivatives, and retaining any two candidate real zeros ${\beta }_1,{\beta }_2$ of $L({\chi }_1)L({\chi }_2)$, therefore givesZeros in any other factors only decrease this upper bound. The sole pole term comes from zeta.

Put $H=\log (q_1{q}_2)$ and choose $a>0$ so small that $Ca<1/10$. If both $1-{\beta }_j<a/(4H)$, take $\sigma =1+a/H$. The upper bound is then at mosta contradiction. Taking $b=a/4$ proves the theorem, including the multiplicity assertion.

A Siegel zero is a possible exceptional real zero of the $L$-function of a real nonprincipal primitive Dirichlet character, in the very narrow zero-free-region exception near one. Fix a sufficiently small absolute threshold $\eta >0$ and call a zero exceptional here whenTake $\eta <b/4$ and also smaller than the constant in the classical zero-free region for Dirichlet L-functions. Such a zero, if present, is real and simple; its existence is not asserted. This choice fixes the constants consistently for the requested separation conclusions.

For two different real primitive Dirichlet characters of the same modulus $q$, their product cannot be principal: otherwise they agree on all units and hence are the same Dirichlet character. Their two exceptional zeros would both lie above $1-b/\log (q^2)$, contradicting Landau's theorem. Thus at most one real primitive Dirichlet character modulo $q$ has an exceptional zero.

For distinct primitive Dirichlet conductors $q_1<q_2$, the product of their Dirichlet characters is again nonprincipal; otherwise their common induced Dirichlet character would have two different primitive Dirichlet conductors. Suppose $q_2\le q_1^2$. ThenAgain both zeros violate the two-zero prohibition. Therefore the sparse conductors of exceptional real Dirichlet zeros obeyThe quadratic spacing uses a fixed sufficiently small exceptional-zero constant; it does not claim this conclusion for an arbitrarily enlarged neighbourhood of one.

A suitable large sieve statement is the following. If ${\alpha }_j$ are separated modulo one by at least $0<\delta \le 1$ and $a_n$ is supported on $N$ consecutive integers, thenThe sharper classical constant $N-1+{\delta }^{-1}$ also suffices, but is unnecessary for the requested bound. This is the exponential-sum large sieve.

Put $M=|A|$, $S(\alpha )={\sum }_{n\in A}e(n\alpha )$, and $A_p(r)=\#\{n\in A:n\equiv r(\mathrm{mod}p)\}$. By the orthogonality of roots of unity,At most $p-k(p)$ of these residue counts are nonzero. The Cauchy-Schwarz inequality gives $M^2\le (p-k(p)){\sum }_r{A}_p(r{)}^2$, and the frequency $h=0$ contributes exactly $M^2$. Thus, if $k(p)<p$,If $k(p)=p$ for some prime, $A$ is empty and the result is immediate.

All fractions $h/p$, $1\le h<p$, $p\le X$, are distinct reduced fractions. Their circular spacing is at least $X^{-2}$, because two distinct fractions of these denominators differ modulo one by at least $1/(p{p}^{\prime })$. Apply the large sieve with $a_n=1_A(n)$ and $\delta =X^{-2}$, and sum the preceding lower bounds:For $M>0$ and a positive sieve denominator, division provesWhen the denominator is zero this asserts no restriction; that degenerate case is interpreted as a vacuous bound.

For the least-nonresidue application, first establish the positive density of power-smooth integers. Fix $\eta =1/k$, with an integer $k\ge 2$, and let $H$ tend to infinity. Choose ordered primes, with repetitions allowed, in the intervalTheir product $d$ satisfies $H^{1-\eta }\le d\le H$. Every number $md\le H$ has $m\le H^{\eta }$, so is $H^{\eta }$-smooth. By partial summation of the Prime number theorem, or the Mertens theorem for reciprocal primes,The number of ordered representations $(m,{\ell }_1,\dots ,{\ell }_k)$ is at leastbecause $\lfloor H/d\rfloor \ge H/(2d)$ for $1\le d\le H$.

This representation count must not be confused with a count of distinct integers. A number at most $H$ has at most $\lfloor 1/(\eta -{\eta }^2)\rfloor$ prime factors in that interval, counted with multiplicity. There are therefore only a bounded number, depending on $\eta$, of ordered $k$-tuples which can occur as divisors of it; the cofactor is then fixed. Dividing by this bounded multiplicity provesfor a fixed ${\kappa }_{\eta }>0$ and all sufficiently large $H$.

Now work on a dyadic prime interval $Q<p\le 2Q$ and let ${\mathcal{E}}_Q$ be the primes there with $n(p)>p^{0.01}$. Take $H=Q^2$ and $\eta =1/200$, so $H^{\eta }=Q^{0.01}$. Let $A$ be the $Q^{0.01}$-smooth integers at most $Q^2$. The density lemma gives $|A|\ge \kappa Q^2$ for an absolute $\kappa >0$.

For each $p\in {\mathcal{E}}_Q$, every prime factor of a member of $A$ is at most $Q^{0.01}\le p^{0.01}<n(p)$ and is smaller than $p$. Hence it is a nonzero quadratic residue modulo $p$. Multiplicativity of the Legendre symbol makes every member of $A$ a nonzero quadratic residue modulo $p$. It therefore avoids all $(p-1)/2$ quadratic-nonresidue classes. In the sieve inequality set $k(p)=(p-1)/2$ at exceptional primes and zero at every other prime up to $X=2Q$. For odd $p$, $k(p)/p\ge 1/3$, soThus each dyadic interval has at most $36/\kappa$ exceptional primes. The finitely many small intervals can be absorbed into this absolute bound. Summing the $O(\log N)$ intervals up to $N$ proves the large-sieve logarithmic exceptional-prime bound for least quadratic nonresidues:The least nonresidue is normally defined for odd primes; any convention at the prime two changes the count by at most one.

Let $T(N)$ count pairs $n,n+2$ both prime with $n+2\le N$. The Selberg sieve replaces primality by the necessary condition that the polynomial $F(n)=n(n+2)$ have no small prime divisor. Its strength is a nonnegative quadratic majorant with optimizable divisor weights; its limitation is that a sifted integer need not be prime.

For a prime $p$, let $\nu (p)$ count the forbidden residues of $n$ modulo $p$. We have $\nu (2)=1$, since the two roots coincide modulo two, and $\nu (p)=2$ for every odd prime, where the roots are zero and $-2$. The Chinese remainder theorem makes $\nu (d)$ multiplicative on squarefree integers. With $g(d)=\nu (d)/d$,These local densities constitute the sieve distribution for the twin-prime problem. Since ${\sum }_{p\le z}g(p)=2\log \log z+O(1)$, it is a dimension-two sieve, which is why the expected upper bound has two logarithms in the denominator.

Let $P(R)={\prod }_{p\le R}p$ and choose real Selberg sieve weights ${\lambda }_d$ supported on squarefree $d\le R$, with ${\lambda }_1=1$. If $\gcd (F(n),P(R))=1$, the only supported divisor of $F(n)$ is one. HenceExpanding and using the distribution of the polynomial roots givesHere $[d,e]$ denotes the least common multiple. The divisor-square support reaches $R^2$, although each individual weight is supported only to $R$; keeping these two levels distinct is essential for estimating the remainder.

The Selberg sieve diagonalization solves the main-term minimization exactly. On squarefree integers putMultiplicativity givesAlso, Möbius inversion gives ${\sum }_{r\le R}\mu (r)Y_r={\lambda }_1=1$. Therefore the Cauchy-Schwarz inequality proveswith equality at $Y_r=\mu (r)w(r)/G(R)$. Inverting the divisor sums gives the optimizing weightsIn particular ${\lambda }_1=1$ and $Q(\lambda )=1/G(R)$.

These weights have $|{\lambda }_d|\le 1$, which supplies a simple rigorous remainder estimate. Indeed, multiply the inner sum by ${\prod }_{p\mid d}(1-g(p){)}^{-1}={\sum }_{e\mid d}w(e)$. The terms are $w(em)$ for distinct squarefree integers $em\le R$ with $e\mid d$ and $(m,d)=1$, hence form a subset of the sum defining $G(R)$. Since $\nu ([d,e])\le \nu (d)\nu (e)$ and $\nu (d)\le \tau (d)$,Thus

For this sieve $w(2)=1$ and $w(p)=2/(p-2)$ for odd primes. Here is a direct proof that $G(R)\asymp {\log }^{2}R$, sufficient for the upper bound. PutThe Mertens theorem for reciprocal primes implies $W(z)\asymp {\log }^{2}z$, by taking logarithms and using the convergence of ${\sum }_{p}g(p{)}^2$. Give each divisor $d\mid P(z)$ probability $w(d)/W(z)$. Its expected logarithm isby the Mertens first theorem. With $z=R^{1/8}$ this is at most $\frac{1}{3}\log R$ for large $R$. The Markov inequality shows that at least two thirds of the total product weight has $d\le R$. These terms occur in $G(R)$, so $G(R)\gg W(R^{1/8})\gg {\log }^{2}R$. Conversely $G(R)\le W(R)\ll {\log }^{2}R$, proving the claim without treating an untruncated Euler product as a truncated divisor sum.

Choose, for example, $R=N^{1/4}$. Any twin-prime pair with smaller member greater than $R$ survives this sieve; pairs with smaller member at most $R$ contribute at most $O(R)$. ConsequentlyThe chosen level is deliberately enough to prove the correct logarithmic order; sharper level and remainder analyses improve the numerical upper-bound constant.

The local correction factor also explains the conjectured main-term constant. Relative to two independent primality conditions, the singular series isThe twin-prime constant $C_2$ is positive and convergent because its logarithm has an absolutely convergent tail. The factor two at $p=2$ records that only one parity is allowed, while each odd-prime factor records the two distinct forbidden residues. The Hardy–Littlewood twin-prime asymptotic conjecture predictsThis is a conjecture, not a consequence of the upper-bound calculation.

The parity problem in sieve theory is the obstruction to reversing the argument. The nonnegative square majorizes all survivors, including composites with sufficiently large prime factors; small-divisor information does not isolate the desired prime-factor parity or force both factors to be prime. Therefore the Selberg sieve establishes the correct upper-bound scale and the arithmetic local factors, but by itself does not prove a positive lower bound for twin primes, their infinitude, or the conjectured asymptotic.

The Von Mangoldt function is supported on prime powers:Write $e(t)=\exp (2\pi it)$. A convenient form of the Siegel–Walfisz theorem is: for every fixed $A,B>0$, uniformly for $q\le (\log x{)}^B$ and $(a,q)=1$,The implied constant can be ineffective because of possible Siegel zeros; the modulus bound is logarithmic, not an unrestricted uniformity assertion.

Apply this to modulus five and separate the reduced residue classes:The last sum is $O(\log N)$: only powers of five can contribute in the zero residue class. By the orthogonality of roots of unity,since two is coprime to five and the sum including $a=0$ vanishes. As $\phi (5)=4$, the Siegel–Walfisz theorem yieldsThe sum is complex-valued, but the displayed error controls its absolute difference from the real main term.

Use the integer norm lower bound for rational approximation to a quadratic irrational. The integer $2q^2-a^2$ is nonzero, since $\sqrt{2}$ is irrational. If $a/q<2$, thenbecause $\sqrt{2}+a/q<\sqrt{2}+2<4$. If $a/q\ge 2$, the difference is at least $2-\sqrt{2}>1/4\ge 1/(4q^2)$. ThusIn particular, $\sqrt{2}$ is a badly approximable number.