Hardy–Ramanujan theorem

In mathematics, the Hardy–Ramanujan theorem, proved by Ramanujan and checked by Hardy^[1] states that the normal order of the number ${\displaystyle \omega (n)}$ of distinct prime factors of a number ${\displaystyle n}$ is ${\displaystyle \log \log n}$.

Roughly speaking, this means that most numbers have about this number of distinct prime factors.

A more precise version^[2] states that for every real-valued function ${\displaystyle \psi (n)}$ that tends to infinity as ${\displaystyle n}$ tends to infinity $${\displaystyle |\omega (n)-\log \log n|<\psi (n){\sqrt {\log \log n}}}$$ or more traditionally $${\displaystyle |\omega (n)-\log \log n|<{(\log \log n)}^{{\frac {1}{2}}+\varepsilon }}$$ for almost all (all but an infinitesimal proportion of) integers. That is, let ${\displaystyle g(x)}$ be the number of positive integers ${\displaystyle n}$ less than ${\displaystyle x}$ for which the above inequality fails: then ${\displaystyle g(x)/x}$ converges to zero as ${\displaystyle x}$ goes to infinity.

A simple proof to the result was given by Pál Turán, who used the Turán sieve to prove that^[3]

$${\displaystyle \sum _{n\leq x}|\omega (n)-\log \log x|^{2}\ll x\log \log x.}$$

The same results are true of ${\displaystyle \Omega (n)}$, the number of prime factors of ${\displaystyle n}$ counted with multiplicity. This theorem is generalized by the Erdős–Kac theorem, which shows that ${\displaystyle \omega (n)}$ is essentially normally distributed. There are many proofs of this, including the method of moments (Granville & Soundararajan)^[4] and Stein's method (Harper).^[5] It was shown by Durkan that a modified version of Turán's result allows one to prove the Hardy–Ramanujan Theorem with any even moment.^[6]

• Almost prime
• Turán–Kubilius inequality

• Kuo, Wentang; Liu, Yu-Ru (2008), "The Erdős–Kac theorem and its generalizations", in De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian (eds.), Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13--17, 2006, CRM Proceedings and Lecture Notes, vol. 46, Providence, RI: American Mathematical Society, pp. 209–216, ISBN 978-0-8218-4406-9, Zbl 1187.11024
• Hildebrand, A. (2001) [1994], "Hardy-Ramanujan theorem", Encyclopedia of Mathematics, EMS Press