Q: Did you ever realized that the Prime Number Theorem is equivalent to the statement that the nth prime number pn satisfies
NOTE: The Fields medalist who keeps on searching for the structure and randomness in the primes numbers!!…
In a lecture on prime numbers for a general audience, Fields medalist Terence Tao described one approach to proving the prime number theorem in poetic terms: Listening to the “music” of the primes. We start with a “sound wave” that is “noisy” at the prime numbers and silent at other numbers; this is the von Mangoldt function. Then we analyze its notes or frequencies by subjecting it to a process akin to Fourier transform; this is the Mellin transform. The next and most difficult step is to prove that certain “notes” cannot occur in this music. This exclusion of certain notes leads to the statement of the prime number theorem. According to Tao, this proof yields much deeper insights into the distribution of the primes than the “elementary” proofs.
The Prime Math Theorem – The 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. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée-Poussin in 1896 using ideas introduced by Bernhard Riemann (in particular, the Riemann zeta function).
This means that for large enough N, the probability that a random integer not greater than N is prime is very close to 1 / log(N). Consequently, a random integer with at most 2n digits (for large enough n) is about half as likely to be prime as a random integer with at most n digits. For example, among the positive integers of at most 1000 digits, about one in 2300 is prime (log(101000) ≈ 2302.6), whereas among positive integers of at most 2000 digits, about one in 4600 is prime (log(102000) ≈ 4605.2). In other words, the average gap between consecutive prime numbers among the first N integers is roughly log(N).
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.
Let π(x) be the prime-counting function that gives the number of primes less than or equal to x, for any real number x. The prime number theorem then states that x / log(x) is a good approximation to π(x), in the sense that the limit of the quotient of the two functions π(x) and x / log(x) as x increases without bound is 1:
known as the asymptotic law of distribution of prime numbers. Using asymptotic notation 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 x increases without bound. Instead, the theorem states that x/log(x) approximates π(x) in the sense that the relative error of this approximation approaches 0 as x increases without bound.
The prime number theorem is equivalent to the statement that the nth prime number pn satisfies
the asymptotic notation means again that the relative error of this approximation approaches 0 as n increases without bound. For example, the 200 · 1015th prime number is 8512677386048191063, and (200 · 1015)log(200 · 1015) rounds to 7967418752291744388, a relative error of about 6.4%.
The prime number theorem is also equivalent to:
where ϑ and ψ are the first and the second Chebyshev functions respectively.
Prime-Counting Function in Terms of the Logarithmic Integral
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 Carl Friedrich Gauss, Peter Gustav Lejeune 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 in 1899 La Vallée Poussin proved that
for some positive constant a, where O(…) is the big O notation. This has been improved to
Because of the connection between the Riemann zeta function and π(x), the Riemann hypothesis 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 and only if the Riemann hypothesis is true, the error term in the above relation can be improved to
for all x ≥ 2657. He also derived a similar bound for the Chebyshev prime-counting function ψ:
for all x ≥ 73.2. This latter bound has been shown to express a variance to mean power law (when regarded as a random function over the integers), 1/f noise and to also correspond to the Tweedie compound Poisson distribution. Parenthetically, the Tweedie distributions represent a family of scale invariant distributions that serve as foci of convergence for a generalization of the central limit theorem.
The logarithmic integral Li(x) is larger than π(x) for “small” values of x. This is because it is (in some sense) counting not primes, but prime powers, where a power pn of a prime p is counted as 1/n of a prime. This suggests that Li(x) should usually be larger than π(x) by roughly Li(x1/2)/2, and in particular should usually be larger than π(x). However, in 1914, J. E. Littlewood proved that this is not always the case. The first value of x where π(x) exceeds Li(x) is probably around x = 10316; see the article on Skewes’ number for more details.
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. This belief was somewhat shaken by a proof of the PNT based on Wiener’s tauberian theorem, though this could be set aside if Wiener’s theorem were deemed to have a “depth” equivalent to that of complex variable methods. There is no rigorous and widely accepted definition of the notion of elementary proof in number theory. One definition is “a proof that can be carried out in first order Peano arithmetic.” There are number-theoretic statements (for example, the Paris–Harrington theorem) provable using second order but not first order methods, but such theorems are rare to date.
In March 1948, Atle Selberg established, by elementary means, the asymptotic formula
for primes p  . By July of that year, Selberg and Paul Erdős 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,” and showed that technically “elementary” methods (in other words Peano arithmetic) 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.
Prime Number Theorem for Arithmetic Progressions
Let denote the number of primes in the arithmetic progression a, a + n, a + 2n, a + 3n, … less than x. Lejeune Dirichlet and Legendre conjectured, and Vallée-Poussin proved, that, if a and n are coprime, then
In other words, the primes are distributed evenly among the residue classes [a] modulo n with gcd(a, n) = 1. This is stronger than Dirichlet’s theorem on arithmetic progressions (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 gives a good estimate for the distribution of primes in residue classes.