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 ω(n) of distinct prime factors of a number n is log(log(n)). Roughly speaking, this means that most numbers have about this number of distinct prime factors.
Precise statement
A more precise version states that for every real-valued function ψ(n) that tends to infinity as n tends to infinity
- [math]\displaystyle{ |\omega(n)-\log\log n|\lt \psi(n)\sqrt{\log\log n} }[/math]
or more traditionally
- [math]\displaystyle{ |\omega(n)-\log\log n|\lt {(\log\log n)}^{\frac12 +\varepsilon} }[/math]
for almost all (all but an infinitesimal proportion of) integers. That is, let g(x) be the number of positive integers n less than x for which the above inequality fails: then g(x)/x converges to zero as x goes to infinity.
History
A simple proof to the result (Turán 1934) was given by Pál Turán, who used the Turán sieve to prove that
- [math]\displaystyle{ \sum_{n \le x} | \omega(n) - \log\log x|^2 \ll x \log\log x \ . }[/math]
Generalizations
The same results are true of Ω(n), the number of prime factors of n counted with multiplicity. This theorem is generalized by the Erdős–Kac theorem, which shows that ω(n) is essentially normally distributed.
References
- Hardy, G. H.; Ramanujan, S. (1917), "The normal number of prime factors of a number n", Quarterly Journal of Mathematics 48: 76–92, http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper35/page1.htm
- Kuo, Wentang; Liu, Yu-Ru (2008), "The Erdős–Kac theorem and its generalizations", in De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian, Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13--17, 2006, CRM Proceedings and Lecture Notes, 46, Providence, RI: American Mathematical Society, pp. 209–216, ISBN 978-0-8218-4406-9
- 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
- Hazewinkel, Michiel, ed. (2001), "Hardy-Ramanujan theorem", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Main_Page
 |  |
