Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 25 (Topics in Analytic Number Theory)

Write $1(n)=1$ and let $\epsilon$ be the Identity for Dirichlet convolution. The Möbius function uses the empty-product convention $\mu (1)=1$; the Von Mangoldt function has $\Lambda (1)=0$. We first establish all the arithmetic function identities needed below. Every integer divisor of $n$ contributes one to $\tau (n)$, so $\tau =1\ast 1$. If $n>1$ has $r$ distinct prime factors, the squarefree divisors correspond to their subsets andAt $n=1$ the sum is one. Thus $\mu \ast 1=\epsilon$. Writing $n={\prod }_p{p}^{v_p(n)}$, the only divisors with nonzero Von Mangoldt function are $p,p^2,\dots ,p^{v_p(n)}$, and henceThe Dirichlet convolution is commutative by replacing $d$ with $n/d$, and associative because either bracketing sums $f(a)g(b)h(c)$ over $abc=n$. ConsequentlyThese are consequences of the definitions, rather than unproved invocations of Möbius inversion.

To identify the constant, integrate on each interval $[j,j+1)$:The tail is $O(1/J)$, since the integrand is at most $2/x^2$ for $x\ge 2$. Summation therefore gives $\gamma ={\lim }_{J\to \infty }(H_J-\log (J+1))$, where $H_J$ is the harmonic number, and $H_J=\log J+\gamma +O(1/J)$. Thus this is Euler's constant.

Put $r=\lfloor \sqrt{N}\rfloor$. Counting pairs of positive integers whose product is at most $N$, and subtracting the square counted twice, gives the Dirichlet hyperbola method identitySince $r=\sqrt{N}+O(1)$, the harmonic number estimate yieldsThe increasing natural logarithm also satisfies ${\sum }_{n\le N}\log n=N\log N-N+O(\log (2N))$ by comparison with its integral. Subtracting proves

For the second implication, denote the Mertens function by $M(x)$ and the Second Chebyshev function by $\psi (x)$. Apply the proved Dirichlet convolution identities to $b(n)=\tau (n)-\log n-2\gamma 1(n)$:Summing this identity over integers up to $N$ gives the exact relationFix an integer $K\ge 2$. The contribution to $E(N)$ from $d\le N/K$ has absolute value at mostFor $d>N/K$, group by $j=\lfloor N/d\rfloor$. This gives exactlyunder the assumed cancellation $M(x)=o(x)$; extending that assumption from integers to real $x$ uses $M(x)=M(\lfloor x\rfloor )$. Therefore ${\mathrm{limsup}}_{N\to \infty }|E(N)|/N\ll K^{-1/2}$. Letting $K\to \infty$ proves the prime number asymptotic from Mertens cancellation:

Use the Fourier transform convention $\hat{m}(t)=\int e^{-itx}dm(x)$. The complex measure is finite because ${\sum }_n|f(n)|n^{-\sigma }<\infty$. The Möbius divisor-sum identity, proved in the preceding solution, allows multiplication of absolutely convergent Dirichlet series and givesHere $\zeta$ is the Riemann zeta function. We prove the estimates in the intended range $1<\sigma \le 2$. A uniform estimate of the printed form for all $\sigma >1$ would be false: at $t=0$, $F(\sigma )\to 1$ as $\sigma \to \infty$, while its proposed upper bound tends to zero. A version valid for every $\sigma >1$ replaces $(\sigma -1{)}^{-3/4}$ by $1+(\sigma -1{)}^{-3/4}$.

For completeness, unique prime factorization and absolute convergence give $\zeta (s)={\prod }_p(1-p^{-s}{)}^{-1}$ andas the logarithm defined by that Euler product. The elementary nonnegative trigonometric polynomialtherefore proves the three-four-one inequality for Euler productsWe also need elementary uniform bounds for derivatives of the Riemann zeta function. For an integer $H\ge 1$, summation by parts givesThis continues the function to $\Re s>0$ with just the pole at one. For $1\le \sigma \le 2$, $|t|\ge 1$, choose $H=\lceil 2+|t|\rceil$. Differentiating $j$ times, the finite Dirichlet polynomial is bounded by ${\sum }_{n\le H}(\log n{)}^j/n{\ll }_j{\log }^{j+1}(2+|t|)$. Derivatives of the second term have the same bound, since $|s-1|\ge 1$. In the last term, differentiated integrands are bounded by $u^{-\sigma -1}(\log u{)}^j$, whose integral is $O_j(H^{-\sigma }{\log }^j(2H))$; multiplication by $|s|\ll H$ is harmless. It follows thatAs $\zeta (\sigma )\le 1+(\sigma -1{)}^{-1}$, the three-four-one inequality for Euler products gives, for $|t|\ge 1$,To handle bounded $t$, first note that $\zeta$ cannot vanish at $1+i{t}_0$ for $t_0\ne 0$: a zero of order $m\ge 1$ would make the three-four-one product $O((\sigma -1{)}^{4m-3})\to 0$, contradicting its lower bound one. At $s=1$, the reciprocal $F$ extends holomorphically with a simple zero, since the pole of $\zeta$ has residue one. Thus $F$ and all its derivatives are bounded on the compact rectangle $1\le \sigma \le 2$, $|t|\le 1$. This proves the requested reciprocal zeta bounds near the line one:

For the derivative estimate, repeatedly differentiate $F=1/\zeta$. Every term of $F^{(k)}$ is a constant timesThe preceding derivative bounds and reciprocal estimate bound this by $O_k((\sigma -1{)}^{-3(k+1)/4}{\log }^{3k+1}(2+|t|))$. Compact-height bounds supply the remaining range. Since ${\partial }_t^{k}F(\sigma +it)=i^k{F}^{(k)}(\sigma +it)$, this has exactly the requested dependence, with an explicit logarithmic exponent linear in $k$ for $k\ge 1$.

Here is the unsmoothing a logarithmically weighted sum argument with the normalization repaired. For real $v$,Indeed the Fourier transform of $u{e}^{-\sigma u}{1}_{u\ge 0}$ is $(\sigma +it{)}^{-2}$, so Fourier inversion gives the identity, also at $v=0$ by continuity. In a vertical contour integral the coefficient is $1/(2\pi i)$ and the differential is $ds=idt$. The printed real-$t$ integral has $dt$ with $1/(2\pi i)$ and is missing this factor of $i$.

Set $a_m=\mu (m)(\log m{)}^k$, taking $(\log 1{)}^0=1$ when $k=0$. Its Dirichlet series is $(-1{)}^k{F}^{(k)}(s)$. The logarithmically smoothed Perron formula, justified by absolute convergence, givesFor $x\ge 3$ choose $\sigma =1+1/\log x$. The integral of ${\log }^{3k+1}(2+|t|)/|\sigma +it{|}^2$ is finite, with a constant depending only on $k$, and $x^{\sigma }=ex$. Thus, with $\beta =3(k+1)/4$,For $0<h\le 1$, subtraction gives the exact finite-difference identityThe last sum is $O_k((x{h}^2+h)(\log x{)}^k)$, since there are $O(xh+1)$ terms. ConsequentlyFor $k\ge 3$, choose $h=(\log x{)}^{(\beta -k)/2}$ to get exponent $(\beta +k)/2=7k/8+3/8$. For $0\le k<3$, the trivial bound $O_k(x(\log x{)}^k)$ is already no larger than that estimate. The extra $(\log x{)}^k$ term is absorbed for fixed $k$. HenceThis also yields the cancellation needed for the Prime number theorem. Choose a fixed $k>3$, discard $m\le \sqrt{x}$ at cost $O(\sqrt{x})$ for the unweighted sum, and use partial summation with $(\log m{)}^{-k}$ on the rest. The displayed bound gives $M(x)=O_k(x(\log x{)}^{-k/8+3/8})=o(x)$; the preceding solution then gives $\psi (x)\sim x$.

For $\Re s>1$, the Euler products areThe Dirichlet character is completely multiplicative, and unique prime factorization expands each finite product into the terms of the corresponding Dirichlet series supported on those primes. Absolute convergence permits passage to all primes. More strongly, the absolutely convergent Euler product logarithm givessince the sum of absolute values is bounded by ${\sum }_{n\ge 2}{\sum }_{m\ge 1}{n}^{-m\Re s}/m<\infty$.

We prove nonvanishing of a nonprincipal Dirichlet L-function at one, including real Dirichlet characters. If $\chi$ is nonprincipal modulo $q$, periodicity and the given Orthogonality of Dirichlet characters bound $A_{\chi }(x)={\sum }_{n\le x}\chi (n)$ by $q$. Partial summation giveswhich is holomorphic for $\Re s>0$ by locally uniform convergence, including after differentiation. The principal Dirichlet character instead haswith a simple pole at one.

For a nonreal Dirichlet character, consider $P(s)={\prod }_{\chi \mathrm{mod}q}L(s,\chi )$. For real $\sigma >1$, its Euler product logarithm isThe given character inversion with $a=1$ makes each inner sum either $\phi (q)$ or zero, so $P(\sigma )\ge 1$. If $L(1,\chi )=0$ for a nonreal Dirichlet character, then $L(1,\overline{\chi })=0$ as well, since their values at real $s$ are conjugate. These are two distinct factors. All nonprincipal factors are holomorphic at one, and only the principal factor has a simple pole. Their two zeros would force $P(\sigma )\to 0$, a contradiction.

For a real nonprincipal Dirichlet character, suppose $L(1,\chi )=0$. Then $G(s)=\zeta (s)L(s,\chi )$ is holomorphic throughout $\Re s>0$: the supplied continuation of the Riemann zeta function has no other pole there, and the zero cancels the pole at one. On $\Re s>1$ its Dirichlet series has coefficientsTo check the sign explicitly, for a prime power $p^j$ the local sum is $j+1$ if $\chi (p)=1$, is $1$ for even $j$ and $0$ for odd $j$ if $\chi (p)=-1$, and is $1$ if $\chi (p)=0$. Multiplication over prime factors proves nonnegativity and $g_{m^2}\ge 1$. Also $g_n\le \tau (n)$, so termwise derivatives at $s=2$ are justified by absolute convergence:The disc $|s-2|<2$ lies in $\Re s>0$. Its Taylor series therefore converges at $s=1/2$, and Tonelli theorem givesThis contradicts holomorphy at $1/2$. It is the positive-coefficient argument behind the Landau theorem for a Dirichlet series with nonnegative coefficients, proved here rather than invoked. Thus $L(1,\chi )\ne 0$ for every nonprincipal Dirichlet character.

It remains to detect the primes. For real $\sigma >1$, the Euler product logarithm satisfiesuniformly as $\sigma \downarrow 1$: terms with $m\ge 2$ are bounded in absolute value by ${\sum }_{n\ge 2}{\sum }_{m\ge 2}{n}^{-m}/m<\infty$. For a nonprincipal Dirichlet character, a holomorphic logarithm of $L$ exists near one by the nonvanishing just proved. On a short real interval it differs from the Euler product logarithm by a fixed multiple of $2\pi i$, so the prime sum stays bounded. For the principal Dirichlet character, the simple pole instead givesApplying the supplied Orthogonality of Dirichlet characters for a reduced residue class $a$ now yieldsThe right side tends to infinity, whereas a finite set of primes would give a bounded left side. Therefore every residue class coprime to $q$ contains infinitely many primes, proving the Dirichlet theorem on primes in arithmetic progressions.

Write $e(t)=\exp (2\pi it)$ and use $\Vert t\Vert$ for distance to the nearest integer. The Dirichlet approximation theorem, in its pigeonhole form, says that for every real $\alpha$ and integer $Q\ge 1$ there are coprime integers $a,q$ with $1\le q\le Q$ and $|\alpha -a/q|\le 1/(qQ)$. Indeed put the $Q+1$ fractional parts of $0,\alpha ,\dots ,Q\alpha$ into $Q$ equal intervals; two lie in the same interval. Their difference gives $|q\alpha -a|\le 1/Q$, and reducing the fraction preserves the claimed bound. This includes rational $\alpha$.

For $t\ge s$, the finite geometric series has length $L=t-s+1$. When $\theta \notin \mathbb{Z}$,The last inequality uses the concavity of sine on $[0,\pi /2]$. The triangle inequality also gives $L$. At integer $\theta$ the sum has absolute value $L$, interpreting the reciprocal as infinity. Thus the precise exponential geometric sum bound isThe interval must be nonempty; for $t<s$ its sum is zero and its length should be defined as $\max (0,t-s+1)$, rather than using a potentially negative bound.

For the separated points, assume $Q\ge 2$ and $\delta >0$. An arc of length $2r\le 1$ contains at most $1+2r/\delta$ of the points, by ordering them along the arc. Points with $\Vert {\theta }_i\Vert \le 1/Q$ contribute $O(Q+{\delta }^{-1})$. In the dyadic annulus $2^j/Q<\Vert {\theta }_i\Vert \le 2^{j+1}/Q$, each summand is $O(Q{2}^{-j})$ and there are at most $1+2^{j+2}/(Q\delta )$ points. There are $O(\log (2Q))$ nonempty annuli, giving the stronger separated reciprocal-distance sumIf there is only one point the bound is immediate; otherwise $\delta \le 1/2$. The printed $\log Q$ requires a lower bound away from $Q=1$; $\log (2Q)$ avoids that endpoint defect.

A useful version of the quadratic Weyl inequality is the following, with $(a,q)=1$, $1\le q\le Q$ and $|\alpha -a/q|\le 1/(qQ)$:For $N\ge 2$, expand the square of this quadratic exponential sum by $h=n-m$:The exponential geometric sum bound therefore gives $|S{|}^2\ll N+{\sum }_{h\le N}\min (N+1,\Vert 2\alpha h{\Vert }^{-1})$. For $q\ge 8$, partition these $h$ into blocks of length at most $\lfloor q/4\rfloor$. Two different points in one block have difference $d$ with $0<|d|<q/4$. The reduced denominator of $2a/q$ is at least $q/2$, so $\Vert 2ad/q\Vert \ge 1/q$, whileThus the rotations $2\alpha h$ are separated by at least $1/(2q)$ in each block. The separated reciprocal-distance sum bounds each block by $O(N+q\log (2N))$. There are $O(N/q+1)$ blocks, and henceFor $q<8$ or $N<2$, the trivial bound supplies the same assertion with an absolute constant. The same proof applies to ${\sum }_{n=1}^{N}e(\alpha n^2)$, whose difference sums also have interval endpoints.

We finally prove a polynomial rate of quantitative quadratic recurrence, without using the optional finite-group assumption. For $0<\epsilon \le 1/2$, use the periodic triangular bump $b(t)=(1-\Vert t\Vert /\epsilon {)}_{+}$. It is ${\epsilon }^{-1}$ times the periodic convolution of two interval indicators, and therefore has the nonnegative Fourier coefficientsIts Fourier series is absolutely convergent, ${\sum }_r\hat{b}(r)=b(0)=1$, and the coefficient tail is ${\sum }_{|r|>R}\hat{b}(r)\ll 1/(\epsilon R)$. Suppose that $\Vert \alpha n^2\Vert \ge \epsilon$ for every $1\le n\le N$. Then ${\sum }_{n}b(\alpha n^2)=0$. Choose $R=\lceil C{\epsilon }^{-2}\rceil$ with a sufficiently large absolute $C$, so that the contribution of frequencies $|r|>R$ has absolute value at most $N\epsilon /2$. The zero frequency contributes $N\epsilon$. Since all coefficients are nonnegative and their sum is one, some $1\le r\le R$ must satisfyApply the Dirichlet approximation theorem to $r\alpha$ with $Q=N$, obtaining a reduced $a/q$, $q\le N$. The quadratic Weyl inequality then impliesSet $\epsilon =N^{-1/8}$. For sufficiently large $N$, the $N\log (2N)$ term is absorbed on the left, giving $q\ll {\epsilon }^{-2}\log (2N)$. The integer $n=rq$ consequently satisfiesMoreover the approximating integer is $arq$, andThis contradicts the assumed avoidance. Increasing the absolute constant handles the finitely many smaller $N$, uniformly for every real $\alpha$. Thus

The rational approximation below is taken in lowest terms, $(a,q)=1$, with $1\le q\le Q$, and $X>0$. This is necessary for denominator-sensitive exponential sum estimates and for the final Ramanujan sum to equal $\mu (q)$. If $0<X<1$, the defining sum over $a\le X$ is empty and $S_4=0$; hence we may assume $1\le X<\sqrt{N}$.

Set $c_u={\sum }_{a\mid u,a\le X}\mu (a)$, so $|c_u|\le \tau (u)$, and write the given Vaughan identity term as the Type II sumUse a dyadic decomposition into $u\in (U,2U]$, $d\in (D,2D]$, retaining $ud\le N$. Empty blocks may be discarded; every remaining block has $U,D\ge X$, $UD<N$, and there are $O({\log }^2(2N))$ blocks. Denote a block by $T$. The Cauchy-Schwarz inequality givesBy the allowed divisor-square summatory bound, the first factor is $O(U{\log }^3(2N))$. Expand the second factor. The diagonal $d_1=d_2$ contributes $O(UD{\log }^2(2N))$, using $0\le \Lambda (d)\le \log (2N)$. For a pair $d_1\ne d_2$, the allowed $u$ form the intervalThus the exponential geometric sum bound applies to this interval even though the original block has a hyperbolic cutoff. For each difference $h=|d_1-d_2|\le D$, there are $O(D)$ ordered pairs, giving an upper boundfor the expanded second factor, with an absolute constant $C$ accommodating integer endpoints. The supplied reciprocal fractional-part sum near a rational, with $M\asymp D$ and $R\asymp U$, bounds the last sum byOne may also derive this directly from the separated reciprocal-distance sum by splitting $h$ into blocks of length at most $q/2$; the approximation error between two block points is at most $1/(2q)$, and the rational rotations are separated by $1/q$.

Combining the estimates yieldsSince $UD<N$ and $U,D\ge X$, both $U,D\le N/X$. Taking square roots provesSumming the dyadic blocks establishes the rational-phase Type II estimate and, in particular, the requested bound with an explicit logarithmic power:

The Siegel–Walfisz theorem states that for fixed $A,C>0$, uniformly for $q\le (\log N{)}^A$ and $(b,q)=1$,The constant is allowed to be ineffective. Apply this with $C=A+B+2$ to the reduced residue classes. Their contribution to the prime exponential sum issince there are at most $q\le (\log N{)}^A$ residue classes. To evaluate the Ramanujan sum, the Möbius divisor-sum identity gives $1_{(b,q)=1}={\sum }_{d\mid (b,q)}\mu (d)$. Then the finite geometric series givesWhen $(a,q)=1$, only $m=1$ remains, giving $c_q(a)=\mu (q)$. The omitted nonunits contribute only prime powers $p^j$ with $p\mid q$. For each such prime, the sum of their Von Mangoldt function weights is at most $\log N$, so their total is at most $\omega (q)\log N=O_A(\log N\log \log (3N))$, absorbed by the stated error. This proves the major-arc value of the prime exponential sum:The original PDF does not state coprimality in this last request. Without it the asserted main term is genuinely false: $a=q=2$ makes $e(an/q)=1$ and hence ${\hat{\Lambda }}_N(a/q)=\psi (N)\sim N$, whereas $\mu (2)/\phi (2)=-1$. For an arbitrary numerator the correct main term is $N{c}_q(a)/\phi (q)$, with $c_q(a)$ given by the divisor formula above. Reducing the fraction before applying the boxed result is the equivalent repair.