Namespaces
Variants
Actions

Difference between revisions of "Hardy-Ramanujan theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (→‎References: zbl link)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
''(on the normal number of prime factors of an integer)''
 
''(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
+
For any integer $n \ge 2$, let $\omega(n)$ denote the number of distinct prime factors of $n$. The Hardy–Ramanujan theorem [[#References|[a5]]] states that the function $\omega(n)$ has [[Normal order of an arithmetic function|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 \ .
 +
$$
  
<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 $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} \ .
 +
$$
  
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
+
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.
  
<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 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]]). 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 function]]s $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}\,) \ .
 +
$$
  
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.
+
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]]).
  
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
+
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 $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 [[#References|[a3]]], is that the numbers $p_j(n)$ are, in a suitable sense, normally distributed with mean $j$ and standard deviation $\sqrt j$; see [[#References|[a3]]].
  
<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>
+
====References====
 
+
<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>
+
<TR><TD valign="top">[a1]</TD> <TD valign="top">  P.D.T.A. Elliott,  "Probabilistic number theory" , '''I–II''' , Springer  (1979-1980) {{ZBL|0431.10029}}{{ZBL|0431.10030}}</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 {{ZBL|0061.07902}}</TD></TR>
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]]).
+
<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 {{ZBL|0303.10039}}</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){{ZBL|0653.10001}}</TD></TR>
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
+
<TR><TD valign="top">[a5]</TD> <TD valign="top"> 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}}</TD></TR>
 
+
<TR><TD valign="top">[a6]</TD> <TD valign="top"> G. Tenenbaum,  "Introduction to analytic and probabilistic number theory" , Graduate Studies in Mathematics 163, Amer. Math. Soc. 2015. {{ZBL|1336.11001}}</TD></TR>
<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>
 
 
<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====
+
{{TEX|done}}
<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>
 

Latest revision as of 07:30, 18 March 2023

(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=22553
This article was adapted from an original article by A. Hildebrand (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article