Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 28 (Analytic Number Theory)

Write $\vartheta (x)={\sum }_{p\le x}\log p$ and $\psi (x)={\sum }_{n\le x}\Lambda (n)$ for the two Chebyshev functions, and $\pi (x)$ for the prime-counting function. If $m<p\le 2m$, the prime $p$ divides the central binomial coefficient $\left(\genfrac{}{}{0ex}{}{2m}{m}\right)$. ConsequentlySum this inequality over dyadic integers $m=1,2,4,\dots ,2^{k-1}$. It gives $\vartheta (2^k)\le 2^{k+1}\log 2$. Monotonicity, with $2^{k-1}<x\le 2^k$, gives $\vartheta (x)=O(x)$ for real $x\ge 2$. This is the Chebyshev estimate from central binomial coefficients; no information about the distribution of primes beyond unique factorization has been used.

Split the primes at $\sqrt{x}$. For $p>\sqrt{x}$, $\log p>\frac{1}{2}\log x$, soSince $\sqrt{x}=O(x/\log x)$,We also need $\psi (x)=O(x)$. The contributions of higher prime powers satisfybecause only $k\le \log x/\log 2$ contribute, and $\vartheta (x^{1/k})\ll \sqrt{x}$ for $k\ge 2$.

The Von Mangoldt divisor identity is $\log n={\sum }_{d\mid n}\Lambda (d)$, which follows by factoring $n$ into prime powers. Summing it for $n\le M$, with $M$ a positive integer, givesThe bound already proved makes the last error $O(M)$. Integral comparison for ${\sum }_{n\le M}\log n$, or the Stirling formula, gives $\log (M!)=M\log M-M+O(\log M)$. ThereforeThe contribution from higher prime powers is uniformly bounded:Subtract it, and replace $M$ by $\lfloor x\rfloor$, to obtain the Mertens first theorem

Now fix $\delta >0$. Apply partial summation to $A(t)$ and $f(t)=(\log t{)}^{-1-\delta }$. With the lower endpoint interpreted as $2^{-}$, so that the prime $2$ is included, this givesThe boundary term tends to zero, and the integral converges, since $A(t)\ll \log t$ and ${\int }_2^{\infty }dt/(t(\log t{)}^{1+\delta })<\infty$. Thus the series converges for every positive $\delta$. Keeping the main term of $A(t)$ also gives the useful logarithmically weighted reciprocal-prime tailIndeed, subtract the finite partial sum from the limiting integral: the boundary contributes $-(\log x{)}^{-\delta }$ and the main integral contributes $(1+\delta )(\log x{)}^{-\delta }/\delta$.

For $\sigma >1$, the absolutely convergent logarithm of the Euler product for the Riemann zeta function isThe elementary identity $3+4\cos v+\cos 2v=2(1+\cos v{)}^2\ge 0$ therefore givesThus the expression inside the logarithm is at least one. The Meromorphic continuation of the Riemann zeta function to the right half-plane has only a simple pole at one, of residue one. It follows, for example, fromwhose integral is holomorphic there.

Suppose $t\ne 0$ and $\zeta$ has a zero of order $m\ge 1$ at $1+it$. As $\sigma \downarrow 1$, the real factor is $O((\sigma -1{)}^{-3})$, the middle factor is $O((\sigma -1{)}^{4m})$, and the factor at $1+2it$ is bounded. Their product would tend to zero, contradicting its lower bound one. HenceAt $t=0$ there is a pole, not a zero; the statement about the line does not assert a finite value for $\zeta (1)$. This proves the three-four-one product proof of zeta boundary nonvanishing.

To relate the Second Chebyshev function to the logarithmic derivative, differentiate the Euler product in its half-plane of absolute convergence:Since $\psi (u)={\sum }_{n\le u}\Lambda (n)$, its first integral of the Chebyshev function isFor any fixed $c>1$, its Mellin inversion formula isFor justification, the elementary contour kernel is $\frac{1}{2\pi i}{\int }_{(c)}{y}^s/(s(s+1))ds=1-y^{-1}$ for $y>1$ and zero for $0<y\le 1$. Close left or right and take the residues at zero and minus one; at $y=1$ the continuous value is zero. Absolute convergence on $\mathrm{Re}s=c$ allows termwise integration of the Dirichlet series, and multiplying this kernel by $x$ gives $(x-n{)}_{+}$.

Here is how the relation yields the asymptotic. Move the contour to the left, using the functional equation of the Riemann zeta function to control the left-hand side. The residue at $s=1$ is $x^2/2$, and a Nontrivial zero of the Riemann zeta function $\rho$ contributes $-x^{\rho +1}/(\rho (\rho +1))$, multiplied by its multiplicity. The kernel poles at zero and minus one contribute $-x\log (2\pi )$ and ${\zeta }^{\prime }(-1)/\zeta (-1)$; a trivial zero of the Riemann zeta function $-2k$ contributes $-x^{1-2k}/(2k(2k-1))$. Thus the smoothed explicit formula for the Chebyshev function isFor the contour argument, use heights avoiding the zero ordinates and then let those heights increase. The local zero bound from the Riemann–von Mangoldt formula, together with the Local partial-fraction expansion of the Riemann zeta logarithmic derivative, permits heights with logarithmic-derivative bound $O({\log }^{2}T)$ in each fixed vertical strip. The horizontal integrals then vanish because the denominator is of size $T^2$. After that, send the left edge through negative odd integers to minus infinity; the functional equation of the Riemann zeta function bounds the logarithmic derivative there by a logarithm, and $x^{s+1}$ makes the left integral vanish for fixed $x>1$. This explains why this smoothing allows a convergent contour calculation without a quantitative zero-free region.

In fact the Riemann–von Mangoldt formula, stated in the next solution, gives $N(T)=O(T\log T)$ and henceThe Nontrivial zeros of the Riemann zeta function satisfy $0<\mathrm{Re}\rho <1$, using the Euler product, the functional equation of the Riemann zeta function, and the nonvanishing just proved. For each such zero, $x^{\rho -1}\to 0$ as $x\to \infty$, whereas $|x^{\rho -1}|\le 1$ for $x\ge 1$. The dominated convergence theorem therefore makes the absolutely convergent zero sum, divided by $x^2$, tend to zero. All the other displayed terms are $o(x^2)$. We obtain

It remains to unsmooth; differentiating an asymptotic without justification would not suffice. Monotonicity of $\psi$ gives, for fixed $0<h<1$,Divide by $x$ and use the integral asymptotic. The lower and upper limits lie between $1-h/2$ and $1+h/2$. Letting $h\downarrow 0$ proves $\psi (x)\sim x$. Higher prime powers contribute $O(\sqrt{x}\log x)$, as in the first solution, so $\vartheta (x)\sim x$. Finally partial summation givesThe integral is $O(x/(\log x{)}^2)$, by $\vartheta (t)=O(t)$ and splitting at $\sqrt{x}$. Hencewhich is the Prime number theorem.

Use the meromorphic completionThe functional equation of the Riemann zeta function isIts entire version is $\xi (s)=\frac{1}{2}s(s-1)Z(s)$ with $\xi (s)=\xi (1-s)$. The completion $Z$ itself has poles at zero and one; it should not be confused with the entire Riemann xi function.

We prove the equation by a theta integral. SetThe Gaussian Fourier transform, with kernel $e^{-2\pi ixy}$, isFor example, differentiation in $y$ and integration by parts give the differential equation $I^{\prime }(y)=-(2\pi y/t)I(y)$; the Gaussian integral gives $I(0)=t^{-1/2}$. Periodize the Gaussian by summing $e^{-\pi t(x+n{)}^2}$ over integers $n$. Its $k$th Fourier coefficient is the displayed transform at $k$. Both the periodized function and its Fourier series converge absolutely, so evaluation at $x=0$ gives the Poisson summation formula in this case:

For $\mathrm{Re}s>1$, integration term by term in the Gamma function integral givesIndeed, the two terms for $n$ and $-n$ cancel the factor $1/2$, and substitution $v=\pi n^{2}t$ gives ${\pi }^{-s/2}\Gamma (s/2)n^{-s}$. Split at one, and use the transformation above in the integral from zero to one. The elementary contribution isSubstitution $t=1/u$ in the remaining term therefore givesThe theta tail decays exponentially. The integral is consequently an entire function of $s$, with uniform convergence and termwise differentiation on compact subsets. The formula continues $Z$ meromorphically to the whole plane. Both its rational part and its integral are unchanged by $s\mapsto 1-s$, proving the equation and the entire xi formulation. Using the reflection and duplication identities of the Gamma function, one may equivalently writeunderstood as an identity of meromorphic functions, including points where individual factors need continuation.

Now let $N(T)$ count the Nontrivial zeros of the Riemann zeta function $\rho =\beta +i\gamma$ with $0<\gamma \le T$, including multiplicity. The Riemann–von Mangoldt formula isFor $T$ not a zero ordinate, the more precise usual form isHere the argument is continued from $\zeta (2)>0$ along the path $2\to 2+iT\to \frac{1}{2}+iT$. The first formula remains valid at zero ordinates with the stated endpoint convention. Only its leading asymptotic is needed below.

List the positive ordinates as ${\gamma }_1\le {\gamma }_2\le \cdots$, with multiplicity, consistent with this counting function. Put $b_n=2\pi n/\log n$. For every fixed $\epsilon \in (0,1)$,For all sufficiently large $n$, the lower count is less than $n$ and the upper count is greater than $n$. Consequently $(1-\epsilon )b_n<{\gamma }_n\le (1+\epsilon )b_n$. Letting $\epsilon \downarrow 0$ proves the asymptotic inversion of the zeta zero countThis argument works even when several zeros have the same ordinate; “increasing” is interpreted in the standard nondecreasing, multiplicity-counted sense. A count listing only distinct ordinates is a different object and is not determined by this formula alone.

In this notation the Riemann hypothesis says that every Nontrivial zero of the Riemann zeta function has real part one-half:It concerns their horizontal location, not merely the growth of the ordinates, and does not assert that the zeros are simple. The functional equation and complex conjugation make the zero set symmetric about both the real axis and the critical line; the hypothesis puts all the Nontrivial zeros of the Riemann zeta function on that line.

The Selberg upper-bound sieve replaces a difficult coprimality indicator by a nonnegative square whose coefficients can be optimized. Let $P(z)={\prod }_{p\le z}p$, and suppose a finite sequence has divisibility countswhere $g$ is multiplicative on squarefree integers and $0<g(p)<1$. Choose real Selberg sieve weights ${\lambda }_1=1$ supported on $d\mid P(z)$ with $d\le R$. If an entry has no prime factor in $P(z)$, its only weighted divisor is $1$, so its indicator is bounded above by the square of the divisor sum. Summing giveswhere $Q(\lambda )={\sum }_{d,e}{\lambda }_d{\lambda }_{e}g([d,e])$. This is an upper bound regardless of the signs of the weights.

Here is the optimization. On the permitted squarefree integers putThe identitycan be checked one prime at a time: a prime in both $d$ and $e$ gives the factor $1+h(p)=1/g(p)$. ThusFinite Möbius inversion gives ${\lambda }_{d}g(d)={\sum }_{d\mid r}\mu (r/d)Y_r$, and in particular the condition ${\lambda }_1=1$ becomes ${\sum }_r\mu (r)Y_r=1$. The Cauchy-Schwarz inequality now yieldsEquality is attained by $Y_r=\mu (r)k(r)/J$. Inverting again gives the explicit optimizing weightsThey satisfy $|{\lambda }_d|\le 1$. To see this, multiply out ${\prod }_{p\mid d}(1-g(p){)}^{-1}={\sum }_{e\mid d}k(e)$. The numerator becomes the sum of $k(ev)$ over distinct permitted integers $ev\le R$ with $e\mid d$ and $(v,d)=1$, a subset of the terms in $J$. We therefore have a main term $X/J$ and a controllable remainder. This proves the basic Selberg sieve diagonalization and the useful bound on the weights, rather than merely asserting an optimized density.

Apply it to the polynomial $F(n)=n(n+2)$ for $1\le n\le N$. If $\omega (d)$ is the number of roots of $F$ modulo squarefree $d$, the Chinese remainder theorem givesUse $g(d)=\omega (d)/d$, $R=z=N^{1/8}$, and sieve the indices for which $F(n)$ has no prime factor at most $z$. The local weights areWe claim $J(z,z)\gg (\log z{)}^2$. The following truncated-product argument supplies the necessary lower bound. Put $w=z^{1/8}$, and consider all squarefree integers on the primes at most $w$, with total weightGive such an integer $d$ probability $k(d)/W$. Prime inclusion is independent with probability $g(p)$, soby the Mertens first theorem, absorbing the prime $2$ separately. For sufficiently large $z$, this is at most $\frac{1}{2}\log z$. The Markov inequality shows that at least half of $W$ lies on $d\le z$, all of which are terms in $J(z,z)$.

Moreover, partial summation applied to the Mertens first theorem givesIndeed it is $A(w)/\log w+{\int }_2^{w}A(t)/(t(\log t{)}^2)dt$, and the contribution of $A(t)-\log t=O(1)$ has a finite limiting constant with tail $O(1/\log w)$. Expanding the logarithm of $W$ now givesThe error is bounded since ${\sum }_p{p}^{-2}<\infty$. Consequently $W\asymp (\log w{)}^2\asymp (\log z{)}^2$, proving the claim. The exponent two reflects the two forbidden classes at almost every prime.

For the remainder use $|{\lambda }_d|\le 1$ and the simple bound $\omega ([d,e])\le [d,e]\le de$. HenceThe number of surviving indices is thereforeEvery pair of primes $p,p+2$ with $p>z$ survives, since both its prime factors exceed $z$. The exceptional pairs with $p\le z$ number at most $z$. With $z=N^{1/8}$ we obtainThis is the twin-prime upper bound from a quadratic sieve. The method constructs a majorant and bounds the sifted set; it does not give a positive lower bound for twin primes.

Fix integers $q\ge 1$ and $a$ with $(a,q)=1$. We prove the Dirichlet theorem on primes in arithmetic progressions by showing that the prime Dirichlet sum in this residue class diverges as its real exponent decreases to one.

First justify the required Dirichlet L-function facts. If $\chi$ is a nonprincipal Dirichlet character modulo $q$, its sum over a full period is zero: choose a unit $b$ with $\chi (b)\ne 1$, and multiplication by $b$ permutes the residue classes, forcing the sum to equal $\chi (b)$ times itself. Therefore the partial sums $C_{\chi }(u)={\sum }_{n\le u}\chi (n)$ are bounded by $q$. Partial summation giveswhich supplies holomorphic continuation near one, with locally uniform convergence. For the principal Dirichlet character ${\chi }_0$,has a simple pole at one, with residue $\phi (q)/q$.

The assumption in the question gives nonvanishing at one for real nonprincipal characters. We must also prove it for nonreal characters. For a nonreal $\chi$, its square ${\chi }^2$ is nonprincipal. For real $\sigma >1$, logarithms of the Euler products giveFor a prime not dividing $q$, its logarithmic coefficient is $3+4\mathrm{Re}\chi (p{)}^k+\mathrm{Re}\chi (p{)}^{2k}=2(1+\cos \theta {)}^2\ge 0$, where $\chi (p{)}^k=e^{i\theta }$. Primes dividing $q$ contribute only the positive zeta term. If $L(1,\chi )$ vanished to order $m\ge 1$, the product would be $O((\sigma -1{)}^{4m-3})$ and tend to zero: the squared-character factor is bounded because ${\chi }^2$ is nonprincipal. This is a contradiction. HenceThis step uses the given real-character hypothesis and the Euler product positivity for L-function nonvanishing for all remaining characters.

In $\sigma >1$ choose the logarithm furnished by the absolutely convergent Euler product. Its prime-power expansion givesThe error from powers $k\ge 2$ is uniformly bounded as $\sigma \downarrow 1$, by ${\sum }_p{\sum }_{k\ge 2}1/(k{p}^{k\sigma })<\infty$. For nonprincipal $\chi$, nonvanishing and holomorphic continuation at one provide a bounded logarithm in a neighborhood of one. The Euler-product branch differs from that branch by a constant integral multiple of $2\pi i$ on the final real interval, so it too is bounded. ThusFor the principal character, its simple pole instead gives

The Orthogonality of Dirichlet characters gives, for primes not dividing $q$,Multiply by $p^{-\sigma }$ and sum. Absolute convergence allows the interchange for $\sigma >1$, soThe right side tends to infinity. If there were only finitely many primes in the progression, the left side would have a finite limit at one. This contradiction proves infinitely many primes occur in every reduced residue class. For $q=1$ or $2$ the character argument simply has no nonprincipal terms and gives the same conclusion.

For the final deduction the modulus $q$ is fixed. Let $A(t)=\pi (t;q,a)$. The given consequence of the Siegel–Walfisz theorem is $A(t)\sim t/(\phi (q)\log t)$. Partial summation, including the prime $2$ through the lower endpoint $2^{-}$ when appropriate, givesThe boundary is $O_q(1/\log x)$. Write $A(t)=t(1+\epsilon (t))/(\phi (q)\log t)$ with $\epsilon (t)\to 0$. The main integral is $(\log \log x-\log \log 2)/\phi (q)$. The error is $o(\log \log x)$: given $\eta >0$, choose $T$ such that $|\epsilon (t)|\le \eta$ for $t\ge T$. Its integral from $2$ to $T$ is a fixed constant, and its absolute value from $T$ to $x$ is at most $\eta \log \log x/\phi (q)$ plus a fixed constant. Divide by $\log \log x$ and then let $\eta \downarrow 0$. We obtain the reciprocal primes in a fixed arithmetic progression asymptoticThe argument uses the supplied prime-counting asymptotic in this last part; the preceding infinitude proof did not assume the Prime number theorem in arithmetic progressions.