4. Die Primzahlzählfunktion

Der kombinatorische Beweis von Axel Thue liefert mehr als die Unendlichkeit der Primzahlen. Wir erhalten eine neue Einsicht über die Häufigkeit der Primzahlen. Hierzu definieren wir:

Definition (Anzahl darstellbarer Zahlen)

Seien p₁ < … < p_k Primzahlen, und sei n ≥ 1. Dann setzen wir:

D(p₁, …, p_k; n) = |{ 1 ≤ a ≤ n | a ist darstellbar mit p₁, …, p_k }|.

Die Zahl D(p₁, …, p_k; n) gibt an, wie viele Zahlen des Intervalls { 1, …, n } eine Primfaktorzerlegung besitzen, in der lediglich die Primzahlen p₁, …, p_k auftauchen. Enthalten die Primzahlen p₁, …, p_k alle Primzahlen des Intervalls { 1, …, n }, so gilt

D(p₁, …, p_k; n) = |{1, …, n }| = n.

Dies folgt aus der Existenz einer Primfaktorzerlegung.

Beispiele

D(2; 1) = |{ 1 }| = 1 (mit der Darstellung 2⁰ der 1)

D(2; 10) = |{ 1, 2, 4, 8 }| = 4

D(2, 3; 10) = |{ 1, 2, 3, 4, 6, 8, 9 }| = 7

D(2, 3, 5, 7; 10) = |{ 1, …, 10 }| = 10

D(2; 2ⁿ) = |{ 1, 2, 4, …, 2ⁿ }| = n + 1 für alle n ≥ 0

Aus unserem kombinatorischen Beweis der Unendlichkeit der Primzahlen gewinnen wir:

Satz (Abschätzung der darstellbaren Zahlen)

Seien p₁ < … < p_k Primzahlen, und sei n ≥ 1. Dann gilt:

(a)	D(p₁, …, p_k; 2ⁿ − 1) ≤ n^k.

(b)	D(p₁, …, p_k; 2ⁿ) ≤ n^k, falls k ≥ 2.

Beweis

Die erste Aussage ergibt sich direkt aus dem Beweis von Thue. Für die zweite Aussage beobachten wir, dass

(+) D(p₁, …, p_k; 2ⁿ) ≤ D(p₁, …, p_k; 2ⁿ − 1) + 1,

wobei Gleichheit genau dann gilt, falls p₁ = 2. Sei nun k ≥ 2. Dann gilt

p₁^n − 1 p₂¹ > p₁^n − 1 p₁ = p₁ⁿ ≥ 2ⁿ,

sodass wir in der Abschätzung „D(p₁, …, p_k; 2ⁿ − 1) ≤ n^k“ des Beweises mindestens eine Kombination der Exponenten zu viel berücksichtigt haben. Damit ist D(p₁, …, p_k; 2ⁿ − 1) < n^k, und aus (+) folgt die Behauptung.

Wegen D(2; 2ⁿ) = n + 1 für alle n ist (b) im Fall k = 1 und n^k = n im Allgemeinen nicht gültig. Ist n ≥ 2 und sind p₁ < … < p_k alle Primzahlen in { 1, …, 2ⁿ }, so gilt k ≥ 2 und damit

2ⁿ = D(p₁, …, p_k; 2ⁿ) ≤ n^k.

Anwendung des Logarithmus zur Basis 2 liefert

k ≥ ^log₂(2ⁿ)_log₂(n) = ⁿ_log₂(n).

Damit haben wir ein neues Ergebnis über die Anzahl der Primzahlen in einem Intervall der Form { 1, …, 2ⁿ } gefunden. Wir definieren hierzu allgemein:

Definition (Primzahlzählfunktion)

Die Primzahlzählfunktion π : ℕ* → ℕ ist definiert durch

π(n) = „die Anzahl der Primzahlen im Intervall { 1 , …, n }“ für alle n ≥ 1.

Die Funktion π heißt die Primzahlzählfunktion.

Es gilt also π(n) = |{ p ≤ n | p prim }| für alle n ≥ 1. Zum Beispiel ist

π(1) = 0, π(2) = 1, π(3) = π(4) = 2, π(5) = π(6) = 3, …

An jeder Primzahlstelle p springt die Zählfunktion um 1, sodass

π(p) = π(p − 1) + 1.

Ist n zusammengesetzt, so gilt dagegen π(n) = π(n − 1). Ist p_k die k-te Primzahl, so gilt π(p_k) = k. Die π-Funktion liefert also den Index, wenn sie auf eine Primzahl angewendet wird.

Die Primzahlzählfunktion π auf den natürlichen Zahlen bis n = 100

Die Primzahlzählfunktion π auf den natürlichen Zahlen bis n = 1000

Die Primzahlzählfunktion bildet ein Herzstück der Zahlentheorie und wirft viele Fragen auf. Die Unendlichkeit der Primzahlen besagt, dass π(n) gegen unendlich strebt, wenn n gegen unendlich strebt. Nun fragen wir genauer:

Wie schnell wächst die Funktion?

Dieser Frage werden wir im Folgenden immer wieder begegnen. Unsere Überlegungen zeigen (zusammen mit der Umrechnungsformel log₂(n) = log(n)/log(2) für den Logarithmus):

Satz (Abschätzung der Primzahlzählfunktion, I)

Für alle n ≥ 2 gilt

π(2ⁿ) ≥ ⁿ_log₂(n) = ^{n log(2)}_log(n).

Speziell gibt es für alle natürlichen Zahlen m ≥ 1 mindestens 2^m/m Primzahlen in { 1, …, 2^{2^m} }.

Beweis

Die Ungleichung haben wir oben schon bewiesen. Für den Spezialfall betrachten wir n = 2^m mit log₂(n) = m.

Wir betrachten ein konkretes Beispiel zur Illustration:

Beispiel

Für n = 8 erhalten wir, dass es im Intervall { 1, …, 2⁸ } = { 1, …, 256 } mindestens

k = ⁸_log₂(8) = ⁸_log₂(2³) = ⁸₃ = 2 ²₃

Primzahlen gibt, also mindestens 3. Die tatsächliche Anzahl ist 54, sodass unsere Abschätzung sehr schwach ist.

Vergleich mit dem Beweis von Euklid

Auch der Beweis von Euklid liefert eine Abschätzung für die Primzahlzählfunktion. Ist p₁ < p₂ < … < p_n < … eine Aufzählung aller Primzahlen, so zeigt das Argument von Euklid, dass

p_n + 1 ≤ p₁ … p_n + 1 für alle n ≥ 1.

Hieraus gewinnen wir:

(+) p_n ≤ 2^2ⁿ für alle n ≥ 1.

Zum Beweis beobachten wir:

p₁ = 2 ≤ 4 = 2^2¹

p₂ ≤ p₁ + 1 ≤ 2p₁ ≤ 2^2⁰ 2^2¹ ≤ 2^2²

p₃ ≤ p₁ p₂ + 1 ≤ 2p₁p₂ ≤ 2^2⁰ 2^2¹ 2^2² ≤ 2^2³,

und allgemein durch Induktion

p_n + 1 ≤ p₁ … p_n + 1 ≤ 2^2⁰ 2^2¹ … 2^2ⁿ ≤ 2^{2^n + 1} für alle n ≥ 1,

wobei wir die geometrische Summenformel 2⁰ + 2¹ + … + 2ⁿ = 2^n + 1 − 1 verwenden.

Damit erhalten wir also aus dem Beweis von Euklid die Abschätzung

π(2^2ⁿ) ≥ π(p_n) = n für alle n ≥ 1.

Die Abschätzung π(2^2ⁿ) ≥ 2ⁿ/n aus dem kombinatorischen Argument ist deutlich besser.

Experiment: Exponentensummen

Wir können unsere Abschätzung noch etwas verbessern, indem wir verwenden, dass e₁ + … + e_k ≤ n gilt, wenn ein Produkt 2^e₁ 3^e₂ … p_k^e_k eine Zahl eines Intervalle { 1, …, 2ⁿ } darstellt. Es gibt genau

$( \binom{n + k - 1}{k - 1} )$ = ^{(n + 1) (n + 2) … (n + k − 1)}_{(k − 1)!}

k-Tupel (e₁, …, e_k) in { 0, …, n } mit e₁ + … + e_k = n. Denn diese Tupel entsprechen genau den Tupeln der Länge n + k − 1 in { 0, 1 } mit genau k − 1 Null-Einträgen. Zum Beispiel entspricht (2, 4, 1, 0) dem Tupel (1, 1, 0, 1, 1, 1, 1, 0, 1, 0). Beide Tupel repräsentieren die Summe 2 + 4 + 1 + 0 = 7 mit n = 7 und k = 4. Wir können dieses kombinatorische Argument anschaulich so beschreiben: Wir schreiben n Einheiten als Wort 111…111 auf und fügen nun k − 1 Nullzeichen an beliebigen Stellen ein, wobei auch die erste und letzte Position erlaubt ist und Nullen direkt aufeinanderfolgen können. Dadurch einsteht ein 0-1-Wort der Länge n + k − 1. Diese Worte entsprechen genau den Summen e₁ + … + e_k = n, wenn die 0 als Pluszeichen gelesen wird.

Sind nun wieder p₁ < … < p_k alle Primzahlen eines Intervalls { 1, …, 2ⁿ }, so zeigt unsere verbesserte Zählung, dass

2ⁿ = D(p₁, …, p_k; 2ⁿ) ≤ $( \binom{n + k - 1}{k - 1} )$ = ^{(n + 1) (n + 2) … (n + k − 1)}_{(k − 1)!}

Im Gegensatz zu 2ⁿ ≤ n^k können wir diese Ungleichung nicht mehr einfach nach k auflösen. Wir können aber wieder konkrete Werte betrachten:

Beispiel

Ist wieder n = 8 und k die Anzahl der Primzahlen in { 1, …, 2⁸ }, so gilt

2⁸ ≤ $( \binom{8 + k - 1}{k - 1} )$ = ^{(8 + 1) (8 + 2) … (8 + k − 1)}_{(k − 1)!}

Es gilt 2⁸ = 256 und für k = 1, 2, 3, … berechnen sich die Binomialkoeffizienten zu 1, 9, 45, 165, 495, … Damit ist k ≥ 5 (da 165 < 256 ≤ 495), sodass wir im Vergleich zur letzten Abschätzung nur wenig gewonnen haben. Die kombinatorische Überlegung war es trotzdem wert.

Eine verbesserte Abschätzung für die Primzahlzählfunktion werden wir im folgenden Essay kennenlernen.