„Es gibt immer eine Primzahl zwischen n und 2n“ – Ein Beweis aus dem BUCH

Der ungarische Mathematiker Paul Erdős (1913-1996) meinte, dass man als Mathematiker, wenn nicht an Gott, so doch wenigstens an das BUCH glauben sollte, in welchem Gott die perfekten Beweise für mathematische Sätze aufbewahrt.

Martin Eigner und Günter Ziegler wagten eine Annäherung an eben jenes BUCH, eine Sammlung mit besonders „schönen“ Beweisen. Mit Ausnahme einiger kleinerer Abänderungen betrachten wir im folgenden Erdős‘ Beweis für das „Bertrandsche Postulat“ aus jenem „BUCH der Beweise“.

Der Mathematiker Joseph Bertrand (1822-1900) stellte 1845 die Behauptung auf, dass es zwischen jeder natürlichen Zahl und ihrem Doppeltem immer eine Primzahl gibt. Formaler ausgedrückt:

Für jedes $n \in \mathbb{N}$ existiert eine Primzahl $p$ mit $n < p \leq 2n$ .

Bertrand verifizierte die Behauptung für natürliche Zahlen bis $n = 3'000'000$ . Einen ersten vollständigen Beweis für das sog. „Bertrandsche Postulat“ lieferte Pafnuty Tschebyschef im Jahr 1850. Der vorliegende Ansatz beruht auf einem Beweis aus einem Aufsatz vor Paul Erdős, der 1932 erschien, als jener gerade mal 19 Jahre alt war.

Beweisprinzip:

Wir werden einen Widerspruchsbeweis (Reductio ad absurdum) durchführen, indem wir die Grösse des Binomialkoeffizienten ${2n \choose n}$ so genau abschätzen, dass wir zeigen können, dass der Binomialkoeffizient „zu klein ausfallen würde“, wenn er keine Primfaktoren im Bereich $n < p \leq 2n$ hätte.

Die „Oper“ hat insgesamt 5 Akte:

1. Akt: Das Bertrandsche Postulat für $n<4000$

Zunächst zeigen wir, dass das Bertrandsche Postulat für $n<4000$ gilt. Dafür müssen wir nicht alle 4000 Fälle prüfen. Es genügt, wenn man folgende Primzahlen betrachtet:

2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 4001

Jedes Intervall $\{ y: n< y \leq 2n \}$ für $n \leq 4000$ enthält eine dieser Primzahlen.

– – – – – – – –

2. Akt: Eine untere Abschätzung für ${2n \choose n}$

Lemma:

Für $n \in \mathbb{N}$ gilt die Abschätzung $\frac{4^n}{2n} \leq {2n \choose n}$

Beweis:

Wir wenden den binomischen Lehrsatz auf $(1+1)^{2n}$ an:

$4^n = 2^{2n} = (1+1)^{2n} = \sum_{k=0}^{2n} {2n \choose k} 1^k 1^{2n-k} = \sum_{k=0}^{2n} {2n \choose k}$

Wir ziehen den ersten und den letzten Summanden aus der Summe hinaus:

$\sum_{k=0}^{2n} {2n \choose k} = {2n \choose 0} + {2n \choose 2n} + \sum_{k=1}^{2n-1} {2n \choose k} = 2 + \sum_{k=1}^{2n-1} {2n \choose k}$

Da ${2n \choose n}$ auf jeden Fall der grösste Binomialkoeffizient ist (siehe auch im Pascalschen Dreieck unten), können wir 2 und ${2n \choose k}$ jeweils mit ${2n \choose n}$ abschätzen, insgesamt addieren wir diesen Koeffizienten somit 2n mal:

$2 + \sum_{k=1}^{2n-1} {2n \choose k} \leq {2n \choose n} + \sum_{k=1}^{2n-1} {2n \choose n} = 2n * {2n \choose n}$

Nun brauchen wir nur noch 2n „rüberzudividieren“:

$4^n \leq 2n * {2n \choose n}$

$\frac{4^n}{2n} \leq {2n \choose n}$

Veranschaulichung im Pascal’schen Dreieck:

Das Pascal’sche Dreieck ist ein Schema zur Darstellung der Binomialkoeffizienten ${n \choose k}$ . Es entspricht der Vorschrift, dass jede Zahl die Summe der beiden über ihr stehenden Zahlen ist. Den Koeffizienten ${n \choose k}$ findet man dabei in der n-ten Zeile an der k-ten Stelle (beide ab Null gezählt).

Das gleiche Dreieck in Binomialkoeffizienten:

Berechnen wir $\sum_{k=0}^{n} {n \choose k}$ , summieren wir also alle Zahlen in der n-ten Zeilen des Pascal’schen Dreiecks, was $2^n$ entspricht.

Im obigen Beweis sind nur die geraden Zeilen von Bedeutung. Daraus resultiert: $\sum_{k=0}^{2n} {2n \choose k} = 4^n$ .

Alle geraden Zeilen im Pascal’schen Dreieck enthalten jeweils ein „mittleres“ Element, das jeweils ${2n \choose n}$ entspricht und jeweils der grösste Koeffizient einer Zeile ist. Alle anderen Koeffizienten kommen jeweils doppelt vor.

– – – – – – –

3. Akt: Eine Abschätzung für das Produkt über alle Primzahlen $p \leq x$

Lemma:

Für jede reelle Zahl $x \leq 2$ gilt: $\prod_{p \leq x} p \leq 4^{x-1}$ .

Wir schätzen also das Produkt aller Primzahlen bis x mit $4^{x-1}$ ab.

Grafisch veranschaulicht ist $4^{x-1}$ die Kurve einer Exponentialfunktion und $\prod_{p \leq x} p$ hat eine „Treppenform“, die jeweils bei einer Primzahl einen „Sprung“ macht. Wir müssen also zeigen, dass die „Treppe“ nie über die „Kurve“ hinausgeht:

Der Beweis erfolgt mittels vollständiger Induktion:

Induktionsanfang: x = 2

$\prod_{p \leq 2} p = 2 \leq 4^{2-1} = 4$ .

Induktionsschritt:

Da 2 die einzige gerade Primzahl ist, müssen wir die Behauptung nur noch für ungerade Zahlen zeigen:

Sei $x = 2m + 1$ mit $m \in \mathbb{N}$ . Die Aussage gelte für $x=2,...,2m$ .

Zu zeigen ist also, dass gilt: $\prod_{p \leq 2m+1} p \leq 4^{2m}$ .

Wir teilen das Produkt „geschickt“ in 2 Produkte auf:

$\prod_{p \leq 2m+1} p =\prod_{p \leq m+1} p * \prod_{m+1 \leq p \leq 2m+1} p$

Da m+1 in der Induktionsvoraussetzung für 2m enthalten ist, gilt:

$\prod_{p \leq m+1} p * \prod_{m+1 \leq 2m+1} p \leq 4^m * \prod_{m+1 < p \leq 2m} p$

Da letzterer Term $\leq 4^{2m}$ sein soll (und $4^m$ bereits darin enthalten ist), müssen wir nur noch zeigen, dass

$\prod_{m+1 < p \leq 2m+1} p \leq 4^m$

Wir schätzen dieses Produkt mit einem Binomialkoeffizienten ab:

$\prod_{m+1 < p \leq 2m+1} p \leq \frac{(2m+1)!}{m! (m+1)!} = {2m+1 \choose m}$

Überlegung dazu: In (2m+1)! ist auf jeden Fall jede Primzahl zwischen m+1 und 2m+1 enthalten. Im Nenner wird jedoch kein Primfaktor grösser als m+1 rausgekürzt. Unsere gewünschten Primzahlen bleiben also in der Primfaktorenzerlegung von ${2m+1 \choose m}$ erhalten.

Veranschaulicht im Pascal’schen Dreieck:

Die Binomialkoeffizienten ${2m+1 \choose m}$ sind jeweils in einer ungeraden Zeile eines der beiden „Mittleren“. Die Summe über einer ungeraden Zeile ergibt in diesem Fall $2*4^m$ . Die Summe der beiden „mittleren“ Koeffizienten ist also sicher kleiner als $2*4^m$ und da sie jeweils paarweise vorkommen, können wir durch 2 dividieren.

Für die Abschätzung wenden wir diesmal den binomischen Lehrsatz auf $(1+1)^{2m+1}$ an:

$2*4^m = (1+1)^{2m+1} = \sum_{k=0}^{2m+1} {2m+1 \choose k}$

Diesmal ziehen wir die beiden „mittleren“ Koeffizienten aus der Summe hinaus:

$\sum_{k=0}^{2m+1} {2m+1 \choose k} = 2 * {2m+1 \choose m} + \sum_{k=0, k \neq m, k \neq m+1}^{2m+1} {2m+1 \choose k}$

Da wir von oben abschätzen, können wir die restliche Summe „weglassen“ und erhalten dadurch die Ungleichung

$2*4^m \leq 2 * {2m+1 \choose m}$

$4^m \leq {2m+1 \choose m}$

– – – – – – –

Zwischenspiel: Die Identität von Legendre

Sei $n \in \mathbb{N}$ . Für die Vielfachheit einer Primzahl p in der Primfaktorenzerlegung von n! gilt:

$\nu_{p} (n!) = \sum_{k=1}^{\infty} \lfloor \frac{n}{p^k}\rfloor$

Die Vielfachheit sagt aus, wie oft eine Primzahl p in der Primfaktorenzerlegung einer Zahl n vorkommt.

Dies lässt sich leicht nachvollziehen: Genau $\lfloor \frac{n}{p}\rfloor$ der Faktoren von $n! = 1*2*3*...*n$ sind durch $p$ teilbar, was uns $\lfloor \frac{n}{p}\rfloor$ p-Faktoren liefert. Weiter sind $\lfloor \frac{n}{p^2}\rfloor$ der Faktoren von $n!$ sogar durch $p^2$ teilbar, was die nächsten $\lfloor \frac{n}{p^2}\rfloor$ Primfaktoren $p$ von $n!$ liefert, usw.

Die folgende Tabelle veranschaulicht die Vielfachheiten der Zahlen von 2 bis 10 und der Primzahlen 2, 3, 5 und 7.

Wenn wir nun die Vielfachheit von $n!$ berechnen, dann addieren sich die Vielfachheiten der Faktoren. Beispiel:

$\nu_{2} (10!) = 1+2+1+3+1= \sum_{k=1}^{\infty} \lfloor \frac{n}{2^k}\rfloor = \lfloor \frac{10}{2} \rfloor + \lfloor \frac{10}{4} \rfloor + \lfloor \frac{10}{8} \rfloor + \lfloor \frac{10}{16} \rfloor + ... = 8$

– – – – – – –

4. Akt: Die Primfaktorzerlegung von ${2n \choose n}$

Nach der Identität von Legendre enthält ${2n \choose n} = \frac{2n!}{n!n!}$ den Primfaktor $p$ genau

$\sum_{k=1}^{\infty} \left( \lfloor \frac{2n}{p^k} \rfloor - 2 \lfloor \frac{n}{p^k} \rfloor \right)$

Mal.

Beobachtungen:

Jeder Summand ist höchstens 1, weil er $\lfloor \frac{2n}{p^k} \rfloor - 2 \lfloor \frac{n}{p^k} \rfloor < \frac{2n}{p^k} - 2 * \left( \frac{n}{p^k} - 1 \right) = 2$ erfüllt.
Die Summanden verschwinden sogar, wenn $p^k > 2n$ ist.
Jede Primzahl p potenziert mit ihrer Vielfachheit ergibt also immer höchstens 2n.
Beispiel: Sei n = 15 und damit ${2n \choose n} = {30 \choose 15}$ . Wir wissen, dass die Potenz $2^5$ nicht in der Primfaktorenzerlegung von ${30 \choose 15}$ vorkommen kann, da $2^5 \geq 30$ .
Primzahlen $p$ die grösser als $\sqrt{n}$ sind, sind höchstens einmal in ${2n \choose n}$ enthalten.
Im Bereich von $2/3n < p \leq n$ ist die Vielfachheit einer Primzahl p gleich 0! D.h. Primzahlen p teilen im Bereich $2/3n < p \leq n$ den Binomialkoeffizienten ${2n \choose n}$ überhaupt nicht! Das ist der Knackpunkt in Erdős‘ Beweis!
Für $3p > 2n$ (und $n \geq 3$ , und damit $p \geq 3$ ) sind nämlich p und 2p die einzigen Vielfachen von p, die als Faktoren im Zähler von $\frac{2n!}{n!n!}$ auftauchen, während wir zwei p-Faktoren im Nenner haben.
Beispiel: Sei n = 15 und damit ${2n \choose n} = {30 \choose 15} = 2^4 * 3^2 * 5 * 17 * 19 * 23 * 29$ . Bereits aufgrund unserer Erkenntnisse können wir sagen, dass „sehr kleine“ Primfaktoren $p < \sqrt{2n} = \sqrt{30} = 5.477...$ in höherer Potenz in ${30 \choose 15}$ auftauchen können, „kleine“ Primzahlen mit $\sqrt{2n} < p \leq \frac{2}{3} n$ bzw. in unserem Beispiel $5.477 < p < 10$ tauchen höchstens einmal auf und Primfaktoren im Intervall $\frac{2}{3} n < p \leq n$ bzw. $10 < p \leq 15$ tauchen überhaupt nicht auf.

Für die Vielfachheit $\nu_{p} \left( {2n \choose n} \right)$ gilt also:

– – – – – – –

5. Akt: Das grosse Finale

Nun können wir ${2n \choose n}$ abschätzen (für $n \geq 3$ ):

$\frac{4^n}{2n} \leq {2n \choose n} \leq \prod_{p \leq \sqrt{2n}} 2n * \prod_{\sqrt{2n}\leq p \leq 2/3n} p * \prod_{n < p \leq 2n} p$

Und weil es nicht mehr als $\sqrt{2n}$ Primzahlen $p \leq \sqrt{2n}$ gibt:

$4^n \leq (2n)^{1+\sqrt{2n}} * \prod_{\sqrt{2n}\leq p \leq 2/3n} p * \prod_{n < p \leq 2n} p$

Für den Widerspruchsbeweis nehmen wir nun an, dass es keine Primzahl p gibt zwischen n und 2n.

Wenn es keine Primzahl $p$ gibt mit $n < p \leq 2n$ , so ist in der obigen Ungleichung das zweite Produkt gleich 1.

Nun setzen wir noch die Abschätzung $\prod_{p \leq x} p \leq 4^{x-1}$ (siehe 3. Akt) ein und erhalten:

$4^n \leq (2n)^{1+\sqrt{2n}} * 4^{\frac{2}{3} n}$

Umgeformt ergibt sich:

$4^{\frac{1}{3} n} \leq (2n)^{1+\sqrt{2n}}$

Dies ist für grosse n ( $> 467$ ) auf jeden Fall falsch! Und für n kleiner als 4000 haben wir Bertrand’s Postulat eh schon bewiesen.

q.e.d. 🙂

– – – – – – –

Nachspiel: Geht es noch besser?

Aus unserer Ungleichung kann man noch mehr herausholen. So kann man aus

$\prod_{n< p \leq 2n} p \geq 2^{\frac{1}{30}n}$ für $n \geq 4000$ herleiten, dass es mindestens

$\log_{2n} \left( 2^{\frac{1}{30}n} \right) = \frac{1}{30} \frac{n}{\log_{2} n + 1}$ Primzahlen im Bereich zwischen n und 2n gibt.

Der Primzahlsatz besagt, dass die Anzahl der Primzahlen unter einer gegebenen Grösse nicht mehr als ungefähr 10% nach unten und nach oben von der logarithmischen Funktion $\frac{x}{\ln (x)}$ abweicht.

Eine Verschärfung von Bertrands Postulat ist der Satz von Sylvester, der besagt, dass der Binomialkoeffizient ${n \choose k}$ immer einen Primteiler $p > k$ hat.

Viele Fragen bleiben jedoch bis heute unbeantwortet, etwa ein Beweis der Riemannschen Vermutung oder der Frage, ob es zwischen $n^2$ und $n(n+1)$ immer mindestens eine Primzahl gibt.

– – – – – – –

Weiterführende Informationen:

M. Aigner, G. M. Ziegler: Das BUCH der Beweise. 2. Auflage, 2004, insb. S. 7-13.
P. Erdős: Beweis eines Satzes von Tschebyschef. In: Acta Sci. Math. 5 (1930-1932), S. 194-198. (Online)
P. Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. 2. Auflage, 2004.
U. Dudley: Elementary Number Theory. 2008, insb. S. 177-179.
de.wikipedia.org: Bertrandsches Postulat
youtube.com: Das Bertrandsche Postulat

Teilen mit:

Hinterlasse einen Kommentar Antwort abbrechen