Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 124 / 5

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.