1. Der Satz von Chebyshev, I

Im Jahr 1852 veröffentlichte Chebychev eine Abschätzung der Primzahlzählfunktion, die die Funktion n/log(n) ins Rampenlicht rückt. Es ergibt sich dadurch ein neuer sehr starker Beweis der Unendlichkeit der Primzahlen. Weiter konnte Chebychev das Bertrandsche Postulat beweisen, demzufolge sich zwischen einer Zahl n und 2n immer mindestens eine Primzahl befindet. Diese Ergebnisse bilden das Thema dieses Abschnitts. Sie lassen sich − vor allem durch weitere Arbeiten von Ernst Landau (1927) und Paul Erdös (1932) − vergleichsweise kurz und elementar beweisen. Es wird keine komplexe Analysis verwendet. Im Zentrum stehen Binomialkoeffizienten, kombinatorische Zählungen und trickreiche, aber letztendlich einfache Abschätzungen.

 Das Hauptergebnis lässt sich wie folgt formulieren:

Satz (Satz von Chebyshev)

Es gibt reelle Zahlen c1, c2 mit 0 < c1 < 1 < c2 derart, dass für alle n > 1 gilt:

c1 nlog(n)  ≤  π(n)  ≤  c2 nlog(n).

 Im nächsten Abschnitt werden wir den Primzahlsatz betrachten, der zur Zeit von Chebyshevs Arbeit eine offene Vermutung war. Dieser Satz ist äquivalent dazu, dass für alle c1 < 1 < c2 ein n0 > 1 existiert, sodass für alle n ≥ n0 gilt:

c1 nlog(n)  ≤  π(n)  ≤  c2 nlog(n).

In diesem Sinne ist der Satz von Chebyshev eine Vorstufe des Primzahlsatzes, die die Größenordnung der Primzahlzählfunktion korrekt erfasst.

 Der Satz lässt sich in verschiedenen Varianten beweisen. Dabei gilt: Je näher die Konstanten c1 und c2 bei der 1 liegen, desto schwieriger wird ein Beweis (und die Abschätzungen gelten dann in der Regel nicht mehr für alle n ≥ 1, sondern nur noch ab einer Stelle n0. Wir streben hier einen möglichst kurzen Beweis an und zeigen die Aussage mit den Konstanten

c1  =  log(2)/4  =  0,1732…

c2  =  3log(2)  =  2,0794…

Für interessierte Leser verbessern wir die erste Konstante dann noch zu log(2)/2.

 Der Beweis zerfällt in zwei Teile, wobei der Nachweis der oberen Schranke c2 etwas einfacher ist. In diesem Essay ermitteln wir c2, im folgenden dann c1.

Die mittleren Binomialkoeffizienten

 Für unseren Beweis des Satzes von Chebyshev spielen die mittleren Binomialkoeffizienten

bn  =  2nn  =  (2n)!n!n!  =  (n + 1)(n + 2) … (2n)n!  mit n ≥ 1

eine Schlüsselrolle. Die folgende mit Hilfe eines Computers berechnete Tabelle gibt einen Eindruck von diesen Koeffizienten.

n

bn

Primfaktorzerlegung von bn

1

2

21

2

6

21 · 31

3

20

22 · 51

4

70

21 · 51 · 71

5

252

22 · 32 · 71

6

924

22 · 31 · 71 · 111

7

3432

23 · 31 · 111 · 131

8

12870

21 · 32 · 51 · 111 · 131

9

48620

22 · 51 · 111 · 131 · 171

10

184756

22 · 111 · 131 · 171 · 191

11

705432

23 · 31 · 71 · 131 · 171 · 191

12

2704156

22 · 71 · 131 · 171 · 191 · 231

13

10400600

23 · 52 · 71 · 171 · 191 · 231

14

40116600

23 · 33 · 52 · 171 · 191 · 231

15

155117520

24 · 32 · 51 · 171 · 191 · 231 · 291

16

601080390

21 · 32 · 51 · 171 · 191 · 231 · 291 · 311

17

2333606220

22 · 33 · 51 · 111 · 191 · 231 · 291 · 311

18

9075135300

22 · 31 · 52 · 71 · 111 · 191 · 231 · 291 · 311

19

35345263800

23 · 31 · 52 · 71 · 111 · 231 · 291 · 311 · 371

20

137846528820

22 · 32 · 51 · 71 · 111 · 131 · 231 · 291 · 311 · 371

Die mittleren Binomialkoeffizienten b1, …, b20

Augenfällig sind die durchweg sehr kleinen Exponenten der Primfaktorzerlegungen. Auch in der Primfaktorzerlegung der riesigen Zahl

b100  =  90548514656103281165404177077484163874504589675413336841320

ist jeder Exponent kleinergleich 3. Die Zahl b100 ist durch 23 und 132 teilbar, alle anderen Exponenten sind gleich 1 (vgl. die folgende Tabelle). Die Primfaktorzerlegung der Binomialkoeffizienten wird im Folgenden eine wichtige Rolle spielen und wir werden sie genau untersuchen.

 Die mittleren Binomialkoeffizienten bieten zahlreiche Möglichkeiten für eigene Entdeckungen. Wir fügen deswegen noch Beispiele für größere n an.

n

Primfaktorzerlegung von bn

21

23 · 3 · 5 · 11 · 13 · 23 · 29 · 31 · 37 · 41

22

23 · 3 · 5 · 13 · 23 · 29 · 31 · 37 · 41 · 43

23

24 · 33 · 52 · 13 · 29 · 31 · 37 · 41 · 43

24

22 · 32 · 52 · 13 · 29 · 31 · 37 · 41 · 43 · 47

25

23 · 32 · 72 · 13 · 29 · 31 · 37 · 41 · 43 · 47

26

23 · 33 · 72 · 17 · 29 · 31 · 37 · 41 · 43 · 47

27

24 · 72 · 17 · 29 · 31 · 37 · 41 · 43 · 47 · 53

28

23 · 5 · 7 · 11 · 17 · 29 · 31 · 37 · 41 · 43 · 47 · 53

29

24 · 3 · 5 · 7 · 11 · 17 · 19 · 31 · 37 · 41 · 43 · 47 · 53

30

24 · 7 · 11 · 17 · 19 · 31 · 37 · 41 · 43 · 47 · 53 · 59

31

25 · 7 · 11 · 17 · 19 · 37 · 41 · 43 · 47 · 53 · 59 · 61

32

2 · 32 · 72 11 · 17 · 19 · 37 · 41 · 43 · 47 · 53 · 59 · 61

60

24 · 32 · 7 · 13 · 17 · 23 · 31 · 37 · 61 · 67 · 71 · 73 · 79 · 83 · 89 · 97

· 101 · 103 · 107 · 109 · 113

61

25 · 32 · 7 · 112 · 13 · 17 · 23 · 31 · 37 · 67 · 71 · 73 · 79 · 83 · 89 · 97

· 101 · 103 · 107 · 109 · 113

62

25 · 33 · 7 · 112 · 13 · 17 · 23 · 37 · 41 · 67 · 71 · 73 · 79 · 83 · 89 · 97

· 101 · 103 · 107 · 109 · 113

63

26 · 3 · 53 · 112 · 13 · 17 · 23 · 37 · 41 · 67 · 71 · 73 · 79 · 83 · 89 · 97

· 101 · 103 · 107 · 109 · 113

64

2 · 3 · 53 · 112 · 13 · 17 · 23 · 37 · 41 · 67 · 71 · 73 · 79 · 83 · 89 · 97

· 101 · 103 · 107 · 109 · 113 · 127

100

23 · 3 · 5 · 11 · 132 · 17 · 37 · 53 · 59 · 61

· 101 · 103 · 107 · 109 · 113 · 127 · 131 · 137 · 139 · 149

· 151 · 157 · 163 · 167 · 173 · 179 · 181 · 191 · 193 · 197 · 199

127

27 · 33 · 7 · 11 · 132 · 19 · 23 · 43 · 47 · 67 · 71 · 73 · 79 · 83

· 131 · 137 · 139 · 149 · 151 · 157 · 163 · 167 · 173 · 179 · 181 · 191 · 193 · 197 · 199

· 211 · 223 · 227 · 229 · 233 · 239 · 241 · 251

128

2 · 34 · 5 · 7 · 11 · 132 · 17 · 19 · 23 · 43 · 47 · 67 · 71 · 73 · 79 · 83

· 131 · 137 · 139 · 149 · 151 · 157 · 163 · 167 · 173 · 179 · 181 · 191 · 193 · 197 · 199

· 211 · 223 · 227 · 229 · 233 · 239 · 241 · 251

200

23 · 32 · 5 · 72 · 11 · 172 · 192 · 23 · 29 · 41 · 43 · 53 · 67 · 71 · 73 · 79

· 101 · 103 · 107 · 109 · 113 · 127 · 131 · 211 · 223 · 227 · 229

· 233 · 239 · 241 · 251 · 257 · 263 · 269 · 271 · 277 · 281 · 283 · 293

· 307 · 311 · 313 · 317 · 331 · 337 · 347 · 349

· 353 · 359 · 367 · 373 · 379 · 383 · 389 · 397

 Wir halten einige Eigenschaften unserer Koeffizienten fest. Sei hierzu n ≥ 1 beliebig. Aufgrund der kombinatorischen Bedeutung der Binomialkoeffizienten ist bn die Anzahl der n-elementigen Teilmengen der Menge { 1, …, 2n }. Da diese Menge genau 22n Teilmengen besitzt, gilt bn ≤ 22n. Alternativ lässt sich der Binomische Lehrsatz verwenden, um dies einzusehen:

22n  =  (1 + 1)2n  =  ∑k ≤ 2n 2nk 1k 12n − k  =  ∑k ≤ 2n 2nk  ≥  bn.

Weiter gilt

bn  =   (n + 1)(n + 2) … (n + n)1 · 2 · … · n  =  ∏1 ≤ k ≤ n n + kk  ≥  ∏1 ≤ k ≤ n 2  =  2n.

Insgesamt ist also 2n ≤ bn ≤ 22n. Wir können diese Abschätzung noch verbessern:

Satz (Größenabschätzung der mittleren Binomialkoeffizienten)

Sei n ≥ 1. Dann gilt:

22n2n  ≤  bn  ≤  22n − 1.

Beweis

Zum Beweis der ersten Ungleichung beobachten wir, dass bn maximal unter allen Binomialkoeffizienten 2nk mit 0 ≤ k ≤ n ist. Denn ist k ≤ n beliebig, so zeigt ein Vergleich der Faktoren, dass

n! n!  ≤  k! (2n − k)!

Hieraus folgt die Behauptung. Damit gilt:

(+)  bn  ≥  2n0 + 2n2n,  2n1,  …,  2n2n−1,

wobei wir für die erste Ungleichung noch verwenden, dass bn ≥ 2 = 1 + 1.

Da die 2n Zahlen auf der rechten Seite in (+) die Summe 22n besitzen, muss eine dieser Zahlen größergleich 22n/(2n) sein. Da bn maximal unter diesen Zahlen ist, ergibt sich die erste Ungleichung.

Zum Beweis der zweiten Ungleichung sei N die Menge aller n-elementigen Teilmengen von M = { 1, …, 2n }. Wir definieren nun eine Funktion

f : N → ℘(M) − N

wie folgt: Ist A  ∈  N und 2n  ∉  A, so setzen wir f (A) = A ∪ { 2n }. Andernfalls sei f (A) = A − { 2n }. Dann ist f injektiv, sodass

|N|  ≤  |℘(M) − N|  =  22n − |N|.

Folglich ist

bn  =  |N|  ≤  22n /2  =  22n − 1.

prim1-AbbID-bincoeff1

Die Binomialkoeffizienten 20k für k = 0, …, 20. Der mittlere Koeffizienten ist b10.

Gezeigt sind zudem die Schranken 220/20 = 52428,8 und 219 = 524288 für b10.

 Der folgende Satz gibt einen ersten Eindruck von der Bedeutung der Binomialkoeffizienten für die Primzahlen. Zudem erklärt er bereits die 1-Exponenten bei den größeren Primzahlen in den Primfaktorzerlegungen der obigen Tabelle.

Satz (Teilbarkeitseigenschaften der mittleren Binomialkoeffizienten)

Sei n ≥ 1. Dann gilt:

(1)

bn ist gerade.

(2)

Jeder Primfaktor von bn ist kleinergleich 2n.

(3)

Sei p prim mit n < p ≤ 2n. Dann ist p ein Teiler von bn.

(4)

(n + 1)π(2n) − π(n)  ≤  ∏n < p ≤ 2n p  ≤  bn.

(5)

Ist n ≥ 2, so ist ∏n < p ≤ 2n p  ≤  bn/2.

Beweis

Es gilt bn = 2 2n−1n−1, sodass bn gerade ist. Kombinatorische Alternative: Sei N die Menge aller n-elementigen Teilmengen von M = { 1, …, 2n }. Mit jedem A  ∈  N ist auch das Komplement M − A  ∈  N. Damit ist bn gerade. Die Aussagen (2) und (3) folgen aus der Bruchdarstellung

bn  =  (n + 1)(n + 2) … (2n)n!.

Eine Primzahl p > 2n kommt im Zähler nicht vor. Eine eine Primzahl p mit n < p < 2n kommt im Zähler, nicht aber im Nenner vor, sodass sie nicht gekürzt wird. Die erste Ungleichung in (4) gilt, da das Produkt aus genau π(2n) − π(n) Faktoren größergleich n + 1 besteht. Da jede Primzahl p im Intervall { n + 1, …, 2n } ein Teiler von bn ist, gilt auch die zweite Ungleichung. Die Ungleichung (5) ergibt sich daraus, dass bn für alle n ≥ 1 gerade ist und die Primzahl 2 nicht im Produkt auftaucht, falls n ≥ 2.

Eine obere Schranke

 Wir haben nun alle Bausteine zusammen, um die zweite Hälfte des Satzes von Chebyshev beweisen zu können. Entscheidend ist die Abschätzung

nπ(2n) − π(n)  ≤  (n + 1)π(2n) − π(n)  ≤  bn  ≤  22n − 1  für alle n ≥ 1,

aus der sich

nπ(2n)  ≤  22n − 1 nπ(n)  für alle n ≥ 1

ergibt. Hieraus lässt sich induktiv eine Abschätzung für nπ(n) gewinnen, die zu einer oberen Schranke für π(n) führt. Die folgende Darstellung folgt der eleganten Version aus [ Robertson/Staton 2005 ]. Wir brauchen noch einen Hilfssatz:

Satz (Abschätzung von π(2n))

Für allen n ≥ 8 gilt π(2n) ≤ n − 2.

Beweis

Alle geraden Zahlen größer als 2 sind nicht prim. Weiter sind 1, 9 und 15 nicht prim. Damit gilt für alle n ≥ 8, dass

π(2n)  ≤  |{ 1, …, 2n } − ({ 4, 6, 8, …, 2n } ∪ { 1, 9, 15 })|  =  n − 2.

 Damit können wir nun zeigen:

Satz (Satz von Chebyshev, obere Schranke)

Sei n ≥ 1. Dann gilt:

(+)  nπ(n)  <  23n.

Folglich gilt

π(n)  ≤  3log(2) n/log(n)  für alle n > 1.

Beweis

Die Ungleichung lässt sich leicht für n = 1, …, 14 direkt verifizieren. Sei nun n ≥ 8 derart, dass (+) für n gilt, d. h. es gelte nπ(n) < 23n. Dann folgt aus unseren Abschätzungen, dass

(2n − 1)π(2n − 1)  <  (2n)π(2n)  =  2π(2n) nπ(2n)  =  2π(2n) nπ(2n) − π(n) nπ(n)

 <  2n − 2 bn 23n  ≤  2n − 2 22n − 1 23n  =  26n − 3  =  23(2n − 1)  <  23(2n).

Diese Abschätzung zeigt, dass sich die Gültigkeit der Ungleichung (+) für jedes n ≥ 8 von n nach 2n − 1 und 2n vererbt. Von 8 vererbt sich (+) also auf 15 und 16, von 9 auf 17 und 18, …, von 14 auf 27 und 28, von 15 auf 29 und 30 usw. Damit gilt (+) für alle n ≥ 1 (Beweis durch starke Induktion oder Betrachtung eines kleinsten Gegenbeispiels). Der Zusatz ergibt sich durch Anwendung der Logarithmus-Funktion.