Prime number theorem

It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs.

Based on the tables by Anton Felkel and Jurij Vega, Adrien-Marie Legendre conjectured in 1797 or 1798 that π(a) is approximated by the function a / (A log a + B), where A and B are unspecified constants.

[6] In 1838 Peter Gustav Lejeune Dirichlet came up with his own approximating function, the logarithmic integral li(x) (under the slightly different form of a series, which he communicated to Gauss).

In two papers from 1848 and 1850, the Russian mathematician Pafnuty Chebyshev attempted to prove the asymptotic law of distribution of prime numbers.

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 x goes to infinity of π(x) / (x / log(x)) exists at all, then it is necessarily equal to one.

In particular, it is in this paper that the idea to apply methods of complex analysis to the study of the real function π(x) originates.

Extending Riemann's ideas, two proofs of the asymptotic law of the distribution of prime numbers were found independently by Jacques Hadamard[1] and Charles Jean de la Vallée Poussin[2] and appeared in the same year (1896).

[15] 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.

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 x (claimed to be the correct asymptotic order of ψ(x)) appears on the right-hand side, followed by (presumably) lower-order asymptotic terms.

To do this, we take for granted that ζ(s) is meromorphic in the half-plane Re(s) > 0, and is analytic there except for a simple pole at s = 1, and that there is a product formula for Re(s) > 1.

This product formula follows from the existence of unique prime factorization of integers, and shows that ζ(s) is never zero in this region, so that its logarithm is defined there and Write s = x + iy ; then Now observe the identity so that for all x > 1.

has a simple pole at s = 1 and ζ(x + 2iy) stays analytic, the left hand side in the previous inequality tends to 0, a contradiction.

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 ψ(x) does not converge absolutely but only conditionally and in a "principal value" sense.

In a handwritten note on a reprint of his 1838 paper "Sur l'usage des séries infinies dans la théorie des nombres", 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 π(x) is given by the offset logarithmic integral function Li(x), defined by Indeed, this integral is strongly suggestive of the notion that the "density" of primes around t should be 1 / log t. This function is related to the logarithm by the asymptotic expansion So, the prime number theorem can also be written as π(x) ~ Li(x).

In fact, in another paper[17] in 1899 de la Vallée Poussin proved that for some positive constant a, where O(...) is the big O notation.

The constant involved in the big O notation was estimated in 1976 by Lowell Schoenfeld,[21] assuming the Riemann hypothesis: for all x ≥ 2657.

This latter bound has been shown to express a variance to mean power law (when regarded as a random function over the integers) and ⁠1/ f ⁠ noise and to also correspond to the Tweedie compound Poisson distribution.

[22]) A lower bound is also derived by J. E. Littlewood, assuming the Riemann hypothesis:[23][24][25] The logarithmic integral li(x) is larger than π(x) for "small" values of x.

In the first half of the twentieth century, some mathematicians (notably G. H. Hardy) believed that there exists a hierarchy of proof methods in mathematics depending on what sorts of numbers (integers, reals, complex) a proof requires, and that the prime number theorem (PNT) is a "deep" theorem by virtue of requiring complex analysis.

[9][26] 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, see an article by Dorian Goldfeld.

[28] The prime number theorem is obtained there in an equivalent form that the Cesàro sum of the values of the Liouville function is zero.

In 2005, Avigad et al. employed the Isabelle theorem prover to devise a computer-verified variant of the Erdős–Selberg 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, it had almost no theory of integration to speak of.

[30] By developing the necessary analytic machinery, including the Cauchy integral formula, Harrison was able to formalize "a direct, modern and elegant proof instead of the more involved 'elementary' Erdős–Selberg argument".

Let πd,a(x) denote the number of primes in the arithmetic progression a, a + d, a + 2d, a + 3d, ... that are less than x. Dirichlet and Legendre conjectured, and de la Vallée Poussin proved, that if a and d are coprime, then where φ is Euler's totient function.

[36] The proof by de la Vallée Poussin implies the following bound: For every ε > 0, there is an S such that for all x > S, The value ε = 3 gives a weak but sometimes useful bound for x ≥ 55:[37] In Pierre Dusart's thesis there are stronger versions of this type of inequality that are valid for larger x.

Cipolla (1902)[41][42] showed that these are the leading terms of an infinite series which may be truncated at arbitrary degree, with where each Pi is a degree-i monic polynomial.

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 argument,[47] summarised as follows: every element of the degree n extension of F is a root of some irreducible polynomial whose degree d divides n; by counting these roots in two different ways one establishes that where the sum is over all divisors d of n. Möbius inversion then yields where μ(k) is the Möbius function.

Graph showing ratio of the prime-counting function π ( x ) to two of its approximations, x / log x and Li( x ) . As x increases (note x axis is logarithmic), both ratios tend towards 1. The ratio for x / log x converges from above very slowly, while the ratio for Li( x ) converges more quickly from below.
Log–log plot showing absolute error of x / log x and Li( x ) , two approximations to the prime-counting function π ( x ) . Unlike the ratio, the difference between π ( x ) and x / log x increases without bound as x increases. On the other hand, Li( x ) − π ( x ) switches sign infinitely many times.
Plot of the function for n 30 000
Graph of the number of primes ending in 1, 3, 7, and 9 up to n for n < 10 000