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