1. Der Satz von Franz Mertens

Es ist instruktiv, den Primzahlsatz mit einem heuristischen Ansatz zu vergleichen, der auf dem Sieb des Eratosthenes beruht. Wir betrachten hierzu eine beliebig große natürliche Zahl n und das Zahlenintervall

2,  3,  4,  …,  n².

Sieben wir alle echten Vielfachen der 2 aus, so bleibt etwa die Hälfte der Zahlen übrig, also etwa n²/2. Für n = 3 und n² = 9 bleiben beispielsweise 2, 3, 5, 7, 9 übrig, für n = 4 und n² = 16 dagegen 2, 3, 5, 7, 9, 11, 13, 15. Die genaue Anzahl der übrigbleibenden Zahlen ist n²/2 für n gerade und (n² + 1)/2 für n ungerade. Sieben wir dagegen alle Vielfachen der 3 aus, so überleben etwa 2/3 der Zahlen, also etwa 2n²/3. Allgemein überleben etwa

(1 − ¹_p)  n²

Zahlen, wenn wir alle echten Vielfachen einer Primzahl p aussieben. Um alle Primzahlen unseres Intervalls zu erhalten, müssen wir nacheinander alle echten Vielfachen der Primzahlen p₁, …, p_k mit

p₁  <  …  <  p_k  ≤  n,  k = π(n),

aussieben. Dies genügt, denn jede zusammengesetzte Zahl unseres Intervall besitzt einen Primteiler kleinergleich n. Wr nehmen nun an, dass jede Siebung mit einer Primzahl p_i einen von den bisherigen Siebungen mit den Primzahlen p₁, …, p_i − 1 unabhängigen Anteil an den überlebenden Zahlen heraussiebt, sodass etwa der Anteil 1 − 1/p_i der bislang überlebenden Zahlen weiterhin überleben. Wir erhalten so die Abschätzung

n² ∏_{p ≤ n, p prim} (1 − ¹_p)

für die Anzahl der Primzahlen im Intervall { 2, …, n² }. Ist unsere Annahme zumindest asymptotisch korrekt, so gilt also

n² ∏_{p ≤ n, p prim} (1 − ¹_p)  ∼  π(n²).

Nach dem Primzahlsatz gilt π(n²) ∼ n²/log(n²). Setzen wir dies auf der rechten Seite ein und dividieren wir auf beiden Seiten durch n², so ergibt sich wegen log(n²) = 2log(n), dass

∏_{p ≤ n, p prim} (1 − ¹_p)  ∼  ¹_{2 log(n)}.

Diese asymptotische Aussage ist nicht richtig, aber unsere Überlegungen sind auch nicht vollkommen falsch! Franz Mertens hat 1874 (also noch vor dem Beweis des Primzahlsatzes) das folgende bemerkenswerte Ergebnis gezeigt:

 Numerisch gilt

e^−γ  =  0,561459483566885169824143214790…

Unsere Heuristik berechnet damit die Anzahl der Primzahlen im Zahlenintervall 2, …, n² asymptotisch zu etwas mehr als 0,56 n²/log(n), während nach dem Primzahlsatz 0,5 n²/log(n) herauskommen sollte. Unser Ansatz überschätzt damit die Anzahl der Primzahlen um etwa 12%. Dass die Anzahl der Primzahlen mit unserer Produktformel nicht korrekt berechnet und sogar überschätzt wird, ist als Mertens Paradox bekannt. Unsere Unabhängigkeitsannahme erweist sich als falsch. Der Satz von Mertens zeigt: Eine Siebung mit einer Primzahl p_i siebt in der Regel mehr Zahlen aus den die Siebungen mit p₁, …, p_i − 1 überlebenden Zahlen aus als wir erwarten würden. Asymptotisch überleben nur 0,5 n²/log(n) Zahlen die Siebung, während wir erwarten, dass mehr als 0,56 n²/log(n) Zahlen überleben. Kurz:

Das Sieb des Eratosthenes siebt stärker als gedacht.

 Das Phänomen lässt sich wahrscheinlichkeitstheoretisch formulieren und erklären: Die Wahrscheinlichkeit, dass eine zufällig ausgewählte natürliche Zahl durch 2 teilbar ist, ist 1/2. Allgemein ist die Wahrscheinlichkeit, dass eine zufällige natürliche Zahl durch p teilbar ist, gleich 1/p. Damit ist 1 − 1/p die Wahrscheinlichkeit einer Zufallszahl, nicht durch p teilbar zu sein. Nehmen wir nun an, dass die Ereignisse, nicht durch eine Primzahl p teilbar zu sein, unabhängig voneinander sind, so erhalten für das Ereignis, dass eine Zufallszahl relativ prim zu allen Primzahlen kleinergleich n ist, Produkte der oben betrachteten Form. Der Satz von Mertens zeigt, dass die Annahme der Unabhängigkeit bei dieser Berechnung der Anzahl der Primzahlen zu einem Fehler führt, und er gibt diesen Fehler genau an.

 Dass unser Ansatz die Primzahlen in einem Intervall 2, …, n² überschätzt, wird erst für relativ große n sichtbar. Für n = 100 sieben wir mit den ersten 25 Primzahlen p₁ = 2, p₂ = 3, …, p₂₄ = 89, p₂₅ = 97. Für i = 0, …, 25 setzen wir

a_i  =  „die Anzahl der Zahlen nach der i-ten Siebung“,

b_i  =  „die gerundete Zahl n² ∏_{1 ≤ j ≤ i} (1 − 1/p_j)“.

Die Zahlen a_i protokollieren die Durchführung des Siebs des Eratosthenes, die Zahlen b_i sind Schätzwerte für die a_i entsprechend unserer Heuristik. Die folgende Tabelle für n = 100 zeigt: Ab etwa der Hälfte des Verfahrens überschätzt unsere Heuristik die Anzahl der Primzahlen, am Ende wird sie unterschätzt.

Für größere n zeigt sich die Überschätzung wie im Satz von Mertens auch am Ende:

Korrelationen

 Im Hinblick auf die wahrscheinlichkeitstheoretische Interpretation bietet es sich an, bei festem n und Primzahlen p in { 1, …, n } die Zufallsvariablen

X_p : { 1, …, n² } → { 0, 1 } mit

X_p(k) = 1, falls p ein Teiler von k ist,  X_p(k) = 0, sonst

auf ihre Korrelation

ρ(X_p, X_q)  =  $\frac{\mathrm{E}(({\mathrm{X}}_{\mathrm{p}}-\mathrm{E}({\mathrm{X}}_{\mathrm{p}}))({\mathrm{X}}_{\mathrm{q}}-\mathrm{E}({\mathrm{X}}_{\mathrm{q}})))}{\sqrt{\text{Var}({\mathrm{X}}_{\mathrm{p}})\text{Var}({\mathrm{X}}_{\mathrm{q}})}}$

zu untersuchen. Für n = 10 erhalten wir für die vier Siebungsprimzahlen p₁ = 2, p₂ = 3, p₃ = 5, p₄ = 7 die folgende Korrelationsmatrix (mit gerundeten Korrelationskoeffizienten):

(ρ(X_pi, X_pj))_{1 ≤i, j ≤4}  =  $( \begin{array}{cccc}1& -0.021& 0& 0\\ -0.021& 1& -0.032& -0.038\\ 0& -0.032& 1& -0.058\\ 0& -0.038& -0.058& 1\end{array} )$

Die Korrelationskoeffizienten sind sehr klein, sodass die Zufallsvariablen „fast“ unabhängig sind. Auch für n = 100 und das Intervall von 1 bis 10000 sind die Koeffizienten klein. Der minimale und maximale Korrelationskoeffizient außerhalb der Diagonale der (25 x 25)-Matrix (mit 25 = π(100)) berechnet sich mit Hilfe eines Computer zu

ρ(X₆₁, X₈₃)  =  − 0,0069  bzw.  ρ(X₄₇, X₅₃)  =  0,000074.

Von den 300 Einträgen oberhalb der Diagonale sind 18 positiv, 19 gleich Null und 263 negativ. Für n = 500 erhalten wir die minimalen und maximale Werte

ρ(X₂₅₁, X₄₉₉)  =  − 0,0014  bzw.  ρ(X₅₃, X₁₃₁)  =  0,0000025.

Oberhalb der Diagonale der (95x95)-Matrix (mit 95 = π(500)) sind 117 Koeffizienten positiv, 31 gleich Null und 4317 negativ.

 Ist n gegeben und sind p, q ≤ n prim, so bedeutet ein negatives Vorzeichen von ρ(X_p, X_q), dass die Teilbarkeitseigenschaften einer Zahl k im Intervall von 1 bis n² bzgl. p und q eher einander entgegengesetzt als einander entsprechend sind. Viele negative Koeffizienten zusammen mit wenigen und sehr kleinen positiven Koeffizienten liefern damit eine Erklärung, warum beim Sieb des Eratosthenes mehr Zahlen ausgesiebt werden als es die Heuristik erwarten lässt. Warum die Vorzeichen der Koeffizienten derart verteilt sind, bleibt selbst erklärungsbedürftig.