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.

Precise statement

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.

History

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.}$$

Generalizations

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]

See also

• Almost prime
• Turán–Kubilius inequality

References

1. Hardy, G. H.; Ramanujan, S. (1917), "The normal number of prime factors of a number n", Quarterly Journal of Mathematics, 48: 76–92, JFM 46.0262.03
2. Heath-Brown, D. R. (2007), "Carmichael numbers with three prime factors", Hardy–Ramanujan Journal, 30: 6–12, doi:10.46298/hrj.2007.156, MR 2440316
3. Turán, Pál (1934), "On a theorem of Hardy and Ramanujan", Journal of the London Mathematical Society, 9 (4): 274–276, doi:10.1112/jlms/s1-9.4.274, ISSN 0024-6107, Zbl 0010.10401
4. Granville, Andrew; Soundararajan, K. (2007), "Sieving and the Erdős-Kac theorem", in Granville, Andrew; Rudnick, Zeév (eds.), Equidistribution in number theory, an introduction: Proceedings of the NATO Advanced Study Institute (the 44th Séminaire de Mathématiques Supérieures (SMS)) held at the Université de Montréal, Montréal, QC, July 11–22, 2005, NATO Science Series II: Mathematics, Physics and Chemistry, vol. 237, Dordrecht: Springer, pp. 15–27, arXiv:math/0606039, doi:10.1007/978-1-4020-5404-4_2, ISBN 978-1-4020-5403-7, MR 2290492
5. Harper, Adam J. (2009), "Two new proofs of the Erdős-Kac theorem, with bound on the rate of convergence, by Stein's method for distributional approximations", Mathematical Proceedings of the Cambridge Philosophical Society, 147 (1): 95–114, doi:10.1017/S0305004109002412, MR 2507311
6. Durkan, Benjamin (2023-10-23), "On the Hardy–Ramanujan Theorem", arXiv:2310.14760 [math.NT]

Further reading

• 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