Jump to content

Hardy–Ramanujan theorem

From Wikipedia, the free encyclopedia
(Redirected from 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 of distinct prime factors of a number is .

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

Precise statement

[edit]

A more precise version[2] states that for every real-valued function that tends to infinity as tends to infinity or more traditionally for almost all (all but an infinitesimal proportion of) integers. That is, let be the number of positive integers less than for which the above inequality fails: then converges to zero as goes to infinity.

History

[edit]

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

Generalizations

[edit]

The same results are true of , the number of prime factors of counted with multiplicity. This theorem is generalized by the Erdős–Kac theorem, which shows that 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

[edit]

References

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

[edit]