Scrivi π(n) per il numero di primi fino a n. Il teorema dei numeri primi afferma che π(n) cresce come n/ln(n). Quando n diventa grande, circa 1 numero su ln(n) nei dintorni di n è primo. Intorno a un milione, all'incirca 1 numero su 14 è primo. Intorno a un miliardo, 1 su 21.
π(n) counts the primes up to n (blue staircase). The Prime Number Theorem says π(n) ~ n/ln(n) — the ratio → 1 as n → ∞. The logarithmic integral Li(n) is even closer.
Gauss congetturò il risultato intorno al 1800 dopo aver studiato tavole di numeri primi. Fu dimostrato indipendentemente nel 1896 da Jacques Hadamard e Charles-Jean de la Vallée Poussin, entrambi usando la funzione zeta di Riemann e l'analisi complessa. Una dimostrazione puramente elementare, senza analisi complessa, fu trovata indipendentemente da Selberg ed Erdős nel 1948.
Table showing density of primes at various scales
| Up to n | Primes π(n) | Density ≈ 1/ln(n) |
|---|---|---|
| 1 000 | 168 | 1 in 7 |
| 1 000 000 | 78 498 | 1 in 14 |
| 10⁹ | 50 847 534 | 1 in 21 |
| 10¹² | 37 607 912 018 | 1 in 28 |
L'Ipotesi di Riemann darebbe il limite più preciso sull'errore: |π(n) - Li(n)| ≤ √n · ln(n) / (8π). Senza di essa sappiamo solo che l'errore è o(n/ln(n)). Per questo l'Ipotesi di Riemann è considerata il più importante problema aperto della matematica: ci direbbe con grande precisione quanto siano prevedibili i divari tra numeri primi.
Un'approssimazione a pi(n) più accurata di n/ln(n) è l'integrale logaritmico Li(n) = integrale da 2 a n di dt/ln(t). Gauss preferiva questa forma. Per n = 1.000.000, n/ln(n) dà 72.382 mentre Li(n) dà 78.628, contro il conteggio esatto di 78.498. L'errore di Li(n) è molto più piccolo. L'ipotesi di Riemann limiterebbe questo errore in modo preciso con sqrt(n) * ln(n).