Difference between revisions of "Distribution of prime numbers"
(Importing text file) |
(MSC 11N05) |
||
Line 1: | Line 1: | ||
+ | {{MSC|11N05}} | ||
+ | |||
A branch of number theory studying distribution laws of prime numbers among natural numbers. The central problem is that of finding the best asymptotic, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335301.png" />, expression for the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335302.png" />, which is the number of prime numbers not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335303.png" />, and for the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335304.png" />, which is the number of prime numbers not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335305.png" /> in the arithmetic progression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335306.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335307.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335308.png" /> for values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335309.png" /> increasing along with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353010.png" />. | A branch of number theory studying distribution laws of prime numbers among natural numbers. The central problem is that of finding the best asymptotic, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335301.png" />, expression for the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335302.png" />, which is the number of prime numbers not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335303.png" />, and for the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335304.png" />, which is the number of prime numbers not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335305.png" /> in the arithmetic progression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335306.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335307.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335308.png" /> for values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d0335309.png" /> increasing along with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353010.png" />. | ||
Revision as of 17:39, 23 November 2014
2020 Mathematics Subject Classification: Primary: 11N05 [MSN][ZBL]
A branch of number theory studying distribution laws of prime numbers among natural numbers. The central problem is that of finding the best asymptotic, as , expression for the function
, which is the number of prime numbers not exceeding
, and for the function
, which is the number of prime numbers not exceeding
in the arithmetic progression
,
,
for values of
increasing along with
.
The fundamental theorem of arithmetic: Any natural number is either a prime number or a unique (up to permutation of factors) product
![]() |
(the so-called canonical representation of ), where
are different prime numbers and
are natural numbers. Thus, the prime numbers form a multiplicative basis for the set of natural numbers. This, though, says nothing about the value of
.
A method used for finding the prime numbers between 1 and is that of the sieve of Eratosthenes, known since the 3rd century B.C. (cf. Eratosthenes, sieve of). The sieve of Eratosthenes is the simplest procedure for obtaining the sequence of prime numbers. But the analytic formula of the sieve,
![]() |
where takes the values of the divisors of the product of all prime numbers
;
is the number of prime divisors of
and
is the integer part of
, is not very well suited for studying
as
.
The examination of the sequence of prime numbers between 1 and :
![]() | (1) |
shows that they get ever sparser on the average as increases. There are arbitrarily long segments of the natural series containing no prime number. For instance, the
numbers of the form
are all composite for any
. At the same time, prime numbers that differ by 2, like 8004119 and 8004121, are encountered in (1) (twins). The behaviour of
as
is one of the most difficult and inspiring problems of number theory.
The first result about is Euclid's theorem:
as
. L. Euler (1737, 1749, see [1]) introduced the function
![]() | (2) |
and showed that
![]() | (3) |
for . Here the series extends over all natural numbers, and the product over all prime numbers. The identity (3) and its generalizations play a fundamental role in the theory of the distribution of prime numbers. Based on the identity, Euler proved that the series
and the product
diverge over the sequence of prime numbers. This is another proof that the set of prime numbers is infinite. Moreover, Euler proved that
![]() |
which shows that there are "many" prime numbers, although almost-all natural numbers are composite in the sense that
![]() |
A significant success was subsequently obtained by P.L. Chebyshev (1851–1852, see [2]). He proved that
1) for any there are sequences
such that
![]() |
![]() |
2) if the quotient converges as
, then the limit is equal to 1.
This solved for the first time the question of the existence of a simple function
![]() |
which approximates optimally.
Then Chebyshev established the true order of growth of , that is, the existence of constants
and
such that
![]() | (4) |
notably, ,
for
. He also proved that for any
the interval
contains at least one prime number (Bertrand's postulate). The proof of (4) is based on Chebyshev's identity
![]() | (5) |
where the function , introduced by Chebyshev, is defined by the sum
![]() |
taken over all powers ,
, of prime numbers
. Namely, if
, the following combination of
:
![]() |
owing to (5), gives the identity
![]() |
which implies
![]() |
By virtue of Stirling's asymptotic formula for this implies an analogue of (4) for
from which (4) is obtained by partial summation. Chebyshev's function
proved to be more convenient for studying the distribution of prime numbers than
, since the best approximation for it is the very argument
. Therefore
is usually considered first and then the corresponding result for
is obtained by partial summation.
Riemann's principle.
In 1859–1860 B. Riemann [3] considered the function , introduced by Euler for
, as a function of a complex variable
, where
and
are real variables, defined by (2) for
(see Zeta-function) and found that this function is extremely important in the theory of the distribution of prime numbers. In particular, he found an expression for the difference
in terms of
and those zeros of
which belong to the strip
; they are called the non-trivial zeros of
.
Instead of Riemann's formula, its simpler finite analogue for , proved (along with Riemann's formula) by H. (von) Mangoldt in 1895, is often used. Namely, for
:
![]() | (6) |
where runs through the non-trivial zeros of
and
is arbitrary.
Since
![]() |
(6) shows that the difference is primarily defined by
(the real part of the right-most zeros
). In particular, the following asymptotic expressions are valid for
and
:
![]() |
![]() |
provided that to the right of a vertical
,
. Conversely, it follows from these relations that
if
. If the Riemann hypothesis holds, that is, if all non-trivial zeros of
lie on the line
, then the asymptotic distribution law for prime numbers must have the form
![]() |
![]() |
and these relations cannot be substantially strengthened. The latter means that there are sequences such that
![]() |
![]() |
Thus, by Riemann's principle, the problem about the asymptotic expressions for and
reduces to that about bounds for the real part of the non-trivial zeros of
. Till now (1983), however, no constant
,
, has been found with the condition
. The desired bound for
turns out to be connected with the imaginary part
of zeros
in such a way that the line
is its asymptote.
The methods of Hadamard and de la Vallée-Poussin.
In its simplest form
![]() |
the asymptotic distribution law for prime numbers was independently obtained in 1896 by J. Hadamard and Ch.J. de la Vallée-Poussin, who proved that , that is, there is no zero of
on the line
. In 1899 de la Vallée-Poussin showed that
in the domain
. It was thereby proved that
![]() |
![]() |
where are constants.
Further extensions of the region containing no zeros of were also obtained (see [4]–[12]).
The method of Weyl–Littlewood.
There is a certain connection between the growth of the modulus of and its zeros near the line
. In particular, if
for
, where
and
are positive non-decreasing functions of
such that
,
as
and
, then there is a constant
such that
in the region
![]() |
The estimate for is here obtained with the help of the partial sums of the series (2). This reduces the problem to the estimation of trigonometric sums of the form
![]() |
By estimating such sums by the Weyl method, J.E. Littlewood showed in 1921 that if
and
, so that
in the region
![]() |
It follows that
![]() |
The method of Vinogradov.
A further advance in the estimation of and
is connected with development by I.M. Vinogradov of a new and substantially more powerful method for the estimation of trigonometric sums (see Vinogradov method). Using this method, he showed in 1938 that
if
![]() |
and consequently that
![]() |
In 1958 Vinogradov and others (see [6]–[11]) showed that if
![]() |
So far (1983) this is the best result concerning bounds on the non-trivial zeros of , to which the following best result on the distribution of prime numbers corresponds:
![]() |
![]() |
The asymptotics for the -th prime number,
, follow from the asymptotics of
. It was also shown (see [21]) that
for all
and that for
,
,
![]() |
and for ,
![]() |
Elementary methods.
This is the name for methods for studying the asymptotic distribution of prime numbers that are not based on Riemann's principle (zeros of the zeta-function) and, in general, on any principles from the theory of functions of a complex variable whatsoever. Such a method was first discovered by A. Selberg [16] and P. Erdös [17]. It is based on the elementary formula of Selberg
![]() | (7) |
A further problem consists in obtaining asymptotics for from the averaged asymptotics for
given by (7). It may be done in different ways but all of them employ the fact that
slowly oscillates. In 1962 E. Bombieri and E. Wirsing proved that
![]() |
for any fixed . In 1970, H.G. Diamond and J. Steinig [19] substantially perfected the principles and techniques of estimation by means of an elementary method. They proved that for
,
![]() |
Finally, in 1973 A.F. Lavrik and A.Sh. Sobirov [20] showed that an elementary method enables one to prove the following theorem: For ,
![]() |
This result is so far the best achievement of the elementary method as regards the distribution of prime numbers. Although it is somewhat weaker than the result obtained by the analytic method, in principle they are close.
The difference between prime numbers.
There are many questions in the distribution of prime numbers that are concerned with differences between prime numbers. Standing out among them are questions about the behaviour of the difference between adjacent prime numbers; the problem on the number of prime twins or, more generally, pairs of prime numbers that differ by
or, in the most general form, the problem about the number of systems
of
prime numbers within the segment
.
Using Riemann's hypothesis it was proved that , and heuristic considerations suggest that probably
. By 1983, the best estimate
, where
,
, was obtained by M.N. Huxley (1973) using the method of the large sieve. As for pairs of prime numbers whose difference is equal to 2 (twins) or to
,
it is still (1983) unknown whether the number of such pairs is finite or not. Let
be the number of prime numbers that do not exceed
and differ by
. In 1919 V. Brun found a sieve method (see Brun sieve) that permitted one to obtain the expected upper bound for
:
![]() |
In addition to that, it was shown by the circle method (see [13]) with the help of Vinogradov's estimates for trigonometric sums with prime numbers (see Vinogradov method) that for any fixed ,
,
![]() |
where
![]() |
This implies, in particular, that for the following asymptotic expression for
holds for all
except for at most
values of
in the range
:
![]() |
Similar results are obtained for sets of prime numbers for all
.
Prime numbers in arithmetic progressions.
The first method (of Euclid) for proving the infinitude of prime numbers can also be applied to certain arithmetic progressions. But the proof by this method that every arithmetic progression , where the first number
and the difference
are relatively prime, contains infinitely many prime numbers has not yet (1983) been given. The problem was solved by another method by P. Dirichlet (1837–1840), who extended an idea of Euler in showing that
as
for prime numbers
. To do this he introduced certain arithmetical functions — characters
(see Dirichlet character) and functions
(see Dirichlet
-function), which, like
for
and
, serve as a basic means of studying
and its analogue
![]() |
For a fixed value of ,
,
, the majority of results indicated above for
and
carry over to
and
. However, of special interest here are the results for values of
that increase with
, as these are important in additive number theory and elsewhere. In this case, other significant difficulties arise, connected mostly with estimating
, the largest real zero of
modulo
. It can be proved using the Page theorem that for
,
,
![]() |
and as a result of C.L. Siegel's bound (1935), for any fixed , for
,
![]() |
where is the Euler
-function,
is a positive constant and
is an ineffective constant
, that is,
cannot be computed for given
.
If the extended Riemann hypothesis (cf. Riemann hypotheses) is true, then for ,
![]() |
Thus, up till 1983 it has been proved that the prime numbers are uniformly distributed over all progressions
,
, of difference
only for
. As far as segments of progressions
are concerned, for example with
for any
, it does not even follow from the above that such a progression contains at least one prime number.
The sieve method of Brun, like the modification suggested by Selberg in 1947, shows that for all ,
,
, there is an upper bound
![]() |
with absolute constant , but no lower bounds for
are obtainable by these methods.
By the Riemann principle for a zero of
lying in the strip
,
has the form
![]() | (8) |
![]() |
where the prime on the indicates summation over complex
,
is the real zero of
if it exists and is greater than
, and
![]() |
for any .
From (8) one sees that if one disregards the term corresponding to , the remainder term is determined by the double sum and depends also on the real part of
and on all the
with
having a zero
with
. If, for
,
denotes the number of zeros of
in the rectangle
,
, then the problem of estimating the remainder term for
and its mean value is reduced to the problem of estimating the density of the distribution of the zeros of
-functions:
![]() | (9) |
Thus, the reduction of various estimates for prime numbers is concerned not so much with the lack of zeros of in the critical strip, but with their comparatively rare distribution there.
The realization of this idea has been one of the central directions of research on the distribution of prime numbers over the last forty years. A start was made by Yu.V. Linnik with his discovery in 1941 of the method of the large sieve (see [22], and also [14], [24]). Especially important are the theorems on the least prime number in an arithmetic progression, the behaviour of and
on the average for
, and on the double averaging of these functions over
,
, and over
.
Namely, in 1944 Linnik [23] showed that as the sum
in (9) has the bound
, where
is a constant; from this he deduced the existence of a constant
such that any arithmetic progression
,
,
, contains a prime number less than
. The latest estimate of Linnik's constant is
; but if the density hypothesis is correct, i.e. if
, then
.
In 1965, A.I. Vinogradov and Bombieri independently obtained strong estimates for in (9). A more complete method of estimating these sums was found by H. Montgomery (1969). One of the results on estimating
is the following result on the average distribution of prime numbers in arithmetic progressions:
![]() |
![]() |
for any constant and
. These estimates cannot be substantially improved, because the extended Riemann hypothesis implies that
.
Other problems on the distribution of prime numbers are as follows. Let be the number of integers of the form
which are products of
prime numbers. H. Richert (1953) proved that
![]() |
![]() |
![]() |
where ,
,
,
, and the
are determined by series depending on
,
,
, and
.
E. Landau (1903–1918) carried over certain results on the distribution of prime numbers to algebraic number fields. Let be an algebraic number field of degree
and let
be the number of prime ideals in
with norm
. Then
![]() |
where is an absolute positive constant, and
![]() |
where is the negation of the symbol
(small).
Much studied is the function denoting the amount of natural numbers
not containing prime divisors less than
. For
and
as
, such numbers are called quasi-prime numbers. By applying the sieve method to these numbers there arose a fairly complete theory of their distribution, similar to that expected from the distribution of prime numbers. The distribution of numbers with small prime divisors has also been considered (see [15]).
References
[1] | L. Euler, "Einleitung in die Analysis des Unendlichen" , Springer (1983) (Translated from Latin) |
[2] | P.L. Chebyshev, "Oeuvres de P.L. Tchebycheff" , 1–2 , Chelsea (1961) (Translated from Russian) |
[3] | B. Riemann, "Werke" , Teubner (1892) |
[4] | A.E. Ingham, "The distribution of prime numbers" , Cambridge Univ. Press (1932) |
[5] | A.I. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian) |
[6] | I.M. Vinogradov, "A new estimate of the function ![]() |
[7] | I.M. Vinogradov, "The method of trigonometric sums in the theory of numbers" , Interscience (1954) (Translated from Russian) |
[8] | E.C. Titchmarsh, "The theory of the Riemann zeta-function" , Clarendon Press (1951) |
[9] | K. Prachar, "Primzahlverteilung" , Springer (1957) |
[10] | A.A. Karatsuba, "Fundamentals of analytic number theory" , Moscow (1975) (In Russian) |
[11] | L.-K. Hua, "Abschätzungen von Exponentialsummen und ihre Anwendung in der Zahlentheorie" , Enzyklopaedie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen , 1 : 2 (1959) (Heft 13, Teil 1) |
[12] | N.G. Chudakov, "Introductions to the theory of Dirichlet ![]() |
[13] | A.F. Lavrik, "On the distribution of primes based on I.M. Vinogradov's method of trigonometric sums" Trudy Mat. Inst. Steklov. , 64 (1961) pp. 90–125 (In Russian) |
[14] | H. Davenport, "Multiplicative number theory" , Springer (1980) |
[15] | H. Halberstam, H.-E. Richert, "Sieve methods" , Acad. Press (1974) |
[16] | A. Selberg, "An elementary proof of the prime-number theorem" Ann. of Math. , 50 (1949) pp. 305–313 |
[17] | P. Erdös, "On a new method in elementary number theory which leads to an elementary proof of the prime number theorem" Proc. Nat. Acad. Sci. USA , 35 (1949) pp. 374–384 |
[18] | A.F. Lavrik, "Survey address" , Internat. Conf. on Number Theory , Moscow (1981) (In Russian) |
[19] | H.G. Diamond, J. Steinig, "An elementary proof of the prime number theorem with a remainder term" Indag. Math. , 11 (1970) pp. 199–258 |
[20] | A.F. Lavrik, A.Sh. Sobirov, "On the remainder term in the elementary proof of the prime number theorem" Soviet Math. Dokl. , 211 (1973) pp. 1063–1066 Dokl. Akad. Nauk SSSR , 211 : 3 (1973) pp. 534–536 |
[21] | B. Rosser, "The ![]() ![]() |
[22] | Yu.V. Linnik, "The large sieve" Dokl. Akad. Nauk SSSR , 30 : 4 (1941) pp. 292–294 (In Russian) |
[23] | Yu.V. Linnik, "On the least prime in an arithmetic progression I. The basic theorem" Mat. Sb. , 15 (1944) pp. 139–178 (In Russian) |
[24] | A.F. Lavrik, "A survey of Linnik's large sieve and the density theory of zeros of ![]() |
Comments
In formula (7) above, is the (von) Mangoldt function, which has the value
if
is a prime power
and is zero otherwise.
Concerning estimates of trigonometric sums see also Trigonometric sums, method of.
Some more facts. Although numerical tables do not suggest it, the function changes sign infinitely often. This was shown by Littlewood. By the work of H. Iwaniec, J. Pintz and C.J. Mozzochi it is now (1986) known that
with
. The largest known prime twin is
(W. Keller, 1983).
Many interesting facts, both computationally and theoretically, on the distribution of primes can be found in [a5], which is written in an elementary style. For elementary methods one can also consult [a1]. In [a4] one finds a simple proof of the prime number theorem.
The fact that there are infinitely many primes (i.e. as
) is also known as the Euclidean prime number theorem. The prime number theorem states that
is asymptotically equal to
(cf. also de la Vallée-Poussin theorem). The Dirichlet prime number theorem states that there are infinitely many primes in every arithmetic progression (i.e.
as
).
For the result of Bombieri–Vinogradov see also (the references to) Density hypothesis.
References
[a1] | H.G. Diamond, "Elementary methods in the study of the distribution of prime numbers" Bull. Amer. Math. Soc. , 7 (1982) pp. 553–589 |
[a2] | W.J. Ellison, M. Mendès France, "Les nombres premiers" , Hermann (1975) |
[a3] | A. Ivic, "The Riemann zeta-function" , Wiley (1985) |
[a4] | D.J. Newman, "Simple analytic proof of the prime number theorem" Amer. Math. Monthly , 87 (1980) pp. 693–696 |
[a5] | H. Riesel, "Prime numbers and computer methods for factorisation" , Birkhäuser (1985) |
[a6] | E. Bombieri, "La grand crible dans la théorie analytique des nombres" Astérisque , 18 (1974) |
Distribution of prime numbers. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Distribution_of_prime_numbers&oldid=34908