2. Der Satz von Chebyshev, II
In diesem Essay weisen wir die Existenz einer unteren Schranke c1 wie im Satz von Chebyshev nach. Es ergibt sich dadurch ein neuer Beweis für die Unendlichkeit der Primzahlen, der im Hinblick auf die Primzahlzählfunktion alle bisherigen Beweise in den Schatten stellt.
Strategie des Beweises
Wir verwenden erneut die mittleren Binomialkoeffizienten
bn = = (2n)!n!n! = (n + 1)(n + 2) … (2n)n! mit n ≥ 1
und zeigen, dass die Primfaktorzerlegung von bn „kleine“ Faktoren im folgenden Sinne besitzt:
(+) Jeder Faktor pe der Primfaktorzerlegung von bn ist beschränkt durch 2n.
Damit können wir die kleinen Exponenten der Primfaktorzerlegungen von bn in unseren Tabellen erklären: Ist p > , so ist p2 > 2n. Folglich ist der Exponent von p in der Primfaktorzerlegung von bn kleinergleich 1. Und auch für die kleineren Primzahlen sind die Faktoren beschränkt durch 2n, sodass ihre Exponenten nicht allzu groß sein können. Da die Primfaktorzerlegung von bn höchstens π(2n) Faktoren besitzt (jeder Primteiler von bn ist kleinergleich 2n), erhalten wir aus (+):
(++) bn ≤ (2n)π(2n).
Nun ist die Primzahlzählfunktion auf der rechten Seite einer Abschätzung aufgetaucht, sodass wir durch Anwendung des Logarithmus untere Schranken für diese Funktion erhalten können!
Anwendung des Satzes von Legendre auf die Binomialkoeffizienten
Entscheidendes Hilfsmittel zum Beweis von (+) ist der Satz von Legendre, an den wir erinnern möchten:
Satz (Satz von Legendre)
Seien n ≥ 1 und p prim. Dann gilt
exp(n!) = ⌊np⌋ + ⌊np2⌋ + ⌊np3 ⌋ + …
Damit erhalten wir ein das folgende sehr wichtige Ergebnis:
Satz (p-Exponenten von bn)
Seien n ≥ 1. Dann ist jeder Faktor pexp(bn) der Primfaktorzerlegung von bn beschränkt durch 2n. Insbesondere ist exp(bn) ≤ 1, falls p > . Genauer gilt für jede Primzahl p:
exp(bn) = ∑k ≥ 1 ( ⌊2npk⌋ − 2 ⌊npk⌋ ) ≤ αp, wobei
αp = „das größte k mit pk ≤ 2n“ = ⌊log(2n)log(p)⌋ .
Beweis
Nach Definition gilt
bn = (2n)!n!n!,
sodass
exp(bn) = exp(2n!) − 2exp(n!).
Damit ergibt sich die erste Identität aus der zweifachen Anwendung des Satzes von Legendre und des Kommutativgesetzes. Die Ungleichung folgt aus der allgemeinen Eigenschaft
⌊2x⌋ − 2 ⌊x⌋ ∈ { 0, 1 } für alle x ∈ ℝ.
der Rundungsfunktion und der Tatsache, dass alle Summanden gleich 0 sind, sobald pk > 2n. Damit tragen höchstens αp Summanden den Wert 1 zur Summe bei.
Die im Beweis verwendete 0-1-wertige Funktion ⌊2x⌋ − 2 ⌊x⌋
Damit haben wir das Ziel (+) unserer Strategie erreicht und das Phänomen der „kleinen Exponenten“ der Primfaktorzerlegung der mittleren Binomialkoeffizienten erklärt (aber immer noch nicht vollständig analysiert und verwertet, vgl. die folgenden Essays). Es fehlt nun nur noch ein letzter Schritt:
Eine untere Schranke für den Satz von Chebyshev
Aus dem Satz über die p-Exponenten von bn können wir nun zum ersten Mal eine Abschätzung für die Primzahlzählfunktionen gewinnen, in der die Funktion n/log(n) auf der linken Seite auftaucht. Zunächst erreichen wir dies nur für gerade Stellen der Form π(2n), sodass noch technische Nacharbeiten notwendig sind − zum Glück aber in einem sehr kleinen Umfang.
Satz (Satz von Chebyshev, untere Schranke für gerade Stellen)
Sei n ≥ 1. Dann gilt:
π(2n) ≥ log(2) nlog(2n) = log(2)2 2nlog(2n).
Beweis
Nach dem vorangehenden Satz gilt mit den dortigen Bezeichnungen:
bn = ∏p ≤ 2n pexp(bn) ≤ ∏p ≤ 2n pα(p) ≤ ∏p ≤ 2n 2n = (2n)π(2n).
Unsere elementare untere Abschätzung 2n ≤ bn liefert
2n ≤ (2n)π(2n).
Anwendung der Logarithmus-Funktion liefert die Ungleichung.
Damit sind wir fast am Ziel. Durch Halbierung des Faktors log(2) erhalten wir die noch fehlende Abschätzung von π an ungeraden Stellen 2n + 1:
Satz (Satz von Chebyshev, untere Schranke)
Für alle n > 1 gilt:
π(n) ≥ log(2)4 nlog(n).
Beweis
Für gerade n haben wir die Ungleichung bereits bewiesen (sogar besser mit 2 statt 4 im Nenner). Für ungerade n beobachten wir, dass
π(2n + 1) ≥ π(2n) ≥ log(2)4 4nlog(2n) ≥ log(2)4 2n + 1log(2n + 1),
wobei wir zuletzt verwenden, dass 4n ≥ 2n + 1 und log(2n) ≤ log(2n + 1) für alle n ≥ 1 gilt.
Beispiel
Wegen log(2n) = n log(2) ergeben sich schöne Abschätzungen für die Potenzen von 2. Für alle n ≥ 1 gilt
π(2n) ≥ log(2)4 2nlog(2n) = 2n4n.
Der Leser vergleiche dies mit den Ergebnissen unserer früheren Beweise der Unendlichkeit der Primzahlen.
Eine verbesserte Konstante
Die Schranke log(2)/4 = 0,1732… liegt nicht sehr nahe an der 1. Ein besseres Ergebnis können wir erhalten, wenn wir anstelle der Abschätzung 2n ≤ bn die schärfere Abschätzung 22n/(2n) ≤ bn verwenden:
Satz (Satz von Chebyshev, verbesserte untere Schranke)
Sei n ≥ 1. Dann gilt:
π(2n) ≥ log(2) 2nlog(2n) − 1.
Weiter gilt:
(a) | π(2n) ≥ log(2) nlog(2n) + 1 für alle n ≥ 2. |
(b) | π(n) ≥ log(2)2 nlog(n) für alle n > 1. |
Beweis
Wie oben gilt bn ≤ (2n)π(2n). Mit 22n/(2n) ≤ bn gilt 22n ≤ (2n)π(2n) + 1, woraus die Abschätzung durch Anwendung des Logarithmus folgt.
Ist n ≥ 8, so ist 4n ≥ (2n)4, sodass log(2)n ≥ 2log(2n). Also ist
π(2n) ≥ log(2)nlog(2n) + log(2)nlog(2n) − 1 ≥ log(2)nlog(2n) + 2 − 1.
Dies zeigt (a) für alle n ≥ 8. Dass die Ungleichung auch für n = 2, …, 7 gilt, kann leicht durch Ausrechnen überprüft werden.
Aus (a) ergibt sich (b) für alle geraden Zahlen größergleich 4. Offenbar gilt die Ungleichung auch für n = 2, sodass (b) für alle geraden Zahlen gezeigt ist. Ist nun n ≥ 2, so gilt nach (a), dass
π(2n + 1) ≥ π(2n) ≥ log(2)2 2nlog(2n + 1) + 1 ≥ log(2)2 2n + 1log(2n + 1),
wobei wir zuletzt verwenden, dass log(2)/(2log(2n + 1)) ≤ 1 für alle n ≥ 1. Schließlich gilt (b) für n = 3, sodass die Aussage für alle n ≥ 1 gezeigt ist.
Damit haben wir also unsere Konstante log(2)/4 um den Faktor 2 verbessert. Die Verbesserung der Konstanten im Satz von Chebyshev kann man als eine Art Sport betreiben. Systematische Abschätzungen, die Werte c1,k, c2,k, sk mit
c1, k nlog(n) ≤ π(n) ≤ c2, k nlog(n) für alle n ≥ sk, limk c1, k = limk c2, k = 1
ans Licht brächten, würden einem elementaren Beweis des Primzahlsatzes gleichkommen.
Zusammenfassung zum Satz von Chebychev
Wir haben gezeigt:
Satz (Satz von Chebyshev)
Für alle n > 1 gilt:
log(2)2 nlog(n) ≤ π(n) ≤ 3 log(2) nlog(n).
mit log(2)/2 = 0,3465… und 3log(2) = 2,0794…
Die beiden Konstanten ergaben sich durch eine Analyse der Primfaktorzerlegung der mittleren Binomialkoeffizienten: Die Faktoren der Zerlegung von bn sind beschränkt durch 2n (entscheidend für die untere Schranke) und alle Primzahlen zwischen n und 2n kommen in der Zerlegung vor (entscheidend für die obere Schranke). Insgesamt haben wir einen engen Zusammenhang zwischen π(n) und n/log(n) hergestellt, und unsere Abschätzungen lassen es plausibel erscheinen, dass die beiden Konstanten noch weiter von unten und oben an die 1 angenähert werden können. Der Satz von Chebychev ist ebenso bestechend wie unfertig: Er ruft uns mit seinen eher zufällig wirkenden Konstanten auf, die Primzahlzählfunktion genauer zu untersuchen. Bevor wir dies tun wollen wir noch einige Früchte ernten (Bertrandsches Postulat) und weitere Geheimnisse der Primfaktorzerlegung der Binomialkoeffizienten lüften.