3. Das Bertrandsche Postulat

Bereits unsere ersten Abschätzungen der Primzahlzählfunktion haben ergeben, dass es für alle n ≥ 1 mindestens n Primzahlen im Intervall { 1, …, 2ⁿ } gibt (vgl. den Essay zum kombinatorischen Beweis von Perott). Dies motiviert die folgende Frage:

Liegt zwischen 2ⁿ und 2^n + 1 immer mindestens eine Primzahl?

Die Antwort ist „ja“, und es gilt sogar stärker:

 Das Ergebnis besticht durch seine einfache Formulierung: Zwischen einer Zahl und ihrem Doppelten liegt immer eine Primzahl. Dabei kann „zwischen“ sogar als „echt zwischen“ gelesen werden, wenn wir Zahlen ab 2 betrachten: Für alle n ≥ 2 gibt es eine Primzahl p mit n < p < 2n. Denn ist n ≥ 2, so ist 2n eine gerade zusammengesetzte Zahl.

 Der Satz von Bertrand-Chebyshev wurde 1845 als Hypothese von Joseph Bertrand formuliert und für viele Zahlen wie in unseren Beispielen per Hand verifiziert. Chebyshev gelang kurze Zeit später ein analytischer Beweis der Hypothese von Bertrand (veröffentlicht 1852). Wir geben in diesem Essay einen Beweis des „Elementarmagiers“ Erdös von 1932, der auf dem Beweis des Satzes von Chebyshev aufbaut. Erdös verwendete Methoden, die Landau in seinen „Vorlesungen über Zahlentheorie“ von 1927 entwickelt hatte. Zunächst wollen wir die Aussage noch etwas genauer betrachten. Äquivalent ist:

Diese Version folgt unmittelbar aus der obigen. Um die Umkehrung einzusehen, nehmen wir an, dass die Primzahlformulierung gilt. Das Bertrandsche Postulat gilt für n = 1. Ist nun n ≥ 2 beliebig, so sei q die größte Primzahl kleinergleich n. Dann gibt es eine Primzahl p mit q < p ≤ 2q. Aufgrund der Maximalität von q ist p > n. Wegen q ≤ n gilt 2q ≤ 2n, sodass insgesamt n < p ≤ 2n.

 Durch die Konzentration auf Primzahlen wie in der Primzahlformulierung lässt sich das Bertrandsche Postulat für ein großes Anfangsstück der natürlichen Zahlen überraschend leicht nachweisen. Ist

2 = p₁  <  p₂  <  p₃  <  …  <  p_k

eine Folge von Primzahlen mit p_i + 1 < 2p_i für alle i < k, so zeigt die Folge, dass für alle n < p_k eine Primzahl p mit n < p ≤ 2n existiert, d. h. das Postulat gilt „bis p_k“. Zum Beweis betrachten wir wieder ein maximales i mit p_i ≤ n.

 Nach diesen Vorbereitungen können wir nun den Beweis des Bertrandschen Postulats nach Erdös präsentieren. Dabei bauen wir auf den Ergebnissen und Methoden auf, die wir in den vorangehenden Essays zum Satz von Chebyshev entwickelt haben.

Schritt 1:  Abschätzung der Primzahlfakultät

 Wir beginnen mit einer für sich interessanten Abschätzung des Produkts der ersten Primzahlen. Für jede natürliche Zahl n hatten wir die Primzahlfakultät n# definiert durch

n#  =  „das Produkt aller Primzahlen p mit p ≤ n“  =  ∏_p ≤ n p.

(Hier und im Folgenden bezeichnet wieder ein „p“ im Index einer Summe oder eines Produkts stets eine Primzahl.)

Mit Hilfe der mittleren Binomialkoeffizienten können wir nun zeigen:

Schritt 2:  Neue Abschätzung der mittleren Binomialkoeffizienten

 Sei n ≥ 1. Wir haben schon verwendet, dass in den mittleren Binomialkoeffizienten

b_n  =  $( \genfrac{}{}{0ex}{}{2\mathrm{n}}{\mathrm{n}} )$  =  ^{(n + 1)(n + 2) … (2n)}_n!

jede Primzahl p mit n < p ≤ 2n jeweils genau einmal vorkommt. Erdös hat nun bemerkt (er spricht in seiner Arbeit vom „springenden Punkt“ seines Beweises), dass die Primzahlen zwischen 2/3 n und n gar nicht vorkommen:

 Der Leser vergleiche hierzu noch einmal die Tabelle der Primfaktorzerlegungen von b₁, …, b₂₀ im vorletzten Essay. Es gilt b₁ = 2 und b₂ = 6, sodass die Voraussetzung n ≥ 3 (die p ≠ 2 impliziert) wichtig ist.

 Sei n ≥ 3. Dann können wir die die Primfaktorzerlegung von b_n schreiben als

b_n  =  ∏_{2 ≤ p ≤ 2n/3} p^ex_p(b_n)  ∏_{n < p ≤ 2n} p.

Wir setzen nun w = $\sqrt{2\mathrm{n}}$. Dann gilt ⌊w⌋ ≤ n, sodass wir die folgende dreiteilige Darstellung erhalten:

b_n  =  ∏_{2 ≤ p ≤ w} p^ex_p(b_n)  ∏_{w < p ≤ 2n/3} p^ex_p(b_n)  ∏_{n < p ≤ 2n} p.

Nun schätzen wir die drei Produkte der Reihe nach ab:

Wir erhalten damit:

 Das folgende Diagramm visualisiert das Ergebnis.

Schritt 3:  Beweis des Bertrandschen Postulats

 Wir haben nun alle Bausteine in der Hand, um das Bertrandsche Postulat in einer starken Form beweisen zu können. Für alle n ≥ 1 setzen wir

B(n)  =  π(2n)  −  π(n)  (mit „B“ wie „Bertrand“).

Wir verwenden die dritte Abschätzung, die etwas einfacher zu handhaben ist und eine durchweg positive Abschätzung liefert. Sei also n ≥ 98 (oder n ≥ 6 mit der Bemerkung). Dann gilt

(+)  ²²ⁿ_2n  ≤  b_n  <  (2n)^{$\sqrt{\mathrm{n}/2}$ − 1} 4^{2n/3 − 2} (2n)^B(n)

Ab jetzt werden die Binomialkoeffizienten nicht mehr benötigt. Multiplikation mit 2n und Sammeln der Potenzen ergibt

4^n/3 + 2  <  (2n)^{$\sqrt{\mathrm{n}/2}$ + B(n)}.

Durch Anwendung der Logarithmusfunktion zur Basis 2 erhalten wir

(n/3 + 2) log₂(4)  <  ($\sqrt{\mathrm{n}/2}$ + B(n)) log₂(2n).

Es gilt log₂(4) = 2. Wir haben also gezeigt:

Unsere Diagramme machen glaubhaft, dass die rechte (blau gezeichnete) Seite der Ungleichung des Satzes für alle n ≥ 1 positiv ist. Der Nachweis wird mit Hilfe der folgenden Abschätzung relativ übersichtlich:

 Damit können wir nun zeigen:

 Damit haben wir weit mehr bewiesen als das Bertrandsche Postulat. Zwischen einer natürlichen Zahl n und ihrem Doppelten befinden sich für große n sehr viele Primzahlen. Die Größenordnung der rechten Seite des Satzes entspricht der Größenordnung n/log(n) des Primzahlsatzes.