Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 30 (Additive Number Theory)

Use $e(t)=e^{2\pi it}$ and the Fourier transform convention $\hat{f}(\xi )={\int }_{\mathbb{R}}f(x)e(-x\xi )dx$, initially for an integrable function. For the interval indicator function, direct integration givesThe integral bound is one, and the displayed numerator has modulus at most two. By the convolution theorem, the Fourier transform of the $m$-fold convolution is its $m$th power. Thus the Fourier decay of repeated interval convolutions givesAt zero, interpret the second term of the minimum as infinity.

The Schwartz space $\mathcal{S}(\mathbb{R})$ consists of smooth functions for which every Schwartz seminorm ${\sup }_x|x^a{f}^{(b)}(x)|$ is finite, for nonnegative integers $a,b$. Differentiation under the integral sign and integration by parts giveAll differentiated integrands are integrable, and their boundary terms vanish because of rapid decay. The last transform is bounded by its integrand's $L^1$ norm. The same argument applies at every derivative order, so $\hat{f}\in \mathcal{S}(\mathbb{R})$.

For $f\in \mathcal{S}(\mathbb{R})$, the Poisson summation formula isTo prove it, form the periodization of a Schwartz function $F(x)={\sum }_{n}f(x+n)$. Rapid decay gives uniform convergence of this series and of every differentiated series on $[0,1]$, so $F$ is a smooth periodic function. Its Fourier coefficients areThe series ${\sum }_k\hat{f}(k)e(kx)$ converges absolutely and uniformly. Its Fourier coefficients equal those of $F$. The uniqueness theorem for Fourier series says that two integrable functions with the same coefficients agree almost everywhere; as both functions here are continuous, they agree everywhere. Evaluating at zero proves Poisson summation.

The Gaussian Fourier transform of $e^{-\pi t{x}^2}$, $t>0$, is $t^{-1/2}{e}^{-\pi {\xi }^2/t}$. Apply Poisson summation to obtain the transformation of the Jacobi theta functionFor $\Re s>1$, termwise integration in the Mellin transform gives the Mellin representation of the completed Riemann zeta functionSplit at one and substitute $t=1/u$ in the lower integral. The theta transformation givesThe integral is an entire function of $s$, since $\vartheta (t)-1$ decays exponentially. This pole-subtracted theta integral for the completed zeta function supplies a meromorphic continuation with simple poles at zero and one. Both the rational term and the integral are unchanged by $s\mapsto 1-s$, proving the functional equation of the Riemann zeta functionEquivalently the Riemann xi function $\xi (s)=\frac{1}{2}s(s-1)\Lambda (s)$ is entire and satisfies $\xi (s)=\xi (1-s)$. The reflection and duplication identities for the Gamma function also give $\zeta (s)=2^s{\pi }^{s-1}\sin (\pi s/2)\Gamma (1-s)\zeta (1-s)$ by meromorphic continuation.

Write $F(s)=-{\zeta }^{\prime }(s)/\zeta (s)$ and ${\psi }_{\Gamma }={\Gamma }^{\prime }/\Gamma$. The global partial-fraction expansion of the zeta logarithmic derivative isHere $\gamma$ is the Euler--Mascheroni constant, and the sum includes multiplicities of the Nontrivial zeros of the Riemann zeta function. The paired terms are locally absolutely convergent away from their poles, by the Riemann–von Mangoldt formula. This identity follows by differentiating the genus-one Hadamard factorization of the Riemann xi function and using the Gamma function recurrence.

We first prove the classical zero-free region of the Riemann zeta function. The Euler-product nonvanishing of the Riemann zeta function and its functional equation place every nontrivial zero in the closed strip $0\le \beta \le 1$; no assertion about zeros on its boundary is needed yet. The real logarithmic derivative of Riemann xi and the digamma function asymptotic imply, for $1<\sigma \le 2$ and $|t|\ge 1$,Every summand being subtracted is nonnegative. If $\beta +it$ is a zero, retaining its summand gives $\Re F(\sigma +it)\le C\log (|t|+2)-1/(\sigma -\beta )$; at height $2t$ the upper bound $C\log (|t|+2)$ suffices. At real $\sigma$ the simple pole of $\zeta$ gives $F(\sigma )=1/(\sigma -1)+O(1)$.

For $\sigma >1$, the Dirichlet series $F(s)={\sum }_n\Lambda (n)n^{-s}$ has nonnegative coefficients. The identity $3+4\cos u+\cos 2u=2(1+\cos u{)}^2\ge 0$ therefore gives the three-four-one zero-free-region argumentWith $L=\log (|t|+2)$, a zero at $\beta +it$ would consequently satisfyChoose $\sigma =1+a/L$, with an absolute $a>0$ sufficiently small, and put $c=a/8$. If $\beta \ge 1-c/L$, this inequality would imply $4/(a+c)\le 3/a+C$. But $4/(a+a/8)-3/a=5/(9a)>C$ for small enough $a$, a contradiction.

For any fixed $t\ne 0$, the same positivity inequality as $\sigma \downarrow 1$ excludes a zero at $1+it$: its negative contribution has coefficient at least four, whereas the real pole contributes only three. Any zero at $1+2it$ only strengthens the contradiction. The pole at $s=1$ has a zero-free punctured neighbourhood. By compactness, the remaining bounded-height portion of the line has a zero-free neighbourhood as well. Shrink $c$ to combine these facts with the large-height bound. Hencewith the understanding that $s=1$ is a pole.

The Riemann–von Mangoldt explicit formula for the Second Chebyshev function, with half weight at a prime-power endpoint, isThe zero sum uses symmetric height truncation. To estimate it, take a half-integer $x$ and use the truncated explicit formula for the second Chebyshev functionThe zero-free region gives $|x^{\rho }|\le x\exp (-c\log x/\log (T+2))$ for these zeros. The Riemann–von Mangoldt formula and partial summation give ${\sum }_{|\Im \rho |\le T}|\rho {|}^{-1}\ll {\log }^2(T+2)$. Choose $T=\exp (\sqrt{\log x})$. Both the zero sum and the truncation error are then $O(x{e}^{-c^{\prime }\sqrt{\log x}})$ after reducing the positive constant to absorb logarithmic factors. Replacing an arbitrary $X$ by $\lfloor X\rfloor +1/2$ preserves the Von Mangoldt function sum and changes the main term by at most one. This proves the requested form of the Prime number theorem:

Let $A(x)$ count primes $p\le x$ for which $p+2$ is also prime. We prove $A(x)\ll x/{\log }^{2}x$ using a quadratic Selberg sieve, then apply Abel summation.

For $F(n)=n(n+2)$, each odd prime has exactly two roots modulo that prime. The Chinese remainder theorem gives the polynomial root density in a sievefor odd squarefree integers $d$. Put $R=x^{1/8}$ and choose the optimizing real Selberg sieve weights ${\lambda }_d$, supported on these $d\le R$, with ${\lambda }_1=1$. If $p,p+2$ are prime and $p>R$, their weight $({\sum }_{d\mid F(p)}{\lambda }_d{)}^2$ is one. It is nonnegative for every other integer. Expanding the square therefore givesThe Selberg sieve diagonalization makes the main quadratic form $1/J(R)$, whereThe optimal Selberg weights have modulus at most one. Since ${\rho }_F([d,e])\le [d,e]\le R^2$, the remainder is at most $O(R^4)$.

For completeness, the lower bound on $J$ is where the second logarithm enters. Restrict to primes $3\le p\le y=R^{1/8}$ and put $k(p)=2/(p-2)$. The full product $W={\prod }_{3\le p\le y}(1+k(p))$ is $\asymp {\log }^{2}y$, since its logarithm is $2{\sum }_{3\le p\le y}1/p+O(1)$ and the Mertens second theorem applies. Give the associated squarefree divisor $d$ probability $k(d)/W$. Prime inclusion probabilities are $2/p$, so the Mertens first theorem givesfor large $R$. The Markov inequality shows that at least half the weight has $d\le R$. This proves the truncated Euler-product lower bound $J(R)\gg W\gg {\log }^{2}R$. Consequently the twin-prime upper bound from a quadratic sieve isFinally, Abel summation givesThe tail is dominated by ${\int }_3^{\infty }dt/(t{\log }^{2}t)<\infty$. Thus reciprocal-sum convergence from a counting bound proves convergence of the first reciprocal sum. The second is smaller termwise. We have proved Brun's theorem:Counting each twin prime just once changes at most a finite repetition and gives the same conclusion.

Put $d=\gcd (k,p-1)$ and write $S(a)={\sum }_{x\in {\mathbb{F}}_p}e(a{x}^k/p)=p{G}_{a,p}$. The multiplicative group of a finite field is cyclic, so on its nonzero elements the $k$th-power map has kernel of size $d$. For $y\ne 0$, character orthogonality consequently giveswhere the sum is over its multiplicative characters. Thus, for $a\ne 0$,The term from the trivial character is $-1$ and cancels the initial one.

For a nontrivial character, the prime-field character Gauss sum identity can be proved directly. Since $|\chi (z)|=1$ on nonzero elements, substituting $y=tz$ givesThe inner sum is $p-1$ for $t=1$ and $-1$ otherwise. Since ${\sum }_{t\ne 0}\chi (t)=0$, the result is $p$. The triangle inequality now proves the power Gauss sum over a prime field boundThis also includes $d=1$, when the nonzero-frequency sum vanishes.

For $x\in {\mathbb{F}}_p$, additive character orthogonality counts its representations as three powers:The zero-frequency term is $p^2$. Each other term has $|S(a)|\le k\sqrt{p}$, soIf $p>k^6$, this is less than $p^2$, giving $R(x)>0$ for every $x$. Hence $p>k^6$ is a sufficient threshold for the three power summands over a large prime field conclusion.

Put $S(\theta )={\sum }_{r=1}^{n}e(\theta r^3)$. Its modulus is the modulus of the Fourier transform in the question, independently of the sign convention. We use Hua's lemma in the cubic form ${\int }_0^1|S{|}^8{\ll }_{\delta }{n}^{5+\delta }$; the cubic eighth-moment proof by differencing establishes this from the subpower bound for the divisor function. Thereforeand $n\asymp N^{1/3}$ imply ${\sup }_m|S|{\gg }_{\delta }{n}^{1-\delta }$. Choose an actual $\theta \in m$ attaining at least half this bound; attainment of the supremum itself is unnecessary.

Fix $\epsilon >0$ and put ${\epsilon }_0=\min (\epsilon ,1/6)$. The Dirichlet approximation theorem with $Q=\lfloor N^{1-{\epsilon }_0}\rfloor$ gives coprime integers $a,q$ satisfyingThe cubic Weyl inequality, which is the quantitative equidistribution estimate needed here, saysCompare it with the lower bound. Choose $\delta ,\eta >0$ so small that $b=4(\delta +\eta )/3<{\epsilon }_0/2$. It follows thatBut $n^{-1}=O(N^{-1/3})$ and $q/n^3=O(N^{-{\epsilon }_0})$. Both are $o(N^{-b})$, so for large $N$ the first term must supply this lower bound. Consequently $q{\ll }_{\epsilon }{N}^b{\ll }_{\epsilon }{N}^{\epsilon }$, while the approximation above gives $\Vert q\theta \Vert \ll N^{{\epsilon }_0-1}\le N^{\epsilon -1}$. Enlarging the constants covers bounded $N$. ThusHere $\Vert \cdot \Vert$ is distance modulo one. A ninth moment of this size therefore forces at least one near-rational frequency, rather than merely a large pointwise sum somewhere outside $m$.

Extend $f$ by zero outside $[1,N]\cap \mathbb{Z}$. Here is a dyadic endpoint convention for small Type I and Type II sums. Write $D_M=[M,2M)\cap \mathbb{Z}$, with $M$ a power of two. Type I sums are $\delta$-small if, for every $M\le N^{1/100}$, dyadic $K$ with $MK\le N$, and arbitrary integer intervals $I_m\subset D_K$,Type II sums are $\delta$-small if, for all dyadic $M,K\in [N^{1/100},N^{99/100}]$ and sequences $|a_m|,|b_n|\le 1$,Zero extension handles boxes crossing the endpoint $mn=N$. Fixed choices of open or closed dyadic endpoints do not matter, but interval uniformity and uniformity in both bounded coefficient sequences do matter. These are the estimates used in the Vinogradov Type I–II method.

An interesting technical step is Fourier separation of interval cutoffs. For an integer interval $I_m$, let $\widehat{1_{I_m}}(\theta )={\sum }_{r\in I_m}e(-r\theta )$. Discrete Fourier inversion givesThe exponential geometric sum bound gives a common envelope $H_N(\theta )\ll \min (N,\Vert \theta {\Vert }^{-1})$, with ${\int }_0^1{H}_N\ll \log (2N)$. Divide the interval transform by this envelope: at each frequency it is a bounded coefficient depending on $m$, and $e(n\theta )$ is a bounded coefficient depending on $n$. The Type II sum assumption therefore bounds the interval-cutoff sum by $O(\delta N\log N)$. Choosing the outer unit phases to turn each inner sum into its modulus extends the Type I sum bound to boxes where both variables are in the Type II range.

Take $U=V=\lfloor N^{1/3}\rfloor$. With subscripts denoting truncation of arithmetic functions, the Vaughan identity iswhere $\ast$ now means Dirichlet convolution. For completeness it follows from $\mu \ast 1=ϵ$ and $\Lambda \ast 1=\log$: expand ${\mu }_{>U}\ast {\Lambda }_{>V}\ast 1$, cancel the short terms, and retain $\Lambda$. The short first term contributes $O(N^{1/3}\log N)$ to the sum against $f$.

The next two terms give Type I sums. The logarithmic term has outer coefficient $\mu (m)$, $m\le U$, and inner factor $\log n$, removed by partial summation at a cost $O(\log N)$. In the other term the outer variable is $m=cd\le UV$ with coefficientThis logarithmic coefficient bound in Vaughan identity avoids a loss from a divisor weight. On boxes with short outer variable use the hypothesis directly; on boxes where both variables are at least $N^{1/100}$ use the extended bound proved above. Boxes with inner variable less than $N^{1/100}$ contain at most $O(N^{2/3+1/100})$ pairs in total and are treated trivially. All remaining inner scales are at most $N^{99/100}$ whenever the outer scale exceeds $N^{1/100}$.

For the final convolution, group the variables asBoth variables lie between constant multiples of $N^{1/3}$ and $N^{2/3}$, well inside the Type II range. Divide $b(n)$ by $\log N$, and apply the Type II sum estimate. If the product cutoff is kept explicitly, Fourier separation of interval cutoffs costs only one extra logarithm; zero extension also permits its omission. There are $O({\log }^{2}N)$ boxes in the dyadic decomposition. The coefficient bound and, where needed, partial summation cost at most one more logarithm. These estimates give the convenient boundWith $\delta =(\log N{)}^{-20}$, each term is $o(N)$, proving the assertion. The grouping of the long term uses the nonnegativity of the Von Mangoldt function; more usual groupings instead control a divisor coefficient by a second-moment truncation. Ben Green's notes, Sections 2.3–2.4 describe that standard alternative.

Now take the sign version of the Thue–Morse sequence, $f(n)=(-1{)}^{s_2(n)}$. Concatenation of binary digits gives $f(a{2}^j+r)=f(a)f(r)$ for $0\le r<2^j$. Expanding over all choices of digits proves the Thue–Morse Fourier productPair adjacent factors. If $u=|\cos (\pi t)|$, their modulus issince the maximum on $[0,1]$ occurs at $u=1/\sqrt{3}$. Thus $|S_j(\theta )|\ll 2^{\sigma j}$ uniformly, where $\sigma =\frac{1}{2}{\log }_{2}B=2-\frac{3}{4}{\log }_{2}3<1$.

Every integer interval $J\subset [0,N]$ is a disjoint union of aligned binary blocks with at most two blocks of each length. On such a block the digit concatenation identity and the Thue–Morse Fourier product give the same bound, up to a unit phase. Summing the geometric series proves the uniform interval cancellation for binary digit parityFor a fixed $m$, the sum ${\sum }_{n\in I_m}f(mn)$ is a sum over multiples of $m$ in an integer interval $J\subset [1,N]$. The additive character orthogonality filter givesIts modulus is $O(N^{\sigma })$, independently of $m$ and the interval. Summing at most $O(N^{1/100})$ outer values proves the small Type I sums for binary digit parity:This is smaller than $(\log N{)}^{-20}$ for sufficiently large $N$. It proves the required Type I cancellation; the substantially harder Type II cancellation is not needed for this final clause.