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

| ω ( n ) − log ⁡ log ⁡ n | < ψ ( n ) log ⁡ log ⁡ n {\displaystyle |\omega (n)-\log \log n|<\psi (n){\sqrt {\log \log n}}}

or more traditionally

| ω ( n ) − log ⁡ log ⁡ n | < ( log ⁡ log ⁡ n ) 1 2 + ε {\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 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

∑ n ≤ x | ω ( n ) − log ⁡ log ⁡ x | 2 ≪ x log ⁡ log ⁡ x   . {\displaystyle \sum _{n\leq x}|\omega (n)-\log \log x|^{2}\ll x\log \log x\ .}

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

  1. ^ G. H. Hardy and Srinivasa Ramanujan (1917)
  • 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