View source for Hardy-Ramanujan theorem

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

For any integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h1100801.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h1100802.png" /> denote the number of distinct prime factors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h1100803.png" />. The Hardy–Ramanujan theorem [[#References|[a5]]] states that the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h1100804.png" /> has normal order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h1100805.png" /> in the sense that, given any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h1100806.png" />, almost all positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h1100807.png" /> satisfy

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h1100808.png" /></td> </tr></table>

Here,  "almost all"  means that the number of positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h1100809.png" /> for which the indicated property holds is asymptotically equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008010.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008011.png" />. A stronger, and best-possible, version of this result shows that, given any real-valued function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008012.png" /> tending to infinity as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008013.png" />, almost all positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008014.png" /> satisfy

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008015.png" /></td> </tr></table>

The same estimate holds for the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008016.png" />, the total number of prime factors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008017.png" />, i.e., the number of prime factors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008018.png" /> 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 [[#References|[a1]]] or [[#References|[a6]]] for a general reference and also [[Number theory, probabilistic methods in|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008020.png" /> (and, in fact, a large class of additive functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008021.png" />; cf. [[Additive arithmetic function|Additive arithmetic function]]) satisfy

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008022.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008023.png" /></td> </tr></table>

This shows that the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008025.png" /> are, in a sense, normally distributed with mean <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008026.png" /> and standard deviation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008027.png" /> (cf. also [[Normal distribution|Normal distribution]]).

Another generalization of the Hardy–Ramanujan theorem, due to P. Erdös ([[#References|[a2]]]; see also [[#References|[a4]]], Chapt. 1), describes the size of the prime factors of a random integer. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008028.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008029.png" /> denote the sequence of distinct prime factors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008030.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008031.png" /> be given, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008032.png" /> be a function tending arbitrarily slowly to infinity as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008033.png" />. Then, for almost-all positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008034.png" />, the inequalities

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008035.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008036.png" /></td> </tr></table>

hold. A related result, due to J. Galambos [[#References|[a3]]], is that the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008037.png" /> are, in a suitable sense, normally distributed with mean <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008038.png" /> and standard deviation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008039.png" />; see [[#References|[a3]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P.D.T.A. Elliott,   "Probabilistic number theory" , '''I–II''' , Springer  (1979-1980)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdös,   "On the distribution function of additive functions"  ''Ann. of Math.'' , '''47'''  (1946)  pp. 1–20</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Galambos,   "The sequences of prime divisors of integers"  ''Acta Arith.'' , '''31'''  (1976)  pp. 213–218</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.R. Hall,   G. Tenenbaum,   "Divisors" , ''Tracts in Math.'' , '''90''' , Cambridge Univ. Press  (1988)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  G.H. Hardy,   S. Ramanujan,   "The normal number of prime factors of a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110080/h11008040.png" />"  ''Quart. J. Math.'' , '''48'''  (1917)  pp. 76–92</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  G. Tenenbaum,   "Introduction to analytic and probabilistic number theory" , Cambridge Univ. Press  (1995)</TD></TR></table>