Escreva π(n) para o número de primos até n. O teorema dos números primos diz que π(n) cresce como n/ln(n). Quando n fica maior, cerca de 1 em cada ln(n) números próximos de n é primo. Perto de um milhão, aproximadamente 1 em cada 14 números é primo. Perto de um bilhão, 1 em cada 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 conjecturou o resultado por volta de 1800 após estudar tabelas de primos. A prova independente veio em 1896 com Jacques Hadamard e Charles-Jean de la Vallée Poussin, ambos usando a função zeta de Riemann e análise complexa. Uma prova puramente elementar (sem análise complexa) foi encontrada independentemente por Selberg e Erdős em 1948.
Table showing density of primes at various scales
| Bis n | Primzahlen π(n) | Dichte ≈ 1/ln(n) |
|---|---|---|
| 1 000 | 168 | 1 von 7 |
| 1 000 000 | 78 498 | 1 von 14 |
| 10⁹ | 50 847 534 | 1 von 21 |
| 10¹² | 37 607 912 018 | 1 von 28 |
A hipótese de Riemann daria o limite mais preciso para o erro: |π(n) - Li(n)| ≤ √n · ln(n) / (8π). Sem ela, só sabemos que o erro é o(n/ln(n)). É por isso que a hipótese de Riemann é o problema em aberto mais importante da matemática: ela diria exatamente quão previsíveis são os intervalos entre primos.
Uma aproximação mais precisa para pi(n) do que n/ln(n) é a integral logarítmica Li(n) = integral de 2 até n de dt/ln(t). Gauss preferia essa forma. Para n = 1.000.000: n/ln(n) dá 72.382, enquanto Li(n) dá 78.628, contra a contagem exata de 78.498. O erro de Li(n) é muito menor. A hipótese de Riemann limitaria esse erro precisamente por sqrt(n) * ln(n).