Fachwissenschaftliches Seminarzur Zahlentheorie

Vortragsunterlagen zu:„Das Bertrandsche Postulat“

Eine Frage in der analytischen Zahlentheorie ist die Existenz von Primzahlen in gewissenIntervallen. In diesem Vortrag soll nun das (gelöste) Problem, ob es für jede natürlicheZahl n eine Primzahl p mit n < p ≤ 2n gibt, vorgestellt und bewiesen werden.

Das Bertrandsche Postulat

Wir haben gesehen, dass die Primzahlen 2,3,5,7,... eine unendlicheFolge bilden. Daraus kann man auch folgern, dass es beliebig große Lückenzwischen den Primzahlen geben muss. Schreibt man nämlich N :: 2 '3 '5 . . . . .p für das Produkt aller Primzahlen, die kleiner sind als k + 2, dannkann keine der k Zahlen

N + 2 ,1y ' + 3 , IV + 4 , . . . , l y ' + k ,N + ( k + 1 )

prim sein, denn für 2 < i <,k + t hat z einen Primfaktor, der kleinerist alsk + 2, und dieser Faktor teill auch ly', und damit auch .A/ + z. Mit diesemRezept finden wir zum Beispiel für k : 10, dass keine der zehnZahlen

2312.2313,2314, . . .,2321

prim ist.Aber es gibt trotzdem obere Schranken für die Größe der Lücken in derFolge der Primzahlen. Das ,,Bertrandsche Postulat'' besagt nämlich, dass,die Lücke bis zur nächsten Primzahl nie größer sein kann als die Zahl, ander wir die Suche beginnen". Diese berühmte Behauptung wurde 1845 vonJoseph Bertrand aufgestellt und immerhin bis n : 3 000 000 verifiziert.Vollständig bewiesen, für alle n, hat sie Pafnuty Tschebyschew im Jahr1850. Einen viel einfacheren Beweis hat das indische Genie Ramanujangefunden. Unser Beweis aus dem BUCH ist von Paul Erd6s: aus seinemersten Aufsatz, der 1932 erschien, als Erd6s 19 war.

ffi# Das Bertrandsche Postulat.f f i Fär jedesn) I g ibtes e ine Pr imzahlpmitn <p <2n.H

I Beweis. Wir werden die Größe des Binomialkoeffizienten (f) so genauabschätzen, dass wir zeigenkönnen, dass der Binomialkoeffizient,,zu kleinausfallen" würde, wenn er keine Primfaktoren im Bereich n < p I 2nhätte. Die Oper hat insgesamt fünf Akte.

(1) Wir beweisen das Bertrandsche Postulat zunächst für n < 4000. Dafürmuss man nicht 4000 Fälle überprüfen: Es reicht (das ist der ,,Landau-TricK') zu überprüfen, dass

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

Kapitel 2

Beweis eines Satres von T3chebyschef.Vüi P. EnDdi in 8ldnpcrt.

F(r den uoerst !on T$c{EBlscffEF trowlasenrn Satz) laqtdes*n €s zwischrn €iner f,ltürlichei Zahl rfid ihf€r rweitcheniicl. we.igstcns eiilc Primrahl gjbt, Iicgen i! dcr lilerallr nchrercRcwrise vor. Als einldchslen kann nän ohne Zwcifel dcn Fcwcis!ün R$ÄNUJANT) bcrfichiltn- lrt seilreh Wrrk Vtrlesililgen ilbelililhtanlhmrie (Leiprif, 1927i, Band I, S. 60*68 gibt H€rr LaND^ueinen bcsondcß €hhched Baweis l{r einen Sitz 6ber die Anrahldcr Ptinlnhlen lnter cirer gcgcbcncn Grclzc, als wßlchefi un-millelttar told, diß für ein gccignclcs t rwischcn eirer nalürlichenZrh l un , l jh te r q - fachrn s ic ls e im p ' in iTa l l l i rg l . Für d ie augea-blicklichen Zwecken des Hcrm L^NDAU konrnt es nlcht luf dl€numerisahe Bcstinrn)ung der im tselveis a0fkulenden Konslanlensni nan überzeugt $ich nber durch iinc fiunlcrische Vcrfolgungdrs Beweiscs lrichl. düß 4 jcdcnlalls gr6fief al$ 2 susfällt-

,n den irig,:nden Zeiltn werile i(L ?rigen, däß mar durchuinr Vrrslhärfurg der dlm LaN$^!schen Beweis zugrunde liegch-deh ldeen zü einem Beüeis des obln tNährlch TsH€BYsclEf-sc len Satzeg ge lcngrn lnnn. der - ' w ie mi r gLhr i f , t - 0n E in -fachkeil nicht hj0ter den llAüäNUJ,sschen llewcis sieht. {iriechischcl'lilchilahen snllin inr filgcndetr drrrchvügs po!ili!e, lnteiiis([eßu lhs ta l tn n l lü r l i chc Zah len I 'eze i€hneü j d ie Bczc ichn lng p i s tf ü f Pr imrah le i l v r ) rbeha l ten .

L Der B i f ,omolkoc f l i r i cu l

i2n\ -,- \?-u')-)\ 0 / ( n ! 1 "

--[i;ln^'^"' '"., ^ tlodi o! BedüM s Pns{rt!i:,loün41 ol th. tn-

dlak Molh.nttkdt S,r,?ir. tl il!rg). 5. l8t-lB -, CDlttt.d Pa!üs olssrxrvr$ RrrrNrjrAx (Qr'bfldg., lu?i, s. s-?I'.

Joseph Bertrand

Das Bertrandsche Postulat

I r''t t rN

eine Folge von Primzahlen ist, in der jede Primzahl kleiner ist als zweimaldie vorhergehende. Also enthält jedes Interval {y : n < A < 2n},mitn < 4000, eine dieser vierzehn Primzahlen.

(2) Als Nächstes zeigen wir

l lrp'1 t

wobei unsere Notation - hier und im Folgenden - implizieren soll, dassdas Produkt über alle Primzahlen p < n genommen wird. Unser Beweisdafür verwendet Induktion über die Anzahl dieser Primzahlen. Er stammtnicht aus Erd6s' erstem Aufsatz, aber er ist auch von Erd6s (der Rand

, zeigl Notizen dazu in seiner Handschrift), und er ist ein wahrer BUCH-Beweis. Zunächst gilt für die größte Primzahl q I r

T T " : I l o u n d 4 o - r I 4 t - 1 'T L Y I I "P 1 , P 1 q

Damit reicht es, (1) für den Fallzuzeigen,dass r : q eine Primzahl ist' Fürq : 2 erhaltenwir ,,2 ( 4', also kümmern wir uns jetzt um die ungeradenPrimzahlen q : 2m+I. (Dabei dürfen wir mit einem Induktionsschluss an-nehmen, dass die Aussage schon für alle ganzen Zahlenir. {2,3,. ",2*}bewiesen ist.) Für Q :2m t 1 zerlegen wir das Produkt und rechnen

< 4*22* : 42-

''l&d'l F''' ß4--k'4n , /l/LIt ßtll " q\ It")

, r hrtil\ t l t ^ t

'M'ft

(1 ,1. rl11s2:f [rn+l

l l l .lW nt^| 'ltw\

f '+*'lrtt*tt

,il.1 : ,A: **,il,;*,= n^('*:t)Alle Komponenten dieses ,fiinzeilers" sind leicht einzusehen. So gilt

i lpp 1 m { 7

nach Induktionsvoraussetzung. Die Ungleichung

TT , 1 (zm+t )r+ . \ m /n] I<P12ml1

folgt aus der Beobachtung, dass ('T\ : #-"#. eine ganze Zahl ist,wobei die Primzahlen, die auf der linken Seite auftauchen, alle den Zähler(2m + 1)! teilen, aber nicht den Nenner ml(m -l1)!. Und schließlich gilt

/ c - r 1 \

( " ; - ) = " -

weil(zm + i) uno f':' :.t)\ m / \ m r t /

zwei (gleiche!) Summanden sind, die in der Summe2 r n * L ^ r \\ - i : lm+ i \/ ' \ k Ik :0

'2' ' " -

enthalten sind.

Das B ertrandsche Postulat

(3) Nach dem Satz von Legendre (siehe den Kasten) enthält Cn :den Primfaktor p genau

. i- f l ' : l -, l3l)*. ,L. , r \ lpr )

- lpn J)

Mal. Dabei ist jeder Summand höchstens 1, weil er

_ ,

erfüllt und eine ganzeZahl ist. Die Summanden verschwinden sogar, wennpk > 2nist.Damit enthält ('zf) Aen Faktorp

m a x { r : p ' < 2 n }

Mal. Also ist die größte Potenz von p, die (2|) teitt, nicht größer als 2n.Insbesondere sind Primzahlenp, die größer als t/2n sind,höchstens einmalin (':) enthalten.Und schließlich - und laut Erd6s ist dies der Knackpunkt seines Beweises- teilen Primzahlen p im Bereich ?" a p ( n den Binomialkoeffizienten(2j) tiUertraupt nichtl Für 3p > 2n (und n ) 3, und damit p > 3) sindnämlich p und2p die einzigen Vielfachen von p, die als Faktoren imZähler

l r - \ lvon ffi auftauchen, während wir zwei p-Faktoren im Nenner haben.

(4) Ietzt können *n (':) abschätzen. Für n ) 3 erhalten wir mit einerAbschätzuns von Seite 13 für die untere Schranke

tk > 1

(2n) ln l n l Der Sak von Legendre

Die Zahl nl entltilt den Primfalaor pSenau

s l n l) l - lz-/ LDE .)

k > l '

Mal.

I Beweis. Cenau lf,J derFaktorenvon n ! = 1 '2 '3 . . . . .n s ind durchp teilbar, was uns lffJ r-fuktot"otiefert. Weiter sind LPI der Fakto-ren von n! sogar durch p2 teilbar,was die nächsten Lfrl f.irfuno.ropvonnt liefert, usw. tr(#)-,1#)) =

r1

*=( ' ! \= i l 2nv o /

P1 t ' t2ni l p I IP,

J2n<p< ]n n1P12n

Beispiele wie

GE) : z ' . b2 . 7 .17 . re .2s(11) : z t . 33 . b2 . r r .19 .22( i 3 ) : z ' . J2 . 5 . r r . r e . 2s . 2ezeigen, dass ,,sehr kleine" Primfaktorenp < \/2n in höherer Potenz in (2[)auftauchen können,,"kleine" Primzah-len mit t/Zn < p < Jn tauchenhöchstens einmal auf, während Faktorenin dem Intervall ?rn {p ( n überhauptnicht auftauchen.

und damit, weil es nicht mehr als J2nPrimzahlenp < 1/2n gibt,

4" < (2n)r+t/zn II p II p für n ) 3. (2)t/2n<p<ln n<P12n

(5) Nehmen wir nun an, dass es keine Primzahl p gibt mit n < p 1 2n,so dass das zweite Produkt in (2) also 1 ist. Durch Einsetzen von (1) in (2)erhalten wir

4^ < (2n)1+'/zn 4?",also

4ä" < (2r) ' *@, (3)

was für große n nicht stimmen kannl Das ist sogar so drastisch falsch, dasswir es (für n > 4000) ganz ohne Taschenrechner sehen können: Wenn wir

10 D as B ertrandsche Postulat

nämlich o. * 1 ( 2" verwenden (was für alle a ) 2 gilt, nach Induktion),so erhalten wir

2n: ( f /2" )u . ( l f /2" )+ 1)u < 26lv ' ; ) <26w, (4)

und damit für n, > 50 (so dass 1'8 < 2\/rn gilt) aus (3) und (4)

Zr" < lZrf(t+^/n) a 2tr/2"(tz+ra"/n) a 2zo Vzn'/2" : 220(2n)2/z .

Dies liefert (zn\r/s ( 20, und damit n < 4000. n

Aus solchen Abschätzungen kann man noch mehr herausholen: Aus (2)kann man mit denselben Methoden

i l p>2#" fü r n>4000n1P12n

ableiten und damit, dass es mindestens

logr. (zÄ') : n;----- -rog2n + r

Primzahlen in dem Bereich zwischen nund2n glbt.Das ist keine schlechte Abschätzung; die ,,wahrd' Zahl det Primzahlen indiesem Bereich ist ungefähr nf logn. Dies folgt aus dem ,trimzahlsatl"der besagt, dass der Grenzwert

. . # {p<n iPPr imzah l }L f r r r -

existiert, und gleich llrl oar", ffi;" Resultat wurde zuerst vonHadamard und de la Vall6e-Poussin 1896 bewiesen; Selberg und Erdöshaben 1948 einen elementaren Beweis (ohne komplexe Analysis, aberimmer noch lang und kompliziert) gefunden. Über den Primzahlsatz selbstist das letzte Wort wohl noch nicht gesprochen: So würde etwa ein Beweisder Riemannschen Vermutung (siehe Seite 48), eines der wichtigsten un-gelösten Probleme der Mathematik, auch eine substantielle Verbesserungder Abschätzungen im Primzahlsatz liefern. Aber auch das BertrandschePostulat könnte man noch ordentlich verbessern. Die folgende Frage vonOpperman (1832) ist nämlich immer noch nicht beantwortet [4, S. 248]:

Gibt es fi)r jedes n ) 2 mindestens eine Primzahl zwischen(n - 7)n und n2, und mindestens eine zwischen n2 und n(n * 1) ?Gibt es als'o zwischen lwei aufeinander folgenden Quadratzahlenimmer mindestens zwei Primzahlen?

Immerhin ist die letzte Aussage für den Fall bewiesen, dass man stattQuadratzahlen hinreichend große Kubikzahlen betrachtet [3].

130

Das Bertrandsche Postulat

In

is--rstisn-rg:le)n

Anhang: Einige AbschätzungenAbschätzung durch Integrale

Es gibt eine sehr-einfache-aber-effektive Methode, Summen durch Integra-le abzuschätzen (die uns schon auf Seite 4 begegnet ist). Um beispielsweisedie harmoni s c he n Zahl en

t,: i lAK

abzuschätzen, machen wir die nebenstehende Skizze und leiten aus ihrn 1 r n t

Hn- r : I i . I ]a t : Iosn7 " K J t L

ab, indem wir die Fläche unter dem Graphen von /(t) : + (1 3 t < n)mit der Fläche der dunkler schraffierten Rechtecke vergleichen, und

1 - - 1 1 f n 1

H ,_ ' : f i r I )a t : l osn ,' n k=u rk J t t

indem wir mit der Fläche der größeren Rechtecke (also auch der hellerschraffierten Teile) vergleichen. Zusammen genommen ergibt dies

l o g n - f ! < H . ( l o g n f 1 .n

Insbesondere gilt also ,t: r. ---+ oo, und die Wachstumsgeschwindigkeit

von Hn ist durch ,\g # : 1 gegeben. Aber man kennt viel bessereAbschätzungen (siehe [2]), wie

1 1 1 _ / 1 \H n : l o g n t . y + 2 n _ t 2 " r + t z o n n * " ( * / ,

wobei 1 x 0.5772die ,,Eulersche Konstante" bezeichnet.

Fakultäten abschätzen - die Stirlingsche Formel

Dieselbe Methode, auf

log(n!) : 1o82 * log3 *

angewendet, liefert

n. t i _ ,. . . * l o s n : ) I o e k

k:2

logtdt < log(nl) ,Iog((n - t)\ . 1,"wobei sich das Intesral leicht ausrechnen lässt:

Hier bezeichret O ($) eine Funktionf(n), die f(n) ! c4 erfüllt, für eineKonstante c > 0.

att

lr" ,ort d,t : [t rog t - t): : nLogn - n 'r 1.

D as B ertrands che Postulat12

Hierbedeutet f(n) - g(n)' dassl ( - \

l im r* :1 g i l t .n + @ g \ n )

Damit bekommen wir eine untere Abschärn'ng

n l , > e n t o a n - n * 7 : " ( : ) "

und gleichzeitig eine obere Abschätzung

n l : n ( n - 1 ) l . r " n l o s n - n * l : " " ( 2 ) "

Diese beiden Abschätzungen reichen für viele zwecke aus; wieder kannman aber ,,wenn nötigl. mit genauerer Analyse mehr herausholen, insbe-sondere die Stirlingsch, P6Y7n:eI

- / 7 1 ' \ nnl - tt2trn\-.)

Aber es gibt noch sehr viel präzisere versionen dieses Resultats, etwa

- / T ' L \ " / , 1 1 1 3 9 ^ / 1 \ \nt : t/2rnl:) (t* ' . * za,n, -

ir*op* " \A ) )

Binomialkoeffi zienten abschätzen

Schon aus der Definition der Binomialkoeffizienten (i) ats die Anzahl derk-Teilmengen einer n-Menge wissen wir, dass die Folge (ä)' (?), ' ' ' ,(:)der Binomialkoeffi zienten

o sich aufsummiert ,, i (1) :2"k:0

r symmetrischi* (i) : C1*).

Aus der FunktionalgleichunC (;) : "=P (*1 r) t"it"t man leicht ab, dassfür jedes n, die Binomialkoeffizienten (i) eine Folge bilden, die symme-trisih und unimodal ist: sie steigt bis zur Mitte an, so dass die mittlerenBinomialkoeffizienten die größten in der Folge sind:

1 : (ä) . (?) < .... i{p) : G,ipt)Hier bezeichnen fz.l bzw. [r'] diezahlr, abgerundetbzw. aufgerundetbiszur nächsten ganzen Zahl.Mit Hilfe der oben angegebenen Formeln für die Asymptotik der Fakultätenkann man sehr genaue Abschätzungen für die Größe der Binomialkoeffizi-enten ableiten. In diesem Buch brauchen wir aber nur sehr schwache undeinfache Abschätzungen, wie die folgenden:

11 1

7 2 11 3 3 1

1 4 6 41 5 1 0 1 0 5

1 6 1 5 2 0 1 51 7 2 1 3 5 3 5 2 7Das Pascalsche Dreieck

11

6 17 1

D as B e rtrandsche Po stulat 13

)rr)

SS

e-)n

IS

enzi-nd

und

f w n ) 2 ,

mit Gleichheit nur ftir n : 2.Insbesondere haben wu

für n, ) 1.

Der mittlere Binomialkoeffizient (ü"1) ist näimlich der größte Eintrag in

der Folge der n zahlen (ä) + fi), (?), (;), . . ., (.?-,,),deren Summe 2'und deren Mittelwert damit + ist.Schließlich halten wir als obere Schranke für die Binomialkoeffizienten

/ " \ _ n ( n - L ) " ' ( n - k * 1 , ) n k n kl l : -

\ k / k t S^<2* - t

fest, was eine halbwegs vemünftige Abschätzung fiir die ,,kleinen" Bino-mialkoeffizienten am Anfang der Folge ist, für die n im Vergleich zu kgroß ist.

Literatur[1] P. ERDös: Beweis eines Satzes von Tschebyschef, Acta Sci' Math. (Szeged) 5

(1930-32), 194-198.

t2l R. L. GRAHAM, D. E. KNUTH & O. PATASHNTKI Concrete Mathematics'A Foundationfor Computer Science, Addrson-Wesley, Reading MA 1989'

[3] F. IscHEBscK: Primzahlfragen und ihre Geschichte, Mathematische Seme-sterberichte 40 (1993), l2l-132.

[4] P. RIBENB otv.: The New Book of Prime Number Records, Springer-Verlag,New York 1989.

2nn

H