Prime Number Distribution: From the Theorem to the Riemann Hypothesis

The Thinning of Primes

Among the first 100 integers, 25 are prime — one in four. Among the first 1,000, 168 are prime — one in six. Among the first 10 million, 664,579 are prime — one in fifteen. Primes become progressively rarer as numbers grow larger, yet they never stop appearing. Euclid proved the infinitude of primes around 300 BCE. Understanding precisely how that thinning proceeds took mathematicians another 2,000 years — and the deepest question about it remains unsolved.

The Prime Number Theorem

The Prime Number Theorem (PNT) states that the number of primes up to x, denoted π(x), satisfies:

π(x) ≈ x / ln(x)

where ln(x) is the natural logarithm. Equivalently, the probability that a randomly chosen integer near x is prime is approximately 1/ln(x).

Carl Friedrich Gauss conjectured a related result at age 15 or 16 while studying prime tables, noting around 1792–1793 that primes thin according to a logarithmic density. He also formulated the superior approximation using the logarithmic integral Li(x). The formal proof came independently from Jacques Hadamard and Charles de la Vallée Poussin in 1896, both using complex analysis tools — specifically, proving that the Riemann zeta function has no zeros on the line where the real part equals 1.

Li(x) always overestimates π(x) for all computed values of x. But John Edensor Littlewood proved in 1914 that the difference changes sign infinitely often — meaning that for some (astronomically large) value of x, π(x) exceeds Li(x). The first such crossover is estimated to occur around 10³¹⁶, a number so large it has no physical meaning but carries profound mathematical significance.

Prime Gaps

A prime gap is the difference between consecutive primes. The gap after 2 is 1 (between 2 and 3). The gap after 3 is 2. By the PNT, the average gap near a large prime p is approximately ln(p) — about 23 near primes in the range of 10¹⁰. But individual gaps vary wildly around this average.

• Maximal prime gaps: The largest known prime gap of exactly 1,510 consecutive composite numbers follows the prime 1,693,182,318,746,371
• Arbitrarily large gaps: Proven to exist. For any n, there exist n consecutive composite numbers: the sequence n! + 2, n! + 3, ..., n! + n consists entirely of composites
• Bounded gaps: Yitang Zhang proved in 2013 that there are infinitely many prime pairs with gap less than 70,000,000 — a breakthrough toward the twin prime conjecture. The Polymath8 project reduced this bound to 246 within a year.

The Twin Prime Conjecture

Twin primes are prime pairs differing by 2: (3,5), (5,7), (11,13), (17,19), (29,31), ...). The twin prime conjecture asserts that infinitely many such pairs exist. Despite substantial computational evidence — twin primes extend to at least (2,996,863,034,895 × 2^1,290,000 ± 1, found in 2016) — no proof exists.

The twin prime conjecture is a special case of the Hardy-Littlewood conjecture (1923), which predicts an asymptotic density of twin primes consistent with the PNT via a precise constant now called the twin prime constant C₂ ≈ 0.6601618. This conjecture has been verified numerically to extraordinarily large values but has not been proved.

The Riemann Hypothesis

Bernhard Riemann's 1859 paper "On the Number of Primes Less Than a Given Magnitude" (Über die Anzahl der Primzahlen unter einer gegebenen Grösse) connected the distribution of primes to the zeros of the function now called the Riemann zeta function:

ζ(s) = 1 + 1/2^s + 1/3^s + 1/4^s + ...

defined for complex numbers s. This function has "trivial" zeros at negative even integers and "non-trivial" zeros scattered in the complex plane. Riemann conjectured that all non-trivial zeros lie on the critical line where the real part of s equals exactly 1/2.

The Riemann Hypothesis is not merely a curiosity — hundreds of theorems in analytic number theory are proved "conditionally on RH," meaning the proof works only if the hypothesis is true. A proof (or disproof) would immediately verify or overturn all of them simultaneously.

The Largest Known Prime (2024)

As of October 2024, the largest known prime is 2^136,279,841 − 1, a Mersenne prime discovered by the Great Internet Mersenne Prime Search (GIMPS) on October 12, 2024. It has 41,024,320 digits — if printed in standard type, it would fill roughly 20,000 pages. It is the 52nd known Mersenne prime.

Mersenne primes have the form 2^p − 1 where p itself is prime. They are not the only large primes — but they are the easiest to verify using the Lucas-Lehmer primality test, which is highly efficient for this specific form. Whether infinitely many Mersenne primes exist is an open question; the distribution of prime exponents p for which 2^p − 1 is prime remains poorly understood theoretically, despite the enormous computational effort invested in finding them.

• GIMPS has used volunteer computing (distributed across tens of thousands of CPUs) since 1996
• Every new Mersenne prime found by GIMPS earns its discoverer a cash prize from the Electronic Frontier Foundation: $3,000 for a prime exceeding 1 million digits (first found 1999), $150,000 for first exceeding 100 million digits (first found 2018)
• The billion-digit prime prize of $250,000 remains unclaimed