Prime Number Theorem — Mathematics Knowledge System

Overview

The Prime Number Theorem (PNT) describes the asymptotic distribution of prime numbers. Letting π(x) denote the number of primes not exceeding x, the PNT states that π(x) ~ x/ln x as x → ∞, or equivalently π(x) ~ Li(x) where Li(x) = ∫₂^x dt/ln t is the logarithmic integral. First conjectured by Gauss and Legendre from numerical data in the 1790s, it was proved independently by Hadamard and de la Vallée Poussin in 1896 using complex analysis and properties of the Riemann zeta function.

Intuition

Among the integers near x, primes become sparser: intuitively, a number near x has roughly a 1/ln x chance of being prime. Summing this probability from 2 to x gives the logarithmic integral Li(x) ≈ x/ln x as a first approximation. The PNT confirms that this heuristic is asymptotically exact. The deeper reason is that the Riemann zeta function has no zeros on Re(s) = 1, which controls the error in the prime counting function.

Formal Definition

Definition

Let π(x) count the number of primes p ≤ x. The prime counting function satisfies the following asymptotic relation.

\pi(x) \sim \frac{x}{\ln x} \quad (x \to \infty)

Prime Number Theorem (Gauss-Legendre form)

\pi(x) \sim \mathrm{Li}(x) = \int_2^x \frac{dt}{\ln t} \quad (x \to \infty)

PNT in terms of the logarithmic integral

\psi(x) = \sum_{p^k \leq x} \ln p \sim x \quad (x \to \infty)

Equivalent form using the Chebyshev psi function

\psi(x) = x - \sum_{\rho} \frac{x^\rho}{\rho} - \ln(2\pi) + O(1)

Riemann's explicit formula (sum over nontrivial zeros ρ of ζ)

Notation

Notation	Meaning
$\pi(x)$	Number of primes p ≤ x
$\mathrm{Li}(x) = \int_2^x \frac{dt}{\ln t}$	Logarithmic integral
$\psi(x) = \sum_{p^k \leq x} \ln p$	Chebyshev psi function
$\theta(x) = \sum_{p \leq x} \ln p$	Chebyshev theta function
$\rho = \sigma + it$	Non-trivial zero of the Riemann zeta function

Properties

Equivalent forms of the PNT

\pi(x) \sim x/\ln x \iff \psi(x) \sim x \iff \theta(x) \sim x

Error term (under RH)

\pi(x) = \mathrm{Li}(x) + O(\sqrt{x}\ln x)

PNT for arithmetic progressions (Dirichlet)

\pi(x; q, a) \sim \frac{x}{\phi(q) \ln x} \quad \gcd(a,q)=1

Worked Examples

1
The PNT gives π(x) ≈ x/ln x.
$\pi(10^6) \approx \frac{10^6}{\ln 10^6} = \frac{10^6}{6\ln 10} \approx \frac{10^6}{13.816} \approx 72{,}382$
2
The actual count is π(10⁶) = 78,498. The better approximation Li(10⁶) ≈ 78,628 is much closer.
$\mathrm{Li}(10^6) \approx 78{,}628 \quad (\text{actual: } 78{,}498)$

✓ Answer

The PNT gives ≈ 72,382; the more accurate Li approximation gives ≈ 78,628 versus the true 78,498.

Practice Problems

Mediumfree response

Show that π(x) ~ x/ln x implies the n-th prime pₙ ~ n ln n.

Hardfree response

Explain why the key step ζ(1+it) ≠ 0 can be proved using the inequality 3 + 4cos θ + cos 2θ ≥ 0.

Common Mistakes

Common Mistake

Treating π(x) ~ x/ln x as an exact equality

The tilde symbol ~ denotes asymptotic equivalence: the ratio π(x)/(x/ln x) → 1, not that the two sides are equal. The error |π(x) - x/ln x| grows without bound; Li(x) provides a much better approximation.

Common Mistake

Thinking the Riemann Hypothesis is needed to prove the PNT

The PNT is proved (without RH) by showing ζ(s) ≠ 0 on the line Re(s) = 1. The Riemann Hypothesis (all nontrivial zeros have Re(s) = 1/2) would improve the error term but is not needed for the basic PNT.

Quiz

The Prime Number Theorem states that as x → ∞:

π(x) = x / ln x exactlyπ(x) / (x / ln x) → 1π(x) = Li(x) exactlyπ(x) grows like √x

The PNT was first proved in 1896 by:

Gauss and LegendreRiemann and ChebyshevHadamard and de la Vallée Poussin (independently)Selberg and Erdős

Historical Background

Gauss, around 1793, observed from prime tables that the density of primes near x is approximately 1/ln x, suggesting π(x) ≈ Li(x). Legendre proposed the approximation π(x) ≈ x/(ln x - 1.08366) in 1798. Riemann's 1859 paper connected π(x) to the zeros of the zeta function ζ(s). The actual proof required showing ζ(s) ≠ 0 on the line Re(s) = 1, which Hadamard and de la Vallée Poussin achieved independently in 1896. An elementary proof (not using complex analysis) was found by Selberg and Erdős in 1949.

1793
Gauss conjectures π(x) ≈ Li(x) from numerical tables
Carl Friedrich Gauss
1798
Legendre proposes an approximation formula for π(x)
Adrien-Marie Legendre
1859
Riemann relates π(x) to zeros of ζ(s)
Bernhard Riemann
1896
Hadamard and de la Vallée Poussin independently prove the PNT
Jacques Hadamard, Charles-Jean de la Vallée Poussin
1949
Selberg and Erdős give the first elementary proof
Atle Selberg, Paul Erdős

Summary

The PNT states π(x) ~ x/ln x; equivalently π(x) ~ Li(x) = ∫₂^x dt/ln t.
Proved in 1896 by Hadamard and de la Vallée Poussin via the non-vanishing of ζ(s) on Re(s) = 1.
The Chebyshev functions ψ(x) and θ(x) are equivalent forms: ψ(x) ~ x ⟺ PNT.
The error in the PNT is controlled by the location of zeros of ζ(s); RH gives the optimal error bound O(√x ln x).
The PNT extends to arithmetic progressions: π(x; q, a) ~ x/(φ(q) ln x) for gcd(a,q) = 1.

References

BookHadamard, J. — Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques, Bull. Soc. Math. France 24 (1896), 199–220
Bookde la Vallée Poussin, C.-J. — Recherches analytiques sur la théorie des nombres premiers, Ann. Soc. Sci. Bruxelles 20 (1896), 183–256
BookApostol, T.M. — Introduction to Analytic Number Theory (1976), Springer, Chapter 4
BookDavenport, H. — Multiplicative Number Theory, 3rd ed. (2000), Springer, Chapters 13–18
WebsiteWikipedia — Prime number theorem
WebsiteMathWorld — Prime Number Theorem
WebsiteNIST DLMF — §27.12 Asymptotic Formulas