Hardy-Ramanujan theorem

(on the normal number of prime factors of an integer)

For any integer $n \ge 2$, let $\omega(n)$ denote the number of distinct prime factors of $n$. The Hardy–Ramanujan theorem [a5] states that the function $\omega(n)$ has normal order $\log\log n$ in the sense that, given any $\epsilon > 0$, almost all positive integers $n$ satisfy $$ |\omega(n) - \log\log n| < \epsilon \log\log n \ . $$

Here, "almost all" means that the number of positive integers $n \le x$ for which the indicated property holds is asymptotically equal to $x$ as $x\rightarrow\infty$. A stronger, and best-possible, version of this result shows that, given any real-valued function $\psi(n)$ tending to infinity as $n\rightarrow\infty$, almost all positive integers $n$ satisfy $$ |\omega(n) - \log\log n| < \psi(n) \sqrt{\log\log n} \ . $$

The same estimate holds for the function $\Omega(n)$, the total number of prime factors of $n$, i.e., the number of prime factors of $n$ counted with multiplicity.

The Hardy–Ramanujan theorem led to the development of probabilistic number theory, a branch of number theory in which properties of integers are studied from a probabilistic point of view (see [a1] or [a6] for a general reference and also Number theory, probabilistic methods in). One of the main theorems in this area, and a far-reaching generalization of the Hardy–Ramanujan theorem, is the Erdös–Kac theorem, which states that the functions $f=\omega$ and $f=\Omega$ (and, in fact, a large class of additive arithmetic functions $f$ satisfy $$ \lim_{x\rightarrow\infty}\frac{1}{x} \sharp\left\lbrace{ n \le x : f(n) \le \log\log n + t \sqrt{\log\log n} }\right\rbrace = \frac{1}{2\pi} \int_{-\infty}^t e^{-x^2/2} dx\ \ \ (\,t \in \mathbf{R}\,) \ . $$

This shows that the values of $\omega(n)$ and $\Omega(n)$ are, in a sense, normally distributed with mean $\log\log n$ and standard deviation $\sqrt{\log\log n}$ (cf. also Normal distribution).

Another generalization of the Hardy–Ramanujan theorem, due to P. Erdös ([a2]; see also [a4], Chapt. 1), describes the size of the prime factors of a random integer. For $n\ge2$, let $p_1(n) < p_2(n) < \ldots < p_{\omega(n)}(n)$ denote the sequence of distinct prime factors of $n$. Let $\epsilon>0$ be given, and let $\psi(n)$ be a function tending arbitrarily slowly to infinity as $n \rightarrow\infty$. Then, for almost-all positive integers $n$, the inequalities $$ |\log\log p_j(n) - j| < (1+\epsilon) \sqrt{2j\log\log j} \ , $$ $$ \psi(n) < j \le \omega(n)$ $$ hold. A related result, due to J. Galambos [a3], is that the numbers $p_j(n)$ are, in a suitable sense, normally distributed with mean $j$ and standard deviation $\sqrt j$; see [a3].

References

[a1]	P.D.T.A. Elliott, "Probabilistic number theory" , I–II , Springer (1979-1980)
[a2]	P. Erdös, "On the distribution function of additive functions" Ann. of Math. , 47 (1946) pp. 1–20
[a3]	J. Galambos, "The sequences of prime divisors of integers" Acta Arith. , 31 (1976) pp. 213–218
[a4]	R.R. Hall, G. Tenenbaum, "Divisors" , Tracts in Math. , 90 , Cambridge Univ. Press (1988)
[a5]	G.H. Hardy, S. Ramanujan, "The normal number of prime factors of a number $n$" Quart. J. Math. , 48 (1917) pp. 76–92
[a6]	G. Tenenbaum, "Introduction to analytic and probabilistic number theory" , Cambridge Univ. Press (1995)