Namespaces
Variants
Actions

Difference between revisions of "Distribution of prime numbers"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎Prime numbers in arithmetic progressions.: link to Dirichlet L-function)
(latex details)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
<!--
 +
d0335301.png
 +
$#A+1 = 373 n = 5
 +
$#C+1 = 373 : ~/encyclopedia/old_files/data/D033/D.0303530 Distribution of prime numbers
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
{{MSC|11N05}}
 
{{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 $  x \rightarrow \infty $,  
 +
expression for the function $  \pi ( x) $,  
 +
which is the number of prime numbers not exceeding $  x $,  
 +
and for the function $  \pi ( x;  d, l) $,
 +
which is the number of prime numbers not exceeding $  x $
 +
in the arithmetic progression $  dn + l $,
 +
$  1 \leq  l \leq  d $,  
 +
$  n = 1, 2 \dots $
 +
for values of d $
 +
increasing along with $  x $.
  
The fundamental theorem of arithmetic: Any natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353011.png" /> is either a prime number or a unique (up to permutation of factors) product
+
The fundamental theorem of arithmetic: Any natural number $  n > 1 $
 +
is either a prime number or a unique (up to permutation of factors) product
  
<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/d/d033/d033530/d03353012.png" /></td> </tr></table>
+
$$
 +
= \
 +
p _ {1} ^ {n _ {1} } \dots
 +
p _ {k} ^ {n _ {k} }
 +
$$
  
(the so-called canonical representation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353013.png" />), where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353014.png" /> are different prime numbers and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353015.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353016.png" />.
+
(the so-called canonical representation of $  n $),  
 +
where $  p _ {1} \dots p _ {k} $
 +
are different prime numbers and $  n _ {1} \dots n _ {k} $
 +
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 $  \pi ( x) $.
  
A method used for finding the prime numbers between 1 and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353017.png" /> is that of the sieve of Eratosthenes, known since the 3rd century B.C. (cf. [[Eratosthenes, sieve of|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,
+
A method used for finding the prime numbers between 1 and $  x $
 +
is that of the sieve of Eratosthenes, known since the 3rd century B.C. (cf. [[Eratosthenes, sieve of|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,
  
<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/d/d033/d033530/d03353018.png" /></td> </tr></table>
+
$$
 +
\pi ( x) -
 +
\pi ( \sqrt x ) + 1  = \
 +
\sum _ { d }
 +
(- 1) ^ {\nu ( d) }
 +
\left [
 +
{
 +
\frac{x}{d}
 +
}
 +
\right ] ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353019.png" /> takes the values of the divisors of the product of all prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353020.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353021.png" /> is the number of prime divisors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353023.png" /> is the integer part of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353024.png" />, is not very well suited for studying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353025.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353026.png" />.
+
where d $
 +
takes the values of the divisors of the product of all prime numbers $  \leq  \sqrt x $;  
 +
$  \nu ( d) $
 +
is the number of prime divisors of d $
 +
and $  [ u] $
 +
is the integer part of $  u $,  
 +
is not very well suited for studying $  \pi ( x) $
 +
as $  x \rightarrow \infty $.
  
The examination of the sequence of prime numbers between 1 and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353027.png" />:
+
The examination of the sequence of prime numbers between 1 and $  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/d/d033/d033530/d03353028.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
2, 3, 5, 7, 11, 13 \dots p,
 +
$$
  
shows that they get ever sparser on the average as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353029.png" /> increases. There are arbitrarily long segments of the natural series containing no prime number. For instance, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353030.png" /> numbers of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353031.png" /> are all composite for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353032.png" />. At the same time, prime numbers that differ by 2, like 8004119 and 8004121, are encountered in (1) ([[Twins|twins]]). The behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353033.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353034.png" /> is one of the most difficult and inspiring problems of number theory.
+
shows that they get ever sparser on the average as $  x $
 +
increases. There are arbitrarily long segments of the natural series containing no prime number. For instance, the $  n - 1 $
 +
numbers of the form $  n! + 2 \dots n! + n $
 +
are all composite for any $  n \geq  2 $.  
 +
At the same time, prime numbers that differ by 2, like 8004119 and 8004121, are encountered in (1) ([[Twins|twins]]). The behaviour of $  \pi ( x) $
 +
as $  x \rightarrow \infty $
 +
is one of the most difficult and inspiring problems of number theory.
  
The first result about <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353035.png" /> is Euclid's theorem: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353036.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353037.png" />. L. Euler (1737, 1749, see [[#References|[1]]]) introduced the function
+
The first result about $  \pi ( x) $
 +
is Euclid's theorem: $  \pi ( x) \rightarrow \infty $
 +
as $  x \rightarrow \infty $.  
 +
L. Euler (1737, 1749, see [[#References|[1]]]) introduced the 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/d/d033/d033530/d03353038.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
\zeta ( s)  = \sum _ {n = 1 } ^  \infty  n  ^ {-s}
 +
$$
  
 
and showed that
 
and showed that
  
<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/d/d033/d033530/d03353039.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
\zeta ( s)  = \prod _ { p }
 +
\left ( 1 - {
 +
\frac{1}{p  ^ {s} }
 +
}
 +
\right ) ^ {-1}
 +
$$
  
for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353040.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353041.png" /> and the product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353042.png" /> diverge over the sequence of prime numbers. This is another proof that the set of prime numbers is infinite. Moreover, Euler proved that
+
for $  s > 1 $.  
 +
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 $  \sum 1/p $
 +
and the product $  \prod ( 1 - 1/p)  ^ {-1} $
 +
diverge over the sequence of prime numbers. This is another proof that the set of prime numbers is infinite. Moreover, Euler proved that
  
<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/d/d033/d033530/d03353043.png" /></td> </tr></table>
+
$$
 +
\pi ( x)  >   \mathop{\rm log}  {
 +
\frac{x}{e}
 +
} ,
 +
$$
  
 
which shows that there are  "many"  prime numbers, although almost-all natural numbers are composite in the sense that
 
which shows that there are  "many"  prime numbers, although almost-all natural numbers are composite in the sense that
  
<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/d/d033/d033530/d03353044.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{\pi ( x) }{x}
 +
}  \rightarrow  0 \ \
 +
\textrm{ as }  x \rightarrow \infty .
 +
$$
  
 
A significant success was subsequently obtained by P.L. Chebyshev (1851–1852, see [[#References|[2]]]). He proved that
 
A significant success was subsequently obtained by P.L. Chebyshev (1851–1852, see [[#References|[2]]]). He proved that
  
1) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353045.png" /> there are sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353046.png" /> such that
+
1) for any $  m, M > 0 $
 +
there are sequences $  x, y \rightarrow \infty $
 +
such that
  
<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/d/d033/d033530/d03353047.png" /></td> </tr></table>
+
$$
 +
\pi ( x) -  \mathop{\rm li}  x  < \
 +
Mx  \mathop{\rm log}  ^ {-m}  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/d/d033/d033530/d03353048.png" /></td> </tr></table>
+
$$
 +
\pi ( y) -  \mathop{\rm li}  y  > - My  \mathop{\rm log}  ^ {-m}  y;
 +
$$
  
2) if the quotient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353049.png" /> converges as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353050.png" />, then the limit is equal to 1.
+
2) if the quotient $  ( \pi ( x)  \mathop{\rm log}  x)/x $
 +
converges as $  x \rightarrow \infty $,  
 +
then the limit is equal to 1.
  
 
This solved for the first time the question of the existence of a simple function
 
This solved for the first time the question of the existence of a simple 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/d/d033/d033530/d03353051.png" /></td> </tr></table>
+
$$
 +
\mathop{\rm li}  x  \equiv \
 +
\int\limits _ { 2 } ^ { x }
  
which approximates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353052.png" /> optimally.
+
\frac{du }{ \mathop{\rm log}  u }
 +
  = \
 +
{
 +
\frac{x}{ \mathop{\rm log}  x }
 +
} + \dots +
  
Then Chebyshev established the true order of growth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353053.png" />, that is, the existence of constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353054.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353055.png" /> such that
+
\frac{( r - 1)!
 +
x }{ \mathop{\rm log}  ^ {r}  x }
 +
+
 +
O \left (
 +
{
 +
\frac{x}{ \mathop{\rm log} ^ {r + 1 }  x }
 +
}
 +
\right ) ,
 +
$$
  
<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/d/d033/d033530/d03353056.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
which approximates  $  \pi ( x) $
 +
optimally.
  
notably, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353057.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353058.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353059.png" />. He also proved that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353060.png" /> the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353061.png" /> contains at least one prime number (Bertrand's postulate). The proof of (4) is based on Chebyshev's identity
+
Then Chebyshev established the true order of growth of  $  \pi ( x) $,  
 +
that is, the existence of constants  $  a > 0 $
 +
and  $  A > 0 $
 +
such that
  
<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/d/d033/d033530/d03353062.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
$$ \tag{4 }
 +
a {
 +
\frac{x}{ \mathop{\rm log}  x }
 +
< \
 +
\pi ( x) < \
 +
A {
 +
\frac{x}{ \mathop{\rm log}  x }
 +
} ;
 +
$$
  
where the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353063.png" />, introduced by Chebyshev, is defined by the sum
+
notably,  $  a = 0.92 \dots $,
 +
$  A = 1.05 \dots $
 +
for  $  x \geq  x _ {0} $.  
 +
He also proved that for any  $  n \geq  2 $
 +
the interval  $  ( n, 2n) $
 +
contains at least one prime number (Bertrand's postulate). The proof of (4) is based on Chebyshev's identity
  
<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/d/d033/d033530/d03353064.png" /></td> </tr></table>
+
$$ \tag{5 }
 +
F ( x)  \equiv \
 +
\mathop{\rm log}  [ x]!  = \
 +
\sum _ {n \leq  x }
 +
\psi \left (
 +
{
 +
\frac{x}{n}
 +
}
 +
\right ) ,
 +
$$
  
taken over all powers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353066.png" />, of prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353067.png" />. Namely, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353068.png" />, the following combination of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353069.png" />:
+
where the function  $  \psi $,  
 +
introduced by Chebyshev, is defined by the sum
  
<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/d/d033/d033530/d03353070.png" /></td> </tr></table>
+
$$
 +
\psi ( x)  = \
 +
\sum _ {p  ^ {m} \leq  x }
 +
\mathop{\rm log}  p  = \
 +
\sum _ {n < x }
 +
\Delta ( n),
 +
$$
 +
 
 +
taken over all powers  $  p  ^ {m} $,
 +
$  m \in \mathbf N $,
 +
of prime numbers  $  p $.
 +
Namely, if  $  x \geq  30 $,
 +
the following combination of  $  \mathop{\rm log}  [ u]! $:
 +
 
 +
$$
 +
F ^ { * } ( x)  = \
 +
F ( x) + F
 +
\left (
 +
{
 +
\frac{x}{30}
 +
}
 +
\right ) - F
 +
\left (
 +
{
 +
\frac{x}{2}
 +
}
 +
\right ) - F
 +
\left (
 +
{
 +
\frac{x}{3}
 +
}
 +
\right ) - F
 +
\left (
 +
{
 +
\frac{x}{6}
 +
}
 +
\right ) ,
 +
$$
  
 
owing to (5), gives the identity
 
owing to (5), gives the identity
  
<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/d/d033/d033530/d03353071.png" /></td> </tr></table>
+
$$
 +
F ^ { * } ( x)  = \
 +
\psi ( x) - \psi
 +
\left (
 +
{
 +
\frac{x}{6}
 +
}
 +
\right ) + \psi
 +
\left (
 +
{
 +
\frac{x}{7}
 +
}
 +
\right ) - \psi
 +
\left (
 +
{
 +
\frac{x}{10}
 +
}
 +
\right ) + \dots ,
 +
$$
  
 
which implies
 
which implies
  
<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/d/d033/d033530/d03353072.png" /></td> </tr></table>
+
$$
 +
\psi ( x) - \psi
 +
\left (
 +
{
 +
\frac{x}{6}
 +
}
 +
\right )  < \
 +
F  ^ {*} ( x)  < \
 +
\psi ( x).
 +
$$
  
By virtue of Stirling's asymptotic formula for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353073.png" /> this implies an analogue of (4) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353074.png" /> from which (4) is obtained by partial summation. Chebyshev's function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353075.png" /> proved to be more convenient for studying the distribution of prime numbers than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353076.png" />, since the best approximation for it is the very argument <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353077.png" />. Therefore <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353078.png" /> is usually considered first and then the corresponding result for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353079.png" /> is obtained by partial summation.
+
By virtue of Stirling's asymptotic formula for $  n! $
 +
this implies an analogue of (4) for $  \psi ( x) $
 +
from which (4) is obtained by partial summation. Chebyshev's function $  \psi ( x) $
 +
proved to be more convenient for studying the distribution of prime numbers than $  \pi ( x) $,  
 +
since the best approximation for it is the very argument $  x $.  
 +
Therefore $  \psi ( x) $
 +
is usually considered first and then the corresponding result for $  \pi ( x) $
 +
is obtained by partial summation.
  
 
==Riemann's principle.==
 
==Riemann's principle.==
In 1859–1860 B. Riemann [[#References|[3]]] considered the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353080.png" />, introduced by Euler for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353081.png" />, as a function of a complex variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353082.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353083.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353084.png" /> are real variables, defined by (2) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353085.png" /> (see [[Zeta-function|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353086.png" /> in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353087.png" /> and those zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353088.png" /> which belong to the strip <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353089.png" />; they are called the non-trivial zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353090.png" />.
+
In 1859–1860 B. Riemann [[#References|[3]]] considered the function $  \zeta ( s) $,  
 +
introduced by Euler for $  s > 1 $,  
 +
as a function of a complex variable $  s = \sigma + it $,  
 +
where $  \sigma $
 +
and $  t $
 +
are real variables, defined by (2) for $  \sigma > 1 $(
 +
see [[Zeta-function|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 $  \pi ( x) -  \mathop{\rm li}  x $
 +
in terms of $  x $
 +
and those zeros of $  \zeta ( s) $
 +
which belong to the strip 0 \leq  \sigma \leq  1 $;  
 +
they are called the non-trivial zeros of $  \zeta ( s) $.
  
Instead of Riemann's formula, its simpler finite analogue for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353093.png" />, proved (along with Riemann's formula) by H. (von) Mangoldt in 1895, is often used. Namely, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353094.png" />:
+
Instead of Riemann's formula, its simpler finite analogue for $  \psi ( x) $,  
 +
proved (along with Riemann's formula) by H. (von) Mangoldt in 1895, is often used. Namely, for $  x > 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/d/d033/d033530/d03353095.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>
+
$$ \tag{6 }
 +
\psi ( x)  = x -
 +
\sum _ {| \gamma | \leq  T }
 +
{
 +
\frac{x  ^  \rho  } \rho
 +
} + O
 +
\left (
 +
{
 +
\frac{x}{T}
 +
} \
 +
\mathop{\rm log}  ^ {2}  xT +
 +
\mathop{\rm log}  2x
 +
\right ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353096.png" /> runs through the non-trivial zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353097.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d03353098.png" /> is arbitrary.
+
where $  \rho = \rho + i \gamma $
 +
runs through the non-trivial zeros of $  \zeta ( s) $
 +
and $  T \geq  2 $
 +
is arbitrary.
  
 
Since
 
Since
  
<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/d/d033/d033530/d03353099.png" /></td> </tr></table>
+
$$
 +
\sum _ {| \gamma | \leq  T }
 +
{
 +
\frac{1} \gamma
 +
}  \ll  \
 +
\mathop{\rm log}  ^ {2}  T,
 +
$$
  
(6) shows that the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530100.png" /> is primarily defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530101.png" /> (the real part of the right-most zeros <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530102.png" />). In particular, the following asymptotic expressions are valid for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530103.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530104.png" />:
+
(6) shows that the difference $  \psi ( x) - x $
 +
is primarily defined by $  \beta $(
 +
the real part of the right-most zeros $  \rho $).  
 +
In particular, the following asymptotic expressions are valid for $  \psi ( x) $
 +
and $  \pi ( 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/d/d033/d033530/d033530105.png" /></td> </tr></table>
+
$$
 +
\psi ( x)  = \
 +
x + O
 +
( x  ^  \theta  \
 +
\mathop{\rm log}  ^ {2}  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/d/d033/d033530/d033530106.png" /></td> </tr></table>
+
$$
 +
\pi ( x)  =   \mathop{\rm li}  x + O ( x  ^  \theta    \mathop{\rm log}  x),
 +
$$
  
provided that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530107.png" /> to the right of a vertical <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530108.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530109.png" />. Conversely, it follows from these relations that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530110.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530111.png" />. If the Riemann hypothesis holds, that is, if all non-trivial zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530112.png" /> lie on the line <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530113.png" />, then the asymptotic distribution law for prime numbers must have the form
+
provided that $  \zeta ( x) \neq 0 $
 +
to the right of a vertical $  \sigma = \theta $,
 +
$  1/2 \leq  \theta < 1 $.  
 +
Conversely, it follows from these relations that $  \zeta ( s) \neq 0 $
 +
if $  \sigma \geq  \theta $.  
 +
If the Riemann hypothesis holds, that is, if all non-trivial zeros of $  \zeta ( s) $
 +
lie on the line $  \sigma = 1/2 $,  
 +
then the asymptotic distribution law for prime numbers must have 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/d/d033/d033530/d033530114.png" /></td> </tr></table>
+
$$
 +
\psi ( x)  = \
 +
x + O ( \sqrt x \
 +
\mathop{\rm log}  ^ {2}  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/d/d033/d033530/d033530115.png" /></td> </tr></table>
+
$$
 +
\pi ( x)  =   \mathop{\rm li}  x + O ( \sqrt x  \mathop{\rm log}  x),
 +
$$
  
and these relations cannot be substantially strengthened. The latter means that there are sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530116.png" /> such that
+
and these relations cannot be substantially strengthened. The latter means that there are sequences $  x, y \rightarrow \infty $
 +
such that
  
<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/d/d033/d033530/d033530117.png" /></td> </tr></table>
+
$$
 +
\pi ( x) -  \mathop{\rm li}  x  < \
 +
- \sqrt 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/d/d033/d033530/d033530118.png" /></td> </tr></table>
+
\frac{ \mathop{\rm log}  \mathop{\rm log}  \mathop{\rm log}  x }{ \mathop{\rm log}  \mathop{\rm log}  x }
 +
,
 +
$$
  
Thus, by Riemann's principle, the problem about the asymptotic expressions for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530119.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530120.png" /> reduces to that about bounds for the real part of the non-trivial zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530121.png" />. Till now (1983), however, no constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530122.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530123.png" />, has been found with the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530124.png" />. The desired bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530125.png" /> turns out to be connected with the imaginary part <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530126.png" /> of zeros <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530127.png" /> in such a way that the line <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530128.png" /> is its asymptote.
+
$$
 +
\pi ( y) -  \mathop{\rm li}  y  >  + y
 +
\frac{ \mathop{\rm log}  \mathop{\rm log}  \mathop{\rm log}  y }{ \mathop{\rm log}  \mathop{\rm log}  y }
 +
.
 +
$$
 +
 
 +
Thus, by Riemann's principle, the problem about the asymptotic expressions for $  \psi ( x) $
 +
and $  \pi ( x) $
 +
reduces to that about bounds for the real part of the non-trivial zeros of $  \zeta ( x) $.  
 +
Till now (1983), however, no constant $  \theta $,
 +
$  1/2 \leq  \theta < 1 $,  
 +
has been found with the condition $  \beta < \theta $.  
 +
The desired bound for $  \beta $
 +
turns out to be connected with the imaginary part $  \gamma $
 +
of zeros $  \rho $
 +
in such a way that the line $  \sigma = 1 $
 +
is its asymptote.
  
 
==The methods of Hadamard and de la Vallée-Poussin.==
 
==The methods of Hadamard and de la Vallée-Poussin.==
 
In its simplest form
 
In its simplest 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/d/d033/d033530/d033530129.png" /></td> </tr></table>
+
$$
 +
\lim\limits _ {x \rightarrow \infty } \
 +
{
 +
\frac{\pi ( x)  \mathop{\rm log}  x }{x}
 +
= \
 +
\lim\limits _ {x \rightarrow \infty } \
 +
{
 +
\frac{\psi ( x) }{x}
 +
= 1
 +
$$
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530130.png" />, that is, there is no zero of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530131.png" /> on the line <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530132.png" />. In 1899 de la Vallée-Poussin showed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530133.png" /> in the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530134.png" />. It was thereby proved that
+
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 $  \zeta ( 1 + it) \neq 0 $,  
 +
that is, there is no zero of $  \zeta ( s) $
 +
on the line $  \sigma = 1 $.  
 +
In 1899 de la Vallée-Poussin showed that $  \zeta ( \sigma + it) \neq 0 $
 +
in the domain $  \sigma \geq  1 - c/ \mathop{\rm log} ( | t | + 2) $.  
 +
It was thereby proved that
  
<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/d/d033/d033530/d033530135.png" /></td> </tr></table>
+
$$
 +
\psi ( x)  = x + O
 +
( x  \mathop{\rm exp} (- a
 +
\sqrt { \mathop{\rm log}  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/d/d033/d033530/d033530136.png" /></td> </tr></table>
+
$$
 +
\pi ( x)  =   \mathop{\rm li}  x + O ( x  \mathop{\rm exp} (- b \sqrt { \mathop{\rm log}  x } )) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530137.png" /> are constants.
+
where $  a, b > 0 $
 +
are constants.
  
Further extensions of the region containing no zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530138.png" /> were also obtained (see [[#References|[4]]]–[[#References|[12]]]).
+
Further extensions of the region containing no zeros of $  \zeta ( s) $
 +
were also obtained (see [[#References|[4]]]–[[#References|[12]]]).
  
 
==The method of Weyl–Littlewood.==
 
==The method of Weyl–Littlewood.==
There is a certain connection between the growth of the modulus of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530139.png" /> and its zeros near the line <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530140.png" />. In particular, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530141.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530142.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530143.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530144.png" /> are positive non-decreasing functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530145.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530146.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530147.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530148.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530149.png" />, then there is a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530150.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530151.png" /> in the region
+
There is a certain connection between the growth of the modulus of $  \zeta ( s) $
 +
and its zeros near the line $  \sigma = 1 $.  
 +
In particular, if $  | \zeta ( s) | \ll  \mathop{\rm exp}  \phi ( t) $
 +
for $  1 - \theta ( t) \leq  \sigma \leq  2 $,  
 +
where $  \phi ( t) $
 +
and $  1/ \theta ( t) $
 +
are positive non-decreasing functions of $  t \geq  0 $
 +
such that $  \theta ( t) \leq  1 $,  
 +
$  \phi ( t) \rightarrow \infty $
 +
as $  t \rightarrow \infty $
 +
and $  \phi ( t)/ \theta ( t) \ll  \mathop{\rm exp}  \phi ( t) $,  
 +
then there is a constant $  A $
 +
such that $  \zeta ( s) \neq 0 $
 +
in the region
  
<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/d/d033/d033530/d033530152.png" /></td> </tr></table>
+
$$
 +
\sigma  \geq  1 -
  
The estimate for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530153.png" /> 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
+
\frac{A \theta ( 2t + 1) }{\phi ( 2t + 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/d/d033/d033530/d033530154.png" /></td> </tr></table>
+
The estimate for  $  \zeta ( s) $
 +
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|Weyl method]], J.E. Littlewood showed in 1921 that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530155.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530156.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530157.png" />, so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530158.png" /> in the region
+
$$
 +
\sum _ {v < n \leq  u }
 +
\mathop{\rm exp} ( it  \mathop{\rm log}  n).
 +
$$
  
<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/d/d033/d033530/d033530159.png" /></td> </tr></table>
+
By estimating such sums by the [[Weyl method|Weyl method]], J.E. Littlewood showed in 1921 that  $  | \zeta ( s) | \ll  \mathop{\rm log}  ^ {5}  t $
 +
if  $  t > A $
 +
and  $  \sigma \geq  1 - \mathop{\rm log}  ^ {2}  \mathop{\rm log}  t/  \mathop{\rm log}  t $,
 +
so that  $  \zeta ( s) \neq 0 $
 +
in the region
 +
 
 +
$$
 +
\sigma  \geq  1 -
 +
 
 +
\frac{A  \mathop{\rm log}  \mathop{\rm log}  t }{ \mathop{\rm log}  t }
 +
.
 +
$$
  
 
It follows that
 
It follows that
  
<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/d/d033/d033530/d033530160.png" /></td> </tr></table>
+
$$
 +
\pi ( x)  = \
 +
\mathop{\rm li}  x + O
 +
( x  \mathop{\rm exp} (- a
 +
\sqrt { \mathop{\rm log}  x  \mathop{\rm log}  \mathop{\rm log}  x } )).
 +
$$
  
 
==The method of Vinogradov.==
 
==The method of Vinogradov.==
A further advance in the estimation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530161.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530162.png" /> 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|Vinogradov method]]). Using this method, he showed in 1938 that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530163.png" /> if
+
A further advance in the estimation of $  \pi ( x) $
 +
and $  \psi ( x) $
 +
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|Vinogradov method]]). Using this method, he showed in 1938 that $  \zeta ( s) \neq 0 $
 +
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/d/d033/d033530/d033530164.png" /></td> </tr></table>
+
$$
 +
\sigma  \geq  1 - {
 +
\frac{c}{ \mathop{\rm log}  ^ {3/4} ( | t | + 2) \
 +
\mathop{\rm log}  ^ {3/4}  \mathop{\rm log} ( | t | + 2) }
 +
} ,
 +
$$
  
 
and consequently that
 
and consequently that
  
<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/d/d033/d033530/d033530165.png" /></td> </tr></table>
+
$$
 +
\pi ( x)  = \
 +
\mathop{\rm li}  x + O
 +
( x  \mathop{\rm exp} (- a \
 +
\mathop{\rm log}  ^ {4/7}  x \
 +
\mathop{\rm log}  ^ {-3/7} \
 +
\mathop{\rm log}  x)).
 +
$$
  
In 1958 Vinogradov and others (see [[#References|[6]]]–[[#References|[11]]]) showed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530166.png" /> if
+
In 1958 Vinogradov and others (see [[#References|[6]]]–[[#References|[11]]]) showed that $  \zeta ( s) \neq 0 $
 +
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/d/d033/d033530/d033530167.png" /></td> </tr></table>
+
$$
 +
\sigma  \geq  1 - {
 +
\frac{c}{ \mathop{\rm log}  ^ {2/3}
 +
( | t | + 2) \
 +
\mathop{\rm log}  ^ {1/3}  \mathop{\rm log}
 +
( | t | + 2) }
 +
} .
 +
$$
  
So far (1983) this is the best result concerning bounds on the non-trivial zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530168.png" />, to which the following best result on the distribution of prime numbers corresponds:
+
So far (1983) this is the best result concerning bounds on the non-trivial zeros of $  \zeta ( s) $,  
 +
to which the following best result on the distribution of prime numbers corresponds:
  
<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/d/d033/d033530/d033530169.png" /></td> </tr></table>
+
$$
 +
\pi ( x)  = \
 +
\mathop{\rm li}  x +
 +
O ( x  \mathop{\rm exp}
 +
(- a  \mathop{\rm log}  ^ {3/5} \
 +
x  \mathop{\rm log}  ^ {-1/5} \
 +
\mathop{\rm log}  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/d/d033/d033530/d033530170.png" /></td> </tr></table>
+
$$
 +
\psi ( x)  = x + O ( x  \mathop{\rm exp} (- b  \mathop{\rm log}  ^ {3/5}  x  \mathop{\rm log}  ^ {-1/5}  \mathop{\rm log}  x)).
 +
$$
  
The asymptotics for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530171.png" />-th prime number, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530172.png" />, follow from the asymptotics of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530173.png" />. It was also shown (see [[#References|[21]]]) that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530174.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530175.png" /> and that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530176.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530177.png" />,
+
The asymptotics for the $  n $-
 +
th prime number, $  p _ {n} \sim n  \mathop{\rm log}  n $,  
 +
follow from the asymptotics of $  \pi ( x) $.  
 +
It was also shown (see [[#References|[21]]]) that $  p _ {n} > n  \mathop{\rm log}  n $
 +
for all $  n \geq  1 $
 +
and that for $  17 \leq  x \leq  e  ^ {100} $,  
 +
$  x \geq  e  ^ {200} $,
  
<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/d/d033/d033530/d033530178.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{x}{ \mathop{\rm log}  x }
 +
< \
 +
\pi ( x)  < \
 +
{
 +
\frac{x}{ \mathop{\rm log}  x - 2 }
 +
} ;
 +
$$
  
and for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530179.png" />,
+
and for $  x \geq  55 $,
  
<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/d/d033/d033530/d033530180.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{x}{ \mathop{\rm log}  x + 2 }
 +
< \
 +
\pi ( x)  < \
 +
{
 +
\frac{x}{ \mathop{\rm log}  x - 4 }
 +
} .
 +
$$
  
 
==Elementary methods.==
 
==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 [[#References|[16]]] and P. Erdös [[#References|[17]]]. It is based on the elementary formula of Selberg
 
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 [[#References|[16]]] and P. Erdös [[#References|[17]]]. It is based on the elementary formula of Selberg
  
<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/d/d033/d033530/d033530181.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>
+
$$ \tag{7 }
 +
\psi ( x)  \mathop{\rm log}  x +
 +
\sum _ {n \leq  x }
 +
\psi \left (
 +
{
 +
\frac{x}{n}
 +
}
 +
\right )
 +
\Lambda ( n)  = \
 +
2x  \mathop{\rm log}  x + O ( x).
 +
$$
  
A further problem consists in obtaining asymptotics for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530182.png" /> from the averaged asymptotics for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530183.png" /> given by (7). It may be done in different ways but all of them employ the fact that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530184.png" /> slowly oscillates. In 1962 E. Bombieri and E. Wirsing proved that
+
A further problem consists in obtaining asymptotics for $  \psi ( x) $
 +
from the averaged asymptotics for $  \psi ( u) $
 +
given by (7). It may be done in different ways but all of them employ the fact that $  \psi ( x) $
 +
slowly oscillates. In 1962 E. Bombieri and E. Wirsing proved that
  
<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/d/d033/d033530/d033530185.png" /></td> </tr></table>
+
$$
 +
\psi ( x)  = \
 +
x + O
 +
( x  \mathop{\rm log}  ^ {-A}  x)
 +
$$
  
for any fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530186.png" />. In 1970, H.G. Diamond and J. Steinig [[#References|[19]]] substantially perfected the principles and techniques of estimation by means of an elementary method. They proved that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530187.png" />,
+
for any fixed $  A > 0 $.  
 +
In 1970, H.G. Diamond and J. Steinig [[#References|[19]]] substantially perfected the principles and techniques of estimation by means of an elementary method. They proved that for $  x \geq  \mathop{\rm exp}  \mathop{\rm exp}  100 $,
  
<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/d/d033/d033530/d033530188.png" /></td> </tr></table>
+
$$
 +
| \psi ( x) - x |  < \
 +
x  \mathop{\rm exp} (- \mathop{\rm log}  ^ {1/7} \
 +
x  \mathop{\rm log}  ^ {-2}  \mathop{\rm log}  x).
 +
$$
  
Finally, in 1973 A.F. Lavrik and A.Sh. Sobirov [[#References|[20]]] showed that an elementary method enables one to prove the following theorem: For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530189.png" />,
+
Finally, in 1973 A.F. Lavrik and A.Sh. Sobirov [[#References|[20]]] showed that an elementary method enables one to prove the following theorem: For $  x \geq  \mathop{\rm exp}  \mathop{\rm exp}  10  ^ {3} $,
  
<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/d/d033/d033530/d033530190.png" /></td> </tr></table>
+
$$
 +
| \psi ( x) - x |  < \
 +
x  \mathop{\rm exp} (- \mathop{\rm log}  ^ {1/6} \
 +
x  \mathop{\rm log}  ^ {-3}  \mathop{\rm log}  x).
 +
$$
  
 
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.
 
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.==
 
==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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530191.png" /> between adjacent prime numbers; the problem on the number of prime twins or, more generally, pairs of prime numbers that differ by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530192.png" /> or, in the most general form, the problem about the number of systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530193.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530194.png" /> prime numbers within the segment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530195.png" />.
+
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 $  d _ {n} = p _ {n + 1 }  - p _ {n} $
 +
between adjacent prime numbers; the problem on the number of prime twins or, more generally, pairs of prime numbers that differ by $  2k $
 +
or, in the most general form, the problem about the number of systems $  p, p + u _ {1} \dots p + u _ {m} $
 +
of  $  m + 1 $
 +
prime numbers within the segment  $  [ 1, x] $.
 +
 
 +
Using Riemann's hypothesis it was proved that  $  d _ {n} \ll  \sqrt {p _ {n} }  \mathop{\rm log}  p _ {n} $,
 +
and heuristic considerations suggest that probably  $  d _ {n} \ll  \mathop{\rm log}  ^ {2}  p _ {n} $.  
 +
By 1983, the best estimate  $  d _ {n} \ll  p _ {n}  ^  \delta  $,
 +
where  $  \delta = ( 7/12) + \epsilon $,
 +
$  \epsilon > 0 $,
 +
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  $  2k $,
 +
$  k = 1, 2 \dots $
 +
it is still (1983) unknown whether the number of such pairs is finite or not. Let  $  \pi _ {k} ( x) $
 +
be the number of prime numbers that do not exceed  $  x $
 +
and differ by  $  2k $.  
 +
In 1919 V. Brun found a sieve method (see [[Brun sieve|Brun sieve]]) that permitted one to obtain the expected upper bound for  $  \pi _ {k} ( x) $:
  
Using Riemann's hypothesis it was proved that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530196.png" />, and heuristic considerations suggest that probably <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530197.png" />. By 1983, the best estimate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530198.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530199.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530200.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530201.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530202.png" /> it is still (1983) unknown whether the number of such pairs is finite or not. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530203.png" /> be the number of prime numbers that do not exceed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530204.png" /> and differ by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530205.png" />. In 1919 V. Brun found a sieve method (see [[Brun sieve|Brun sieve]]) that permitted one to obtain the expected upper bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530206.png" />:
+
$$
 +
\pi _ {k} ( x) \ll  \
 +
{
 +
\frac{x}{ \mathop{\rm log}  ^ {2}  x }
 +
}
 +
\prod _ { p\mid  } k
 +
\left (
 +
1 - {
 +
\frac{1}{p}
 +
}
 +
\right ) ^ {-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/d/d033/d033530/d033530207.png" /></td> </tr></table>
+
In addition to that, it was shown by the [[Circle method|circle method]] (see [[#References|[13]]]) with the help of Vinogradov's estimates for trigonometric sums with prime numbers (see [[Vinogradov method|Vinogradov method]]) that for any fixed  $  A > 1 $,
 +
$  M > 0 $,
  
In addition to that, it was shown by the [[Circle method|circle method]] (see [[#References|[13]]]) with the help of Vinogradov's estimates for trigonometric sums with prime numbers (see [[Vinogradov method|Vinogradov method]]) that for any fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530208.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530209.png" />,
+
$$
 +
\sum _ {1 \leq  2h \leq  x  \mathop{\rm log}  ^ {-A}  x }
 +
\left [
 +
\pi _ {k} ( x) - f ( x)
 +
\prod _ {\begin{array}{c}
 +
p\mid  k \\
 +
p > 2
 +
\end{array}
 +
}
  
<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/d/d033/d033530/d033530210.png" /></td> </tr></table>
+
\frac{p - 1 }{p - 2 }
 +
 
 +
\right ]  ^ {2}  \ll  \
 +
x  ^ {3}  \mathop{\rm log} ^ {- A - M }  x,
 +
$$
  
 
where
 
where
  
<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/d/d033/d033530/d033530211.png" /></td> </tr></table>
+
$$
 +
f ( x)  = 2
 +
\prod _ {p > 2 }
 +
\left ( 1 -
 +
{
 +
\frac{1}{( p - 1)  ^ {2} }
 +
}
 +
\right )
 +
\int\limits _ { 2 } ^ { x }
  
This implies, in particular, that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530212.png" /> the following asymptotic expression for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530213.png" /> holds for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530214.png" /> except for at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530215.png" /> values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530216.png" /> in the range <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530217.png" />:
+
\frac{du }{ \mathop{\rm log}  ^ {2}  u }
 +
.
 +
$$
  
<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/d/d033/d033530/d033530218.png" /></td> </tr></table>
+
This implies, in particular, that for  $  X = x  \mathop{\rm log}  ^ {-A}  x $
 +
the following asymptotic expression for  $  \pi _ {k} ( x) $
 +
holds for all  $  1 \leq  k \leq  X $
 +
except for at most  $  X  \mathop{\rm log}  ^ {-M}  x $
 +
values of  $  k $
 +
in the range  $  1 \leq  k \leq  X $:
  
Similar results are obtained for sets of prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530219.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530220.png" />.
+
$$
 +
\pi _ {k} ( x)  \sim  2
 +
\prod _ {p > 2 }
 +
\left ( 1 -
 +
{
 +
\frac{1}{( p - 1)  ^ {2} }
 +
}
 +
\right )
 +
{
 +
\frac{x}{ \mathop{\rm log}  ^ {2}  x }
 +
}
 +
\prod _ {\begin{array}{c}
 +
p\mid  k \\
 +
p > 2
 +
\end{array}
 +
}
 +
 
 +
\frac{p - 1 }{p - 2 }
 +
.
 +
$$
 +
 
 +
Similar results are obtained for sets of prime numbers $  p, p + u _ {1} \dots p + u _ {m} $
 +
for all $  m \geq  1 $.
  
 
==Prime numbers in arithmetic progressions.==
 
==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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530221.png" />, where the first number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530222.png" /> and the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530223.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530224.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530225.png" /> for prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530226.png" />. To do this he introduced certain arithmetical functions — characters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530227.png" /> (see [[Dirichlet character|Dirichlet character]]) and functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530228.png" /> (see [[Dirichlet L-function|Dirichlet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530229.png" />-function]]), which, like <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530230.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530231.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530232.png" />, serve as a basic means of studying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530233.png" /> and its analogue
+
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 $  dn + l $,  
 +
where the first number $  l $
 +
and the difference d $
 +
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 $  \sum 1/p  ^ {s} \rightarrow \infty $
 +
as $  s \rightarrow 1 + 0 $
 +
for prime numbers $  p \equiv l (  \mathop{\rm mod}  d) $.  
 +
To do this he introduced certain arithmetical functions — characters $  \chi = \chi ( n, d) $(
 +
see [[Dirichlet character|Dirichlet character]]) and functions $  L ( s, \chi ) $(
 +
see [[Dirichlet L-function|Dirichlet $  L $-
 +
function]]), which, like $  \zeta ( s) $
 +
for  $  \pi ( x) $
 +
and  $  \psi ( x) $,
 +
serve as a basic means of studying  $  \pi ( x;  d, l) $
 +
and its analogue
 +
 
 +
$$
 +
\psi ( x;  d, l)  = \
 +
\sum _ {\begin{array}{c}
 +
n \leq  x,
 +
\\
 +
n \equiv l  (  \mathop{\rm mod}  d)
 +
\end{array}
 +
}
 +
\Lambda ( n).
 +
$$
 +
 
 +
For a fixed value of  $  d $,
 +
$  1 \leq  l \leq  d $,
 +
$  ( l, d) = 1 $,
 +
the majority of results indicated above for  $  \pi ( x) $
 +
and  $  \psi ( x) $
 +
carry over to  $  \pi ( x;  d, l) $
 +
and  $  \psi ( x;  d, l) $.  
 +
However, of special interest here are the results for values of  $  d $
 +
that increase with  $  x $,
 +
as these are important in additive number theory and elsewhere. In this case, other significant difficulties arise, connected mostly with estimating  $  d $,
 +
the largest real zero of  $  L ( s, \chi ) $
 +
modulo  $  d $.  
 +
It can be proved using the [[Page theorem|Page theorem]] that for $  1 \leq  d \leq  (  \mathop{\rm log}  x) ^ {2 - \epsilon } $,
 +
$  0 < \epsilon < 1/2 $,
 +
 
 +
$$
 +
\psi ( x;  d, l)  = \
 +
{
 +
\frac{x}{\phi ( d) }
 +
} +
 +
O ( x  \mathop{\rm exp} (- a \
 +
\mathop{\rm log} ^ {\epsilon /3 }  x)),
 +
$$
 +
 
 +
and as a result of C.L. Siegel's bound (1935), for any fixed  $  A > 1 $,
 +
for  $  1 \leq  d \leq  \mathop{\rm log}  ^ {A}  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/d/d033/d033530/d033530234.png" /></td> </tr></table>
+
$$
 +
\psi ( x; d, l)  = \
 +
{
 +
\frac{x}{\phi ( d) }
 +
} +
 +
O ( x  \mathop{\rm exp} (- c _ {1} \sqrt { \mathop{\rm log}  x } )),
 +
$$
  
For a fixed value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530235.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530236.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530237.png" />, the majority of results indicated above for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530238.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530239.png" /> carry over to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530240.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530241.png" />. However, of special interest here are the results for values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530242.png" /> that increase with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530243.png" />, as these are important in additive number theory and elsewhere. In this case, other significant difficulties arise, connected mostly with estimating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530244.png" />, the largest real zero of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530245.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530246.png" />. It can be proved using the [[Page theorem|Page theorem]] that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530247.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530248.png" />,
+
where  $  \phi ( d) $
 +
is the Euler  $  \phi $-
 +
function, $  a $
 +
is a positive constant and $  c _ {1} = c _ {1} ( A) $
 +
is an ineffective constant  $  > 0 $,  
 +
that is, $  c _ {1} $
 +
cannot be computed for given  $  A $.
  
<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/d/d033/d033530/d033530249.png" /></td> </tr></table>
+
If the extended Riemann hypothesis (cf. [[Riemann hypotheses|Riemann hypotheses]]) is true, then for  $  d \leq  x $,
  
and as a result of C.L. Siegel's bound (1935), for any fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530250.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530251.png" />,
+
$$
 +
\psi ( x;  d, l)  = \
 +
{
 +
\frac{x}{\phi ( d) }
 +
} +
 +
O ( \sqrt x  \mathop{\rm log}  ^ {2}  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/d/d033/d033530/d033530252.png" /></td> </tr></table>
+
Thus, up till 1983 it has been proved that the prime numbers are uniformly distributed over all  $  \phi ( d) $
 +
progressions  $  1 \leq  l \leq  d $,
 +
$  ( l, d) = 1 $,
 +
of difference  $  d $
 +
only for  $  d \leq  \mathop{\rm log}  ^ {A}  x $.
 +
As far as segments of progressions  $  dn + l \leq  x $
 +
are concerned, for example with  $  d = x  ^  \epsilon  $
 +
for any  $  \epsilon > 0 $,
 +
it does not even follow from the above that such a progression contains at least one prime number.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530253.png" /> is the Euler <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530254.png" />-function, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530255.png" /> is a positive constant and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530256.png" /> is an ineffective constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530257.png" />, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530258.png" /> cannot be computed for given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530259.png" />.
+
The sieve method of Brun, like the modification suggested by Selberg in 1947, shows that for all  $  1 \leq  d < x $,
 +
$  1 \leq  l \leq  d $,  
 +
$  ( l, d) = 1 $,
 +
there is an upper bound
  
If the extended Riemann hypothesis (cf. [[Riemann hypotheses|Riemann hypotheses]]) is true, then for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530260.png" />,
+
$$
 +
\pi ( x;  d, l)  \ll  \
  
<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/d/d033/d033530/d033530261.png" /></td> </tr></table>
+
\frac{Cx }{\phi ( d)  \mathop{\rm log}  {
 +
\frac{x}{d}
 +
} }
 +
,
 +
$$
  
Thus, up till 1983 it has been proved that the prime numbers are uniformly distributed over all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530262.png" /> progressions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530263.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530264.png" />, of difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530265.png" /> only for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530266.png" />. As far as segments of progressions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530267.png" /> are concerned, for example with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530268.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530269.png" />, it does not even follow from the above that such a progression contains at least one prime number.
+
with absolute constant  $  C $,  
 +
but no lower bounds for  $  \pi ( x;  d, l) $
 +
are obtainable by these methods.
  
The sieve method of Brun, like the modification suggested by Selberg in 1947, shows that for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530270.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530271.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530272.png" />, there is an upper bound
+
By the Riemann principle for a zero  $  \rho = \beta + i \gamma $
 +
of  $  L ( s, \chi ) $
 +
lying in the strip  $  0 \leq  \sigma \leq  1 $,  
 +
$  \psi ( x;  d, l) $
 +
has 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/d/d033/d033530/d033530273.png" /></td> </tr></table>
+
$$ \tag{8 }
 +
\psi ( x; d, l)  = \
  
with absolute constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530274.png" />, but no lower bounds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530275.png" /> are obtainable by these methods.
+
\frac{\psi ( x) }{\phi ( d) }
 +
+
 +
$$
  
By the Riemann principle for a zero <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530276.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530277.png" /> lying in the strip <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530278.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530279.png" /> has the form
+
$$
 +
- {
 +
\frac{1}{\phi ( d) }
 +
} \left ( \sum _  \chi  {}
 +
\prime \overline \chi \; ( l) \sum _ {| \gamma | \leq  T } {
 +
\frac{x  ^  \rho  } \rho
 +
} + {
 +
\frac{\overline \chi \; ( l) x  ^  \alpha  } \alpha
 +
} \right ) + R,
 +
$$
  
<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/d/d033/d033530/d033530280.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>
+
where the prime on the  $  \sum $
 +
indicates summation over complex  $  \chi $
 +
$  \mathop{\rm mod}  d $,
 +
$  \alpha $
 +
is the real zero of  $  L ( s, \chi ) $
 +
if it exists and is greater than  $  1 - C _ {0} / \mathop{\rm log}  d $,
 +
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/d/d033/d033530/d033530281.png" /></td> </tr></table>
+
$$
 +
R  \ll  xT  ^ {-1} \
 +
\mathop{\rm log}  ^ {2}  dx +
 +
x  ^ {1/4}  \mathop{\rm log}  x,
 +
$$
  
where the prime on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530282.png" /> indicates summation over complex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530283.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530284.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530285.png" /> is the real zero of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530286.png" /> if it exists and is greater than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530287.png" />, and
+
for any  $  T \geq  2 $.
  
<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/d/d033/d033530/d033530288.png" /></td> </tr></table>
+
From (8) one sees that if one disregards the term corresponding to  $  \alpha $,
 +
the remainder term is determined by the double sum and depends also on the real part of  $  \rho $
 +
and on all the  $  L ( x, \chi ) $
 +
with  $  \chi $
 +
$  \mathop{\rm mod}  d $
 +
having a zero  $  \rho $
 +
with  $  \mathop{\rm Re}  \rho = \beta $.
 +
If, for  $  0.5 \leq  \sigma \leq  1 $,
 +
$  N ( \sigma , T, \chi ) $
 +
denotes the number of zeros of  $  L ( s, \chi ) $
 +
in the rectangle  $  \sigma \leq  \mathop{\rm Re}  s \leq  1 $,
 +
$  | t | \leq  T $,
 +
then the problem of estimating the remainder term for  $  \psi ( x; d, l) $
 +
and its mean value is reduced to the problem of estimating the density of the distribution of the zeros of  $  L $-
 +
functions:
  
for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530289.png" />.
+
$$ \tag{9 }
 +
\left .
  
From (8) one sees that if one disregards the term corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530290.png" />, the remainder term is determined by the double sum and depends also on the real part of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530291.png" /> and on all the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530292.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530293.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530294.png" /> having a zero <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530295.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530296.png" />. If, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530297.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530298.png" /> denotes the number of zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530299.png" /> in the rectangle <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530300.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530301.png" />, then the problem of estimating the remainder term for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530302.png" /> and its mean value is reduced to the problem of estimating the density of the distribution of the zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530303.png" />-functions:
+
\begin{array}{c}
 +
N _ {1}  \equiv \
 +
\sum _ {\chi  \mathop{\rm mod}  d } {} \prime
 +
N ( \sigma , T, \chi ), \\
 +
N _ {2}  \equiv \
 +
\sum _ {d \leq  D } \
 +
\sum _ {\chi  \mathop{\rm mod}  d } {} \prime
 +
N ( \sigma , T, \chi ). \\
 +
\end{array}
  
<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/d/d033/d033530/d033530304.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>
+
\right \}
 +
$$
  
Thus, the reduction of various estimates for prime numbers is concerned not so much with the lack of zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530305.png" /> in the critical strip, but with their comparatively rare distribution there.
+
Thus, the reduction of various estimates for prime numbers is concerned not so much with the lack of zeros of $  L ( s, \chi ) $
 +
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|large sieve]] (see [[#References|[22]]], and also [[#References|[14]]], [[#References|[24]]]). Especially important are the theorems on the least prime number in an arithmetic progression, the behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530306.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530307.png" /> on the average for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530308.png" />, and on the double averaging of these functions over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530309.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530310.png" />, and over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530311.png" />.
+
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|large sieve]] (see [[#References|[22]]], and also [[#References|[14]]], [[#References|[24]]]). Especially important are the theorems on the least prime number in an arithmetic progression, the behaviour of $  \pi ( x;  d, l) $
 +
and $  \psi ( x;  d, l) $
 +
on the average for d \leq  D $,  
 +
and on the double averaging of these functions over $  1 \leq  l \leq  d $,
 +
$  ( l, d) = 1 $,  
 +
and over d \leq  D $.
  
Namely, in 1944 Linnik [[#References|[23]]] showed that as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530312.png" /> the sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530313.png" /> in (9) has the bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530314.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530315.png" /> is a constant; from this he deduced the existence of a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530316.png" /> such that any arithmetic progression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530317.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530318.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530319.png" />, contains a prime number less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530320.png" />. The latest estimate of Linnik's constant is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530321.png" />; but if the density hypothesis is correct, i.e. if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530322.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530323.png" />.
+
Namely, in 1944 Linnik [[#References|[23]]] showed that as d \rightarrow \infty $
 +
the sum $  N _ {1} $
 +
in (9) has the bound $  \ll  d ^ {a ( 1 - \sigma ) } $,  
 +
where $  a $
 +
is a constant; from this he deduced the existence of a constant $  c $
 +
such that any arithmetic progression $  dn + l $,
 +
$  1 \leq  l \leq  d $,
 +
$  ( l, d) = 1 $,  
 +
contains a prime number less than d ^ {c} $.  
 +
The latest estimate of Linnik's constant is $  c = 17 $;  
 +
but if the density hypothesis is correct, i.e. if $  N _ {1} \ll  ( dT) ^ {2 ( 1 - \sigma + \epsilon ) } $,  
 +
then $  c = 2 + \epsilon $.
  
In 1965, A.I. Vinogradov and Bombieri independently obtained strong estimates for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530324.png" /> in (9). A more complete method of estimating these sums was found by H. Montgomery (1969). One of the results on estimating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530325.png" /> is the following result on the average distribution of prime numbers in arithmetic progressions:
+
In 1965, A.I. Vinogradov and Bombieri independently obtained strong estimates for $  N _ {2} $
 +
in (9). A more complete method of estimating these sums was found by H. Montgomery (1969). One of the results on estimating $  N _ {2} $
 +
is the following result on the average distribution of prime numbers in arithmetic progressions:
  
<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/d/d033/d033530/d033530326.png" /></td> </tr></table>
+
$$
 +
\sum _ {d \leq  \sqrt x  \mathop{\rm log}  ^ {-B}  x }
 +
\max _ {y \leq  x } \
 +
\max _ {( l, d) = 1 } \
 +
\left |
 +
\psi ( y; d, l) -
 +
{
 +
\frac{y}{\phi ( d) }
 +
} \
 +
\right |  \ll  \
 +
x  \mathop{\rm log}  ^ {-A}  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/d/d033/d033530/d033530327.png" /></td> </tr></table>
+
$$
 +
\sum _ {d \leq  \sqrt x  \mathop{\rm log}  ^ {-B}  x } \max _ {y
 +
\leq  x }  \max _ {( l, d) = 1 }  \left | \pi ( y;
 +
d, l) -  
 +
\frac{ \mathop{\rm li}  y }{\phi ( d) }
 +
\right |  \ll  x  \mathop{\rm log}  ^ {-A}  x,
 +
$$
  
for any constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530328.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530329.png" />. These estimates cannot be substantially improved, because the extended Riemann hypothesis implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530330.png" />.
+
for any constant $  A $
 +
and $  B = A + 7/2 $.  
 +
These estimates cannot be substantially improved, because the extended Riemann hypothesis implies that $  B = A + 2 $.
  
Other problems on the distribution of prime numbers are as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530331.png" /> be the number of integers of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530332.png" /> which are products of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530333.png" /> prime numbers. H. Richert (1953) proved that
+
Other problems on the distribution of prime numbers are as follows. Let $  \pi _  \nu  ( x;  d, l) $
 +
be the number of integers of the form $  dn + l \leq  x $
 +
which are products of $  \nu $
 +
prime numbers. H. Richert (1953) proved that
  
<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/d/d033/d033530/d033530334.png" /></td> </tr></table>
+
$$
 +
\pi _  \nu  ( x; d, l) =
 +
$$
  
<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/d/d033/d033530/d033530335.png" /></td> </tr></table>
+
$$
 +
= \
 +
{
 +
\frac{1}{\phi ( d) }
 +
} \sum _ {m = 0 } ^ { {r }  ( x) }  \sum _
 +
{h = 0 } ^ {  \nu  - 1 } A _  \nu  ( h, m, d) \int\limits _ { 2 } ^ { 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/d/d033/d033530/d033530336.png" /></td> </tr></table>
+
\frac{ \mathop{\rm log}  ^ {h}  \mathop{\rm log}  u }{ \mathop{\rm log} ^ {m + 1 }  u }
 +
  du +
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530337.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530338.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530339.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530340.png" />, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530341.png" /> are determined by series depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530342.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530343.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530344.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530345.png" />.
+
$$
 +
+
 +
O ( x  \mathop{\rm exp} (- r ( x))) + O \left ( x ^ {1 -
 +
1/bd  ^  \epsilon  }
 +
\frac{ \mathop{\rm log} ^ {\nu - 1 }  d   \mathop{\rm log} ^
 +
{\nu - 1 }  \mathop{\rm log}  x }{\phi ( d)  \mathop{\rm log}  x }
 +
\right ) ,
 +
$$
  
E. Landau (1903–1918) carried over certain results on the distribution of prime numbers to algebraic number fields. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530346.png" /> be an algebraic number field of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530347.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530348.png" /> be the number of prime ideals in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530349.png" /> with norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530350.png" />. Then
+
where  $  r ( x) = c \sqrt { \mathop{\rm log}  x } $,
 +
$  c \geq  20 $,
 +
$  b = b ( \epsilon ) $,
 +
$  \epsilon > 0 $,
 +
and the $  A ( h, m, d) $
 +
are determined by series depending on  $  h $,
 +
$  m $,
 +
d $,
 +
and  $  \nu $.
  
<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/d/d033/d033530/d033530351.png" /></td> </tr></table>
+
E. Landau (1903–1918) carried over certain results on the distribution of prime numbers to algebraic number fields. Let  $  K $
 +
be an algebraic number field of degree  $  n $
 +
and let  $  \pi ( x;  K) $
 +
be the number of prime ideals in  $  K $
 +
with norm  $  \leq  x $.  
 +
Then
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530352.png" /> is an absolute positive constant, and
+
$$
 +
\pi ( x;  K)  = \
 +
\mathop{\rm li}  x + O
 +
\left (
 +
x  \mathop{\rm exp}
 +
\left (
 +
- {
 +
\frac{c}{\sqrt n }
 +
}
 +
\sqrt { \mathop{\rm log}  x }
 +
\right ) \right ) ,
 +
$$
  
<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/d/d033/d033530/d033530353.png" /></td> </tr></table>
+
where  $  c $
 +
is an absolute positive constant, and
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530354.png" /> is the negation of the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530355.png" /> (small).
+
$$
 +
\pi ( x) -  \mathop{\rm li}  x  = \
 +
\pm  \Omega
  
Much studied is the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530356.png" /> denoting the amount of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530357.png" /> not containing prime divisors less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530358.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530359.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530360.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530361.png" />, 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 [[#References|[15]]]).
+
\frac{\sqrt x }{ \mathop{\rm log}  x }
 +
\
 +
\mathop{\rm log}  \mathop{\rm log}  \mathop{\rm log}  x,
 +
$$
  
====References====
+
where $ \Omega $
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> L. Euler,  "Einleitung in die Analysis des Unendlichen" , Springer (1983)  (Translated from Latin)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  P.L. Chebyshev,  "Oeuvres de P.L. Tchebycheff" , '''1–2''' , Chelsea  (1961)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  B. Riemann,  "Werke" , Teubner  (1892)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.E. Ingham,  "The distribution of prime numbers" , Cambridge Univ. Press  (1932)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A.I. Vinogradov,  "Selected works" , Springer  (1985)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  I.M. Vinogradov,  "A new estimate of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530362.png" />"  ''Izv. Akad. Nauk SSSR Ser. Mat.'' , '''22''' :  2  (1958)  pp. 161–164  (In Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  I.M. Vinogradov,  "The method of trigonometric sums in the theory of numbers" , Interscience  (1954)  (Translated from Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  E.C. Titchmarsh,  "The theory of the Riemann zeta-function" , Clarendon Press  (1951)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  K. Prachar,  "Primzahlverteilung" , Springer  (1957)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  A.A. Karatsuba,  "Fundamentals of analytic number theory" , Moscow  (1975)  (In Russian)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  N.G. Chudakov,  "Introductions to the theory of Dirichlet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530363.png" />-functions" , Moscow-Leningrad  (1947)  (In Russian)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  H. Davenport,  "Multiplicative number theory" , Springer  (1980)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  H. Halberstam,  H.-E. Richert,  "Sieve methods" , Acad. Press  (1974)</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  A. Selberg,  "An elementary proof of the prime-number theorem"  ''Ann. of Math.'' , '''50'''  (1949)  pp. 305–313</TD></TR><TR><TD valign="top">[17]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[18]</TD> <TD valign="top">  A.F. Lavrik,  "Survey address" , ''Internat. Conf. on Number Theory'' , Moscow  (1981)  (In Russian)</TD></TR><TR><TD valign="top">[19]</TD> <TD valign="top">  H.G. Diamond,  J. Steinig,  "An elementary proof of the prime number theorem with a remainder term"  ''Indag. Math.'' , '''11'''  (1970)  pp. 199–258</TD></TR><TR><TD valign="top">[20]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[21]</TD> <TD valign="top">  B. Rosser,  "The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530364.png" />-th prime is greater than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530365.png" />"  ''Proc. London Math. Soc. (2)'' , '''45'''  (1939)  pp. 21–44</TD></TR><TR><TD valign="top">[22]</TD> <TD valign="top">  Yu.V. Linnik,  "The large sieve"  ''Dokl. Akad. Nauk SSSR'' , '''30''' :  4  (1941)  pp. 292–294  (In Russian)</TD></TR><TR><TD valign="top">[23]</TD> <TD valign="top">  Yu.V. Linnik,  "On the least prime in an arithmetic progression I. The basic theorem"  ''Mat. Sb.'' , '''15'''  (1944)  pp. 139–178  (In Russian)</TD></TR><TR><TD valign="top">[24]</TD> <TD valign="top">  A.F. Lavrik,  "A survey of Linnik's large sieve and the density theory of zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530366.png" />-functions"  ''Russian Math. Surveys'' , '''15''' : 2 (1980) pp. 63–76  ''Uspekhi Mat. Nauk'' , '''35''' :  2  (1980)  pp. 55–65</TD></TR></table>
+
is the negation of the symbol $ o $(
 +
small).
  
 +
Much studied is the function  $  F ( x, y) $
 +
denoting the amount of natural numbers  $  \leq  x $
 +
not containing prime divisors less than  $  y $.
 +
For  $  y = x ^ {1/ \xi } $
 +
and  $  \xi = \xi ( x) \rightarrow \infty $
 +
as  $  x \rightarrow \infty $,
 +
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 [[#References|[15]]]).
  
 +
====References====
 +
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L. Euler,  "Einleitung in die Analysis des Unendlichen" , Springer  (1983)  (Translated from Latin)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  P.L. Chebyshev,  "Oeuvres de P.L. Tchebycheff" , '''1–2''' , Chelsea  (1961)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  B. Riemann,  "Werke" , Teubner  (1892)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.E. Ingham,  "The distribution of prime numbers" , Cambridge Univ. Press  (1932)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A.I. Vinogradov,  "Selected works" , Springer  (1985)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  I.M. Vinogradov,  "A new estimate of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530362.png" />"  ''Izv. Akad. Nauk SSSR Ser. Mat.'' , '''22''' :  2  (1958)  pp. 161–164  (In Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  I.M. Vinogradov,  "The method of trigonometric sums in the theory of numbers" , Interscience  (1954)  (Translated from Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  E.C. Titchmarsh,  "The theory of the Riemann zeta-function" , Clarendon Press  (1951)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  K. Prachar,  "Primzahlverteilung" , Springer  (1957)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  A.A. Karatsuba,  "Fundamentals of analytic number theory" , Moscow  (1975)  (In Russian)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  N.G. Chudakov,  "Introductions to the theory of Dirichlet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530363.png" />-functions" , Moscow-Leningrad  (1947)  (In Russian)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  H. Davenport,  "Multiplicative number theory" , Springer  (1980)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  H. Halberstam,  H.-E. Richert,  "Sieve methods" , Acad. Press  (1974)</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  A. Selberg,  "An elementary proof of the prime-number theorem"  ''Ann. of Math.'' , '''50'''  (1949)  pp. 305–313</TD></TR><TR><TD valign="top">[17]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[18]</TD> <TD valign="top">  A.F. Lavrik,  "Survey address" , ''Internat. Conf. on Number Theory'' , Moscow  (1981)  (In Russian)</TD></TR><TR><TD valign="top">[19]</TD> <TD valign="top">  H.G. Diamond,  J. Steinig,  "An elementary proof of the prime number theorem with a remainder term"  ''Indag. Math.'' , '''11'''  (1970)  pp. 199–258</TD></TR><TR><TD valign="top">[20]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[21]</TD> <TD valign="top">  B. Rosser,  "The $n$-th prime is greater than $n \log n$"  ''Proc. London Math. Soc. (2)'' , '''45'''  (1939)  pp. 21–44</TD></TR><TR><TD valign="top">[22]</TD> <TD valign="top">  Yu.V. Linnik,  "The large sieve"  ''Dokl. Akad. Nauk SSSR'' , '''30''' :  4  (1941)  pp. 292–294  (In Russian)</TD></TR><TR><TD valign="top">[23]</TD> <TD valign="top">  Yu.V. Linnik,  "On the least prime in an arithmetic progression I. The basic theorem"  ''Mat. Sb.'' , '''15'''  (1944)  pp. 139–178  (In Russian)</TD></TR><TR><TD valign="top">[24]</TD> <TD valign="top">  A.F. Lavrik,  "A survey of Linnik's large sieve and the density theory of zeros of L-functions"  ''Russian Math. Surveys'' , '''15''' :  2  (1980)  pp. 63–76  ''Uspekhi Mat. Nauk'' , '''35''' :  2  (1980)  pp. 55–65</TD></TR></table>
  
 
====Comments====
 
====Comments====
In formula (7) above, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530367.png" /> is the (von) [[Mangoldt function|Mangoldt function]], which has the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530368.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530369.png" /> is a prime power <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530370.png" /> and is zero otherwise.
+
In formula (7) above, $  \Lambda ( n) $
 +
is the (von) [[Mangoldt function|Mangoldt function]], which has the value $  \mathop{\rm log}  p $
 +
if $  n $
 +
is a prime power $  p  ^ {m} $
 +
and is zero otherwise.
  
 
Concerning estimates of trigonometric sums see also [[Trigonometric sums, method of|Trigonometric sums, method of]].
 
Concerning estimates of trigonometric sums see also [[Trigonometric sums, method of|Trigonometric sums, method of]].
  
Some more facts. Although numerical tables do not suggest it, the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530371.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530372.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530373.png" />. The largest known prime twin is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530374.png" /> (W. Keller, 1983).
+
Some more facts. Although numerical tables do not suggest it, the function $  \pi ( x) -  \mathop{\rm li} ( x) $
 +
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 d _ {n} \ll  p _ {n}  ^  \theta  $
 +
with $  \theta = 11/12 - 1/384 $.  
 +
The largest known prime twin is $  1639494 ( 2  ^ {4423} - 1) \pm  1 $(
 +
W. Keller, 1983).
  
 
Many interesting facts, both computationally and theoretically, on the distribution of primes can be found in [[#References|[a5]]], which is written in an elementary style. For elementary methods one can also consult [[#References|[a1]]]. In [[#References|[a4]]] one finds a simple proof of the prime number theorem.
 
Many interesting facts, both computationally and theoretically, on the distribution of primes can be found in [[#References|[a5]]], which is written in an elementary style. For elementary methods one can also consult [[#References|[a1]]]. In [[#References|[a4]]] one finds a simple proof of the prime number theorem.
  
The fact that there are infinitely many primes (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530375.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530376.png" />) is also known as the [[Euclidean prime number theorem|Euclidean prime number theorem]]. The prime number theorem states that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530377.png" /> is asymptotically equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530378.png" /> (cf. also [[De la Vallée-Poussin theorem|de la Vallée-Poussin theorem]]). The Dirichlet prime number theorem states that there are infinitely many primes in every arithmetic progression (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530379.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033530/d033530380.png" />).
+
The fact that there are infinitely many primes (i.e. $  \pi ( x) \rightarrow \infty $
 +
as $  x \rightarrow \infty $)  
 +
is also known as the [[Euclidean prime number theorem|Euclidean prime number theorem]]. The prime number theorem states that $  \pi ( x) $
 +
is asymptotically equal to $  x (  \mathop{\rm log}  x)  ^ {-1}$(
 +
cf. also [[De la Vallée-Poussin theorem|de la Vallée-Poussin theorem]]). The Dirichlet prime number theorem states that there are infinitely many primes in every arithmetic progression (i.e. $  \pi ( x;  d, l) \rightarrow \infty $
 +
as $  x \rightarrow \infty $).
  
For the result of Bombieri–Vinogradov see also (the references to) [[Density hypothesis|Density hypothesis]].
+
For the result of Bombieri–Vinogradov see also (the references to) [[Density hypothesis]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H.G. Diamond,  "Elementary methods in the study of the distribution of prime numbers"  ''Bull. Amer. Math. Soc.'' , '''7'''  (1982)  pp. 553–589</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W.J. Ellison,  M. Mendès France,  "Les nombres premiers" , Hermann  (1975)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Ivic,  "The Riemann zeta-function" , Wiley  (1985)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.J. Newman,  "Simple analytic proof of the prime number theorem"  ''Amer. Math. Monthly'' , '''87'''  (1980)  pp. 693–696</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  H. Riesel,  "Prime numbers and computer methods for factorisation" , Birkhäuser  (1985)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E. Bombieri,  "La grand crible dans la théorie analytique des nombres"  ''Astérisque'' , '''18'''  (1974)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H.G. Diamond,  "Elementary methods in the study of the distribution of prime numbers"  ''Bull. Amer. Math. Soc.'' , '''7'''  (1982)  pp. 553–589</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W.J. Ellison,  M. Mendès France,  "Les nombres premiers" , Hermann  (1975)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Ivic,  "The Riemann zeta-function" , Wiley  (1985)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.J. Newman,  "Simple analytic proof of the prime number theorem"  ''Amer. Math. Monthly'' , '''87'''  (1980)  pp. 693–696</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  H. Riesel,  "Prime numbers and computer methods for factorisation" , Birkhäuser  (1985)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E. Bombieri,  "La grand crible dans la théorie analytique des nombres"  ''Astérisque'' , '''18'''  (1974)</TD></TR></table>

Latest revision as of 08:29, 14 January 2024


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 $ x \rightarrow \infty $, expression for the function $ \pi ( x) $, which is the number of prime numbers not exceeding $ x $, and for the function $ \pi ( x; d, l) $, which is the number of prime numbers not exceeding $ x $ in the arithmetic progression $ dn + l $, $ 1 \leq l \leq d $, $ n = 1, 2 \dots $ for values of $ d $ increasing along with $ x $.

The fundamental theorem of arithmetic: Any natural number $ n > 1 $ is either a prime number or a unique (up to permutation of factors) product

$$ n = \ p _ {1} ^ {n _ {1} } \dots p _ {k} ^ {n _ {k} } $$

(the so-called canonical representation of $ n $), where $ p _ {1} \dots p _ {k} $ are different prime numbers and $ n _ {1} \dots n _ {k} $ 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 $ \pi ( x) $.

A method used for finding the prime numbers between 1 and $ x $ 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,

$$ \pi ( x) - \pi ( \sqrt x ) + 1 = \ \sum _ { d } (- 1) ^ {\nu ( d) } \left [ { \frac{x}{d} } \right ] , $$

where $ d $ takes the values of the divisors of the product of all prime numbers $ \leq \sqrt x $; $ \nu ( d) $ is the number of prime divisors of $ d $ and $ [ u] $ is the integer part of $ u $, is not very well suited for studying $ \pi ( x) $ as $ x \rightarrow \infty $.

The examination of the sequence of prime numbers between 1 and $ x $:

$$ \tag{1 } 2, 3, 5, 7, 11, 13 \dots p, $$

shows that they get ever sparser on the average as $ x $ increases. There are arbitrarily long segments of the natural series containing no prime number. For instance, the $ n - 1 $ numbers of the form $ n! + 2 \dots n! + n $ are all composite for any $ n \geq 2 $. At the same time, prime numbers that differ by 2, like 8004119 and 8004121, are encountered in (1) (twins). The behaviour of $ \pi ( x) $ as $ x \rightarrow \infty $ is one of the most difficult and inspiring problems of number theory.

The first result about $ \pi ( x) $ is Euclid's theorem: $ \pi ( x) \rightarrow \infty $ as $ x \rightarrow \infty $. L. Euler (1737, 1749, see [1]) introduced the function

$$ \tag{2 } \zeta ( s) = \sum _ {n = 1 } ^ \infty n ^ {-s} $$

and showed that

$$ \tag{3 } \zeta ( s) = \prod _ { p } \left ( 1 - { \frac{1}{p ^ {s} } } \right ) ^ {-1} $$

for $ s > 1 $. 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 $ \sum 1/p $ and the product $ \prod ( 1 - 1/p) ^ {-1} $ diverge over the sequence of prime numbers. This is another proof that the set of prime numbers is infinite. Moreover, Euler proved that

$$ \pi ( x) > \mathop{\rm log} { \frac{x}{e} } , $$

which shows that there are "many" prime numbers, although almost-all natural numbers are composite in the sense that

$$ { \frac{\pi ( x) }{x} } \rightarrow 0 \ \ \textrm{ as } x \rightarrow \infty . $$

A significant success was subsequently obtained by P.L. Chebyshev (1851–1852, see [2]). He proved that

1) for any $ m, M > 0 $ there are sequences $ x, y \rightarrow \infty $ such that

$$ \pi ( x) - \mathop{\rm li} x < \ Mx \mathop{\rm log} ^ {-m} x, $$

$$ \pi ( y) - \mathop{\rm li} y > - My \mathop{\rm log} ^ {-m} y; $$

2) if the quotient $ ( \pi ( x) \mathop{\rm log} x)/x $ converges as $ x \rightarrow \infty $, then the limit is equal to 1.

This solved for the first time the question of the existence of a simple function

$$ \mathop{\rm li} x \equiv \ \int\limits _ { 2 } ^ { x } \frac{du }{ \mathop{\rm log} u } = \ { \frac{x}{ \mathop{\rm log} x } } + \dots + \frac{( r - 1)! x }{ \mathop{\rm log} ^ {r} x } + O \left ( { \frac{x}{ \mathop{\rm log} ^ {r + 1 } x } } \right ) , $$

which approximates $ \pi ( x) $ optimally.

Then Chebyshev established the true order of growth of $ \pi ( x) $, that is, the existence of constants $ a > 0 $ and $ A > 0 $ such that

$$ \tag{4 } a { \frac{x}{ \mathop{\rm log} x } } < \ \pi ( x) < \ A { \frac{x}{ \mathop{\rm log} x } } ; $$

notably, $ a = 0.92 \dots $, $ A = 1.05 \dots $ for $ x \geq x _ {0} $. He also proved that for any $ n \geq 2 $ the interval $ ( n, 2n) $ contains at least one prime number (Bertrand's postulate). The proof of (4) is based on Chebyshev's identity

$$ \tag{5 } F ( x) \equiv \ \mathop{\rm log} [ x]! = \ \sum _ {n \leq x } \psi \left ( { \frac{x}{n} } \right ) , $$

where the function $ \psi $, introduced by Chebyshev, is defined by the sum

$$ \psi ( x) = \ \sum _ {p ^ {m} \leq x } \mathop{\rm log} p = \ \sum _ {n < x } \Delta ( n), $$

taken over all powers $ p ^ {m} $, $ m \in \mathbf N $, of prime numbers $ p $. Namely, if $ x \geq 30 $, the following combination of $ \mathop{\rm log} [ u]! $:

$$ F ^ { * } ( x) = \ F ( x) + F \left ( { \frac{x}{30} } \right ) - F \left ( { \frac{x}{2} } \right ) - F \left ( { \frac{x}{3} } \right ) - F \left ( { \frac{x}{6} } \right ) , $$

owing to (5), gives the identity

$$ F ^ { * } ( x) = \ \psi ( x) - \psi \left ( { \frac{x}{6} } \right ) + \psi \left ( { \frac{x}{7} } \right ) - \psi \left ( { \frac{x}{10} } \right ) + \dots , $$

which implies

$$ \psi ( x) - \psi \left ( { \frac{x}{6} } \right ) < \ F ^ {*} ( x) < \ \psi ( x). $$

By virtue of Stirling's asymptotic formula for $ n! $ this implies an analogue of (4) for $ \psi ( x) $ from which (4) is obtained by partial summation. Chebyshev's function $ \psi ( x) $ proved to be more convenient for studying the distribution of prime numbers than $ \pi ( x) $, since the best approximation for it is the very argument $ x $. Therefore $ \psi ( x) $ is usually considered first and then the corresponding result for $ \pi ( x) $ is obtained by partial summation.

Riemann's principle.

In 1859–1860 B. Riemann [3] considered the function $ \zeta ( s) $, introduced by Euler for $ s > 1 $, as a function of a complex variable $ s = \sigma + it $, where $ \sigma $ and $ t $ are real variables, defined by (2) for $ \sigma > 1 $( 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 $ \pi ( x) - \mathop{\rm li} x $ in terms of $ x $ and those zeros of $ \zeta ( s) $ which belong to the strip $ 0 \leq \sigma \leq 1 $; they are called the non-trivial zeros of $ \zeta ( s) $.

Instead of Riemann's formula, its simpler finite analogue for $ \psi ( x) $, proved (along with Riemann's formula) by H. (von) Mangoldt in 1895, is often used. Namely, for $ x > 1 $:

$$ \tag{6 } \psi ( x) = x - \sum _ {| \gamma | \leq T } { \frac{x ^ \rho } \rho } + O \left ( { \frac{x}{T} } \ \mathop{\rm log} ^ {2} xT + \mathop{\rm log} 2x \right ) , $$

where $ \rho = \rho + i \gamma $ runs through the non-trivial zeros of $ \zeta ( s) $ and $ T \geq 2 $ is arbitrary.

Since

$$ \sum _ {| \gamma | \leq T } { \frac{1} \gamma } \ll \ \mathop{\rm log} ^ {2} T, $$

(6) shows that the difference $ \psi ( x) - x $ is primarily defined by $ \beta $( the real part of the right-most zeros $ \rho $). In particular, the following asymptotic expressions are valid for $ \psi ( x) $ and $ \pi ( x) $:

$$ \psi ( x) = \ x + O ( x ^ \theta \ \mathop{\rm log} ^ {2} x), $$

$$ \pi ( x) = \mathop{\rm li} x + O ( x ^ \theta \mathop{\rm log} x), $$

provided that $ \zeta ( x) \neq 0 $ to the right of a vertical $ \sigma = \theta $, $ 1/2 \leq \theta < 1 $. Conversely, it follows from these relations that $ \zeta ( s) \neq 0 $ if $ \sigma \geq \theta $. If the Riemann hypothesis holds, that is, if all non-trivial zeros of $ \zeta ( s) $ lie on the line $ \sigma = 1/2 $, then the asymptotic distribution law for prime numbers must have the form

$$ \psi ( x) = \ x + O ( \sqrt x \ \mathop{\rm log} ^ {2} x), $$

$$ \pi ( x) = \mathop{\rm li} x + O ( \sqrt x \mathop{\rm log} x), $$

and these relations cannot be substantially strengthened. The latter means that there are sequences $ x, y \rightarrow \infty $ such that

$$ \pi ( x) - \mathop{\rm li} x < \ - \sqrt x \frac{ \mathop{\rm log} \mathop{\rm log} \mathop{\rm log} x }{ \mathop{\rm log} \mathop{\rm log} x } , $$

$$ \pi ( y) - \mathop{\rm li} y > + y \frac{ \mathop{\rm log} \mathop{\rm log} \mathop{\rm log} y }{ \mathop{\rm log} \mathop{\rm log} y } . $$

Thus, by Riemann's principle, the problem about the asymptotic expressions for $ \psi ( x) $ and $ \pi ( x) $ reduces to that about bounds for the real part of the non-trivial zeros of $ \zeta ( x) $. Till now (1983), however, no constant $ \theta $, $ 1/2 \leq \theta < 1 $, has been found with the condition $ \beta < \theta $. The desired bound for $ \beta $ turns out to be connected with the imaginary part $ \gamma $ of zeros $ \rho $ in such a way that the line $ \sigma = 1 $ is its asymptote.

The methods of Hadamard and de la Vallée-Poussin.

In its simplest form

$$ \lim\limits _ {x \rightarrow \infty } \ { \frac{\pi ( x) \mathop{\rm log} x }{x} } = \ \lim\limits _ {x \rightarrow \infty } \ { \frac{\psi ( x) }{x} } = 1 $$

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 $ \zeta ( 1 + it) \neq 0 $, that is, there is no zero of $ \zeta ( s) $ on the line $ \sigma = 1 $. In 1899 de la Vallée-Poussin showed that $ \zeta ( \sigma + it) \neq 0 $ in the domain $ \sigma \geq 1 - c/ \mathop{\rm log} ( | t | + 2) $. It was thereby proved that

$$ \psi ( x) = x + O ( x \mathop{\rm exp} (- a \sqrt { \mathop{\rm log} x } )), $$

$$ \pi ( x) = \mathop{\rm li} x + O ( x \mathop{\rm exp} (- b \sqrt { \mathop{\rm log} x } )) , $$

where $ a, b > 0 $ are constants.

Further extensions of the region containing no zeros of $ \zeta ( s) $ were also obtained (see [4][12]).

The method of Weyl–Littlewood.

There is a certain connection between the growth of the modulus of $ \zeta ( s) $ and its zeros near the line $ \sigma = 1 $. In particular, if $ | \zeta ( s) | \ll \mathop{\rm exp} \phi ( t) $ for $ 1 - \theta ( t) \leq \sigma \leq 2 $, where $ \phi ( t) $ and $ 1/ \theta ( t) $ are positive non-decreasing functions of $ t \geq 0 $ such that $ \theta ( t) \leq 1 $, $ \phi ( t) \rightarrow \infty $ as $ t \rightarrow \infty $ and $ \phi ( t)/ \theta ( t) \ll \mathop{\rm exp} \phi ( t) $, then there is a constant $ A $ such that $ \zeta ( s) \neq 0 $ in the region

$$ \sigma \geq 1 - \frac{A \theta ( 2t + 1) }{\phi ( 2t + 1) } . $$

The estimate for $ \zeta ( s) $ 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

$$ \sum _ {v < n \leq u } \mathop{\rm exp} ( it \mathop{\rm log} n). $$

By estimating such sums by the Weyl method, J.E. Littlewood showed in 1921 that $ | \zeta ( s) | \ll \mathop{\rm log} ^ {5} t $ if $ t > A $ and $ \sigma \geq 1 - \mathop{\rm log} ^ {2} \mathop{\rm log} t/ \mathop{\rm log} t $, so that $ \zeta ( s) \neq 0 $ in the region

$$ \sigma \geq 1 - \frac{A \mathop{\rm log} \mathop{\rm log} t }{ \mathop{\rm log} t } . $$

It follows that

$$ \pi ( x) = \ \mathop{\rm li} x + O ( x \mathop{\rm exp} (- a \sqrt { \mathop{\rm log} x \mathop{\rm log} \mathop{\rm log} x } )). $$

The method of Vinogradov.

A further advance in the estimation of $ \pi ( x) $ and $ \psi ( x) $ 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 $ \zeta ( s) \neq 0 $ if

$$ \sigma \geq 1 - { \frac{c}{ \mathop{\rm log} ^ {3/4} ( | t | + 2) \ \mathop{\rm log} ^ {3/4} \mathop{\rm log} ( | t | + 2) } } , $$

and consequently that

$$ \pi ( x) = \ \mathop{\rm li} x + O ( x \mathop{\rm exp} (- a \ \mathop{\rm log} ^ {4/7} x \ \mathop{\rm log} ^ {-3/7} \ \mathop{\rm log} x)). $$

In 1958 Vinogradov and others (see [6][11]) showed that $ \zeta ( s) \neq 0 $ if

$$ \sigma \geq 1 - { \frac{c}{ \mathop{\rm log} ^ {2/3} ( | t | + 2) \ \mathop{\rm log} ^ {1/3} \mathop{\rm log} ( | t | + 2) } } . $$

So far (1983) this is the best result concerning bounds on the non-trivial zeros of $ \zeta ( s) $, to which the following best result on the distribution of prime numbers corresponds:

$$ \pi ( x) = \ \mathop{\rm li} x + O ( x \mathop{\rm exp} (- a \mathop{\rm log} ^ {3/5} \ x \mathop{\rm log} ^ {-1/5} \ \mathop{\rm log} x)), $$

$$ \psi ( x) = x + O ( x \mathop{\rm exp} (- b \mathop{\rm log} ^ {3/5} x \mathop{\rm log} ^ {-1/5} \mathop{\rm log} x)). $$

The asymptotics for the $ n $- th prime number, $ p _ {n} \sim n \mathop{\rm log} n $, follow from the asymptotics of $ \pi ( x) $. It was also shown (see [21]) that $ p _ {n} > n \mathop{\rm log} n $ for all $ n \geq 1 $ and that for $ 17 \leq x \leq e ^ {100} $, $ x \geq e ^ {200} $,

$$ { \frac{x}{ \mathop{\rm log} x } } < \ \pi ( x) < \ { \frac{x}{ \mathop{\rm log} x - 2 } } ; $$

and for $ x \geq 55 $,

$$ { \frac{x}{ \mathop{\rm log} x + 2 } } < \ \pi ( x) < \ { \frac{x}{ \mathop{\rm log} x - 4 } } . $$

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

$$ \tag{7 } \psi ( x) \mathop{\rm log} x + \sum _ {n \leq x } \psi \left ( { \frac{x}{n} } \right ) \Lambda ( n) = \ 2x \mathop{\rm log} x + O ( x). $$

A further problem consists in obtaining asymptotics for $ \psi ( x) $ from the averaged asymptotics for $ \psi ( u) $ given by (7). It may be done in different ways but all of them employ the fact that $ \psi ( x) $ slowly oscillates. In 1962 E. Bombieri and E. Wirsing proved that

$$ \psi ( x) = \ x + O ( x \mathop{\rm log} ^ {-A} x) $$

for any fixed $ A > 0 $. 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 $ x \geq \mathop{\rm exp} \mathop{\rm exp} 100 $,

$$ | \psi ( x) - x | < \ x \mathop{\rm exp} (- \mathop{\rm log} ^ {1/7} \ x \mathop{\rm log} ^ {-2} \mathop{\rm log} x). $$

Finally, in 1973 A.F. Lavrik and A.Sh. Sobirov [20] showed that an elementary method enables one to prove the following theorem: For $ x \geq \mathop{\rm exp} \mathop{\rm exp} 10 ^ {3} $,

$$ | \psi ( x) - x | < \ x \mathop{\rm exp} (- \mathop{\rm log} ^ {1/6} \ x \mathop{\rm log} ^ {-3} \mathop{\rm log} x). $$

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 $ d _ {n} = p _ {n + 1 } - p _ {n} $ between adjacent prime numbers; the problem on the number of prime twins or, more generally, pairs of prime numbers that differ by $ 2k $ or, in the most general form, the problem about the number of systems $ p, p + u _ {1} \dots p + u _ {m} $ of $ m + 1 $ prime numbers within the segment $ [ 1, x] $.

Using Riemann's hypothesis it was proved that $ d _ {n} \ll \sqrt {p _ {n} } \mathop{\rm log} p _ {n} $, and heuristic considerations suggest that probably $ d _ {n} \ll \mathop{\rm log} ^ {2} p _ {n} $. By 1983, the best estimate $ d _ {n} \ll p _ {n} ^ \delta $, where $ \delta = ( 7/12) + \epsilon $, $ \epsilon > 0 $, 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 $ 2k $, $ k = 1, 2 \dots $ it is still (1983) unknown whether the number of such pairs is finite or not. Let $ \pi _ {k} ( x) $ be the number of prime numbers that do not exceed $ x $ and differ by $ 2k $. In 1919 V. Brun found a sieve method (see Brun sieve) that permitted one to obtain the expected upper bound for $ \pi _ {k} ( x) $:

$$ \pi _ {k} ( x) \ll \ { \frac{x}{ \mathop{\rm log} ^ {2} x } } \prod _ { p\mid } k \left ( 1 - { \frac{1}{p} } \right ) ^ {-1} . $$

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 $ A > 1 $, $ M > 0 $,

$$ \sum _ {1 \leq 2h \leq x \mathop{\rm log} ^ {-A} x } \left [ \pi _ {k} ( x) - f ( x) \prod _ {\begin{array}{c} p\mid k \\ p > 2 \end{array} } \frac{p - 1 }{p - 2 } \right ] ^ {2} \ll \ x ^ {3} \mathop{\rm log} ^ {- A - M } x, $$

where

$$ f ( x) = 2 \prod _ {p > 2 } \left ( 1 - { \frac{1}{( p - 1) ^ {2} } } \right ) \int\limits _ { 2 } ^ { x } \frac{du }{ \mathop{\rm log} ^ {2} u } . $$

This implies, in particular, that for $ X = x \mathop{\rm log} ^ {-A} x $ the following asymptotic expression for $ \pi _ {k} ( x) $ holds for all $ 1 \leq k \leq X $ except for at most $ X \mathop{\rm log} ^ {-M} x $ values of $ k $ in the range $ 1 \leq k \leq X $:

$$ \pi _ {k} ( x) \sim 2 \prod _ {p > 2 } \left ( 1 - { \frac{1}{( p - 1) ^ {2} } } \right ) { \frac{x}{ \mathop{\rm log} ^ {2} x } } \prod _ {\begin{array}{c} p\mid k \\ p > 2 \end{array} } \frac{p - 1 }{p - 2 } . $$

Similar results are obtained for sets of prime numbers $ p, p + u _ {1} \dots p + u _ {m} $ for all $ m \geq 1 $.

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 $ dn + l $, where the first number $ l $ and the difference $ d $ 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 $ \sum 1/p ^ {s} \rightarrow \infty $ as $ s \rightarrow 1 + 0 $ for prime numbers $ p \equiv l ( \mathop{\rm mod} d) $. To do this he introduced certain arithmetical functions — characters $ \chi = \chi ( n, d) $( see Dirichlet character) and functions $ L ( s, \chi ) $( see Dirichlet $ L $- function), which, like $ \zeta ( s) $ for $ \pi ( x) $ and $ \psi ( x) $, serve as a basic means of studying $ \pi ( x; d, l) $ and its analogue

$$ \psi ( x; d, l) = \ \sum _ {\begin{array}{c} n \leq x, \\ n \equiv l ( \mathop{\rm mod} d) \end{array} } \Lambda ( n). $$

For a fixed value of $ d $, $ 1 \leq l \leq d $, $ ( l, d) = 1 $, the majority of results indicated above for $ \pi ( x) $ and $ \psi ( x) $ carry over to $ \pi ( x; d, l) $ and $ \psi ( x; d, l) $. However, of special interest here are the results for values of $ d $ that increase with $ x $, as these are important in additive number theory and elsewhere. In this case, other significant difficulties arise, connected mostly with estimating $ d $, the largest real zero of $ L ( s, \chi ) $ modulo $ d $. It can be proved using the Page theorem that for $ 1 \leq d \leq ( \mathop{\rm log} x) ^ {2 - \epsilon } $, $ 0 < \epsilon < 1/2 $,

$$ \psi ( x; d, l) = \ { \frac{x}{\phi ( d) } } + O ( x \mathop{\rm exp} (- a \ \mathop{\rm log} ^ {\epsilon /3 } x)), $$

and as a result of C.L. Siegel's bound (1935), for any fixed $ A > 1 $, for $ 1 \leq d \leq \mathop{\rm log} ^ {A} x $,

$$ \psi ( x; d, l) = \ { \frac{x}{\phi ( d) } } + O ( x \mathop{\rm exp} (- c _ {1} \sqrt { \mathop{\rm log} x } )), $$

where $ \phi ( d) $ is the Euler $ \phi $- function, $ a $ is a positive constant and $ c _ {1} = c _ {1} ( A) $ is an ineffective constant $ > 0 $, that is, $ c _ {1} $ cannot be computed for given $ A $.

If the extended Riemann hypothesis (cf. Riemann hypotheses) is true, then for $ d \leq x $,

$$ \psi ( x; d, l) = \ { \frac{x}{\phi ( d) } } + O ( \sqrt x \mathop{\rm log} ^ {2} x). $$

Thus, up till 1983 it has been proved that the prime numbers are uniformly distributed over all $ \phi ( d) $ progressions $ 1 \leq l \leq d $, $ ( l, d) = 1 $, of difference $ d $ only for $ d \leq \mathop{\rm log} ^ {A} x $. As far as segments of progressions $ dn + l \leq x $ are concerned, for example with $ d = x ^ \epsilon $ for any $ \epsilon > 0 $, 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 $ 1 \leq d < x $, $ 1 \leq l \leq d $, $ ( l, d) = 1 $, there is an upper bound

$$ \pi ( x; d, l) \ll \ \frac{Cx }{\phi ( d) \mathop{\rm log} { \frac{x}{d} } } , $$

with absolute constant $ C $, but no lower bounds for $ \pi ( x; d, l) $ are obtainable by these methods.

By the Riemann principle for a zero $ \rho = \beta + i \gamma $ of $ L ( s, \chi ) $ lying in the strip $ 0 \leq \sigma \leq 1 $, $ \psi ( x; d, l) $ has the form

$$ \tag{8 } \psi ( x; d, l) = \ \frac{\psi ( x) }{\phi ( d) } + $$

$$ - { \frac{1}{\phi ( d) } } \left ( \sum _ \chi {} \prime \overline \chi \; ( l) \sum _ {| \gamma | \leq T } { \frac{x ^ \rho } \rho } + { \frac{\overline \chi \; ( l) x ^ \alpha } \alpha } \right ) + R, $$

where the prime on the $ \sum $ indicates summation over complex $ \chi $ $ \mathop{\rm mod} d $, $ \alpha $ is the real zero of $ L ( s, \chi ) $ if it exists and is greater than $ 1 - C _ {0} / \mathop{\rm log} d $, and

$$ R \ll xT ^ {-1} \ \mathop{\rm log} ^ {2} dx + x ^ {1/4} \mathop{\rm log} x, $$

for any $ T \geq 2 $.

From (8) one sees that if one disregards the term corresponding to $ \alpha $, the remainder term is determined by the double sum and depends also on the real part of $ \rho $ and on all the $ L ( x, \chi ) $ with $ \chi $ $ \mathop{\rm mod} d $ having a zero $ \rho $ with $ \mathop{\rm Re} \rho = \beta $. If, for $ 0.5 \leq \sigma \leq 1 $, $ N ( \sigma , T, \chi ) $ denotes the number of zeros of $ L ( s, \chi ) $ in the rectangle $ \sigma \leq \mathop{\rm Re} s \leq 1 $, $ | t | \leq T $, then the problem of estimating the remainder term for $ \psi ( x; d, l) $ and its mean value is reduced to the problem of estimating the density of the distribution of the zeros of $ L $- functions:

$$ \tag{9 } \left . \begin{array}{c} N _ {1} \equiv \ \sum _ {\chi \mathop{\rm mod} d } {} \prime N ( \sigma , T, \chi ), \\ N _ {2} \equiv \ \sum _ {d \leq D } \ \sum _ {\chi \mathop{\rm mod} d } {} \prime N ( \sigma , T, \chi ). \\ \end{array} \right \} $$

Thus, the reduction of various estimates for prime numbers is concerned not so much with the lack of zeros of $ L ( s, \chi ) $ 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 $ \pi ( x; d, l) $ and $ \psi ( x; d, l) $ on the average for $ d \leq D $, and on the double averaging of these functions over $ 1 \leq l \leq d $, $ ( l, d) = 1 $, and over $ d \leq D $.

Namely, in 1944 Linnik [23] showed that as $ d \rightarrow \infty $ the sum $ N _ {1} $ in (9) has the bound $ \ll d ^ {a ( 1 - \sigma ) } $, where $ a $ is a constant; from this he deduced the existence of a constant $ c $ such that any arithmetic progression $ dn + l $, $ 1 \leq l \leq d $, $ ( l, d) = 1 $, contains a prime number less than $ d ^ {c} $. The latest estimate of Linnik's constant is $ c = 17 $; but if the density hypothesis is correct, i.e. if $ N _ {1} \ll ( dT) ^ {2 ( 1 - \sigma + \epsilon ) } $, then $ c = 2 + \epsilon $.

In 1965, A.I. Vinogradov and Bombieri independently obtained strong estimates for $ N _ {2} $ in (9). A more complete method of estimating these sums was found by H. Montgomery (1969). One of the results on estimating $ N _ {2} $ is the following result on the average distribution of prime numbers in arithmetic progressions:

$$ \sum _ {d \leq \sqrt x \mathop{\rm log} ^ {-B} x } \max _ {y \leq x } \ \max _ {( l, d) = 1 } \ \left | \psi ( y; d, l) - { \frac{y}{\phi ( d) } } \ \right | \ll \ x \mathop{\rm log} ^ {-A} x, $$

$$ \sum _ {d \leq \sqrt x \mathop{\rm log} ^ {-B} x } \max _ {y \leq x } \max _ {( l, d) = 1 } \left | \pi ( y; d, l) - \frac{ \mathop{\rm li} y }{\phi ( d) } \right | \ll x \mathop{\rm log} ^ {-A} x, $$

for any constant $ A $ and $ B = A + 7/2 $. These estimates cannot be substantially improved, because the extended Riemann hypothesis implies that $ B = A + 2 $.

Other problems on the distribution of prime numbers are as follows. Let $ \pi _ \nu ( x; d, l) $ be the number of integers of the form $ dn + l \leq x $ which are products of $ \nu $ prime numbers. H. Richert (1953) proved that

$$ \pi _ \nu ( x; d, l) = $$

$$ = \ { \frac{1}{\phi ( d) } } \sum _ {m = 0 } ^ { {r } ( x) } \sum _ {h = 0 } ^ { \nu - 1 } A _ \nu ( h, m, d) \int\limits _ { 2 } ^ { x } \frac{ \mathop{\rm log} ^ {h} \mathop{\rm log} u }{ \mathop{\rm log} ^ {m + 1 } u } du + $$

$$ + O ( x \mathop{\rm exp} (- r ( x))) + O \left ( x ^ {1 - 1/bd ^ \epsilon } \frac{ \mathop{\rm log} ^ {\nu - 1 } d \mathop{\rm log} ^ {\nu - 1 } \mathop{\rm log} x }{\phi ( d) \mathop{\rm log} x } \right ) , $$

where $ r ( x) = c \sqrt { \mathop{\rm log} x } $, $ c \geq 20 $, $ b = b ( \epsilon ) $, $ \epsilon > 0 $, and the $ A ( h, m, d) $ are determined by series depending on $ h $, $ m $, $ d $, and $ \nu $.

E. Landau (1903–1918) carried over certain results on the distribution of prime numbers to algebraic number fields. Let $ K $ be an algebraic number field of degree $ n $ and let $ \pi ( x; K) $ be the number of prime ideals in $ K $ with norm $ \leq x $. Then

$$ \pi ( x; K) = \ \mathop{\rm li} x + O \left ( x \mathop{\rm exp} \left ( - { \frac{c}{\sqrt n } } \sqrt { \mathop{\rm log} x } \right ) \right ) , $$

where $ c $ is an absolute positive constant, and

$$ \pi ( x) - \mathop{\rm li} x = \ \pm \Omega \frac{\sqrt x }{ \mathop{\rm log} x } \ \mathop{\rm log} \mathop{\rm log} \mathop{\rm log} x, $$

where $ \Omega $ is the negation of the symbol $ o $( small).

Much studied is the function $ F ( x, y) $ denoting the amount of natural numbers $ \leq x $ not containing prime divisors less than $ y $. For $ y = x ^ {1/ \xi } $ and $ \xi = \xi ( x) \rightarrow \infty $ as $ x \rightarrow \infty $, 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 $n$-th prime is greater than $n \log n$" 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 L-functions" Russian Math. Surveys , 15 : 2 (1980) pp. 63–76 Uspekhi Mat. Nauk , 35 : 2 (1980) pp. 55–65

Comments

In formula (7) above, $ \Lambda ( n) $ is the (von) Mangoldt function, which has the value $ \mathop{\rm log} p $ if $ n $ is a prime power $ p ^ {m} $ 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 $ \pi ( x) - \mathop{\rm li} ( x) $ 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 $ d _ {n} \ll p _ {n} ^ \theta $ with $ \theta = 11/12 - 1/384 $. The largest known prime twin is $ 1639494 ( 2 ^ {4423} - 1) \pm 1 $( 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. $ \pi ( x) \rightarrow \infty $ as $ x \rightarrow \infty $) is also known as the Euclidean prime number theorem. The prime number theorem states that $ \pi ( x) $ is asymptotically equal to $ x ( \mathop{\rm log} x) ^ {-1}$( 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. $ \pi ( x; d, l) \rightarrow \infty $ as $ x \rightarrow \infty $).

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)
How to Cite This Entry:
Distribution of prime numbers. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Distribution_of_prime_numbers&oldid=36164
This article was adapted from an original article by A.F. Lavrik (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article