5. Der kombinatorische Beweis von Erdös

Die Divergenz der harmonischen Primzahlreihe lässt sich, wie vielleicht Erdös zuerst bemerkt hat, mit Hilfe der kombinatorischen Argumentation, die wir im Abschnitt über andere Beweise des Satzes von Euklid kennengelernt hatten, ohne Verwendung analytischer Hilfsmittel beweisen. Tatsächlich war es das Hauptziel der Arbeit von Erdös 1938, einen elementaren Beweis zu geben. Wir erinnern an die in dieser Arbeit bewiesene Abschätzung:

Satz (Abschätzung der darstellbaren Zahlen, II)

Seien p₁ < … < p_k Primzahlen, und sei n ≥ 1. Dann gilt

D(p₁, …, p_k; n²) ≤ n 2^k,

wobei D(p₁, …, p_k; n²) die Anzahl der mit p₁, …, p_k darstellbaren Zahlen im Intervall { 1, …, n² } bezeichnet.

Mit Hilfe dieser Abschätzung geben wir nun einen neuen Beweis von:

Satz (Divergenz der harmonischen Primzahlreihe)

∑_{p prim} ¹_p = ∞.

Beweis (Erdös)

Wir nehmen an, dass die Summe endlich ist. Für alle n ≥ 1 sei p_n die n-te Primzahl. Nach unserer Annahme gibt es ein k derart, dass

¹_{p_k + 1} + ¹_{p_k + 2} + … < ¹₂.

Sei nun n eine beliebige natürliche Zahl. Ist p eine Primzahl, so gibt es genau ⌊ n²/p ⌋ Zahlen im Intervall { 1, …, n² }, die p als Teiler besitzen. Damit ist die Anzahl der Zahlen in { 1, …, n² }, die mindestens eine Primzahl p_n mit n > k als Teiler besitzen, beschränkt durch

^n²_{p_k + 1} + ^n²_{p_k + 2} + … < ^n²₂.

Folglich gibt es mindestens n² − n²/2 = n²/2 viele Zahlen in { 1, …, n² }, die sich mit Hilfe der Primzahlen p₁, …, p_k darstellen lassen. Nach der Abschätzung der darstellbaren Zahlen gilt also

n²/2 ≤ D(p₁, …, p_k; n²) ≤ n 2^k,

sodass

n ≤ 2^k + 1.

Diese Ungleichung ist falsch, wenn wir n hinreichend groß wählen. Damit ist unsere Annahme widerlegt und die Summe unendlich.

Die Kehrwerte 1/p erscheinen in diesem Argument als relative Häufigkeiten. Jede p-te natürliche Zahl ist ein Vielfaches von p. Nach der Abschätzung der darstellbaren Zahlen sind bei festem k nur sehr wenige Zahlen in { 1, …, n² } mit Hilfe der ersten k Primzahlen darstellbar, wenn wir n groß genug wählen. Dann kommt bei den meisten Zahlen in { 1, …, n } mindestens eine der anderen Primzahlen p_k + 1, p_k + 2, … vor, und dies führt dazu, dass die relativen Häufigkeiten 1/p in ihrer Summe unbeschränkt sind.

Verwendung der Abschätzungen von Thue und Perott

Der Divergenz-Beweis lässt sich analog mit Hilfe der Abschätzung D(p₁, …, p_k; 2ⁿ) ≤ n^k aus dem Beweis von Thue führen. Wir erhalten hier 2ⁿ/2 ≤ n^k, was nicht sein kann, wenn n groß genug ist. Ebenso ist die Abschätzung D(p₁, …, p_k; n) < 2^k + n/2 aus dem Beweis von Perott geeignet, wenn wir innerhalb unserer Annahme der Endlichkeit der Reihe ein k mit

1/p_k + 1 + 1/p_k + 2 + … < 1/3

betrachten. Dann ist 2n/3 ≤ D(p₁, …, p_k; n) ≤ 2^k + n/2, was für hinreichend große n falsch ist. Offenbar haben Perott (1881) und Thue (1897) die Anwendung ihrer kombinatorischen Zählung auf die harmonische Primzahlreihe übersehen. Erdös hat vermutlich die Arbeiten nicht gekannt, als er sein Argument 1938 (im Alter von 25 Jahren) veröffentlichte.