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 $\omega (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^[2] states that for every real-valued function $\psi (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

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

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

Generalizations

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

References

^ 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
^ 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
^ 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
^ 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
^ 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
^ Durkan, Benjamin (2023-10-23), "On the Hardy–Ramanujan Theorem", arXiv:2310.14760 [math.NT]

Hardy–Ramanujan theorem

Precise statement

History

Generalizations

See also

References

Further reading