Prime Number Theorem

The Prime Number Theorem (PNT) describes the asymptotic distribution of prime numbers. It is one of the deepest results in number theory, connecting the discrete world of primes to continuous analysis.

Statement

Let π(x) denote the number of primes at most x. The Prime Number Theorem states:

π*(x)∼x/ln(x)*as *x→∞

Equivalently, the n-th prime (p_n) satisfies (p_n)~n*ln(n).

Better Approximation

The logarithmic integral gives a more accurate approximation:

π*(x)≈Li(x)=(∫_2^x)(d(t)/ln(t))

Li*(x) is closer to π*(x) than x/ln(x) and captures the distribution of primes more precisely.

Historical Development

Conjectured by Gauss and Legendre around 1800 based on numerical evidence. Proved independently by Hadamard and de la Vallee Poussin in 1896 using complex analysis.

Connection to Riemann Zeta Function

The proof uses properties of the Riemann zeta function:

ζ(s)=(∑_n=1^∞)(1/(ns()))=(∏_p^)(1/(1−p(−s())))

The key step is proving ζ(s) has no zeros on the line R*e(s)=1.

Elementary Proofs

Erdos and Selberg gave elementary proofs in 1949 that avoid complex analysis. However, these proofs are not simpler; they replace analysis with intricate arithmetic arguments.

Error Terms

The Riemann Hypothesis implies the best possible error bound:

π*(x)=Li(x)+O*(√(,x)*ln(x))

Without RH, the best proven error is O*(x*exp(−c√(,ln(x)))).

Prime Density

The density of primes near x is approximately 1/ln(x). A random integer near x has probability about 1/ln(x) of being prime.

Chebyshev Functions

The Chebyshev functions are often easier to work with:

θ(x)=(∑_p≤x^)(ln(p)),ψ(x)=(∑_pk≤x^)(ln(p))

PNT is equivalent to ψ(x)∼x or θ(x)∼x.

Explicit Formula

Riemann discovered an exact formula relating pi(x) to the zeros of zeta(s):

ψ(x)=x−(∑_ρ^)((xρ)/ρ)−ln(2*π)−1/2*ln(1−x(−2))

The sum is over all non-trivial zeros rho of zeta. Each zero contributes an oscillation to the prime distribution.

Primes in Arithmetic Progressions

Dirichlet's theorem: there are infinitely many primes in any arithmetic progression a+n*d with gcd(a,d)=1.

The PNT for arithmetic progressions gives the density: primes are equidistributed among residue classes.

π*(x;d,a)∼1/ϕ(d)x/ln(x)

Numerical Evidence

At x=10: π*(x)=50,847,534 while x/ln(x)=48,254,942 and Li*(x)=50,849,235. Li*(x) is within 1700 of the true count.

Siegel-Walfisz Theorem

Gives uniform estimates for primes in progressions: π*(x;d,a) has the expected density for d up to (ln(x))A for any fixed A.

Bombieri-Vinogradov Theorem

A powerful averaging result: primes are equidistributed in progressions on average, for moduli up to x(1/2−ε). This substitutes for the generalized Riemann hypothesis in many applications.

Proof Sketch

1. Express ψ(x) in terms of ζ(s) using a Mellin transform.

2. Shift the contour of integration to pick up contributions from poles and zeros.

3. Show ζ(s) has no zeros with Re(s)=1 using analytic properties.

4. The contribution from near Re(s)=1 gives the main term x.

Related Conjectures

Twin prime conjecture: infinitely many primes p with p+2 also prime.

Goldbach conjecture: every even number >2 is a sum of two primes.

These remain open but sieve methods give partial results.

Mertens Theorems

Related results about prime sums and products:

(∑_p≤x^)(1/p)=ln(ln(x))+M+o(1)

(∏_p≤x^)(1−1/p)∼(e(−γ))/ln(x)

Here M is Meissel-Mertens constant and gamma is Euler-Mascheroni constant.

Applications

Cryptography: estimating the density of primes for key generation.

Complexity theory: analyzing algorithms that depend on prime distribution.

Analytic number theory: foundation for studying prime gaps, prime races, and arithmetic functions.

Prime Gaps

PNT implies the average gap between consecutive primes near x is about ln(x). The distribution of gaps is related to deeper conjectures.

Bounded Gaps (Zhang-Maynard)

Yitang Zhang proved in 2013 that there are infinitely many pairs of primes differing by at most 70,000,000. This was improved to 246 by the Polymath project.

Generalizations

PNT generalizes to other number fields (Dedekind zeta function), function fields, and algebraic varieties (Weil conjectures).

Probabilistic Interpretation

Cramér's model treats primes as random with density 1/ln(n). This gives surprisingly accurate predictions for many prime statistics.

Summary

The Prime Number Theorem reveals that primes thin out logarithmically but remain infinitely abundant. Its proof connects number theory to complex analysis in a profound way.

Key formula: π*(x)∼x/ln(x), meaning roughly x/ln(x) primes exist up to x.

The connection to the Riemann zeta function and its zeros remains central to understanding primes and drives research on the Riemann Hypothesis.