Given a positive integer $n$, let $p$ be the largest prime less than or equal to $n$.

Let $N(n)=2^{C_2}\cdots p^{C_p}$ be uniformly distributed from $1$ to $n$, and $M(n)=2^{Z_2}\cdots p^{Z_p}$ where $Z_p's$ are independent geometric with $P(Z_p\ge k)=\frac{1}{p^k}$. It can be shown that $C_p$ has probability mass $P(C_p=k)=\frac{\big\lfloor \frac{n}{p^k}\big\rfloor}{n}.$

Consider the metric $d(M,N)=\sum_{p\le n}\vert C_p-Z_p\vert$
($d$ counts the number of prime insertions and deletions needed to convert $N$ to $M$).

Using this metric, we have the Wasserstein metric $d_W(M,N)=\inf_{\text{couplings}}\mathbb{E}d(M,N).$

Arratia (page 10 of https://arxiv.org/pdf/1305.0941.pdf) claims

  • $d_W(M,N)=o(\log \log n)$ implies the Hardy-Ramanujan Theorem (which states that for almost every positive integer $n$, $\omega(n) \approx \log \log n$, where $\omega(n)$ is the number of distinct prime divisors of $n$).
  • $d_W(M,N)=o(\sqrt{\log \log n})$ implies the Erdos-Kac Central Limit Theorem (which states that $\frac{\omega(n)-\log \log n}{\sqrt{\log \log n}}$ has the standard normal distribution.

Further confirmation of this is stated by Bollobas on page 29 of "Contemporary Combinatorics":

enter image description here

How can these results be derived from the asymptotics?


Obviously, one has $$|\omega(M)-\omega(N)|\leq d(M,N).$$ Taking the expectations, we see that for every $n$, we can construct a coupling of $M(n)$ and $N(n)$ such that $$ \mathbb{E}|\omega(M(n))-\omega(N(n))|\leq d_W(M(n),N(n))+\frac{1}{n}. $$ Under the asymptotic estimates above, Chebyshev's inequality implies, for any $\alpha>0$ $$ \mathbb{P}(|\omega(M(n)-\omega(N(n)))|>\alpha \log \log n)=o(1), $$ or, respectively, $$ \mathbb{P}(|\omega(M(n)-\omega(N(n)))|>\alpha \sqrt{\log \log n})=o(1). $$ Hence, Hardy-Ramanujan and Erdos-Kac boil down to the corresponding statements about $\omega(M(n))$. These are just the LLN and the CLT for the independent random variables $$\mathbf{1}_{Z_2\neq 0},\mathbf{1}_{Z_3\neq 0},\mathbf{1}_{Z_5\neq 0}\dots,$$ which are of course well known and standard (e. g., Lindeberg's CLT applies)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.