Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 124 (Probabilistic Number Theory)

An additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for coprime integers $m,n$; a completely additive arithmetic function satisfies this for all positive $m,n$. In either case $f(1)=0$. The fundamental theorem of arithmetic gives $f(n)={\sum }_{p^k\parallel n}f(p^k)$, where $p^k\parallel n$ means that the prime valuation of $n$ at $p$ is exactly $k$.

Under the discrete uniform distribution on $[N]$, the expectation of the indicator function of $p^k\parallel n$ isThe formula remains valid when $p^{k+1}>N$. Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:

For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:Here $\omega$ is the prime omega function and $\Omega$ is the total number of prime factors. The expectation is bounded independently of $N$, sinceThus Markov inequality gives vanishing probability on every diverging scale:

The Möbius function has $\mu (1)=1$, $\mu (n)=0$ when $n$ is divisible by a prime square, and $\mu (n)=(-1{)}^r$ when $n$ is a product of $r$ distinct primes. The Riemann zeta function is initially the Dirichlet series $\zeta (s)={\sum }_{n\ge 1}{n}^{-s}$ for $\sigma =\Re s>1$. Both this Dirichlet series and $\sum \mu (n)n^{-s}$ have absolute convergence, because $|\mu (n)|\le 1$ and $\sum n^{-\sigma }<\infty$.

For a finite set of primes $p\le y$, multiplication of absolutely convergent geometric series and unique prime factorization giveEvery omitted integer has a prime factor exceeding $y$, so it exceeds $y$. The difference from $\zeta (s)$ has absolute value at most ${\sum }_{n>y}{n}^{-\sigma }\to 0$. This proves the Euler product, with the product interpreted as the limit of its finite products:

For the reciprocal identity, absolute convergence justifies multiplying and regrouping the two Dirichlet series by their product index. Their Dirichlet convolution coefficient at $m$ isThe coefficient calculation uses only the squarefree integers dividing $m$. Consequently the reciprocal identity is an identity of absolutely convergent series:

Let $M(x)={\sum }_{n\le x}\mu (n)$ be the Mertens function. Partial summation givesFor any $\Re s>0.9$, choose a sufficiently small $ϵ>0$ with $0.9+ϵ<\Re s$. The assumed bound makes the boundary term tend to zero and makes the integral absolutely convergent. Moreover, on each compact set of this half-plane, one can choose the same $ϵ$, so the integral has locally uniform convergence. Henceis a holomorphic function on $\Re s>0.9$, agreeing with the reciprocal Dirichlet series from part (b) on $\Re s>1$.

The identity theorem applied to the holomorphic functions $(s-1)\zeta (s)F(s)$ and $s-1$ extends their equality throughout $\Re s>0.9$; the assumed simple pole makes the first function holomorphic at $1$. Thus $\zeta (s)F(s)=1$ away from $1$, proving a zero-free half-plane:

To obtain the strongest symmetric conclusion, use the following basic facts explicitly: the functional equation of the Riemann zeta function gives the entire function $\xi (s)=\frac{1}{2}s(s-1){\pi }^{-s/2}\Gamma (s/2)\zeta (s)$ with $\xi (s)=\xi (1-s)$, and the trivial zeros of the Riemann zeta function are the negative even integers. Every Nontrivial zero of the Riemann zeta function is therefore accompanied by its reflection $1-s$. A Nontrivial zero of the Riemann zeta function with real part below $0.1$ would reflect to one above $0.9$, which is impossible. Consequently all nontrivial zeros lie in the closed stripThe $ϵ$ in the hypothesis prevents this argument from excluding either boundary line; the trivial zeros of the Riemann zeta function remain present.

The event that infinitely many $A_n$ occur is ${\mathrm{limsup}}_n{A}_n={\bigcap }_{m\ge 1}{\bigcup }_{n\ge m}{A}_n$. For every $m$, the union bound and monotonicity of a probability measure giveThe right-hand side tends to zero as the tail of a convergent series. Therefore the first Borel-Cantelli conclusion isThis proves the Borel-Cantelli first lemma without any independence assumption.

First, the Cramér model has infinitely many successes almost surely, so every $P_n$ is finite. Indeed, for each fixed $K\ge 3$, independence of the Bernoulli random variables givesThe sum diverges, for example because $1/\log j\ge 1/j$ for $j\ge 3$. Continuity from above of a measure and a countable union bound exclude a final success.

Fix $ϵ>0$ and put $L_k=\lceil (1+ϵ)(\log k{)}^2\rceil$. Let $A_k$ be the event that the whole interval $k+1,\dots ,k+L_k$ consists of failures. By independence and $1-v\le e^{-v}$,Since $L_k=o(k)$, the exponent divided by $\log k$ tends to $-(1+ϵ)$. Thus $\mathbb{P}(A_k)\le k^{-1-ϵ/2}$ for all sufficiently large $k$. The Borel-Cantelli first lemma shows that almost surely every sufficiently large such interval contains a success. Taking $k=P_n$ then gives $P_{n+1}-P_n\le L_{P_n}$ for all sufficiently large $n$.

For each fixed $ϵ$, the limit superior of the normalized gap is therefore at most $1+ϵ$ almost surely. Intersect the probability-one events for $ϵ=1/r$, $r\in \mathbb{N}$, to obtain the Cramér model prime-gap upper bound:

For the simple symmetric random walk, independence and the Rademacher distribution give the moment-generating functionThe function ${\theta }^2/2-\log \cosh \theta$ is even; for $\theta \ge 0$ its derivative is $\theta -\tanh \theta \ge 0$, since the derivative of $\tanh \theta$ is at most one and $\tanh 0=0$. Here $\cosh$ and $\tanh$ are the hyperbolic cosine and hyperbolic tangent. Hence the exponential-moment estimate is

The supplied exponential maximal bound for a symmetric random walk now gives $\mathbb{P}({\max }_{k\le n}{S}_k\ge t\sqrt{n})\le \exp (-\theta t\sqrt{n}+n{\theta }^2/2)$. For $t>0$, choose $\theta =t/\sqrt{n}$; for $t=0$, use the elementary bound by one. Thus

Fix $a>1$, choose $0<\delta <a^2-1$, and set $n_m=\lfloor (1+\delta {)}^m\rfloor$. For large $m$ these form an increasing sequence. Apply the preceding exponential maximal bound for a symmetric random walk at $n_{m+1}$ with threshold $a\sqrt{2n_m\log \log n_m}$. The resulting probability is at mostWe have $n_m/n_{m+1}\to (1+\delta {)}^{-1}$ and $\log \log n_m=\log m+O(1)$. Choose $b$ strictly between $1$ and $a^2/(1+\delta )$; the displayed probabilities are $O(m^{-b})$. By the Borel-Cantelli first lemma, almost surely, eventually ${\max }_{k\le n_{m+1}}{S}_k<a\sqrt{2n_m\log \log n_m}$. For every $n_m\le n\le n_{m+1}$, monotonicity of $n\log \log n$ for large $n$ therefore givesIntersect the probability-one events for $a=1+1/r$ to obtain the upper law of the iterated logarithm:

Use the convention that a z-sieved number is a positive integer with no prime factor strictly below $z$; $1$ is included. Such integers are also called rough numbers. Using instead exclusion of primes at most $z$ changes an endpoint convention, not the following fixed-$u$ asymptotic.

The Buchstab function is the continuous function $w:[1,\infty )\to \mathbb{R}$ determined bySuccessive integration over intervals of length one determines the Buchstab function uniquely from its initial values.

A standard fixed-$u$ form of Buchstab theorem states that, for each fixed $u>1$, as $z\to \infty$,For $1<u\le 2$, this agrees with the Prime number theorem, since apart from an immaterial endpoint the z-sieved numbers in this range are $1$ and the primes from $z$ to $z^u$. The restriction $u>1$ matters: at $u=1$ the count is bounded, so the displayed asymptotic does not hold there.

Put $c=e^{-\gamma }$, where $\gamma$ is the Euler--Mascheroni constant, and let $f(u)=w(u)-c$. The Buchstab function equation becomesThe given Gamma function bound implies $uf(u)\to 0$. Indeed,so $u/\Gamma (u+1)\to 0$.

Suppose first that $f\ge 0$ throughout an interval $[u,u+1]$, with $u\ge 1$. The delay differential equation and integration successively on $[u+1,u+2]$, $[u+2,u+3]$, and so on propagate nonnegativity to the entire tail $[u,\infty )$. In particular, $vf(v)$ is nonnegative and nondecreasing for $v\ge u+1$. Its limit is zero, so it is identically zero there. Thus $f=0$ on that tail.

The delay differential equation then propagates this equality backwards: if $f=0$ for $v\ge a$, then $f(v-1)=0$ for $v>\max (a,2)$. Repeating finitely many times would give $f=0$ on $(1,2)$, contradicting $f(v)=1/v-c$ there. Hence every interval $[u,u+1]$ contains a point where $f<0$.

If instead $f\le 0$ on $[u,u+1]$, the same propagation makes $vf(v)$ nonpositive and nonincreasing on the tail. Its limit zero again forces it to vanish, giving the same contradiction. Thus every such interval also contains a point where $f>0$. The oscillation of the Buchstab function is therefore strict on every unit interval:

For an additive arithmetic function $f$, one standard form of the Turán-Kubilius inequality usesIt states, with an absolute constant,For real $f$, this also bounds the variance under the discrete uniform distribution, because centering at the actual expectation minimizes the mean square.

For the prime omega function, $f(p^k)=1$. The Mertens theorem for reciprocal primes states ${\sum }_{p\le N}1/p=\log \log N+O(1)$. The contribution of higher prime powers is bounded by ${\sum }_{p}1/(p(p-1))\le 1$, as proved in 1(a). It follows that $A_{\omega }(N)=\log \log N+O(1)$ and $B_{\omega }(N{)}^2\ll \log \log N$. Writing $L=\log \log N$, the Turán-Kubilius inequality and Chebyshev inequality therefore yieldThe bounded error in $A_{\omega }-L$ is absorbed by, for example, using the threshold $0.005L$ around $A_{\omega }$ for sufficiently large $N$.

For the multiplication table problem, call a pair $(a,b)\in [N{]}^2$ good when $\omega (a),\omega (b)\ge 0.99L$ and $\omega (\gcd (a,b))\le 0.1L$. The preceding Chebyshev inequality excludes only $O(N^2/L)$ pairs by either of the first two conditions. For the greatest common divisor condition, linearity of expectation under uniform sampling of the two coordinates givesMarkov inequality therefore excludes only another $O(N^2/L)$ pairs.

The prime factors of a product form the union of those of its factors. Consequently, for every good pair,On the other hand, apply the proved concentration estimate at $N^2$. Since $\log \log (N^2)=L+\log 2$, for large $N$ every integer $m\le N^2$ with $\omega (m)\ge 1.88L$ is exceptional there. There are only $O(N^2/L)$ such integers. Products of good pairs lie in this exceptional set; products having only bad representations are at most as numerous as the bad pairs. This proves the multiplication-table upper bound, using distinct prime factors alone:

Expand the two Dirichlet polynomials, keeping the complex conjugate on $B$. The diagonal $m=n$ contributes exactly $T{\sum }_{n\le X}{a}_n\overline{b_n}/n^{2\sigma }$. If $m\ne n$, the exponential integral iswhose absolute value is at most $2/|\log (m/n)|$. Thus the mean-value formula isThis also covers $T=0$.

For $m>n$, integration of $1/x$ over $[n,m]$ gives $\log (m/n)\ge (m-n)/m$; the analogous inequality holds with $m,n$ exchanged. Hence $|\log (m/n){|}^{-1}\le \max (m,n)/|m-n|\le X$. This gives the requested first bound $O(X{\sum }_{m\ne n}|a_n||b_m|/(n^{\sigma }{m}^{\sigma }))$.

For the weighted bound, put ${\alpha }_n=|a_n|n^{-\sigma }$ and ${\beta }_m=|b_m|m^{-\sigma }$. The inequalityreduces the estimate to a row sum and its symmetric counterpart. For a fixed $n$, the preceding logarithm bounds giveHere $n^2/(m(n-m))=n(1/m+1/(n-m))$, and each resulting harmonic sum is $O(\log (2X))$. The symmetric row sum is bounded by $O(m\log (2X))$. Therefore the second error bound is

Let $D(s)={\sum }_{p\le X}{p}^{-s}$, a Dirichlet polynomial supported on primes. The cosine sum is $(D(\sigma +it)+\overline{D(\sigma +it)})/2$, so its $j$th power is a finite linear combination of $D(\sigma +it{)}^k\overline{D(\sigma +it{)}^{j-k}}$, $0\le k\le j$.

The Dirichlet polynomial $D(s{)}^k$ is supported on integers that are products of exactly $k$ primes, counted with multiplicity. Each coefficient is at most $k!$ by unique prime factorization; for $k=0$ the only coefficient is the one at $1$. As $j$ is odd, $k\ne j-k$, so no integer can appear in both supports. Thus every diagonal term vanishes in the mean value of Dirichlet polynomials from part (a).

Both supports lie in $[1,X^j]$. The first error bound in part (a), with that common length, now gives for each termSumming the finitely many terms proves the odd moment of a prime cosine sum estimate:The argument holds for all real $\sigma$ and all $T\ge 0$; no cancellation estimate involving $T$ is needed once the diagonal is absent.

Put $P(t)={\sum }_{n\le \sqrt{t/(2\pi )}}{n}^{-1/2-it}$. The given bound for the Riemann zeta function, together with $(a+b{)}^4\le 8(a^4+b^4)$ for $a,b\ge 0$, givesThe integral over $[0,1]$ is bounded, since the Riemann zeta function has no pole on this compact segment. It remains to estimate the fourth moment of the Riemann zeta function through this moving Dirichlet polynomial cutoff.

Let $L=\lfloor \sqrt{T/(2\pi )}\rfloor$ and $Y=L^2$. In the expansion of $|P(t){|}^4$, a quadruple $n_1,n_2,n_3,n_4\le L$ occurs precisely forIts oscillatory factor is $e^{it\log (n_3{n}_4/(n_1{n}_2))}$, and its weight is $(n_1{n}_2{n}_3{n}_4{)}^{-1/2}$. When $n_1{n}_2=n_3{n}_4$, its integral has length at most $T$. When these products differ, its integral over $[t_0,T]$ has absolute value at most $2/|\log (n_3{n}_4/(n_1{n}_2))|$. Thus the moving cutoff affects the lower endpoint but preserves the off-diagonal bound from part (a).

Write $r_L(m)=\#\{(a,b):a,b\le L,ab=m\}$. The divisor function $d(m)$ bounds $r_L(m)$. Grouping the off-diagonal majorant by the two products and using the weighted row-sum argument in part (a), with coefficient $r_L(m)$ and $\sigma =1/2$, bounds it byThis uses only the given divisor-square summatory bound. For bounded $T$, the desired conclusions follow by boundedness on compact segments, so these estimates may be read for large $T$ with $Y\ge 2$. We have proved the requested diagonal-plus-error estimate:

The diagonal sum equals ${\sum }_{m\le Y}{r}_L(m{)}^2/m\le {\sum }_{m\le Y}d(m{)}^2/m$. If $D(x)={\sum }_{m\le x}d(m{)}^2\ll x{\log }^3(2x)$, then partial summation givesConsequently the full fourth-moment bound is

One general form of the Erdős-Kac theorem is the following. Let $f$ be a real strongly additive arithmetic function, with $|f(p)|\le C$ for all primes, and defineIf $B(x)\to \infty$, then under the discrete uniform distribution on $[N]$,Here the arrow denotes convergence in distribution and $\mathcal{N}(0,1)$ is the standard normal distribution. Equivalently, the probability of being at most $z$ tends to the standard normal distribution function $\Phi (z)$ for every real $z$. Replacing $B(x{)}^2$ by ${\sum }_{p\le x}f(p{)}^2(1-1/p)/p$ is equivalent, because the difference is bounded by $C^2{\sum }_p{p}^{-2}$.

This is a general bounded-prime-weight form, not just the special case $f=\omega$. In that case the Mertens theorem for reciprocal primes gives $A(N)=\log \log N+O(1)$ and $B(N{)}^2=\log \log N+O(1)$, so the classical prime-factor central limit theorem is

Write $y=N^{1/\phi (N)}$, $L={\sum }_{p\le y}|g(p)|$, and $A={\sum }_{p\le y}g(p)/p$. Put $I_p(n)=1_{p\mid n}$ and $Y_p=I_p-1/p$. The strongly additive arithmetic function identity is $g-A={\sum }_{p\le y}g(p)Y_p$.

For any tuple $p_1,\dots ,p_j$, expand ${\prod }_{r=1}^j(I_{p_r}-1/p_r)$ by choosing an indicator in some positions and the constant in the others. If the selected positions contain distinct primes whose product is $d$, thenFor the corresponding product of the independent Bernoulli random variables $X_p$, the expectation is exactly $1/d$. This includes repeated primes, since their indicator functions are idempotent, and the empty selection has zero error. Summing absolute values of all expansion coefficients bounds the difference bywhen $y\ge 2$. Expanding the $j$th power and summing the absolute coefficient weights gives

It remains to center at the actual expectation. Since ${\mathbb{E}}_N{I}_p=\lfloor N/p\rfloor /N$, we have $|{\mathbb{E}}_{N}g-A|\le L/N$. For each $n$, both $g(n)-A$ and $g(n)-{\mathbb{E}}_{N}g$ have absolute value at most $L$, because all their indicator coefficients have absolute value at most one. The identity $u^j-v^j=(u-v){\sum }_{r=0}^{j-1}{u}^{j-1-r}{v}^r$ therefore bounds the change in the central moment by $j{L}^j/N$.

Finally, independence factors each term of the independent central moment. If $q_1,\dots ,q_w$ are the distinct primes of the tuple and $a_i$ their multiplicities, the desired comparison becomesIf $y<2$, then $g=0$ and both sides vanish, so the formula remains valid. The argument also covers complex coefficients $g(p)$; a real-valued assumption is needed for the later normal distribution conclusion, not for this centered moment comparison for additive arithmetic functions.

A useful method of moments in probability states that if real random variables $Z_N$ have all moments, $\mathbb{E}{Z}_N^j\to m_j$ for every integer $j\ge 1$, and $(m_j)$ is the moment sequence of a moment-determinate probability distribution, then $Z_N$ converges to that distribution in the sense of convergence in distribution. In particular, convergence to the standard normal distribution follows from limiting odd moments zero and limiting even moments $(2k-1)!!$. The moment-generating function of a standard normal variable, finite in a neighbourhood of zero, ensures moment determinacy.

For the classical Erdős-Kac theorem, put $L=\log \log N$ and choose, for example, $\phi (N)=L^{1/4}$, with a harmless modification for small $N$. Truncate the prime omega function to primes $p\le y=N^{1/\phi (N)}$. The omitted number of distinct prime factors of any $n\le N$ is at most $\phi (N)$, since a product of $r$ omitted primes exceeds $N^{r/\phi (N)}$. Thus this truncation changes the normalized variable by $o(1)$ uniformly. Also, the Mertens theorem for reciprocal primes gives

Part (b) transfers every fixed normalized central moment of the truncated prime omega function to the independent Bernoulli random variables model. Indeed, its unnormalized error is at most $O_j(N^{2j/\phi (N)-1})$, using ${\sum }_{p\le y}1\le y$, and this tends to zero for each fixed $j$. In the independent expansion, any singleton index has zero expectation; the leading contributions are pairings, giving exactly the standard normal distribution moments, while blocks of size at least three are negligible after normalization. The method of moments in probability, followed by the uniformly negligible truncation and centering errors, proves the Erdős-Kac theorem.

The same strategy proves the bounded-prime-weight form in part (a). Choose $\phi (N)\to \infty$ slowly enough that $\phi (N)=o(B(N))$. The omitted weighted contribution is $O(\phi (N))$; its mean is likewise $O(\phi (N))$, and its independent variance is $O(\log \phi (N)+1)=o(B(N{)}^2)$ by the Mertens theorem for reciprocal primes. Hence the truncated model has the same normalization, and part (b) again transfers each fixed central moment.

Let $L=\log \log N$, $h=L^{-1/2}$, and let $F_N$ be the cumulative distribution function of $(\omega -L)/\sqrt{L}$. Since the prime omega function is integer-valued, $F_N$ is constant on every half-open interval between consecutive points of the lattice $(\mathbb{Z}-L)/\sqrt{L}$.

Choose $k=\lfloor L\rfloor$ and put $\alpha =(k-L)/\sqrt{L}$, $\beta =(k+1-L)/\sqrt{L}$. Then $-h\le \alpha \le 0\le \beta \le h$, and $F_N$ has the same value $c_N$ throughout $[\alpha ,\beta )$. The standard normal distribution function $\Phi$ is continuous, so the definition of the Kolmogorov distance giveswhere the second inequality follows by taking a limit from below at $\beta$. The triangle inequality therefore yieldsThus the integer lattice forces the lower bound:This lattice obstruction to normal approximation does not require a quantitative Erdős-Kac theorem; it follows directly from discreteness and the positive standard normal density near zero.