Namespaces
Variants
Actions

Difference between revisions of "Number theory, probabilistic methods in"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Texed)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
In the broad sense, that part of [[Number theory|number theory]] in which ideas and methods from [[Probability theory|probability theory]] are used.
+
In the broad sense, that part of
 +
[[Number theory|number theory]] in which ideas and methods from
 +
[[Probability theory|probability theory]] are used.
  
By probabilistic number theory in the narrow sense one means the statistical theory of the distribution of values of an [[Arithmetic function|arithmetic function]].
+
By probabilistic number theory in the narrow sense one means the statistical theory of the distribution of values of an
 +
[[Arithmetic function|arithmetic function]].
  
The great majority of arithmetic functions studied in number theory are either additive or multiplicative (cf. [[Additive arithmetic function|Additive arithmetic function]]; [[Multiplicative arithmetic function|Multiplicative arithmetic function]]). Their values are usually distributed in a very complicated way. If one traces the change of values of such functions as the argument runs through the sequence of natural numbers, one obtains a highly chaotic graph such as is usually observed when the additive and multiplicative properties of numbers are considered simultaneously. In classical investigations concerning the distribution of the values of a real arithmetic function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n0679501.png" />, one usually studied the asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n0679502.png" /> itself, or of its average values. In the first case one has to find two simple functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n0679503.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n0679504.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n0679505.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n0679506.png" />, or at least for all sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n0679507.png" />. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n0679508.png" /> denotes the number of distinct prime divisors of a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n0679509.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795010.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795011.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795012.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795013.png" />;
+
The great majority of arithmetic functions studied in number theory are either additive or multiplicative (cf.
 +
[[Additive arithmetic function|Additive arithmetic function]];
 +
[[Multiplicative arithmetic function|Multiplicative arithmetic function]]). Their values are usually distributed in a very complicated way. If one traces the change of values of such functions as the argument runs through the sequence of natural numbers, one obtains a highly chaotic graph such as is usually observed when the additive and multiplicative properties of numbers are considered simultaneously. In classical investigations concerning the distribution of the values of a real arithmetic function $f(m)$, one usually studied the asymptotic behaviour of $f(m)$ itself, or of its average values. In the first case one has to find two simple functions $\psi_1(m)$, $\psi_2(m)$ such that $\psi_1(m) \le f(m) \le \psi_2(m)$ for all $m$, or at least for all sufficiently large $m$. For example, if $\omega(m)$ denotes the number of distinct prime divisors of a number $m$, then $\omega(m) \ge 1$ for all $m > 1$, and $\omega(m) \le 2(\ln \ln m)^{-1} \ln m$ for $m \ge m_0$;
  
<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/n/n067/n067950/n06795014.png" /></td> </tr></table>
+
$$\liminf_{m\to\infty} \omega(m) = 1, $$
 
 
<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/n/n067/n067950/n06795015.png" /></td> </tr></table>
 
  
 +
$$\limsup_{m\to\infty} \omega(m) (\ln m)^{-1} \ln \ln m = 1.$$
 
In the second case one considers the behaviour of
 
In the second case one considers the behaviour of
  
<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/n/n067/n067950/n06795016.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$\frac{1}{n} \sum_{m=1}^n f(m). \tag{1}$$
 
+
For $\omega(m)$ the average value (1) is equal to $(1+o(1) \ln \ln n)$. A solution to the first and to the second problem in the general case gives little information about the function $f(m)$, or about its oscillations. A function may deviate significantly from its average value. Here it turns out that large deviations occur rather seldom. The problem arises of finding bounds within which the values of the function $f(m)$ fluctuate for an overwhelming majority of values of the argument. If $f(m)$ is a real additive arithmetic function, and if
For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795017.png" /> the average value (1) is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795018.png" />. A solution to the first and to the second problem in the general case gives little information about the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795019.png" />, or about its oscillations. A function may deviate significantly from its average value. Here it turns out that large deviations occur rather seldom. The problem arises of finding bounds within which the values of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795020.png" /> fluctuate for an overwhelming majority of values of the argument. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795021.png" /> is a real additive arithmetic function, and if
 
 
 
<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/n/n067/n067950/n06795022.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
 
 
 
where the sums are taken over all prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795023.png" /> and all powers of primes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795024.png" />, respectively, then
 
 
 
<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/n/n067/n067950/n06795025.png" /></td> </tr></table>
 
 
 
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795026.png" /> is an absolute constant. Thus, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795027.png" /> and for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795028.png" /> with the exception of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795029.png" /> numbers, the inequality
 
 
 
<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/n/n067/n067950/n06795030.png" /></td> </tr></table>
 
  
holds (an analogue of the [[Law of large numbers|law of large numbers]] in probability theory). For the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795031.png" /> this inequality can be written in the form
+
$$A_n = \sum_{p \le n} \frac{f(p)}{p}, \qquad B_n^2 = \sum_{p^\alpha \le n} \frac{f^2(p^\alpha)}{p^\alpha}, \tag{2}$$
 +
where the sums are taken over all prime numbers $p \le n$ and all powers of primes $p^\alpha \le n$, respectively, then
  
<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/n/n067/n067950/n06795032.png" /></td> </tr></table>
+
$$\frac{1}{n} \sum_{m=1}^n (f(m) - A_n)^2 \le B_n^2 \left( \frac32 + \frac{c}{\ln n}\right),$$
 +
where $c$ is an absolute constant. Thus, for any $t > 0$ and for all $m \le n$ with the exception of $< (3/2 + c/\ln n)nt^{-2}$ numbers, the inequality
  
Denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795033.png" /> the number of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795034.png" /> that satisfy a condition to be described in between the brackets in place of the dots. If one wants to characterize more exactly the distribution of the values of a real arithmetic function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795035.png" />, then one is forced to consider the asymptotic behaviour of the frequencies
+
$$|f(m) - A_n| < t B_n$$
 +
holds (an analogue of the
 +
[[Law of large numbers|law of large numbers]] in probability theory). For the function $\omega(m)$ this inequality can be written in the form
  
<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/n/n067/n067950/n06795036.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$|\omega(m) - \ln \ln n| < t \sqrt{\ln \ln n}.$$
 +
Denote by $N_n(\cdots)$ the number of natural numbers $m \le n$ that satisfy a condition to be described in between the brackets in place of the dots. If one wants to characterize more exactly the distribution of the values of a real arithmetic function $f(m)$, then one is forced to consider the asymptotic behaviour of the frequencies
  
as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795037.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795038.png" /> is an arbitrary Borel set. Among the asymptotic laws for (3), the most interesting ones are of local or integral form.
+
$$\frac 1n N_n(f(m) \in E) \tag{3}$$
 +
as $n \to \infty$, where $E$ is an arbitrary Borel set. Among the asymptotic laws for (3), the most interesting ones are of local or integral form.
  
 
==Integral laws.==
 
==Integral laws.==
 
One studies the asymptotic behaviour of the distribution function
 
One studies the asymptotic behaviour of the distribution function
  
<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/n/n067/n067950/n06795039.png" /></td> </tr></table>
+
$$F_n(C_n + D_n x) = \frac 1n N_n(f(m) < C_n + D_n x),$$
 +
as $n \to \infty$, for given $C_n, D_n$.
  
as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795040.png" />, for given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795041.png" />.
+
In the case of an additive arithmetic function one searches for conditions under which $F_n(C_n + D_n x)$ converges to some distribution function $F(x)$ at all its points of continuity. Here, if $F(x)$ is not degenerate and $D_n$ must converge to a finite (distinct from $0$) or infinite limit.
  
In the case of an additive arithmetic function one searches for conditions under which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795042.png" /> converges to some distribution function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795043.png" /> at all its points of continuity. Here, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795044.png" /> is not degenerate and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795045.png" /> must converge to a finite (distinct from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795046.png" />) or infinite limit.
+
In the case of a finite limit, it is sufficient to consider only $F_n(C_n + x)$. The function $F_n(C_n + x)$ has a non-degenerate limit distribution as $n \to \infty$, for some $C_n$, if and only if $f(m)$ has the form
  
In the case of a finite limit, it is sufficient to consider only <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795047.png" />. The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795048.png" /> has a non-degenerate limit distribution as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795049.png" />, for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795050.png" />, if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795051.png" /> has the form
+
$$f(m) = a \ln m + g(m),$$
 +
where $a$ is a constant and the function $g(m)$ satisfies the conditions
  
<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/n/n067/n067950/n06795052.png" /></td> </tr></table>
+
$$\sum_{|g(p)| \ge 1} \frac 1p < \infty, \qquad \sum_{|g(p)|<1} \frac{g^2(p)}{p} < \infty.$$
 +
Here $C_n$ must be equal to
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795053.png" /> is a constant and the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795054.png" /> satisfies the conditions
+
$$C_n = a \ln n + \sum_{\substack{p \le n \\ |g(p)| < 1}} \frac{g(p)}{p} + C + o(1),$$
 +
where $C$ is a constant. The choice of $C_n$ is unique up to an additive term $C + o(1)$. The limit distribution is discrete when $\sum_{f(p) \ne 0} 1/p < \infty$, and continuous otherwise.
  
<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/n/n067/n067950/n06795055.png" /></td> </tr></table>
+
In particular, $F_n(x)$ (the case $C_n \equiv 0$) has a limit distribution if and only if the series
 
 
Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795056.png" /> must be equal to
 
 
 
<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/n/n067/n067950/n06795057.png" /></td> </tr></table>
 
 
 
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795058.png" /> is a constant. The choice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795059.png" /> is unique up to an additive term <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795060.png" />. The limit distribution is discrete when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795061.png" />, and continuous otherwise.
 
 
 
In particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795062.png" /> (the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795063.png" />) has a limit distribution if and only if the series
 
 
 
<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/n/n067/n067950/n06795064.png" /></td> </tr></table>
 
  
 +
$$\sum_{|f(p)| \ge 1} \frac 1p, \qquad \sum_{|f(p)| < 1} \frac{f(p)}{p}, \qquad \sum_{|f(p)| < 1} \frac{f^2(p)}{p}$$
 
converge (an analogue of the three-series theorem in probability theory).
 
converge (an analogue of the three-series theorem in probability theory).
  
The case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795065.png" /> has not been completely investigated. Some of the simpler results are presented below, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795067.png" /> are defined by formula (2).
+
The case $D_n \to \infty$ has not been completely investigated. Some of the simpler results are presented below, when $C_n = A_n$ and $D_n = B_n$ are defined by formula (2).
  
If, for any fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795068.png" />,
+
If, for any fixed $\epsilon > 0$,
  
<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/n/n067/n067950/n06795069.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$B_n^{-2} \sum_{\substack{p^\alpha = n \\ |f(p^\alpha)| > \epsilon B_n}} \frac{f^2(p^\alpha)}{p^\alpha} \to 0, \tag{4}$$
 +
as $n \to \infty$ (an analogue of the Lindeberg condition, cf.
 +
[[Lindeberg–Feller theorem|Lindeberg–Feller theorem]]), then
  
as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795070.png" /> (an analogue of the Lindeberg condition, cf. [[Lindeberg–Feller theorem|Lindeberg–Feller theorem]]), then
+
$$F_n(A_n + B_n x) \to \frac{1}{\sqrt{2\pi}} \int_{-\infty}^x e^{-u^2/2} du = \Phi(x) \tag{5}$$
 +
(the normal law). If (4) is satisfied, then $B_n$ is a slowly-varying function of $\ln n$ in the sense of Karamata. Moreover, if $B_n$ is such a function, then (4) is a necessary condition for (5).
  
<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/n/n067/n067950/n06795071.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
Let $B_n$ be a slowly-varying function in $\ln n$. Then $F_n(A_n + B_n x)$ converges to a limit distribution with variance 1 if and only if there exists a non-decreasing function $V(u)$, $-\infty < u < \infty$, such that $V(-\infty) = 0$, $V(\infty) = 1$, and such that as $n \to \infty$, for all $u$ with the possible exception of $u = 0$,
  
(the normal law). If (4) is satisfied, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795072.png" /> is a slowly-varying function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795073.png" /> in the sense of Karamata. Moreover, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795074.png" /> is such a function, then (4) is a necessary condition for (5).
+
$$B_n^{-2} \sum_{\substack{p^\alpha \le n \\ f(p^\alpha) < u B_n}} \frac{f^2(p^\alpha)}{p^\alpha} \to V(u) .$$
 +
The characteristic function $\phi(t)$ of the limit law, if it exists at all, is given by the formula
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795075.png" /> be a slowly-varying function in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795076.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795077.png" /> converges to a limit distribution with variance 1 if and only if there exists a non-decreasing function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795078.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795079.png" />, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795080.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795081.png" />, and such that as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795082.png" />, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795083.png" /> with the possible exception of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795084.png" />,
+
$$\phi(t) = \exp \left( \int_{-\infty}^\infty (e^{itu} - 1 - itu) u^{-2} dV(u) \right).$$
 +
One has studied the rate of convergence to the limit law. For example, if $f(m)$ is a strongly-additive function and if
  
<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/n/n067/n067950/n06795085.png" /></td> </tr></table>
+
$$\mu_n = B_n^{-1} \max_{p\le n} |f(p)| \to 0$$
 +
as $n \to \infty$, then
  
The characteristic function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795086.png" /> of the limit law, if it exists at all, is given by the formula
+
$$F_n(A_n + B_n x) = \Phi(x) + O(\mu_n),$$
 
+
uniformly in $x$.
<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/n/n067/n067950/n06795087.png" /></td> </tr></table>
 
 
 
One has studied the rate of convergence to the limit law. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795088.png" /> is a strongly-additive function and if
 
 
 
<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/n/n067/n067950/n06795089.png" /></td> </tr></table>
 
 
 
as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795090.png" />, then
 
 
 
<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/n/n067/n067950/n06795091.png" /></td> </tr></table>
 
 
 
uniformly in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795092.png" />.
 
  
 
There are similar results for multiplicative arithmetic functions.
 
There are similar results for multiplicative arithmetic functions.
  
 
==Local laws.==
 
==Local laws.==
Here one studies the behaviour of the frequency <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795093.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795094.png" /> for a fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795095.png" />. In the case of a real additive arithmetic function, this frequency always has a limit, which is distinct from zero only for a countable set of values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n06795096.png" />. Let
+
Here one studies the behaviour of the frequency $N_n(f(m) = c)/n$ as $n \to \infty$ for a fixed $c$. In the case of a real additive arithmetic function, this frequency always has a limit, which is distinct from zero only for a countable set of values of $c$. Let
 
 
<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/n/n067/n067950/n06795097.png" /></td> </tr></table>
 
  
 +
$$\lambda_l(f) = \lim_{n\to\infty} \frac 1n N_n(f(m) = c_l), \quad l=1, 2, \ldots,$$
 
be the collection of non-zero limits, assuming that at least one such limit exists. Then
 
be the collection of non-zero limits, assuming that at least one such limit exists. Then
  
<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/n/n067/n067950/n06795098.png" /></td> </tr></table>
+
$$\sum_l \lambda_l(f) = 1$$
 
 
 
and
 
and
  
<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/n/n067/n067950/n06795099.png" /></td> </tr></table>
+
$$\sum_l \lambda_l(f) e^{itc_l} = \prod_p \left( 1 - \frac 1p \right) \sum_{\alpha = 0}^\infty p^{-\alpha} e^{itf(p^\alpha)}.$$
 
+
If $f(m)$ takes only integer values and if
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950100.png" /> takes only integer values and if
 
 
 
<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/n/n067/n067950/n067950101.png" /></td> </tr></table>
 
  
 +
$$\mu_k(f) = \lim_{n\to\infty} \frac 1n N_n(f(m) = k),$$
 
then
 
then
  
<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/n/n067/n067950/n067950102.png" /></td> </tr></table>
+
$$\sum_k \mu_k(f) = 1$$
 
 
 
if and only if
 
if and only if
  
<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/n/n067/n067950/n067950103.png" /></td> </tr></table>
+
$$\sum_{f(p)\ne 0} \frac 1p < \infty.$$
 
+
One has studied the rate of convergence to $\mu_k(f)$. There exists an absolute constant $C$ such that for all integers $k$ and all integer-valued additive arithmetic functions $f(m)$ such that $f(p) = 0$ for all primes $p$,
One has studied the rate of convergence to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950104.png" />. There exists an absolute constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950105.png" /> such that for all integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950106.png" /> and all integer-valued additive arithmetic functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950107.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950108.png" /> for all primes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950109.png" />,
 
 
 
<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/n/n067/n067950/n067950110.png" /></td> </tr></table>
 
  
One has also studied the asymptotic behaviour of the frequency <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950111.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950112.png" /> increases with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950113.png" />.
+
$$\left| \frac 1n N_n(f(m) = k) - \mu_k(f) \right| \le C_n^{-1/2}.$$
 +
One has also studied the asymptotic behaviour of the frequency $N_n(f(m) = k_n)/n$ when $k_n$ increases with $n$.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M. Kac,  "Statistical independence in probability, analysis and number theory" , Math. Assoc. Amer.  (1963)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  I.P. [I.P. Kubilyus] Kubilius,  "Probabilistic methods in the theory of numbers" , Amer. Math. Soc.  (1978)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.P. Kubilyus,  "Current problems of analytic number theory" , Minsk  (1974)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  Yu.V. Linnik,  "The dispersion method in binary additive problems" , Amer. Math. Soc.  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  Yu.V. Linnik,  "Ergodic properties of algebraic fields" , Springer  (1968)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  A.G. Postnikov,  "Ergodic problems in the theory of congruences and of Diophantine approximations" , Amer. Math. Soc.  (1967)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  P.D.T.A. Elliot,  "Probabilistic number theory" , '''1–2''' , Springer  (1979–1980)</TD></TR></table>
+
<table><TR><TD valign="top">[1]</TD>
 +
<TD valign="top">  M. Kac,  "Statistical independence in probability, analysis and number theory" , Math. Assoc. Amer.  (1963)</TD>
 +
</TR><TR><TD valign="top">[2]</TD>
 +
<TD valign="top">  I.P. [I.P. Kubilyus] Kubilius,  "Probabilistic methods in the theory of numbers" , Amer. Math. Soc.  (1978)  (Translated from Russian)</TD>
 +
</TR><TR><TD valign="top">[3]</TD>
 +
<TD valign="top">  I.P. Kubilyus,  "Current problems of analytic number theory" , Minsk  (1974)  (In Russian)</TD>
 +
</TR><TR><TD valign="top">[4]</TD>
 +
<TD valign="top">  Yu.V. Linnik,  "The dispersion method in binary additive problems" , Amer. Math. Soc.  (1963)  (Translated from Russian)</TD>
 +
</TR><TR><TD valign="top">[5]</TD>
 +
<TD valign="top">  Yu.V. Linnik,  "Ergodic properties of algebraic fields" , Springer  (1968)  (Translated from Russian)</TD>
 +
</TR><TR><TD valign="top">[6]</TD>
 +
<TD valign="top">  A.G. Postnikov,  "Ergodic problems in the theory of congruences and of Diophantine approximations" , Amer. Math. Soc.  (1967)  (Translated from Russian)</TD>
 +
</TR><TR><TD valign="top">[7]</TD>
 +
<TD valign="top">  P.D.T.A. Elliot,  "Probabilistic number theory" , '''1–2''' , Springer  (1979–1980)</TD>
 +
</TR></table>
  
  
  
 
====Comments====
 
====Comments====
The Erdös–Kac theorem gives some more precise information on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950114.png" />. Denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950115.png" /> the number of integers in the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950116.png" /> for which the inequalities
+
The Erdös–Kac theorem gives some more precise information on $\omega(n)$. Denote by $N(x;a,b)$ the number of integers in the interval $[3,x]$ for which the inequalities
 +
$$
 +
a \le \frac{ \omega(n) - \log\log n }{ \sqrt{\log\log n} } \le b
 +
$$
 +
hold. Then, as $x \rightarrow \infty$,
 +
$$
 +
N(x;a,b) = (x+o(x)) \frac{1}{\sqrt{2\pi}} \int_a^b e^{-t^2/2} dt \ .
 +
$$
  
<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/n/n067/n067950/n067950117.png" /></td> </tr></table>
+
See
 +
[[#References|[a1]]].
  
hold. Then, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067950/n067950118.png" />,
+
====References====
 +
<table> <TR><TD valign="top">[a1]</TD>
 +
<TD valign="top">  W. Narkiewicz,  "Number theory" , World Sci.  (1983)  pp. 251–259  (Translated from Polish)  {{ZBL|0528.10001}}</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/n/n067/n067950/n067950119.png" /></td> </tr></table>
+
{{TEX|done}}
 
 
See [[#References|[a1]]].
 
 
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W. Najkiewicz,  "Number theory" , World Sci.  (1983)  pp. 251–259  (Translated from Polish)</TD></TR></table>
 

Latest revision as of 04:55, 8 August 2018

In the broad sense, that part of number theory in which ideas and methods from probability theory are used.

By probabilistic number theory in the narrow sense one means the statistical theory of the distribution of values of an arithmetic function.

The great majority of arithmetic functions studied in number theory are either additive or multiplicative (cf. Additive arithmetic function; Multiplicative arithmetic function). Their values are usually distributed in a very complicated way. If one traces the change of values of such functions as the argument runs through the sequence of natural numbers, one obtains a highly chaotic graph such as is usually observed when the additive and multiplicative properties of numbers are considered simultaneously. In classical investigations concerning the distribution of the values of a real arithmetic function $f(m)$, one usually studied the asymptotic behaviour of $f(m)$ itself, or of its average values. In the first case one has to find two simple functions $\psi_1(m)$, $\psi_2(m)$ such that $\psi_1(m) \le f(m) \le \psi_2(m)$ for all $m$, or at least for all sufficiently large $m$. For example, if $\omega(m)$ denotes the number of distinct prime divisors of a number $m$, then $\omega(m) \ge 1$ for all $m > 1$, and $\omega(m) \le 2(\ln \ln m)^{-1} \ln m$ for $m \ge m_0$;

$$\liminf_{m\to\infty} \omega(m) = 1, $$

$$\limsup_{m\to\infty} \omega(m) (\ln m)^{-1} \ln \ln m = 1.$$ In the second case one considers the behaviour of

$$\frac{1}{n} \sum_{m=1}^n f(m). \tag{1}$$ For $\omega(m)$ the average value (1) is equal to $(1+o(1) \ln \ln n)$. A solution to the first and to the second problem in the general case gives little information about the function $f(m)$, or about its oscillations. A function may deviate significantly from its average value. Here it turns out that large deviations occur rather seldom. The problem arises of finding bounds within which the values of the function $f(m)$ fluctuate for an overwhelming majority of values of the argument. If $f(m)$ is a real additive arithmetic function, and if

$$A_n = \sum_{p \le n} \frac{f(p)}{p}, \qquad B_n^2 = \sum_{p^\alpha \le n} \frac{f^2(p^\alpha)}{p^\alpha}, \tag{2}$$ where the sums are taken over all prime numbers $p \le n$ and all powers of primes $p^\alpha \le n$, respectively, then

$$\frac{1}{n} \sum_{m=1}^n (f(m) - A_n)^2 \le B_n^2 \left( \frac32 + \frac{c}{\ln n}\right),$$ where $c$ is an absolute constant. Thus, for any $t > 0$ and for all $m \le n$ with the exception of $< (3/2 + c/\ln n)nt^{-2}$ numbers, the inequality

$$|f(m) - A_n| < t B_n$$ holds (an analogue of the law of large numbers in probability theory). For the function $\omega(m)$ this inequality can be written in the form

$$|\omega(m) - \ln \ln n| < t \sqrt{\ln \ln n}.$$ Denote by $N_n(\cdots)$ the number of natural numbers $m \le n$ that satisfy a condition to be described in between the brackets in place of the dots. If one wants to characterize more exactly the distribution of the values of a real arithmetic function $f(m)$, then one is forced to consider the asymptotic behaviour of the frequencies

$$\frac 1n N_n(f(m) \in E) \tag{3}$$ as $n \to \infty$, where $E$ is an arbitrary Borel set. Among the asymptotic laws for (3), the most interesting ones are of local or integral form.

Integral laws.

One studies the asymptotic behaviour of the distribution function

$$F_n(C_n + D_n x) = \frac 1n N_n(f(m) < C_n + D_n x),$$ as $n \to \infty$, for given $C_n, D_n$.

In the case of an additive arithmetic function one searches for conditions under which $F_n(C_n + D_n x)$ converges to some distribution function $F(x)$ at all its points of continuity. Here, if $F(x)$ is not degenerate and $D_n$ must converge to a finite (distinct from $0$) or infinite limit.

In the case of a finite limit, it is sufficient to consider only $F_n(C_n + x)$. The function $F_n(C_n + x)$ has a non-degenerate limit distribution as $n \to \infty$, for some $C_n$, if and only if $f(m)$ has the form

$$f(m) = a \ln m + g(m),$$ where $a$ is a constant and the function $g(m)$ satisfies the conditions

$$\sum_{|g(p)| \ge 1} \frac 1p < \infty, \qquad \sum_{|g(p)|<1} \frac{g^2(p)}{p} < \infty.$$ Here $C_n$ must be equal to

$$C_n = a \ln n + \sum_{\substack{p \le n \\ |g(p)| < 1}} \frac{g(p)}{p} + C + o(1),$$ where $C$ is a constant. The choice of $C_n$ is unique up to an additive term $C + o(1)$. The limit distribution is discrete when $\sum_{f(p) \ne 0} 1/p < \infty$, and continuous otherwise.

In particular, $F_n(x)$ (the case $C_n \equiv 0$) has a limit distribution if and only if the series

$$\sum_{|f(p)| \ge 1} \frac 1p, \qquad \sum_{|f(p)| < 1} \frac{f(p)}{p}, \qquad \sum_{|f(p)| < 1} \frac{f^2(p)}{p}$$ converge (an analogue of the three-series theorem in probability theory).

The case $D_n \to \infty$ has not been completely investigated. Some of the simpler results are presented below, when $C_n = A_n$ and $D_n = B_n$ are defined by formula (2).

If, for any fixed $\epsilon > 0$,

$$B_n^{-2} \sum_{\substack{p^\alpha = n \\ |f(p^\alpha)| > \epsilon B_n}} \frac{f^2(p^\alpha)}{p^\alpha} \to 0, \tag{4}$$ as $n \to \infty$ (an analogue of the Lindeberg condition, cf. Lindeberg–Feller theorem), then

$$F_n(A_n + B_n x) \to \frac{1}{\sqrt{2\pi}} \int_{-\infty}^x e^{-u^2/2} du = \Phi(x) \tag{5}$$ (the normal law). If (4) is satisfied, then $B_n$ is a slowly-varying function of $\ln n$ in the sense of Karamata. Moreover, if $B_n$ is such a function, then (4) is a necessary condition for (5).

Let $B_n$ be a slowly-varying function in $\ln n$. Then $F_n(A_n + B_n x)$ converges to a limit distribution with variance 1 if and only if there exists a non-decreasing function $V(u)$, $-\infty < u < \infty$, such that $V(-\infty) = 0$, $V(\infty) = 1$, and such that as $n \to \infty$, for all $u$ with the possible exception of $u = 0$,

$$B_n^{-2} \sum_{\substack{p^\alpha \le n \\ f(p^\alpha) < u B_n}} \frac{f^2(p^\alpha)}{p^\alpha} \to V(u) .$$ The characteristic function $\phi(t)$ of the limit law, if it exists at all, is given by the formula

$$\phi(t) = \exp \left( \int_{-\infty}^\infty (e^{itu} - 1 - itu) u^{-2} dV(u) \right).$$ One has studied the rate of convergence to the limit law. For example, if $f(m)$ is a strongly-additive function and if

$$\mu_n = B_n^{-1} \max_{p\le n} |f(p)| \to 0$$ as $n \to \infty$, then

$$F_n(A_n + B_n x) = \Phi(x) + O(\mu_n),$$ uniformly in $x$.

There are similar results for multiplicative arithmetic functions.

Local laws.

Here one studies the behaviour of the frequency $N_n(f(m) = c)/n$ as $n \to \infty$ for a fixed $c$. In the case of a real additive arithmetic function, this frequency always has a limit, which is distinct from zero only for a countable set of values of $c$. Let

$$\lambda_l(f) = \lim_{n\to\infty} \frac 1n N_n(f(m) = c_l), \quad l=1, 2, \ldots,$$ be the collection of non-zero limits, assuming that at least one such limit exists. Then

$$\sum_l \lambda_l(f) = 1$$ and

$$\sum_l \lambda_l(f) e^{itc_l} = \prod_p \left( 1 - \frac 1p \right) \sum_{\alpha = 0}^\infty p^{-\alpha} e^{itf(p^\alpha)}.$$ If $f(m)$ takes only integer values and if

$$\mu_k(f) = \lim_{n\to\infty} \frac 1n N_n(f(m) = k),$$ then

$$\sum_k \mu_k(f) = 1$$ if and only if

$$\sum_{f(p)\ne 0} \frac 1p < \infty.$$ One has studied the rate of convergence to $\mu_k(f)$. There exists an absolute constant $C$ such that for all integers $k$ and all integer-valued additive arithmetic functions $f(m)$ such that $f(p) = 0$ for all primes $p$,

$$\left| \frac 1n N_n(f(m) = k) - \mu_k(f) \right| \le C_n^{-1/2}.$$ One has also studied the asymptotic behaviour of the frequency $N_n(f(m) = k_n)/n$ when $k_n$ increases with $n$.

References

[1] M. Kac, "Statistical independence in probability, analysis and number theory" , Math. Assoc. Amer. (1963)
[2] I.P. [I.P. Kubilyus] Kubilius, "Probabilistic methods in the theory of numbers" , Amer. Math. Soc. (1978) (Translated from Russian)
[3] I.P. Kubilyus, "Current problems of analytic number theory" , Minsk (1974) (In Russian)
[4] Yu.V. Linnik, "The dispersion method in binary additive problems" , Amer. Math. Soc. (1963) (Translated from Russian)
[5] Yu.V. Linnik, "Ergodic properties of algebraic fields" , Springer (1968) (Translated from Russian)
[6] A.G. Postnikov, "Ergodic problems in the theory of congruences and of Diophantine approximations" , Amer. Math. Soc. (1967) (Translated from Russian)
[7] P.D.T.A. Elliot, "Probabilistic number theory" , 1–2 , Springer (1979–1980)


Comments

The Erdös–Kac theorem gives some more precise information on $\omega(n)$. Denote by $N(x;a,b)$ the number of integers in the interval $[3,x]$ for which the inequalities $$ a \le \frac{ \omega(n) - \log\log n }{ \sqrt{\log\log n} } \le b $$ hold. Then, as $x \rightarrow \infty$, $$ N(x;a,b) = (x+o(x)) \frac{1}{\sqrt{2\pi}} \int_a^b e^{-t^2/2} dt \ . $$

See [a1].

References

[a1] W. Narkiewicz, "Number theory" , World Sci. (1983) pp. 251–259 (Translated from Polish) Zbl 0528.10001
How to Cite This Entry:
Number theory, probabilistic methods in. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Number_theory,_probabilistic_methods_in&oldid=19209
This article was adapted from an original article by I.P. Kubilyus (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article