Primzahlsatz

Kernaussage und Primzahlfunktion

Der Primzahlsatz ist ein grundlegender Satz der analytischen Zahlentheorie zur Verteilung der Primzahlen unter den natürlichen Zahlen. Er beschreibt, wie viele Primzahlen bis zu einer großen Grenze x liegen, und damit die langfristige Dichte der Primzahlen.

Die Primzahlfunktion π(x) ist für reelle x definiert als die Anzahl der Primzahlen p mit p≤x:

π(x):=|{p∈ℙ | p≤x}|.

Der Primzahlsatz lautet:

lim_{x→∞} π(x)/(x/ln(x))=1.

Damit ist π(x) für große x näherungsweise x/ln(x). Der Satz sagt nicht, dass beide Werte gleich sind, sondern dass ihr Quotient bei wachsendem x gegen 1 geht. Der Zusammenhang wurde 1793 von Carl Friedrich Gauß und unabhängig davon 1798 von Adrien-Marie Legendre vermutet. Den strengen Beweis lieferten 1896 unabhängig und nahezu gleichzeitig Jacques Salomon Hadamard und Charles-Jean de La Vallée Poussin.

Gleichwertige Aussagen und Folge der Primzahlen

Zwei reelle Funktionen f und g heißen asymptotisch äquivalent, wenn f(x)/g(x) für x→∞ gegen 1 konvergiert. Der Primzahlsatz bedeutet daher auch: Die Funktionen x↦π(x) und x↦x/ln(x) für x>0 sind asymptotisch äquivalent.

Wesentlich gleichwertig ist die Aussage, dass die komplexe Riemannsche Zetafunktion keine Nullstellen s mit Re(s)≥1 besitzt. Ebenfalls gleichwertig ist

lim_{x→∞} ψ(x)/x=1,

wobei ψ die Tschebyscheffsche Psi-Funktion ist. Edmund Landau zeigte 1899 und 1911 ohne funktionentheoretische Hilfsmittel auch die Gleichwertigkeit mit

∑_{n=1}^∞ μ(n)/n=0,

wobei μ die Möbiusfunktion ist.

Für die aufsteigende Primzahlfolge pₙ=2,3,5,… ist der Satz äquivalent zu pₙ∼n ln(n). Für alle n≥6 gilt sogar

ln(n)+ln ln(n)−1 < pₙ/n < ln(n)+ln ln(n).

Außerdem folgt lim_{n→∞} pₙ₊₁/pₙ=1. Aufeinanderfolgende Primzahlen werden also im Verhältnis zu ihrer Größe langfristig immer dichter beieinander liegen, auch wenn ihre absoluten Abstände schwanken können.

Näherungen und Fehlerabschätzungen

Eine bessere Näherung für π(x) als x/ln(x) ist der Integrallogarithmus

Li(x):=∫₂ˣ dt/ln(t).

Er ist asymptotisch äquivalent zu x/ln(x) und damit auch zu π(x). Die Integraldarstellung wird verwendet, weil 1/ln(x) keine elementare Stammfunktion besitzt.

Es gilt

π(x)=Li(x)+O(x·exp(−C(ln(x))^(3/5)(ln ln(x))^(−1/5)))

mit einer positiven Konstante C. Das Landau-Symbol O bedeutet hier: Es gibt eine Konstante D, sodass

|π(x)−Li(x)| < D·x·exp(−C(ln(x))^(3/5)(ln ln(x))^(−1/5))

für alle x gilt. Verbesserungen dieses Fehlerterms hängen mit nullstellenfreien Bereichen der Zetafunktion im kritischen Streifen zusammen.

Unter der riemannschen Vermutung, nach der alle nicht-trivialen Nullstellen auf der Geraden s=1/2 liegen, erhält man nach Helge von Koch (1901)

π(x)=Li(x)+O(√x·ln(x)).

Unter derselben Annahme gab Lowell Schoenfeld 1976 die nicht-asymptotische Schranke

|π(x)−Li(x)| < √x ln(x)/(8π).

Für natürliche n≥67 zeigten John Barkley Rosser und Schoenfeld 1962:

n/(ln(n)−1/2) < π(n) < n/(ln(n)−3/2).

Zahlenbeispiele und Grenzen von Näherungen

Die Primzahldichte heißt π(x)/x. Einige Werte zeigen, dass π(x) im Verhältnis zu x kleiner wird und x/ln(x) relativ genauer wird: Für x=10 ist π(10)=4 und x/ln(x)≈4; für x=10⁶ ist π(x)=78.498, während x/ln(x)≈72.382; für x=10¹² gilt π(x)=37.607.912.018 und x/ln(x)≈36.191.206.825. Der Quotient π(x)/(x/ln(x)) sinkt in diesen Beispielen von etwa 1,160503 bei 10³ auf etwa 1,039145 bei 10¹² und etwa 1,015446 bei 10²⁹.

In der Tabelle steht außerdem li(x):=∫₀ˣ dt/ln(t), mit li(x)=Li(x)+li(2) und li(2)≈1,04516. Dort ist zunächst li(x)>π(x). Dies gilt aber nicht immer: J. E. Littlewood bewies 1914, dass li(x)−π(x) bei wachsendem x unendlich oft das Vorzeichen wechselt. Carter Bays und Richard Hudson zeigten 2000, dass ein solcher Wechsel vor 1,398244·10³¹⁶ auftritt; sie konnten jedoch nicht beweisen, dass dies der erste Vorzeichenwechsel ist. Ihre Berechnungen legen nahe, dass π(x)<li(x) für x<1,398·10³¹⁶ gilt.

Explizite Formeln und Zetafunktionsnullstellen

Explizite Formeln für Primzahlfunktionen gibt es als arithmetische und analytische Formeln. Die analytischen Formeln von Bernhard Riemann und Hans von Mangoldt verknüpfen die Primzahlenzählung mit den Nullstellen ρ der Riemannschen Zetafunktion.

Für x>1 gilt für eine an Sprungstellen gemittelte Tschebyscheff-Funktion:

ψ₀(x)=x−∑ρ x^ρ/ρ−ln(2π)−(1/2)ln(1−x^(−2)),

wobei ψ₀(x)=lim_{ε→0}(ψ(x−ε)+ψ(x+ε))/2. Die ρ sind Nullstellen im kritischen Streifen mit Realteil zwischen 0 und 1. Die Summe ist nur bedingt konvergent und muss nach zunehmendem Absolutwert des Imaginärteils geordnet werden.

Auch für die von Riemann eingeführte Primzahlenzählfunktion Π gibt es eine gemittelte Funktion Π₀(x):

Π₀(x)=li(x)−∑ρ li(x^ρ)−ln 2+∫ₓ^∞ dt/[t(t²−1)ln t].

Aus der Möbius-Inversionsformel folgt exakt

π₀(x)=∑_{n=1}^∞ μ(n)/n · Π₀(x^(1/n)).

Für festes x>1 sind nur endlich viele dieser Summanden von null verschieden. Eine oft angegebene formale Darstellung mit der riemannschen R-Funktion darf jedoch nicht durch gewöhnliches Vertauschen der Summationen begründet werden: Die dabei entstehenden Reihen über nichttriviale und triviale Nullstellen divergieren. Abgeschnittene oder geglättete Nullstellensummen können dennoch die Schwankungen der Primzahlfunktion numerisch darstellen.

Primzahlen in arithmetischen Progressionen

Sei π_{q,a}(x) die Anzahl der Primzahlen höchstens x in der arithmetischen Progression a,a+q,a+2q,…, wobei a und q koprim sind, also (a,q)=1. Dann gilt asymptotisch

π_{q,a}(x)∼Li(x)/φ(q),

wobei φ(q) die Eulersche Phi-Funktion ist, also die Anzahl der zu q teilerfremden Zahlen, die nicht größer als q sind. Primzahlen verteilen sich langfristig somit gleichmäßig auf die zulässigen Restklassen.

Für die Endziffern im Dezimalsystem betrifft dies – abgesehen von 2 und 5 – die Ziffern 1, 3, 7 und 9: Sie sind asymptotisch gleich verteilt. Es gibt jedoch lokale Ungleichgewichte. Beispielsweise liegen unter einer bestimmten Grenze numerisch meist mehr Primzahlen der Form p=3 mod 4 als der Form p=1 mod 4; dies heißt Chebyshev’s Bias oder Primzahl-Rennen. Littlewood zeigte, dass π_{4,3}(x)−π_{4,1}(x) unendlich oft das Vorzeichen wechselt.

Der Satz von Siegel-Walfisz präzisiert die Verteilung, wenn q≤(ln x)^N. Für die Mangoldt-Funktion Λ und

ψ(x;q,a)=∑_{n≤x, n≡a mod q} Λ(n)

gilt für jedes N mit einer Konstante C_N:

ψ(x;q,a)=x/φ(q)+O(x·exp(−C_N(ln x)^(1/2))).

Der Satz ist nicht effektiv, weil keine Größe für C_N angegeben wird.