Distribution of prime numbers

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 " Izv. Akad. Nauk SSSR Ser. Mat. , 22 : 2 (1958) pp. 161–164 (In Russian)
[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 -functions" , Moscow-Leningrad (1947) (In Russian)
[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 -th prime is greater than " Proc. London Math. Soc. (2) , 45 (1939) pp. 21–44
[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 -functions" Russian Math. Surveys , 15 : 2 (1980) pp. 63–76 Uspekhi Mat. Nauk , 35 : 2 (1980) pp. 55–65

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)