2. Einschluss-Ausschluss-Zählungen

In der Version der vollständigen Streichung werden beim Sieb des Eratosthenes alle Zahlen des Intervalls 2, …, n markiert oder gestrichen, viele davon mehrfach. Das Verfahren motiviert eine kombinatorische Zählung, die zu einer der bemerkenswertesten Funktionen der Zahlentheorie führt, nämlich der μ-Funktion von August Ferdinand Möbius (gelesen: Mü-Funktion).

Für unsere Überlegungen ist die sogenannte Floor- oder Abrundungsfunktion unentbehrlich. Da später auch die Ceiling- oder Aufrundungsfunktion auftreten wird, definieren wir an dieser Stelle gleich beide Funktionen. Sie spielen in der Zahlentheorie, so simpel sie vielleicht wirken mögen, an vielen Stellen eine Schlüsselrolle.

Definition (Floor-Funktion, Ceiling-Funktion)

Wir definieren die Floor-Funktion floor : ℝ → ℝ und die Ceiling-Funktion ceiling : ℝ → ℝ durch

floor(x) = „das größte a  ∈  ℤ mit a ≤ x“ für alle x  ∈  ℝ,

ceiling(x) = „das kleinste a  ∈  ℤ mit x ≤ a“ für alle x  ∈  ℝ.

Wir schreiben oft auch ⌊ x ⌋ anstelle von floor(x) und ⌈ x ⌉ anstelle von ceiling(x).

Stellen wir uns eine reelle Zahl x als Punkt auf dem Zahlenstrahl vor, so sind floor(x) und ceiling(x) diejenigen ganzen Zahlen, die wir sehen, wenn wir von x aus nach links bzw. rechts blicken.

Beispiele

(1)	⌊7/2⌋ = 3, ⌈7/2⌉ = 4.

(2)	⌊2⌋ = ⌈2⌉.

(3)	1 = ⌊ 1 ⌋ = ⌊ 1/3 + 2/3 ⌋ = ⌊ 1/3 ⌋ + ⌊2/3⌋ + 1 = 0 + 0 + 1.

Der folgende Satz versammelt einige allgemeine leicht nachzuweisende Eigenschaften der beiden Funktionen:

Satz (Eigenschaften der Floor- und Ceiling-Funktion)

Für alle reellen Zahlen x, y und alle ganzen Zahlen a gilt:

(a)	⌊ x ⌋ ≤ x ≤ ⌈ x ⌉,

(b)	0 ≤ x − ⌊ x ⌋ < 1, 0 ≤ ⌈ x ⌉ − x < 1,

(c)	⌊ x ⌋ = ⌈ x ⌉ genau dann, wenn x  ∈  ℤ,

(d)	⌊ x ⌋ ≤ x < ⌊ x ⌋ + 1, ⌈ x ⌉ − 1 < x ≤ ⌈ x ⌉,

(e)	x − 1 < ⌊ x ⌋ ≤ x, x ≤ ⌈ x ⌉ < x + 1,

(f)	⌊ x + a ⌋ = ⌊ x ⌋ + a, ⌈ x + a ⌉ = ⌈ x ⌉ + a,

(g)	⌊ x ⌋ + ⌊ y ⌋ ≤ ⌊ x + y ⌋ ≤ ⌊ x ⌋ + ⌊ y ⌋ + 1, ⌈ x ⌉ + ⌈ y ⌉ − 1 ≤ ⌈ x + y ⌉ ≤ ⌈ x ⌉ + ⌈ y ⌉,

(h)	⌈x⌉ = − ⌊− x ⌋.

Die Floor-Funktion auf ℝ. Sie springt an den ganzen Zahlen.

Die folgende grundlegende Beobachtung zeigt die Bedeutung der Floor-Funktion für die Zahlentheorie:

Satz (Zählung der Vielfachen in einem Intervall)

Seien d, n ≥ 1 natürliche Zahlen. Dann gilt

⌊ n/d ⌋ = |{ 1 ≤ m ≤ n | m ist ein Vielfaches von d }|.

Hier und im Folgenden bezeichnet |M| die Anzahl der Elemente einer Menge M. Nach dem Satz ist ⌊ n/d ⌋ die Anzahl der Vielfachen von d im Intervall { 1, …, n } und damit die Anzahl der durch d teilbaren Zahlen des Intervalls.

Beweis

Sei a die größte natürliche Zahl mit ad ≤ n. Dann sind genau die a Zahlen

d, 2d, 3d, …, ad

die Vielfachen von d, die im Intervall { 2, …, n } liegen. Nach Definition von a ist a größte natürliche Zahl a mit a ≤ n/d. Damit ist a = ⌊n/d⌋.

Für das Siebverfahren bedeutet dies: Ist p ≤ n prim, so ist ⌊n/p⌋ die Anzahl der Zahlen des Intervalls 2, …, n, die bei der Siebung mit p betrachtet werden (markiert oder gestrichen).

Nach diesen Vorbereitungen können wir unsere kombinatorische Zählung durchführen. Unser Ziel ist, jede Zahl des Intervalls { 2, …, n } genau einmal zu zählen. Natürlich wird sich dadurch am Ende n − 1 ergeben, aber wir erhalten eine interessante Formel, die die Mehrfachstreichungen des Siebverfahrens widerspiegelt. Um die Notation zu vereinfachen, vereinbaren wir:

p-Konvention

In Summen und Produkten bezeichnen p, p₁, p₂, … stets Primzahlen.

Wir betrachten eine fest gewählte Grenze n und führen die vollständige Siebung für das Intervall { 2, …, n } durch. Zunächst gilt die Abschätzung

n − 1 ≤ ∑_p ≤ n ⌊ⁿ_p⌋ = ∑_p ≤ n |{ 2 ≤ m ≤ n | p teilt m }|.

Denn jede natürliche Zahl m des Intervalls { 2, …, n } wird im Siebverfahren betrachtet (markiert oder gestrichen), sodass sie in der Summe mindestens einmal gezählt wird.

Anschaulich ist die Summe auf der rechten Seite die Anzahl aller Primzahlen und Markierungspunkte des Siebverfahrens in den obigen Diagrammen. Wir ersetzen zur Vereinfachung auch die Primzahlen durch Punkte und sprechen im Folgenden nur noch von Punkten. Die Summe ist also die Anzahl der Punkte in unseren Diagrammen. Wir können sie also die Anzahl der Treffer der Siebung ansehen, wobei die markierten Primzahlen als Treffer mitzählen.

Für jede Zahl m in { 2, …, n } gilt:

(#₁) Hat m genau r Primteiler, so wird m in der Summe genau r-mal gezählt.

Im Fall r = 1 (d. h. m ist prim) ist unsere Zählung bereits korrekt. Im Fall r > 1 zählen wir m mehrfach. Wir korrigieren diesen Fehler durch die Abschätzung

n − 1 ≥ ∑_p ≤ n ⌊ⁿ_p⌋ − ∑_{p₁ < p₂ ≤ n} ⌊ⁿ_p₁ p₂ ⌋

= ∑_p ≤ n |{ m ≤ n | p teilt m }| − ∑_{p₁ < p₂ ≤ n} |{ m ≤ n | p₁, p₂ teilt m }|.

Hat eine Zahl m genau zwei Primteiler, so haben wir m in der ersten Summe zweimal und in der zweiten Summe einmal gezählt. Damit ist Zählung nun auch für diese Zahlen korrekt. (Hat m genau einen Primteiler, so wird m in der ersten Summe einmal und in der zweiten Summe nicht gezählt, sodass die Zählung korrekt bleibt.) In unseren Diagrammen haben wir also alle Zahlen m mit genau einem oder genau zwei Punkten korrekt gezählt.

Hat eine Zahl m mehr als zwei Primteiler, so haben wir m in der korrigierten Summe zu oft abgezogen. Genauer gilt:

(#₂) Hat m genau r Primteiler, so wird m genau $( \binom{r}{2} )$ -mal abgezogen.

Ist beispielsweise m = 30 = 2 · 3 · 5, so wird m für die Primzahlpaare (2, 3), (2, 5) und (3, 5) abgezogen, also dreimal. Wir korrigieren unsere Summe erneut und erhalten

n − 1 ≥ ∑_p ≤ n ⌊ⁿ_p⌋ − ∑_{p₁ < p₂ ≤ n} ⌊ⁿ_{p₁ p₂} ⌋ + ∑_{p₁ < p₂ < p₃ ≤ n} ⌊ⁿ_{p₁ p₂ p₃} ⌋.

In dieser Summe wird eine Zahl m in { 2, …, n } mit genau r ≥ 3 Primteilern genau

$( \binom{r}{1} )$ − $( \binom{r}{2} )$ + $( \binom{r}{3} )$

oft gezählt. Für r = 3 ergibt sich 3 − 3 + 1 = 1, also eine korrekte Zählung. In der Sprache unserer Diagramme sind nun alle Zahlen genau einmal gezählt, die einmal, zweimal oder dreimal getroffen werden.

Wir fahren nun in dieser Art und Weise fort. Dass wir durch unsere ±-Korrekturen schließlich den korrekten Wert n − 1 erhalten, ist durch unsere Argumentation vielleicht bereits einleuchtend. Wer es genauer haben möchte, kann den Binomischen Lehrsatz für einen Beweis heranziehen:

Satz (Binomischer Lehrsatz)

Für alle a, b  ∈  ℝ und r  ∈  ℕ gilt

(a + b)^r = ∑_k ≤ r $( \binom{r}{k} )$ a^k b^r − k(Binomischer Lehrsatz)

Der Satz verallgemeinert die aus der Schule bekannten binomischen Formeln (Fall r = 2). Allgemein kann der Satz durch Induktion nach r bewiesen werden. Wir setzen das Ergebnis hier als bekannt voraus, um die Darstellung unseres Zählverfahrens nicht zu unterbrechen.

Für den Spezialfall a = 1 und b = −1 zeigt der Binomische Lehrsatz, dass für einen beliebigen Exponenten r  ∈  ℕ gilt:

0 = (1 − 1)^r = $( \binom{r}{0} )$ − $( \binom{r}{1} )$ + … + (−1)^r $( \binom{r}{r} )$ = ∑_k ≤ r (−1)^k $( \binom{r}{k} )$ .

Folglich ist

(+) 1 = $( \binom{r}{1} )$ − $( \binom{r}{2} )$ + $( \binom{r}{3} )$ − … + (−1)^r − 1 $( \binom{r}{r} )$ = ∑_{1 ≤ k ≤ r} (−1)^k − 1 $( \binom{r}{k} )$ .

Führen wir unsere ±-Korrektur also vollständig durch, so haben wir am Ende jede Zahl m des Intervalls { 2, …, n } genau einmal gezählt: Denn ist r die Anzahl der Primteiler von m, so haben wir m nach (+) insgesamt genau einmal gezählt.

Unsere Überlegungen zeigen:

Satz (Einschluss-Ausschluss-Darstellung einer Zahl)

Sei n ≥ 1. Dann gilt

n = 1 + ∑_{p₁ < … < p_k ≤ n} (−1)^k − 1 ⌊ⁿ_{p₁ … p_k}⌋.

Die Bezeichnung als „Einschluss-Ausschluss“ verweist auf die Korrektur der Zählung: Wir nehmen im ersten Schritt möglicherweise zu viele Elemente auf, schließen im zweiten Schritt möglicherweise zu viele Elemente wieder aus usw.

Wir betrachten ein konkretes Beispiel zur Illustration der Zählung.

Beispiel

Sei n = 30. Die Primzahlen bis n sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Wir erhalten die folgenden Summen:

1 + ∑_p ≤ n ⌊ⁿ_p⌋ = 1 + 15 + 10 + 6 + 4 + 2 + 2 + 1 + 1 + 1 + 1 = 44.

1 + ∑_p ≤ n ⌊ⁿ_p⌋ − ∑_{p₁ < p₂ ≤ n} ⌊ⁿ_{p₁ p₂}⌋ =

= 44 − (5 + 3 + 2 + 1 + 1 + 2 + 1) = 44 − 15 = 29,

wobei die Paare (2, 3), (2, 5), (2, 7), (2, 11), (2, 13), (3, 5), (3, 7) eingehen, alle anderen Produkte sind größer als 30. Im nächsten Schritt trägt nur noch das Tripel (2, 3, 5) einen positiven Wert zur Summe (nämlich 1) bei:

1 + ∑_p ≤ n ⌊ⁿ_p⌋ − ∑_{p₁ < p₂ ≤ n} ⌊ⁿ_{p₁ p₂}⌋ + ∑_{p₁ < p₂ < p₃ ≤ n} ⌊ⁿ_{p₁ p₂ p₃}⌋

= 29 + 1 = 30.

Damit können wir die Zählung bereits nach drei Schritten beenden.

Allgemein erreichen wir den Wert n sehr schnell: Sobald das Produkt p₁ … p_k der ersten k Primzahlen größer als n ist, sind alle Werte der Floor-Funktion gleich 0, sodass sie keinen Beitrag zur Summe mehr liefern.

Beispiel

Eine Computerberechnung liefert die folgenden Partialsummen der Einschluss-Ausschluss-Darstellung:

n = 10	12, 10, …, 10
n = 30	44, 29, 30, …, 30
n = 50	78, 48, 50, …, 50
n = 100	172, 92, 100, …, 100
n = 500	1009, 371, 505, 500, …, 500
n = 1000	2127, 656, 1023, 1000, …, 1000

Für n = 1000 gilt zum Beispiel

2 · 3 · 5 · 7 = 210 ≤ 1000,

210 · 11 = 2310 > 1000,

sodass wir die Berechnung bereits nach 4 Schritten beenden können.

Die Möbius-Funktion

Wir können unser Ergebnis noch in eine etwas andere Form bringen, indem wir die auftretenden Vorzeichen durch eine Funktion beschreiben: Das Vorzeichen eines Summanden hängt von der Anzahl der beteiligten Primzahlen ab. Dies motiviert:

Definition (Möbius-Funktion)

Die Möbius-Funktion μ : ℕ* → ℤ ist wie folgt definiert. Zunächst setzen wir μ(1) = 1. Ist m von der Form p₁ … p_k mit p₁ < … < p_k, so setzen wir

μ(m) = μ(p₁ … p_k) = (−1)^k.

Für alle anderen m setzen wir

μ(m) = 0.

Betrachten wir die Zahl 1 als leeres Produkt von Primzahlen, so ist die Setzung μ(1) = 1 = (−1)⁰ ein Spezialfall der Setzung μ(p₁ … p_k) = (−1)^k. Enthält m eine Primzahl mehrfach (d. h. ist m durch das Quadrat einer Primzahl teilbar), so ist die μ-Funktion gleich 0. Die Möbius-Funktion nimmt nach Definition nur die drei Werte −1, 0 und 1 an.

Wir betrachten einige Beispiele.

Beispiele

Es gilt

μ(1) = 1, μ(2) = −1, μ(3) = −1,

μ(4) = μ(2 · 2) = 0, μ(5) = −1,

μ(6) = μ(2 · 3) = 1, μ(7) = −1,

μ(8) = μ(2 · 2 · 2) = 0, μ(9) = μ(3 · 3) = 0.

Das folgende Diagramm zeigt den typischen unregelmäßigen Verlauf von μ:

Die Möbius-Funktion μ bis 50

Mit Hilfe der Moebius-Funktion können wir unsere Einschluss-Ausschluss-Darstellung in einer bestechenden Art und Weise neu formulieren:

Satz (Darstellung der 1 mit Hilfe der Möbius-Funktion)

Sei n ≥ 1. Dann gilt

1 = ∑_{1 ≤ m ≤ n} μ(m) ⌊ⁿ_m⌋.

Beweis

Nach unserem Satz gilt

1	= n + ∑_{p₁ < … < p_k ≤ n} (−1)^k ⌊ⁿ_{p₁ … p_k}⌋
	= μ(1) ⌊ⁿ₁⌋ + ∑_{2 ≤ m ≤ n} μ(m) ⌊ⁿ_m⌋
	= ∑_{1 ≤ m ≤ n} μ(m) ⌊ⁿ_m⌋.

Das Ergebnis ist ein Spezialfall einer allgemeinen Umkehrformel von Möbius, die wir später kennenlernen werden.

Das folgende Diagramm zeigt exemplarisch, wie die 1 durch die Summe erreicht wird:

Die Partialsummen ∑_{1 ≤ m ≤ k} μ(m) ⌊ⁿ_m⌋ der 1-Darstellung für n = 30 und k = 1, …, 30