1. Asymptotische Gleichheit
Der Beweis der Unendlichkeit der Primzahlen von Euklid gibt uns nur wenig Information über die Verteilung der Primzahlen. Er zeigt: Sind p1, …, pk die ersten k Primzahlen und ist a = p1 … pk + 1, so gibt es eine Primzahl p mit pk < p ≤ a. Die Beweise von Euler und Erdös über die Summe der reziproken Primzahlen liefern schon wesentlich mehr, indem sie zeigen, dass
∑p prim 1p = ∞.
Damit sind die Primzahlen in den natürlichen Zahlen wesentlich häufiger zu finden als die Potenzen 2, 4, …, 2n, … der Zahl 2, da
∑n ≥ 1 12n = 1.
Was lässt sich nun genauer über die Verteilung der Primzahlen sagen? Wie häufig sind sie? Zunächst ist noch nicht einmal klar, wie wir „Häufigkeit“ präzisieren können. Im Zentrum steht die Primzahl-Zählfunktion π mit
π(n) = „die Anzahl der Primzahlen p mit p ≤ n“ für alle natürlichen Zahlen n ≥ 1.
Für jede natürliche Zahl n können wir den Wert π(n) mit Hilfe des Siebverfahrens des Eratosthenes bestimmen. Die Primzahl-Zählfunktion gehört damit zur Klasse der berechenbaren Funktionen. Das ist aber nicht das, was wir anstreben. Ideal wäre ein einfacher Term in der Variablen n, der angibt, wie groß π(n) ist. Ein solcher Term ist nicht bekannt. Bemerkenswerterweise sind aber einfache Terme bekannt, die angeben, wie groß π(n) „ungefähr“ ist. Im Abschnitt über den Satz von Chebychev und das Bertrandsche Postulat hatten wir gezeigt:
Satz (Satz von Chebyshev)
Für alle n > 1 gilt:
c1 nlog(n) ≤ π(n) ≤ c2 nlog(n).
mit c1 = log(2)/2 = 0,3465… und c2 = 3log(2) = 2,0794…
Die Anzahl der Primzahlen im Intervall { 1, …, n } liegt also für alle n > 1 im Intervall [ c1 n/log(n), c2 n/log(n)], das den prominenten Wert n/log(n) umschließt. Das Ergebnis mit seinen „zufälligen“ und durch recht grobe Abschätzungen erhaltenen Konstanten c1, c2 suggeriert:
„Im Intervall { 1, …, n } gibt es ungefähr n/log(n) viele Primzahlen.“
Der Primzahlsatz, den wir in diesem Abschnitt diskutieren, präzisiert das „ungefähr“ dieser Aussage und er stellt eine substantielle Verbesserung des Satzes von Chebychev dar. Es ist ja keineswegs klar, dass n/log(n) der „korrekte“ Anzahlwert ist und nicht etwa (1 + 1/e2) n/log(n) oder dergleichen.
Wir lassen auch wieder reelle Stellen zu und setzen allgemeiner
π(x) = „die Anzahl der Primzahlen p mit p ≤ x“ für alle reellen Zahlen x ≥ 0.
Mit dieser Konvention gilt π : [ 0, ∞ [ → ℝ und die Primzahlzählfunktion lässt sich wie eine übliche reelle Funktion der Analysis behandeln.
Asymptotische Äquivalenz
Um unser „ungefähr“ zu präzisieren, führen wir einen allgemeinen Begriff ein:
Definition (asymptotisch gleich, reelle Funktionen)
Seien f : X → ℝ und g : Y → ℝ reelle Funktionen derart, dass die Definitionsbereiche X, Y ⊆ ℝ nach oben unbeschränkt sind und schließlich übereinstimmen, d. h. es gibt ein x0 ≥ 0 mit X ∩ [ x0, ∞ [ = Y ∩ [ x0, ∞ [. Dann heißen f und g asymptotisch gleich oder asymptotisch äquivalent, falls
limx → ∞ f (x)g(x) = 1.
In Zeichen schreiben wir f ∼ g.
Beispiele
(1) | Wir definieren f, g : ℕ → ℕ durch f (n) = n und g(n) = n + 1 für alle n. Dann gilt f ∼ g. Ist dagegen h : ℕ → ℕ definiert durch h(n) = 2n für alle n, so sind f und h und weiter g und h nicht asymptotisch gleich. |
(2) | Wir definieren f, g : ℝ → ℝ durch f (x) = x2 + 2x + 2 und g(x) = x2 + 5 für alle x ∈ ℝ. Dann gilt f ∼ g. |
Wir lassen in der Definition beliebige unbeschränkte Definitionsbereiche zu. Dadurch ist insbesondere die asymptotische Gleichheit auch für reelle Folgen definiert: Wir fassen nämlich eine reelle Folge (xn)n ∈ ℕ als Funktion von ℕ nach ℝ auf: Für alle n ∈ ℕ ist xn der Wert der Funktion an der Stelle.
Beispiel
Die Folgen (n2 + n + 1)n ∈ ℕ und (n2 − 2n + 2)n ∈ ℕ sind asymptotisch gleich. Die Folgen (1/n)n ≥ 1 und (1/n2)n ≥ 1 sind dagegen nicht asymptotisch gleich.
Konvergieren zwei Funktionen f und g gegen von 0 verschiedene reelle Zahlen a und b, wenn x gegen unendlich konvergiert, so gilt f ∼ g genau dann, wenn a = b. Denn in diesem Fall gilt nach den Limesregeln
limx → ∞ f (x)g(x) = limx → ∞ f (x)limx → ∞ g(x) = ab.
Die asymptotische Äquivalenz ist vor allem dann interessant, wenn f (x) und g(x) beide gegen unendlich oder gegen 0 streben, wenn x gegen unendlich strebt. In diesem Fall besagt f ∼ g, dass die Konvergenz gleich schnell ist, wobei „gleich schnell“ durch die Quotientenbildung präzisiert wird.
Der folgende Satz versammelt einige Eigenschaften.
Satz (Eigenschaften der asymptotischen Äquivalenz)
Für alle reellen Funktionen gilt unter der Voraussetzung der Definiertheit:
(a) | f ∼ f(Reflexivität) f ∼ g impliziert g ∼ f(Symmetrie) f ∼ g und g ∼ h impliziert f ∼ h(Transitivität) |
(b) | f1 ∼ g1 und f2 ∼ g2 impliziert f1 g1 ∼ f2 g2(Multiplikationsregel) |
(c) | h f ∼ h g genau dann, wenn f ∼ g(Kürzungsregel) |
(d) | f ∼ g genau dann, wenn 1/f ∼ 1/g(Invertierungsregel) |
(e) | f ∼ g und limx → ∞ h(x) = ∞ impliziert f ∘ h = g ∘ h(Vorschaltung) |
(f) | f ∼ g genau dann, wenn limx → ∞ (log(f) − log(g)) = 0 |
(g) | Es gebe ein ε > 0 und ein x0 derart, dass |g(x) − 1| ≥ ε für alle x ≥ x0. Dann gilt: f ∼ g impliziert log(f) ∼ log(g).(Logarithmusregel) |
Beweis
zu (a):
Wir zeigen exemplarisch die Transitivität. Es gelte also f ∼ g und g ∼ h. Dann gilt f ∼ h, da
limx → ∞ f (x)/h(x) = limx → ∞ (f (x)/g(x) · g(x)/h(x))
= limx → ∞ f (x)/g(x) · limx → ∞ g(x)/h(x) = 1 · 1 = 1.
zu (b) − (e):
Diese Aussagen werden wie die Aussage (a) durch Einsetzen der Definitionen und Verwendung der Limesregeln bewiesen.
zu (e):
Aufgrund der Stetigkeit des Logarithmus gilt
limx ∞ ∞ f (x)/g(x) = 1 genau dann, wenn limx → ∞ log(f (x)/g(x)) = log(1).
Die 1 ist die einzige Nullstelle des Logarithmus und es gilt
log(x/y) = log(x) − log(y) für alle x, y > 0.
Hieraus ergibt sich die Äquivalenz.
zu (g):
Nach (e) folgt aus f ∼ g, dass
limx → ∞ (log(f) − log(g)) = 0.
Nach der Voraussetzung an g gibt es ein δ > 0, sodass |log(g(x))| > δ für alle x ≥ x0. Hieraus folgt, dass
0 = limx → ∞ log(f (x)) − log(g(x))log(g(x)) = limx → ∞ log(f (x))log(g(x)) − 1.
Dies zeigt, dass log(f) ∼ log(g).
Die folgenden Beispiele zeigen, dass beim Umgang mit der asymptotischen Äquivalenz Vorsicht geboten ist:
Beispiele
(1) | Es gibt keine Additionsregel: Gelten f1 ∼ g1 und f2 ∼ g2, so folgt im Allgemeinen nicht, dass f1 + f2 ∼ g1 + g2. Ein einfaches Gegenbeispiel ist x + 1 ∼ x und −x ∼ −x. |
(2) | Es gibt keine Verknüpfungsregel von links: Aus f ∼ g folgt im Allgemeinen nicht, dass h ∘ f ∼ h ∘ g. Für ein betrachten wir f, g, h mit f (x) = x + 1, g(x) = x und h(x) = exp(x) für alle x. Hier gilt f ∼ g, aber limx → ∞ exp(x + 1)exp(x) = limx → ∞ exp(x)exp(x) exp(1) = e. |
(3) | Die Invertierungsregel gilt für die Multiplikation, aber nicht für die Verknüpfung: Aus f ∼ g folgt für invertierbare Funktionen f und g im Allgemeinen nicht, dass f −1 ∼ g−1. Sei zum Beispiel f (x) = log(x) − 1 und g(x) = log(x) für alle x > 0. Dann gilt f ∼ g, aber limx →∞ f −1(x)g−1(x) = limx → ∞ ex + 1ex = e. |
(4) | Die Logarithmusregel gilt nicht ohne die Voraussetzung, dass g (und unter der Voraussetzung f ∼ g automatisch auch f) schließlich von der 1 wegbleibt. Sind nämlich f und g definiert durch f (x) = exp(2/x) und g(x) = exp(1/x) für alle x > 0, so gilt f (x) = g(x)2 für alle x > 0 und limx → ∞ f (x)g(x) = limx → ∞ exp(1/x) = 1, limx → ∞ log(f (x))log(g(x)) = limx → ∞ 2/x1/x = 2. Folglich gilt f ∼ g, aber nicht log(f) ∼ log(g). |
(5) | Die Umkehrung der Implikation in (g) ist im Allgemeinen ebenfalls nicht gültig. Dies zeigen zum Beispiel wieder die Funktionen f, g mit f (x) = exp(x + 1) und g(x) = exp(x) für alle x. Hier gilt log(f) ∼ log(g), nicht aber f ∼ g. |