Schreibt man π(n) für die Anzahl der Primzahlen bis n, dann besagt der Primzahlsatz, dass π(n) wie n/ln(n) wächst. Je größer n wird, desto seltener werden Primzahlen. In der Nähe von einer Million ist ungefähr jede 14. Zahl prim. In der Nähe von einer Milliarde nur noch etwa jede 21.
π(n) zählt die Primzahlen bis n, als blaue Treppenfunktion. Der Primzahlsatz sagt: π(n) ~ n/ln(n), also geht ihr Quotient für n gegen unendlich gegen 1. Das logarithmische Integral Li(n) ist noch genauer.
Gauss vermutete das Resultat um 1800 nach dem Studium von Primzahltabellen. Bewiesen wurde es 1896 unabhängig voneinander von Jacques Hadamard und Charles-Jean de la Vallée Poussin, beide mithilfe der Riemannschen Zetafunktion und komplexer Analysis. Einen rein elementaren Beweis ohne komplexe Analysis fanden Selberg und Erdős 1948 ebenfalls unabhängig voneinander.
Tabelle zur Dichte der Primzahlen auf verschiedenen Größenskalen.
| 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 |
Die Riemannsche Vermutung würde die schärfste mögliche Schranke für den Fehler liefern: |π(n) - Li(n)| ≤ √n · ln(n) / (8π). Ohne sie wissen wir nur, dass der Fehler o(n/ln(n)) ist. Genau deshalb gilt die Riemannsche Vermutung als das wichtigste offene Problem der Mathematik: Sie würde uns sagen, wie präzise Primzahllücken vorhersagbar sind.
Eine genauere Approximation für π(n) als n/ln(n) ist das logarithmische Integral Li(n) = Integral von 2 bis n über dt/ln(t). Gauss bevorzugte diese Form. Für n = 1.000.000 liefert n/ln(n) den Wert 72.382, Li(n) dagegen 78.628, gegenüber dem exakten Wert 78.498. Der Fehler von Li(n) ist also deutlich kleiner. Die Riemannsche Vermutung würde ihn präzise durch √n · ln(n) abschätzen.