Namespaces
Variants
Actions

Hardy-Ramanujan theorem

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

(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) Zbl 0431.10029Zbl 0431.10030
[a2] P. Erdös, "On the distribution function of additive functions" Ann. of Math. , 47 (1946) pp. 1–20 Zbl 0061.07902
[a3] J. Galambos, "The sequences of prime divisors of integers" Acta Arith. , 31 (1976) pp. 213–218 Zbl 0303.10039
[a4] R.R. Hall, G. Tenenbaum, "Divisors" , Tracts in Math. , 90 , Cambridge Univ. Press (1988)Zbl 0653.10001
[a5] G.H. Hardy, S. Ramanujan, "The normal number of prime factors of a number $n$" Quart. J. Math. , 48 (1917) pp. 76–92 Zbl 46.0262.03
[a6] G. Tenenbaum, "Introduction to analytic and probabilistic number theory" , Graduate Studies in Mathematics 163, Amer. Math. Soc. 2015. Zbl 1336.11001
How to Cite This Entry:
Hardy-Ramanujan theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hardy-Ramanujan_theorem&oldid=52861
This article was adapted from an original article by A. Hildebrand (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article