In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the prime number theorem (PNT) describes the
asymptotic
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
distribution of the
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by
Jacques Hadamard
Jacques Salomon Hadamard (; 8 December 1865 – 17 October 1963) was a French mathematician who made major contributions in number theory, complex analysis, differential geometry and partial differential equations.
Biography
The son of a teac ...
and
Charles Jean de la Vallée Poussin
Charles-Jean Étienne Gustave Nicolas, baron de la Vallée Poussin (14 August 1866 – 2 March 1962) was a Belgian mathematician. He is best known for proving the prime number theorem.
The king of Belgium ennobled him with the title of baron.
Bi ...
in 1896 using ideas introduced by
Bernhard Riemann
Georg Friedrich Bernhard Riemann (; 17 September 1826 – 20 July 1866) was a German mathematician who made contributions to analysis, number theory, and differential geometry. In the field of real analysis, he is mostly known for the first rig ...
(in particular, the
Riemann zeta function
The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
).
The first such distribution found is , where is the
prime-counting function
In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number ''x''. It is denoted by (''x'') (unrelated to the number ).
History
Of great interest in number theory is t ...
(the number of primes less than or equal to ''N'') and is the
natural logarithm
The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
of . This means that for large enough , the
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
that a random integer not greater than is prime is very close to . Consequently, a random integer with at most digits (for large enough ) is about half as likely to be prime as a random integer with at most digits. For example, among the positive integers of at most 1000 digits, about one in 2300 is prime (), whereas among positive integers of at most 2000 digits, about one in 4600 is prime (). In other words, the average gap between consecutive prime numbers among the first integers is roughly .
Statement
Let be the
prime-counting function
In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number ''x''. It is denoted by (''x'') (unrelated to the number ).
History
Of great interest in number theory is t ...
defined to be the number of primes less than or equal to , for any real number . For example, because there are four prime numbers (2, 3, 5 and 7) less than or equal to 10. The prime number theorem then states that is a good approximation to (where log here means the natural logarithm), in the sense that the
limit
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2019 ...
of the ''quotient'' of the two functions and as increases without bound is 1:
:
known as the asymptotic law of distribution of prime numbers. Using
asymptotic notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
this result can be restated as
:
This notation (and the theorem) does ''not'' say anything about the limit of the ''difference'' of the two functions as increases without bound. Instead, the theorem states that approximates in the sense that the
relative error
The approximation error in a data value is the discrepancy between an exact value and some '' approximation'' to it. This error can be expressed as an absolute error (the numerical amount of the discrepancy) or as a relative error (the absolute e ...
of this approximation approaches 0 as increases without bound.
The prime number theorem is equivalent to the statement that the th prime number satisfies
:
the asymptotic notation meaning, again, that the relative error of this approximation approaches 0 as increases without bound. For example, the th prime number is , and ()log() rounds to , a relative error of about 6.4%.
On the other hand, the following asymptotic relations are logically equivalent:
:
As outlined
below, the prime number theorem is also equivalent to
:
where and are
the first and the second Chebyshev functions respectively, and to
:
where
is the
Mertens function
In number theory, the Mertens function is defined for all positive integers ''n'' as
: M(n) = \sum_^n \mu(k),
where \mu(k) is the Möbius function. The function is named in honour of Franz Mertens. This definition can be extended to positive re ...
.
History of the proof of the asymptotic law of prime numbers
Based on the tables by
Anton Felkel and
Jurij Vega
Baron Jurij Bartolomej Vega (also Veha; la, Georgius Bartholomaei Vecha; german: Georg Freiherr von Vega; born ''Vehovec'', March 23, 1754 – September 26, 1802) was a Slovene mathematician, physicist and artillery officer.
Early life
Bor ...
,
Adrien-Marie Legendre
Adrien-Marie Legendre (; ; 18 September 1752 – 9 January 1833) was a French mathematician who made numerous contributions to mathematics. Well-known and important concepts such as the Legendre polynomials and Legendre transformation are named ...
conjectured in 1797 or 1798 that is approximated by the function , where and are unspecified constants. In the second edition of his book on number theory (1808) he then made a
more precise conjecture, with and .
Carl Friedrich Gauss
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
considered the same question at age 15 or 16 "in the year 1792 or 1793", according to his own recollection in 1849. In 1838
Peter Gustav Lejeune Dirichlet
Johann Peter Gustav Lejeune Dirichlet (; 13 February 1805 – 5 May 1859) was a German mathematician who made deep contributions to number theory (including creating the field of analytic number theory), and to the theory of Fourier series and ...
came up with his own approximating function, the
logarithmic integral
In mathematics, the logarithmic integral function or integral logarithm li(''x'') is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is a ...
(under the slightly different form of a series, which he communicated to Gauss). Both Legendre's and Dirichlet's formulas imply the same conjectured asymptotic equivalence of and stated above, although it turned out that Dirichlet's approximation is considerably better if one considers the differences instead of quotients.
In two papers from 1848 and 1850, the Russian mathematician
Pafnuty Chebyshev
Pafnuty Lvovich Chebyshev ( rus, Пафну́тий Льво́вич Чебышёв, p=pɐfˈnutʲɪj ˈlʲvovʲɪtɕ tɕɪbɨˈʂof) ( – ) was a Russian mathematician and considered to be the founding father of Russian mathematics.
Chebyshe ...
attempted to prove the asymptotic law of distribution of prime numbers. His work is notable for the use of the zeta function , for real values of the argument "", as in works of
Leonhard Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
, as early as 1737. Chebyshev's papers predated Riemann's celebrated memoir of 1859, and he succeeded in proving a slightly weaker form of the asymptotic law, namely, that if the limit as goes to infinity of exists at all, then it is necessarily equal to one. He was able to prove unconditionally that this ratio is bounded above and below by two explicitly given constants near 1, for all sufficiently large . Although Chebyshev's paper did not prove the Prime Number Theorem, his estimates for were strong enough for him to prove
Bertrand's postulate
In number theory, Bertrand's postulate is a theorem stating that for any integer n > 3, there always exists at least one prime number p with
:n < p < 2n - 2.
A less restrictive formulation is: for every , there is always ...
that there exists a prime number between and for any integer .
An important paper concerning the distribution of prime numbers was Riemann's 1859 memoir "
On the Number of Primes Less Than a Given Magnitude
" die Anzahl der Primzahlen unter einer gegebenen " (usual English translation: "On the Number of Primes Less Than a Given Magnitude") is seminal9-page paper by Bernhard Riemann published in the November 1859 edition of the ''Monatsberichte der K ...
", the only paper he ever wrote on the subject. Riemann introduced new ideas into the subject, chiefly that the distribution of prime numbers is intimately connected with the zeros of the analytically extended Riemann zeta function of a complex variable. In particular, it is in this paper that the idea to apply methods of
complex analysis
Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates Function (mathematics), functions of complex numbers. It is helpful in many branches of mathemati ...
to the study of the real function originates. Extending Riemann's ideas, two proofs of the asymptotic law of the distribution of prime numbers were found independently by
Jacques Hadamard
Jacques Salomon Hadamard (; 8 December 1865 – 17 October 1963) was a French mathematician who made major contributions in number theory, complex analysis, differential geometry and partial differential equations.
Biography
The son of a teac ...
and
Charles Jean de la Vallée Poussin
Charles-Jean Étienne Gustave Nicolas, baron de la Vallée Poussin (14 August 1866 – 2 March 1962) was a Belgian mathematician. He is best known for proving the prime number theorem.
The king of Belgium ennobled him with the title of baron.
Bi ...
and appeared in the same year (1896). Both proofs used methods from complex analysis, establishing as a main step of the proof that the
Riemann zeta function
The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
is nonzero for all complex values of the variable that have the form with .
During the 20th century, the theorem of Hadamard and de la Vallée Poussin also became known as the Prime Number Theorem. Several different proofs of it were found, including the "elementary" proofs of
Atle Selberg
Atle Selberg (14 June 1917 – 6 August 2007) was a Norwegian mathematician known for his work in analytic number theory and the theory of automorphic forms, and in particular for bringing them into relation with spectral theory. He was awarde ...
and
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
(1949). Hadamard's and de la Vallée Poussin's original proofs are long and elaborate; later proofs introduced various simplifications through the use of
Tauberian theorems In mathematics, Abelian and Tauberian theorems are theorems giving conditions for two methods of summing divergent series to give the same result, named after Niels Henrik Abel and Alfred Tauber. The original examples are Abel's theorem showing tha ...
but remained difficult to digest. A short proof was discovered in 1980 by the American mathematician
Donald J. Newman.
Newman's proof is arguably the simplest known proof of the theorem, although it is non-elementary in the sense that it uses
Cauchy's integral theorem
In mathematics, the Cauchy integral theorem (also known as the Cauchy–Goursat theorem) in complex analysis, named after Augustin-Louis Cauchy (and Édouard Goursat), is an important statement about line integrals for holomorphic functions in t ...
from complex analysis.
Proof sketch
Here is a sketch of the proof referred to in one of
Terence Tao
Terence Chi-Shen Tao (; born 17 July 1975) is an Australian-American mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes ...
's lectures. Like most proofs of the PNT, it starts out by reformulating the problem in terms of a less intuitive, but better-behaved, prime-counting function. The idea is to count the primes (or a related set such as the set of prime powers) with ''weights'' to arrive at a function with smoother asymptotic behavior. The most common such generalized counting function is the
Chebyshev function
In mathematics, the Chebyshev function is either a scalarising function (Tchebycheff function) or one of two related functions. The first Chebyshev function or is given by
:\vartheta(x)=\sum_ \ln p
where \ln denotes the natural logarithm, ...
, defined by
:
This is sometimes written as
:
where is the
von Mangoldt function
In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive.
Definition
The von Mangold ...
, namely
:
It is now relatively easy to check that the PNT is equivalent to the claim that
:
Indeed, this follows from the easy estimates
:
and (using
big notation) for any ,
:
The next step is to find a useful representation for . Let be the Riemann zeta function. It can be shown that is related to the
von Mangoldt function
In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive.
Definition
The von Mangold ...
, and hence to , via the relation
:
A delicate analysis of this equation and related properties of the zeta function, using the
Mellin transform In mathematics, the Mellin transform is an integral transform that may be regarded as the multiplicative version of the two-sided Laplace transform. This integral transform is closely connected to the theory of Dirichlet series, and is
often used i ...
and
Perron's formula In mathematics, and more particularly in analytic number theory, Perron's formula is a formula due to Oskar Perron to calculate the sum of an arithmetic function, by means of an inverse Mellin transform.
Statement
Let \ be an arithmetic function, a ...
, shows that for non-integer the equation
:
holds, where the sum is over all zeros (trivial and nontrivial) of the zeta function. This striking formula is one of the so-called
explicit formulas of number theory, and is already suggestive of the result we wish to prove, since the term (claimed to be the correct asymptotic order of ) appears on the right-hand side, followed by (presumably) lower-order asymptotic terms.
The next step in the proof involves a study of the zeros of the zeta function. The trivial zeros −2, −4, −6, −8, ... can be handled separately:
:
which vanishes for large . The nontrivial zeros, namely those on the critical strip , can potentially be of an asymptotic order comparable to the main term if , so we need to show that all zeros have real part strictly less than 1.
Non-vanishing on
To do this, we take for granted that is
meromorphic
In the mathematical field of complex analysis, a meromorphic function on an open subset ''D'' of the complex plane is a function that is holomorphic on all of ''D'' ''except'' for a set of isolated points, which are poles of the function. The ...
in the half-plane , and is analytic there except for a simple pole at , and that there is a product formula
:
for . This product formula follows from the existence of unique prime factorization of integers, and shows that is never zero in this region, so that its logarithm is defined there and
:
Write ; then
:
Now observe the identity
:
so that
:
for all . Suppose now that . Certainly is not zero, since has a simple pole at . Suppose that and let tend to 1 from above. Since
has a simple pole at and stays analytic, the left hand side in the previous inequality tends to 0, a contradiction.
Finally, we can conclude that the PNT is heuristically true. To rigorously complete the proof there are still serious technicalities to overcome, due to the fact that the summation over zeta zeros in the explicit formula for does not converge absolutely but only conditionally and in a "principal value" sense. There are several ways around this problem but many of them require rather delicate complex-analytic estimates. Edwards's book provides the details. Another method is to use
Ikehara's Tauberian theorem, though this theorem is itself quite hard to prove. D.J. Newman observed that the full strength of Ikehara's theorem is not needed for the prime number theorem, and one can get away with a special case that is much easier to prove.
Newman's proof of the prime number theorem
D. J. Newman gives a quick proof of the prime number theorem (PNT). The proof is "non-elementary" by virtue of relying on complex analysis, but uses only elementary techniques from a first course in the subject:
Cauchy's integral formula
In mathematics, Cauchy's integral formula, named after Augustin-Louis Cauchy, is a central statement in complex analysis. It expresses the fact that a holomorphic function defined on a disk is completely determined by its values on the boundary ...
,
Cauchy's integral theorem
In mathematics, the Cauchy integral theorem (also known as the Cauchy–Goursat theorem) in complex analysis, named after Augustin-Louis Cauchy (and Édouard Goursat), is an important statement about line integrals for holomorphic functions in t ...
and estimates of complex integrals. Here is a brief sketch of this proof. See
for the complete details.
The proof uses the same preliminaries as in the previous section except instead of the function
, the
Chebyshev function
In mathematics, the Chebyshev function is either a scalarising function (Tchebycheff function) or one of two related functions. The first Chebyshev function or is given by
:\vartheta(x)=\sum_ \ln p
where \ln denotes the natural logarithm, ...
is used, which is obtained by dropping some of the terms from the series for
. It is easy to show that the PNT is equivalent to
. Likewise instead of
the function
is used, which is obtained by dropping some terms in the series for
. The functions
and
differ by a function holomorphic on
. Since, as was shown in the previous section,
has no zeroes on the line
,
has no singularities on
.
One further piece of information needed in Newman's proof, and which is the key to the estimates in his simple method, is that
is bounded. This is proved using an ingenious and easy method due to Chebyshev.
Integration by parts shows how
and
are related. For
,
:
Newman's method proves the PNT by showing the integral
:
converges, and therefore the integrand goes to zero as
, which is the PNT. In general, the convergence of the improper integral does not imply that the integrand goes to zero at infinity, since it may oscillate, but since
is increasing, it is easy to show in this case.
To show the convergence of
, for
let
:
and
where
then
:
which is equal to a function holomorphic on the line
.
The convergence of the integral
, and thus the PNT, is proved by showing that
. This involves change of order of limits since it can be written
and therefore classified as a
Tauberian theorem.
The difference
is expressed using
Cauchy's integral formula
In mathematics, Cauchy's integral formula, named after Augustin-Louis Cauchy, is a central statement in complex analysis. It expresses the fact that a holomorphic function defined on a disk is completely determined by its values on the boundary ...
and then shown to be small for
large by estimating the integrand. Fix
and
such that
is holomorphic in the region where
, and let
be the boundary of this region. Since 0 is in the interior of the region,
Cauchy's integral formula
In mathematics, Cauchy's integral formula, named after Augustin-Louis Cauchy, is a central statement in complex analysis. It expresses the fact that a holomorphic function defined on a disk is completely determined by its values on the boundary ...
gives
:
where
is the factor introduced by Newman, which does not change the integral since
is
entire
Entire may refer to:
* Entire function, a function that is holomorphic on the whole complex plane
* Entire (animal), an indication that an animal is not neutered
* Entire (botany)
This glossary of botanical terms is a list of definitions of ...
and
.
To estimate the integral, break the contour
into two parts,
where
and
. Then
where
. Since
, and hence
, is bounded, let
be an upper bound for the absolute value of
. This bound together with the estimate
for
gives that the first integral in absolute value is
. The integrand over
in the second integral is
entire
Entire may refer to:
* Entire function, a function that is holomorphic on the whole complex plane
* Entire (animal), an indication that an animal is not neutered
* Entire (botany)
This glossary of botanical terms is a list of definitions of ...
, so by
Cauchy's integral theorem
In mathematics, the Cauchy integral theorem (also known as the Cauchy–Goursat theorem) in complex analysis, named after Augustin-Louis Cauchy (and Édouard Goursat), is an important statement about line integrals for holomorphic functions in t ...
, the contour
can be modified to a semicircle of radius
in the left half-plane without changing the integral, and the same argument as for the first integral gives the absolute value of the second integral is
. Finally, letting
, the third integral goes to zero since
and hence
goes to zero on the contour. Combining the two estimates and the limit get
:
This holds for any
so
, and the PNT follows.
Prime-counting function in terms of the logarithmic integral
In a handwritten note on a reprint of his 1838 paper "", which he mailed to Gauss, Dirichlet conjectured (under a slightly different form appealing to a series rather than an integral) that an even better approximation to is given by the
offset logarithmic integral
In mathematics, the logarithmic integral function or integral logarithm li(''x'') is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is ...
function , defined by
:
Indeed, this integral is strongly suggestive of the notion that the "density" of primes around should be . This function is related to the logarithm by the
asymptotic expansion In mathematics, an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to ...
:
So, the prime number theorem can also be written as . In fact, in another paper
in 1899 de la Vallée Poussin proved that
:
for some positive constant , where is the
big notation. This has been improved to
:
where
.
In 2016, Trudgian proved an explicit upper bound for the difference between
and
:
:
for
.
The connection between the Riemann zeta function and is one reason the
Riemann hypothesis
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...
has considerable importance in number theory: if established, it would yield a far better estimate of the error involved in the prime number theorem than is available today. More specifically,
Helge von Koch showed in 1901 that if the Riemann hypothesis is true, the error term in the above relation can be improved to
:
(this last estimate is in fact equivalent to the Riemann hypothesis). The constant involved in the big notation was estimated in 1976 by
Lowell Schoenfeld
Lowell Schoenfeld (April 1, 1920 – February 6, 2002) was an American mathematician known for his work in analytic number theory.
Career
Schoenfeld received his Ph.D. in 1944 from University of Pennsylvania under the direction of Hans Rademache ...
: assuming the Riemann hypothesis,
:
for all . He also derived a similar bound for the
Chebyshev prime-counting function :
:
for all . This latter bound has been shown to express a variance to mean
power law
In statistics, a power law is a Function (mathematics), functional relationship between two quantities, where a Relative change and difference, relative change in one quantity results in a proportional relative change in the other quantity, inde ...
(when regarded as a random function over the integers) and
noise
Noise is unwanted sound considered unpleasant, loud or disruptive to hearing. From a physics standpoint, there is no distinction between noise and desired sound, as both are vibrations through a medium, such as air or water. The difference arise ...
and to also correspond to the
Tweedie compound Poisson distribution. (The Tweedie distributions represent a family of
scale invariant
In physics, mathematics and statistics, scale invariance is a feature of objects or laws that do not change if scales of length, energy, or other variables, are multiplied by a common factor, and thus represent a universality.
The technical ter ...
distributions that serve as foci of convergence for a generalization of the
central limit theorem
In probability theory, the central limit theorem (CLT) establishes that, in many situations, when independent random variables are summed up, their properly normalized sum tends toward a normal distribution even if the original variables themselv ...
.)
The
logarithmic integral
In mathematics, the logarithmic integral function or integral logarithm li(''x'') is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is a ...
is larger than for "small" values of . This is because it is (in some sense) counting not primes, but prime powers, where a power of a prime is counted as of a prime. This suggests that should usually be larger than by roughly
and in particular should always be larger than . However, in 1914,
J. E. Littlewood
John Edensor Littlewood (9 June 1885 – 6 September 1977) was a British mathematician. He worked on topics relating to mathematical analysis, analysis, number theory, and differential equations, and had lengthy collaborations with G. H. H ...
proved that
changes sign infinitely often. The first value of where exceeds is probably around ; see the article on
Skewes' number
In number theory, Skewes's number is any of several large numbers used by the South African mathematician Stanley Skewes as upper bounds for the smallest natural number x for which
:\pi(x) > \operatorname(x),
where is the prime-counting function ...
for more details. (On the other hand, the
offset logarithmic integral
In mathematics, the logarithmic integral function or integral logarithm li(''x'') is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is ...
is smaller than already for ; indeed, , while .)
Elementary proofs
In the first half of the twentieth century, some mathematicians (notably
G. H. Hardy
Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis. In biology, he is known for the Hardy–Weinberg principle, a basic principle of pop ...
) believed that there exists a hierarchy of proof methods in mathematics depending on what sorts of numbers (
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s,
reals,
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
) a proof requires, and that the prime number theorem (PNT) is a "deep" theorem by virtue of requiring
complex analysis
Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates Function (mathematics), functions of complex numbers. It is helpful in many branches of mathemati ...
.
This belief was somewhat shaken by a proof of the PNT based on
Wiener's tauberian theorem In mathematical analysis, Wiener's tauberian theorem is any of several related results proved by Norbert Wiener in 1932. They provide a necessary and sufficient condition under which any function in or can be approximated by linear combination ...
, though this could be set aside if Wiener's theorem were deemed to have a "depth" equivalent to that of complex variable methods.
In March 1948,
Atle Selberg
Atle Selberg (14 June 1917 – 6 August 2007) was a Norwegian mathematician known for his work in analytic number theory and the theory of automorphic forms, and in particular for bringing them into relation with spectral theory. He was awarde ...
established, by "elementary" means, the asymptotic formula
:
where
:
for primes .
By July of that year, Selberg and
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
had each obtained elementary proofs of the PNT, both using Selberg's asymptotic formula as a starting point.
These proofs effectively laid to rest the notion that the PNT was "deep" in that sense, and showed that technically "elementary" methods were more powerful than had been believed to be the case. On the history of the elementary proofs of the PNT, including the Erdős–Selberg
priority dispute In science, priority is the credit given to the individual or group of individuals who first made the discovery or propose the theory. Fame and honours usually go to the first person or group to publish a new finding, even if several researchers arr ...
, see an article by
Dorian Goldfeld
Dorian Morris Goldfeld (born January 21, 1947) is an American mathematician working in analytic number theory and automorphic forms at Columbia University.
Professional career
Goldfeld received his B.S. degree in 1967 from Columbia University. ...
.
There is some debate about the significance of Erdős and Selberg's result. There is no rigorous and widely accepted definition of the notion of
elementary proof In mathematics, an elementary proof is a mathematical proof that only uses basic techniques. More specifically, the term is used in number theory to refer to proofs that make no use of complex analysis. Historically, it was once thought that certain ...
in number theory, so it is not clear exactly in what sense their proof is "elementary". Although it does not use complex analysis, it is in fact much more technical than the standard proof of PNT. One possible definition of an "elementary" proof is "one that can be carried out in first-order
Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
." There are number-theoretic statements (for example, the
Paris–Harrington theorem
In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, is true, but not provable in Peano arithmetic. This has been described by some (suc ...
) provable using
second order but not
first-order
In mathematics and other formal sciences, first-order or first order most often means either:
* "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
methods, but such theorems are rare to date. Erdős and Selberg's proof can certainly be formalized in Peano arithmetic, and in 1994, Charalambos Cornaros and Costas Dimitracopoulos proved that their proof can be formalized in a very weak fragment of PA, namely . However, this does not address the question of whether or not the standard proof of PNT can be formalized in PA.
Computer verifications
In 2005, Avigad ''et al.'' employed the
Isabelle theorem prover
The Isabelle automated theorem prover is a higher-order logic (HOL) theorem prover, written in Standard ML and Scala. As an LCF-style theorem prover, it is based on a small logical core (kernel) to increase the trustworthiness of proofs withou ...
to devise a computer-verified variant of the Erdős–Selberg proof of the PNT.
This was the first machine-verified proof of the PNT. Avigad chose to formalize the Erdős–Selberg proof rather than an analytic one because while Isabelle's library at the time could implement the notions of limit, derivative, and
transcendental function
In mathematics, a transcendental function is an analytic function that does not satisfy a polynomial equation, in contrast to an algebraic function.
In other words, a transcendental function "transcends" algebra in that it cannot be expressed alge ...
, it had almost no theory of integration to speak of.
[
In 2009, ]John Harrison
John Harrison ( – 24 March 1776) was a self-educated English Carpentry, carpenter and clockmaker who invented the marine chronometer, a long-sought-after device for solving the History of longitude, problem of calculating longitude while at s ...
employed HOL Light HOL Light is a member of the HOL theorem prover family. Like the other members, it is a proof assistant for classical higher order logic. Compared with other HOL systems, HOL Light is intended to have relatively simple foundations. HOL Light is aut ...
to formalize a proof employing complex analysis
Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates Function (mathematics), functions of complex numbers. It is helpful in many branches of mathemati ...
. By developing the necessary analytic machinery, including the Cauchy integral formula
In mathematics, Cauchy's integral formula, named after Augustin-Louis Cauchy, is a central statement in complex analysis. It expresses the fact that a holomorphic function defined on a disk is completely determined by its values on the boundary o ...
, Harrison was able to formalize "a direct, modern and elegant proof instead of the more involved 'elementary' Erdős–Selberg argument".
Prime number theorem for arithmetic progressions
Let denote the number of primes in the arithmetic progression
An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
that are less than . Dirichlet and Legendre conjectured, and de la Vallée Poussin proved, that if and are coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
, then
:
where is Euler's totient function
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
. In other words, the primes are distributed evenly among the residue classes modulo with . This is stronger than Dirichlet's theorem on arithmetic progressions
In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers ''a'' and ''d'', there are infinitely many primes of the form ''a'' + ''nd'', where ''n'' is als ...
(which only states that there is an infinity of primes in each class) and can be proved using similar methods used by Newman for his proof of the prime number theorem.
The Siegel–Walfisz theorem In analytic number theory, the Siegel–Walfisz theorem was obtained by Arnold Walfisz as an application of a theorem by Carl Ludwig Siegel to primes in arithmetic progressions. It is a refinement both of the prime number theorem and of Dirichlet' ...
gives a good estimate for the distribution of primes in residue classes.
Bennett ''et al.''
proved the following estimate that has explicit constants and (Theorem 1.3):
Let be an integer and let be an integer that is coprime to . Then there are positive constants and such that
:
where
:
and
:
Prime number race
Although we have in particular
:
empirically the primes congruent to 3 are more numerous and are nearly always ahead in this "prime number race"; the first reversal occurs at .[
] However Littlewood showed in 1914 that there are infinitely many sign changes for the function
:
so the lead in the race switches back and forth infinitely many times. The phenomenon that is ahead most of the time is called Chebyshev's bias
In number theory, Chebyshev's bias is the phenomenon that most of the time, there are more primes of the form 4''k'' + 3 than of the form 4''k'' + 1, up to the same limit. This phenomenon was first observed by Russian mathematic ...
. The prime number race generalizes to other moduli and is the subject of much research; Pál Turán
Pál Turán (; 18 August 1910 – 26 September 1976) also known as Paul Turán, was a Hungarian mathematician who worked primarily in extremal combinatorics. He had a long collaboration with fellow Hungarian mathematician Paul Erdős, lasting ...
asked whether it is always the case that and change places when and are coprime to . Granville and Martin give a thorough exposition and survey.
Non-asymptotic bounds on the prime-counting function
The prime number theorem is an ''asymptotic'' result. It gives an ineffective bound on as a direct consequence of the definition of the limit: for all , there is an such that for all ,
:
However, better bounds on are known, for instance Pierre Dusart
Pierre Dusart is a French mathematician at the Université de Limoges who specializes in number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the ...
's
:
The first inequality holds for all and the second one for .
A weaker but sometimes useful bound for is
:
In Pierre Dusart's thesis there are stronger versions of this type of inequality that are valid for larger . Later in 2010, Dusart proved:
:
The proof by de la Vallée Poussin implies the following: For every , there is an such that for all ,
:
Approximations for the 'th prime number
As a consequence of the prime number theorem, one gets an asymptotic expression for the th prime number, denoted by :
:
A better approximation is
:
Again considering the th prime number , this gives an estimate of ; the first 5 digits match and relative error is about 0.00005%.
Rosser's theorem
In number theory, Rosser's theorem states that the ''n''th prime number is greater than n \log n , where \log is the natural logarithm function. It was published by J. Barkley Rosser in 1939.
Its full statement is:
Let ''p'n'' be the ''n''th ...
states that
:
This can be improved by the following pair of bounds:
:
Table of , , and
The table compares exact values of to the two approximations and . The last column, , is the average prime gap
A prime gap is the difference between two successive prime numbers. The ''n''-th prime gap, denoted ''g'n'' or ''g''(''p'n'') is the difference between the (''n'' + 1)-th and the
''n''-th prime numbers, i.e.
:g_n = p_ - p_n.\
W ...
below .
:
The value for was originally computed assuming the Riemann hypothesis
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...
; it has since been verified unconditionally.
Analogue for irreducible polynomials over a finite field
There is an analogue of the prime number theorem that describes the "distribution" of irreducible polynomial
In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted ...
s over a finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
; the form it takes is strikingly similar to the case of the classical prime number theorem.
To state it precisely, let be the finite field with elements, for some fixed , and let be the number of monic ''irreducible'' polynomials over whose degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
is equal to . That is, we are looking at polynomials with coefficients chosen from , which cannot be written as products of polynomials of smaller degree. In this setting, these polynomials play the role of the prime numbers, since all other monic polynomials are built up of products of them. One can then prove that
:
If we make the substitution , then the right hand side is just
:
which makes the analogy clearer. Since there are precisely monic polynomials of degree (including the reducible ones), this can be rephrased as follows: if a monic polynomial of degree is selected randomly, then the probability of it being irreducible is about .
One can even prove an analogue of the Riemann hypothesis, namely that
:
The proofs of these statements are far simpler than in the classical case. It involves a short, combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
argument, summarised as follows: every element of the degree extension of is a root of some irreducible polynomial whose degree divides ; by counting these roots in two different ways one establishes that
:
where the sum is over all divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s of . Möbius inversion
Moebius, Möbius or Mobius may refer to:
People
* August Ferdinand Möbius (1790–1868), German mathematician and astronomer
* Theodor Möbius (1821–1890), German philologist
* Karl Möbius (1825–1908), German zoologist and ecologist
* Paul ...
then yields
:
where is the Möbius function
The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most oft ...
. (This formula was known to Gauss.) The main term occurs for , and it is not difficult to bound the remaining terms. The "Riemann hypothesis" statement depends on the fact that the largest proper divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
of can be no larger than .
See also
* Abstract analytic number theory for information about generalizations of the theorem.
* Landau prime ideal theorem
In algebraic number theory, the prime ideal theorem is the number field generalization of the prime number theorem. It provides an asymptotic formula for counting the number of prime ideals of a number field ''K'', with norm at most ''X''.
Exampl ...
for a generalization to prime ideals in algebraic number fields.
* Riemann hypothesis
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...
Citations
References
*
*
*
*
External links
*
Table of Primes by Anton Felkel
Short video
visualizing the Prime Number Theorem.
an
at MathWorld
''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Dig ...
.
How Many Primes Are There?
an
by Chris Caldwell, University of Tennessee at Martin
The University of Tennessee at Martin (UT Martin or UTM) is a public university in Martin, Tennessee. It is one of the five campuses of the University of Tennessee system. UTM is the only public university in West Tennessee outside of Memphis ...
.
Tables of prime-counting functions
by Tomás Oliveira e Silva
* Eberl, Manuel and Paulson, L. C.br>The Prime Number Theorem (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)
The Prime Number Theorem: the "elementary" proof
− An exposition of the elementary proof of the Prime Number Theorem of Atle Selberg and Paul Erdős a
www.dimostriamogoldbach.it/en/
{{DEFAULTSORT:Prime Number Theorem
Logarithms
Theorems about prime numbers
Theorems in analytic number theory