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[edit]

A more precise version (as in ^[2]) states that for every real-valued function ψ(n) that tends to infinity as n tends to infinity

|\omega (n)-\log \log n|<\psi (n){\sqrt {\log \log n}}

or more traditionally

|\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 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[edit]

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

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

Generalizations[edit]

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. There are many proofs of this, including the method of moments^[3] (Granville & Soundararajan) and Stein's method ^[4](Harper). It was shown by Durkan^[5] that a modified version of Turán's result allows one to prove the Hardy-Ramanujan Theorem with any even moment.

References[edit]

^ G. H. Hardy and Srinivasa Ramanujan (1917)
^ Heath-Brown, D R (2007-01-01). "Carmichael number with three prime factors". Hardy-Ramanujan Journal. Volume 30 - 2007. doi:10.46298/hrj.2007.156. ISSN 2804-7370. {{cite journal}}: |volume= has extra text (help)
^ Granville, Andrew; Soundararajan, K. (2006-06-01), Sieving and the Erd{\H o}s-Kac theorem, doi:10.48550/arXiv.math/0606039, retrieved 2024-07-14
^ Harper, Adam J. (July 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. ISSN 0305-0041.
^ Durkan, Benjamin (2023-10-23), On the Hardy-Ramanujan Theorem, doi:10.48550/arXiv.2310.14760, retrieved 2024-07-14

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
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
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
Hildebrand, A. (2001) [1994], "Hardy-Ramanujan theorem", Encyclopedia of Mathematics, EMS Press

[1] G. H. Hardy and Srinivasa Ramanujan (1917)

[2] Heath-Brown, D R (2007-01-01). "Carmichael number with three prime factors". Hardy-Ramanujan Journal. Volume 30 - 2007. doi:10.46298/hrj.2007.156. ISSN 2804-7370. {{cite journal}}: |volume= has extra text (help)

[3] Granville, Andrew; Soundararajan, K. (2006-06-01), Sieving and the Erd{\H o}s-Kac theorem, doi:10.48550/arXiv.math/0606039, retrieved 2024-07-14

[4] Harper, Adam J. (July 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. ISSN 0305-0041.

[5] Durkan, Benjamin (2023-10-23), On the Hardy-Ramanujan Theorem, doi:10.48550/arXiv.2310.14760, retrieved 2024-07-14

[1]

[2]

[3]

[4]

[5]