Elementary proof of the prime number theorem

Elementary proof of the prime number theorem. The elementary proof of the prime number theorem is a landmark achievement in analytic number theory, first established independently by Atle Selberg and Paul Erdős in 1949. It is termed "elementary" not for its simplicity, but because it avoids the deep machinery of complex analysis and the Riemann zeta function that characterized the original proofs by Jacques Hadamard and Charles Jean de la Vallée Poussin. Instead, the proof relies on intricate combinatorial identities and asymptotic estimates involving the Chebyshev functions and arithmetic functions.

Introduction and statement of the theorem

The prime number theorem describes the asymptotic distribution of prime numbers among the positive integers. Its classical statement is that if π(x) denotes the number of primes not exceeding x, then π(x) ~ x/log x as x → ∞. An equivalent formulation uses the Chebyshev function ϑ(x) = Σ_{p ≤ x} log p, stating ϑ(x) ~ x. The quest for an elementary proof became a major problem following the work of G. H. Hardy, who believed such a proof was impossible using the methods available to Pafnuty Chebyshev and others. The eventual success of Atle Selberg and the subsequent, somewhat contentious, collaboration with Paul Erdős resolved this long-standing question. Their work built upon earlier estimates by Chebyshev and the theorems of Franz Mertens, but required novel combinatorial insights.

Selberg's symmetry formula and asymptotic formulas

The cornerstone of the elementary proof is Selberg's asymptotic formula, discovered by Atle Selberg in 1949. This fundamental identity states that ϑ(x) log x + Σ_{p ≤ x} ϑ(x/p) log p = 2x log x + O(x), where the sum is over primes p. This is often called the symmetry formula due to the symmetric roles played by the terms. A related, crucial formula is Selberg's identity: Λ(n) log n + Σ_{d|n} Λ(d)Λ(n/d) = Σ_{d|n} μ(d) log²(n/d), involving the von Mangoldt function Λ(n) and the Möbius function μ(n). These identities connect sums over primes to sums over integers in a manner amenable to asymptotic analysis without recourse to the Riemann zeta function.

Derivation of the fundamental inequality

From Selberg's asymptotic formula, one can derive an inequality that drives the proof. A key step involves defining the remainder function R(x) = ϑ(x) - x and substituting it into the symmetry formula. Through careful manipulation and the use of the Möbius inversion formula, one obtains an inequality of the form |R(x)| log x ≤ Σ_{p ≤ x} |R(x/p)| log p + O(x). This inequality implicitly forces R(x) to be small relative to x. The analysis relies on auxiliary estimates for sums like Σ_{n ≤ x} Λ(n) and the properties of the Chebyshev function ψ(x), which is related to ϑ(x) via the contribution of prime powers.

Iteration and deduction of the prime number theorem

The final stage employs an iterative bootstrapping argument. The fundamental inequality is used to show that if the ratio ϑ(x)/x has a limit superior and a limit inferior, they must be equal. One considers the quantities L = lim sup R(x)/x and l = lim inf R(x)/x. Substituting into the inequality and using a delicate averaging process involving a parameter α > 1, one derives that L + l ≥ 0 and L + l ≤ 0, forcing L = l = 0. This conclusion, that ϑ(x)/x → 1, is equivalent to the prime number theorem. The iteration cleverly uses the fact that the sums in Selberg's formula sample the function R at scaled arguments x/p.

Technical lemmas and auxiliary estimates

The proof depends on several supporting technical results. Essential among these are estimates for sums of the form Σ_{n ≤ x} μ(n)/n = o(1) and Σ_{n ≤ x} μ(n) log(x/n)/n = O(1), which are elementary analogues of the fact that the Möbius function has mean value zero. Another critical lemma establishes that Σ_{p ≤ x} (log p)/p = log x + O(1), a result closely tied to Mertens' theorems. The manipulation of these sums often involves the Abel summation formula and comparisons with the integral of 1/log t, reminiscent of techniques used by Adrien-Marie Legendre and Carl Friedrich Gauss in their early empirical studies of prime distribution.

Category:Number theory Category:Mathematical proofs Category:Theorems in analytic number theory