Prime Number Theorem

1. Introduction

The Prime Number Theorem (PNT) provides a deep insight into the distribution of prime numbers. It states that the number of primes less than or equal to a given real number x, denoted by π(x), grows asymptotically in proportion to x / ln(x) as x approaches infinity. Despite the seemingly erratic nature of prime numbers, the theorem reveals a remarkable underlying regularity in their density.

This result bridges elementary number theory and advanced analysis, relying on properties of the Riemann zeta function and complex integration. Its proof stands as one of the great achievements of 19th-century mathematics.

2. Formal Statement

Let π(x) denote the prime-counting function, which counts the number of prime numbers less than or equal to x. The Prime Number Theorem asserts:

In asymptotic notation, this is written as π(x) ~ x / ln x. Equivalently, using the logarithmic integral function Li(x) defined as the Cauchy principal value of ∫₂ˣ dt/ln t, the theorem can be expressed more precisely as:

where c is a positive constant. The approximation Li(x) significantly reduces the error term compared to x/ln x.

3. Historical Development

Early Observations

In 1793, Carl Friedrich Gauss and Adrien-Marie Legendre independently conjectured the theorem based on statistical analysis of prime tables. Gauss proposed the approximation π(x) ≈ Li(x), while Legendre suggested π(x) ≈ x/(ln x - 1.08366). Both recognized the asymptotic behavior but lacked rigorous proof.

Bernhard Riemann's Insight

In his seminal 1859 paper "Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse", Bernhard Riemann connected the distribution of primes to the analytic properties of the zeta function ζ(s). He formulated the explicit formula for π(x) involving the non-trivial zeros of ζ(s), laying the groundwork for analytic proofs.

Rigorous Proofs

The theorem was finally proved in 1896 by Jacques Hadamard and Charles Jean de la Vallée Poussin, independently, using complex analysis. Their proofs hinged on showing that ζ(s) has no zeros on the line Re(s) = 1. An elementary proof, avoiding complex analysis, was discovered in 1949 by Atle Selberg and Paul Erdős.

4. Proof Sketch

The analytic proof relies on the contour integration of the logarithmic derivative of the Riemann zeta function. The key steps include:

1. Logarithmic Derivative: Express -ζ'(s)/ζ(s) as a Dirichlet series involving the von Mangoldt function Λ(n).

2. Zero-Free Region: Demonstrate that ζ(s) ≠ 0 for Re(s) = 1. This is achieved by analyzing the argument of ζ(s) and using inequalities involving |ζ(σ+it)|.

3. Perron's Formula: Apply complex contour integration to recover the summatory function of Λ(n), denoted ψ(x).

4. Elementary Equivalence: Show that ψ(x) ~ x is equivalent to π(x) ~ x/ln x using partial summation and Chebyshev's estimates.

The elementary proof by Selberg and Erdős utilizes intricate combinatorial estimates and Selberg's asymptotic formula for sums involving logarithms of primes, avoiding complex analysis entirely.

5. Applications & Extensions

The PNT underpins modern cryptography, algorithm analysis, and probabilistic number theory. Its error term is directly tied to the Riemann Hypothesis: if the hypothesis is true, the error becomes O(√x · ln x), representing the tightest possible bound.

Extensions include:

• Primes in Arithmetic Progressions: Dirichlet's theorem and its quantitative form.
• Prime k-tuples: Hardy-Littlewood conjectures on prime constellations.
• Sieve Methods: Brun's sieve and the sieve of Eratosthenes-Legendre for bounding prime distributions.

The theorem also informs the analysis of randomized algorithms and the expected complexity of integer factorization problems.

6. References

1. Primary Hadamard, J. (1896). Répartition des nombres premiers. Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, 123, 383-385.
2. Primary de la Vallée Poussin, C. J. (1896). Sur la loi de distribution des nombres premiers. Comptes Rendus, 123, 239-242.
3. Textbook Ivic, A. (1990). The Riemann Zeta-Function: Theory and Applications. Dover Publications.
4. Survey Pintz, J. (2003). The Prime Number Theorem: Selberg's Elementary Proof. Annals of Mathematics Studies, 156, 1-34.
5. Historical Kanold, H. (1980). Die Primzahlverteilungstheorie: Historische Entwicklung und moderne Beweise. Springer-Verlag.

7. See Also