Number theory, probabilistic methods in
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 , one usually studied the asymptotic behaviour of
itself, or of its average values. In the first case one has to find two simple functions
,
such that
for all
, or at least for all sufficiently large
. For example, if
denotes the number of distinct prime divisors of a number
, then
for all
, and
for
;
![]() |
![]() |
In the second case one considers the behaviour of
![]() | (1) |
For the average value (1) is equal to
. A solution to the first and to the second problem in the general case gives little information about the function
, 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
fluctuate for an overwhelming majority of values of the argument. If
is a real additive arithmetic function, and if
![]() | (2) |
where the sums are taken over all prime numbers and all powers of primes
, respectively, then
![]() |
where is an absolute constant. Thus, for any
and for all
with the exception of
numbers, the inequality
![]() |
holds (an analogue of the law of large numbers in probability theory). For the function this inequality can be written in the form
![]() |
Denote by the number of natural numbers
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
, then one is forced to consider the asymptotic behaviour of the frequencies
![]() | (3) |
as , where
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
![]() |
as , for given
.
In the case of an additive arithmetic function one searches for conditions under which converges to some distribution function
at all its points of continuity. Here, if
is not degenerate and
must converge to a finite (distinct from
) or infinite limit.
In the case of a finite limit, it is sufficient to consider only . The function
has a non-degenerate limit distribution as
, for some
, if and only if
has the form
![]() |
where is a constant and the function
satisfies the conditions
![]() |
Here must be equal to
![]() |
where is a constant. The choice of
is unique up to an additive term
. The limit distribution is discrete when
, and continuous otherwise.
In particular, (the case
) has a limit distribution if and only if the series
![]() |
converge (an analogue of the three-series theorem in probability theory).
The case has not been completely investigated. Some of the simpler results are presented below, when
and
are defined by formula (2).
If, for any fixed ,
![]() | (4) |
as (an analogue of the Lindeberg condition, cf. Lindeberg–Feller theorem), then
![]() | (5) |
(the normal law). If (4) is satisfied, then is a slowly-varying function of
in the sense of Karamata. Moreover, if
is such a function, then (4) is a necessary condition for (5).
Let be a slowly-varying function in
. Then
converges to a limit distribution with variance 1 if and only if there exists a non-decreasing function
,
, such that
,
, and such that as
, for all
with the possible exception of
,
![]() |
The characteristic function of the limit law, if it exists at all, is given by the formula
![]() |
One has studied the rate of convergence to the limit law. For example, if is a strongly-additive function and if
![]() |
as , then
![]() |
uniformly in .
There are similar results for multiplicative arithmetic functions.
Local laws.
Here one studies the behaviour of the frequency as
for a fixed
. 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
. Let
![]() |
be the collection of non-zero limits, assuming that at least one such limit exists. Then
![]() |
and
![]() |
If takes only integer values and if
![]() |
then
![]() |
if and only if
![]() |
One has studied the rate of convergence to . There exists an absolute constant
such that for all integers
and all integer-valued additive arithmetic functions
such that
for all primes
,
![]() |
One has also studied the asymptotic behaviour of the frequency when
increases with
.
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 |
Number theory, probabilistic methods in. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Number_theory,_probabilistic_methods_in&oldid=43403