Notons π(n) le nombre de nombres premiers jusqu'a n. Le theoreme des nombres premiers dit que π(n) croit comme n/ln(n). Plus n est grand, environ 1 nombre sur ln(n) pres de n est premier. Pres d'un million, environ 1 nombre sur 14 est premier. Pres d'un milliard, 1 sur 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 a conjecture ce resultat vers 1800 apres avoir etudie des tables de nombres premiers. Il a ete demontre independamment en 1896 par Jacques Hadamard et Charles-Jean de la Vallee Poussin, tous deux utilisant la fonction zeta de Riemann et l'analyse complexe. Une preuve purement elementaire (sans analyse complexe) a ete trouvee independamment par Selberg et Erdos en 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'hypothese de Riemann donnerait la borne la plus precise sur l'erreur : |π(n) - Li(n)| ≤ √n · ln(n) / (8π). Sans elle, on sait seulement que l'erreur est o(n/ln(n)). C'est pourquoi l'hypothese de Riemann est le probleme ouvert le plus important des mathematiques : elle nous dirait exactement a quel point les ecarts entre nombres premiers sont previsibles.
Une approximation plus precise de pi(n) que n/ln(n) est l'integrale logarithmique Li(n) = integrale de 2 a n de dt/ln(t). Gauss preferait cette forme. Pour n = 1 000 000 : n/ln(n) donne 72 382 tandis que Li(n) donne 78 628, contre le compte exact de 78 498. L'erreur de Li(n) est bien plus faible. L'hypothese de Riemann bornerait cette erreur precisement a sqrt(n) * ln(n).