Hardy–Ramanujan theorem

In mathematics, the Hardy–Ramanujan theorem, proved by Ramanujan and checked by Hardy 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 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}+\epsilon }$$ 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

$$\sum _{n\le 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) and Stein's method (Harper). 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.

See also

• Almost prime
• Turán–Kubilius inequality