Arithmetische Progressionen von Primzahlen - uni-due.dehx0050/pdf/av.pdf · Primzahlen Primzahlsatz Satz von Szemer´edi Verallg. von Green/Tao Anwendung Deﬁnition Eine arithmetische

Primzahlen Primzahlsatz Satz von Szemeredi Verallg. von Green/Tao Anwendung

Arithmetische Progressionen von Primzahlen


Sei N := {1, 2, 3, . . . } die Menge der naturlichen Zahlen.

Definition

Eine Primzahl ist eine naturliche Zahl > 1, die nur durch 1 unddurch sich selbst teilbar ist.

Beispiel

2, 3, 5, 7, 11, . . . , 232582657 − 1, . . .

Theorem (Eindeutige Primfaktorzerlegung)

Jede naturliche Zahl lasst sich als Produkt von Primzahlenschreiben, und diese Darstellung ist eindeutig bis auf dieReihenfolge der Faktoren.


Sei N := {1, 2, 3, . . . } die Menge der naturlichen Zahlen.

Definition

Eine Primzahl ist eine naturliche Zahl > 1, die nur durch 1 unddurch sich selbst teilbar ist.

Beispiel

2, 3, 5, 7, 11, . . . , 232582657 − 1, . . .

Theorem (Eindeutige Primfaktorzerlegung)

Jede naturliche Zahl lasst sich als Produkt von Primzahlenschreiben, und diese Darstellung ist eindeutig bis auf dieReihenfolge der Faktoren.


Es gibt unendlich viele Primzahlen. Sogar:

1

2+

1

3+

1

5+

1

7+ · · · =

∑p Primzahl

1

pdivergiert.

Viele andere Fragen uber die Struktur der Menge der Primzahlensind offen, zum Beispiel

Vermutung

Es gibt unendlich viele Primzahlzwillinge, also Primzahlen p, sodass auch p + 2 eine Primzahl ist.


Es gibt unendlich viele Primzahlen. Sogar:

1

2+

1

3+

1

5+

1

7+ · · · =

∑p Primzahl

1

pdivergiert.

Viele andere Fragen uber die Struktur der Menge der Primzahlensind offen, zum Beispiel

Vermutung

Es gibt unendlich viele Primzahlzwillinge, also Primzahlen p, sodass auch p + 2 eine Primzahl ist.


Definition

Eine arithmetische Progression von Primzahlen der Lange k isteine Folge p1, p2, . . . , pk von Primzahlen, derart dass je zweiaufeinander folgende Glieder der Folge den gleichen Abstandhaben:

p2 − p1 = p3 − p2 = · · · = pk − pk−1 6= 0

Beispiel

5, 11, 17, 23, 29 (Lange 5, Abstand 6)

5 + 12 · i , i = 0, 1, . . . , 4.

56.211.383.760.397 + 44.546.738.095.860i , i = 0, 1, . . . , 22

(M. Frind, P. Jobling, P. Underwood 2004)


Definition

Eine arithmetische Progression von Primzahlen der Lange k isteine Folge p1, p2, . . . , pk von Primzahlen, derart dass je zweiaufeinander folgende Glieder der Folge den gleichen Abstandhaben:

p2 − p1 = p3 − p2 = · · · = pk − pk−1 6= 0

Beispiel

5, 11, 17, 23, 29 (Lange 5, Abstand 6)

5 + 12 · i , i = 0, 1, . . . , 4.

56.211.383.760.397 + 44.546.738.095.860i , i = 0, 1, . . . , 22

(M. Frind, P. Jobling, P. Underwood 2004)


1 2 3 4 5 6 7 8 9 10 11 12

13 14 15 16 17 18 19 20 21 22 23 24

25 26 27 28 29 30 31 32 33 34 35 36

37 38 39 40 41 42 43 44 45 46 47 48

49 50 51 52 53 54 55 56 57 58 59 60

61 62 63 64 65 66 67 68 69 70 71 72

73 74 75 76 77 78 79 80 81 82 83 84

85 86 87 88 89 90 91 92 93 94 95 96

97 98 99 100 101 102 103 104 105 106 107 108

109 110 111 112 113 114 115 116 117 118 119 120

121 122 123 124 125 126 127 128 129 130 131 132

133 134 135 136 137 138 139 140 141 142 143 144

145 146 147 148 149 150 151 152 153 154 155 156

157 158 159 160 161 162 163 164 165 166 167 168

169 170 171 172 173 174 175 176 177 178 179 180

2 3 5 7 11

13 17 19 23

29 31

37 41 43 47

53 59

61 67 71

73 79 83

89

97 101 103 107

109 113

127 131

137 139

149 151

157 163 167

173 179



Theorem (Green, Tao 2004)

Zu jeder naturlichen Zahl k gibt es unendlich viele arithmetischeProgressionen von Primzahlen der Lange k.

Vorher bekannte Resultate:

van der Corput 1939: Es gibt unendlich viele arithmetischeProgressionen von Primzahlen der Lange 3.


Theorem (Green, Tao 2004)

Zu jeder naturlichen Zahl k gibt es unendlich viele arithmetischeProgressionen von Primzahlen der Lange k.

Vorher bekannte Resultate:

van der Corput 1939: Es gibt unendlich viele arithmetischeProgressionen von Primzahlen der Lange 3.


Offensichtliche Einschrankungen:Ist p, p + r , . . . , p + (k − 1)r eine AP von Primzahlen der Lange k,mit Abstand r , so gilt

Alle Primzahlen < k teilen r .

Beispiel (k=23)

r ≥ 2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 = 223.092.870

Frind, Jobling, Underwood: r = 44.546.738.095.860

Abschatzung nach oben

Green, Tao: moglich ist p + (k − 1)r ≤ 2222222100k

Vermutung: moglich ist p + (k − 1)r ≤ k! + 1,fur k = 23: 23! + 1 = 25.852.016.738.884.976.640.001




Beispiel (k=23)

r ≥ 2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 = 223.092.870








Beispiel (k=23)

r ≥ 2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 = 223.092.870






Der Primzahlsatz

Seiπ(x) = |{p ∈ N; p Primzahl, p ≤ x}|.

0

2.5

5

7.5

10

12.5

15

17.5

20

0 10 20 30 40 50

Theorem (Hadamard, de la Vallee-Poussin 1896)

π(x) ∼ x

log x.


Der Primzahlsatz


0

2 · 103

4 · 103

6 · 103

8 · 103

1 · 104

1.2 · 104

0 2 · 104 4 · 104 6 · 104 8 · 104 1 · 105


π(x) ∼ x

log x.


Der Primzahlsatz


0

2 · 103

4 · 103

6 · 103

8 · 103

1 · 104

1.2 · 104

0 2 · 104 4 · 104 6 · 104 8 · 104 1 · 105


π(x) ∼ x

log x.


Der Primzahlsatz


0

2 · 103

4 · 103

6 · 103

8 · 103

1 · 104

1.2 · 104

0 2 · 104 4 · 104 6 · 104 8 · 104 1 · 105


π(x) ∼ x

log x.


Die Hardy-Littlewood-Vermutung

Wir konnen den Primzahlsatz benutzen, um eine heuristischeUberlegung durchzufuhren, wie viele arithmetische Progressionenvon Primzahlen wir erwarten sollten.

“Wahrscheinlichkeit”, dass x ∈ {1, 2, . . . ,N} prim ist: 1log(N)

Sei 1 ≤ r ≤ N. Wir konnen hoffen, dass die Ereignisse, dass xbzw. x + r prim sind, im wesentlichen unabhangig sind, also

P(x prim und x + r prim) = P(x prim)P(x + r prim) =1

log(N)2.


Die Hardy-Littlewood-Vermutung

Wir konnen den Primzahlsatz benutzen, um eine heuristischeUberlegung durchzufuhren, wie viele arithmetische Progressionenvon Primzahlen wir erwarten sollten.

“Wahrscheinlichkeit”, dass x ∈ {1, 2, . . . ,N} prim ist: 1log(N)

Sei 1 ≤ r ≤ N. Wir konnen hoffen, dass die Ereignisse, dass xbzw. x + r prim sind, im wesentlichen unabhangig sind, also

P(x prim und x + r prim) = P(x prim)P(x + r prim) =1

log(N)2.


Wir fuhren das fort, lassen außerdem den Startpunkt x und denAbstand r variieren, und erhalten heuristisch, dass fur x , r imBereich {1, 2, . . . ,N} ungefahr

N2

log(N)k

arithmetische Progressionen von Primzahlen der Lange k existierensollten.

Diese Argumentation ist offensichtlich zu naiv: wir haben schongesehen, dass r von allen Primzahlen ≤ k geteilt werden muss.

Vermutung (Hardy, Littlewood 1923)

Fur alle k gilt

|{AP von PZ der Lange k mit Startpkt., Abstand in {1, . . . ,N}}|

=γkN2

log(N)k(1 + o(1)).



N2

log(N)k




Fur alle k gilt


=γkN2

log(N)k(1 + o(1)).



N2

log(N)k




Fur alle k gilt


=γkN2

log(N)k(1 + o(1)).


Die Vermutung von Erdos und Turan

Statt nach der Struktur der Menge aller Primzahlen zu fragen,kann man auch fragen, unter welchen Bedingungen eine TeilmengeA ⊆ N arithmetische Progressionen beliebiger Lange enthaltenmuss.

Vermutung (Erdos, Turan 1936)

Ist A ⊆ N eine Teilmenge, so dass∑a∈A

1

adivergiert,

dann enthalt A arithmetische Progressionen beliebiger Lange.


Die Vermutung von Erdos und Turan

Statt nach der Struktur der Menge aller Primzahlen zu fragen,kann man auch fragen, unter welchen Bedingungen eine TeilmengeA ⊆ N arithmetische Progressionen beliebiger Lange enthaltenmuss.

Vermutung (Erdos, Turan 1936)

Ist A ⊆ N eine Teilmenge, so dass∑a∈A

1

adivergiert,

dann enthalt A arithmetische Progressionen beliebiger Lange.


Der Satz von Szemeredi

Theorem (Szemeredi 1975)

Sei A ⊆ N eine Teilmenge mit positiver oberer Dichte, d. h.

lim supN→∞

|A ∩ [1,N]|N

> 0

Dann enthalt A arithmetische Progressionen beliebiger Lange.

Allerdings ist die Dichte von {p Primzahl} ⊂ N gleich 0.


Furstenbergs Beweis

Theorem (Furstenberg 1977)

Sei (X ,B, µ) ein Wahrscheinlichkeitsraum, T : X −→ X einemaßerhaltende Abbildung, d. h. µ(T−1(M)) = µ(M) fur alleM ∈ B. Seien A ∈ B mit µ(A) > 0 und k ∈ N.Dann existiert n ∈ N, so dass

µ(k−1⋂j=0

T−jnA) > 0.


Wende dies an wie folgt: Sei Λ ⊆ Z eine Teilmenge mit positiverDichte.

Definiere T : P(Z) −→ P(Z) durchTM := {n ∈ Z; n + 1 ∈ M}.Sei X der Abschluss von {T nΛ; n ∈ Z} in P(Z),

sei A = {M ∈ X ; 0 ∈ M}.Definiere ein T -invariantes Maß µ auf X mit µ(A) > 0 undfolgere

T n′Λ ∈k−1⋂j=0

T−jnA

fur n, n′ geeignet.


Der schwach mischende Fall

Bernoulli-System:

Seien p1, . . . , pr ∈ R≥0 mit∑r

i=1 pi = 1.

Betrachte (X ,B, µ,T ) gegeben durch

X = {(ωi )i∈Z;ωi ∈ {1, 2, . . . , r}},B die kleinste σ-Algebra, so dass alle Abb. (ωi )i 7→ ωi0

messbar sind,

µ das Produktmaß

µ(ωi1 = j1, ωi2 = j2, . . . , ωin = jn) = pj1 · · · pjn .

T ((ωi )i ) = (ωi+1)i .


Satz

Sei (X ,B, µ,T ) ein Bernoulli-System, und seien A0, . . . ,Ak ∈ B.Dann gilt

limn→∞

µ(A0 ∩ T−nA1 ∩ · · · ∩ T−knAk) = µ(A0)µ(A1) · · ·µ(Ak).


Der kompakte Fall

Sei X = R/Z, B die Borel-σ-Algebra und µ das vomLebesgue-Maß auf R induzierte W-Maß auf X . Sei T : X −→ Xgegeben durch x 7→ x + α, α ∈ R.

Satz

In dieser Situation gilt fur alle k ≥ 1:

lim infN→∞

1

N

N∑n=1

µ(A ∩ T−nA ∩ · · · ∩ T−knA) > 0.


Umformulierung von Szemeredis Satz

Identifiziere {1, . . . ,N} = Z/N.

Fur eine Funktion f : Z/N −→ R und A ⊆ Z/N setze

E (f (n)|n ∈ A) =1

|A|∑n∈A

f (n).

Theorem (Szemeredi)

Sei k ≥ 3, 0 < δ ≤ 1, und sei N ≥ 1 eine Primzahl. Seif : Z/N −→ R mit

0 ≤ f (n) ≤ 1 fur alle n ∈ Z/N, und

E (f (n)|n ∈ Z/N) ≥ δ.

Dann gilt

E (f (n)f (n + r) · · · f (n + (k − 1)r)|n, r ∈ Z/N) ≥ c(k, δ)− oδ(1).


Die Idee von Green und Tao

Finde P ⊆ A ⊆ N, so dass P in A relative Dichte > 0 hat, und dassA so beschaffen ist, dass Szemeredis Satz auch fur Teilmengen vonA gilt.

1. Schritt: Verallgemeinere den Satz von Szemeredi.

Theorem (Green, Tao)

Sei k ≥ 3, 0 < δ ≤ 1. Sei ν : Z/N −→ R≥0 einek-Pseudozufallsdichte. Sei f : Z/N −→ R≥0, so dass

0 ≤ f (n) ≤ ν(n) fur alle n ∈ Z/N, und

E (f (n)|n ∈ Z/N) ≥ δ.

Dann gilt

E (f (n)f (n + r) · · · f (n + (k − 1)r)|n, r ∈ Z/N) ≥ c(k, δ)− oδ,ν(1).


Die Idee von Green und Tao

Finde P ⊆ A ⊆ N, so dass P in A relative Dichte > 0 hat, und dassA so beschaffen ist, dass Szemeredis Satz auch fur Teilmengen vonA gilt.

1. Schritt: Verallgemeinere den Satz von Szemeredi.

Theorem (Green, Tao)

Sei k ≥ 3, 0 < δ ≤ 1. Sei ν : Z/N −→ R≥0 einek-Pseudozufallsdichte. Sei f : Z/N −→ R≥0, so dass

0 ≤ f (n) ≤ ν(n) fur alle n ∈ Z/N, und

E (f (n)|n ∈ Z/N) ≥ δ.

Dann gilt

E (f (n)f (n + r) · · · f (n + (k − 1)r)|n, r ∈ Z/N) ≥ c(k, δ)− oδ,ν(1).


Pseudo-Zufallsdichten

Definition

Eine k-Pseudozufallsdichte ist eine Familie von Funktionen

νN : Z/N −→ R≥0, N ∈ N

die eine

“Linearformenbedingung” und eine

“Korrelationsbedingung”

erfullen.

Beispiel (Konsequenzen der Linearformenbedingung)

E (ν) = 1 + o(1)

E (ν(x)ν(x + h1)ν(x + h2)ν(x + h1 + h2)|x , h1, h2 ∈ Z/N) =1 + o(1)


Anwendung auf die Primzahlen

Seien k ≥ 1, N ∈ N, W =∏

p∈Pp≤w(N)

p, εk = 12k (k+4)!

.

von Mangoldt-Funktion

Λ(n) =

{log p wenn n = pr , p prim,

0 sonst.

W-Trick

Λ(n) =

{φ(W )

W log(Wn + 1) wenn Wn + 1 prim,0 sonst.

f (n) =

{k−12−k−5Λ(n) wenn εkN ≤ n ≤ 2εkN,

0 sonst.



Seien k ≥ 1, N ∈ N, W =∏

p∈Pp≤w(N)

p, εk = 12k (k+4)!

.


Λ(n) =


0 sonst.

W-Trick

Λ(n) =

{φ(W )


f (n) =


0 sonst.



Seien k ≥ 1, N ∈ N, W =∏

p∈Pp≤w(N)

p, εk = 12k (k+4)!

.


Λ(n) =


0 sonst.

W-Trick

Λ(n) =

{φ(W )


f (n) =


0 sonst.


Es gilt

Λ(n) =∑d |n

µ(d) log(n/d).

Definiere abgeschnittene Version von Λ (nach Goldston, Yildirim):

ΛR(n) =∑d|n

d≤R

µ(d) log(R/d).

Theorem

Seien R = Nk−12−k−4und εk = 1

2k (k+4)!. Definiere

ν(n) :=

{φ(W )

WΛR(Wn+1)2

log R wenn εkN ≤ n ≤ 2εkN,

1 sonst.

Dann ist ν eine k-Pseudozufallsdichte, die f majorisiert.

Documents

Arithmetische Progressionen von Primzahlen - uni-due.dehx0050/pdf/av.pdf · Primzahlen Primzahlsatz Satz von Szemer´edi Verallg. von Green/Tao Anwendung Deﬁnition Eine arithmetische