1. Die Möbius-Funktion
Im Abschnitt über Siebverfahren hatten wir die Möbius-Funktion μ kennengelernt, mit ihrer wesentlichen Eigenschaft
μ(p1 · … · pk) = (−1)k für Primzahlen p1 < … < pk.
Daneben ist μ(1) = 1 (was dem Fall k = 0, d. h. der 1 als leerem Produkt von Primzahlen entspricht) und ansonsten ist die Möbius-Funktion gleich 0. Das folgende Diagramm gibt noch einmal einen Eindruck vom Verlauf der Funktion.
Verlauf der Möbius-Funktion bis 250. Dabei sind die von Null verschiedenen Werte μ(n) nach der Anzahl der Primfaktoren von n eingefärbt. Im Anfangsbereich sind Primzahlen (gelb) und Produkte aus zwei oder drei Primzahlen (grün bzw. rot). Erst bei 2 · 3 · 5 · 7 = 210 findet sich ein Produkt aus vier verschiedenen Primzahlen.
Wir wollen die Möbius-Funktion nun genauer untersuchen. Elementare Eigenschaften, die direkt aus der Definition folgen, sind:
Satz (Eigenschaften der μ-Funktion)
Für alle n, m ≥ 1 gilt:
(a) | μ(n m) = μ(n) μ(m), falls n, m teilerfremd. (Multiplikativität) |
(b) | μ(n2) = 0 genau dann, wenn n ≠ 1. |
(c) | μ(n)2 = 1 genau dann, wenn n ist quadratfrei. |
Subtiler ist dagegen die folgende Summen-Eigenschaft, die wir mit einem kombinatorischen Argument beweisen:
Satz (Teilersumme der Möbius-Funktion)
Es gilt:
(a) | ∑d|1 μ(d) = 1, |
(b) | ∑d|n μ(d) = 0 für alle n > 1. |
Beweis
Zunächst gilt ∑d|1 μ(d) = μ(1) = 1. Sei also n > 1, und sei
n = p1e1 … pkek
die kanonische Primfaktorzerlegung von n. Wir entfernen Mehrfachfaktoren und setzen entsprechend
n* = p1 … pk.
Da die μ-Funktion für Zahlen, die eine Primzahl mehrfach enthalten, gleich 0 ist, gilt
∑d|n μ(d) = ∑d|n* μ(d).
Die Teiler von n* entsprechen den Teilmengen von P = { p1, …, pk } durch Produktbildung (wobei der leeren Teilmenge das Produkt 1 entspricht). Für Teilmengen mit gerader Mächtigkeit hat μ den Wert 1, für Teilmengen einer ungeraden Mächtigkeit hat μ den Wert −1. Damit genügt es zu zeigen, dass es genauso viele Teilmengen von P mit gerader wie mit ungerader Mächtigkeit gibt. Dies lässt sich durch Induktion nach k ≥ 1 zeigen oder alternativ mit Hilfe des Binomischen Lehrsatzes: Denn es gilt
0 = (−1 + 1)k = ∑i ≤ k (−1)i 1k − i = ∑i ≤ k (−1)i
Die positiven Summanden der rechte Seite zählen die Teilmengen von P mit gerader Mächtigkeit, die negativen die Teilmengen von P mit ungerader Mächtigkeit. Da die Summe 0 ist, sind die beiden Anzahlen gleich.
Beispiel
Sei n = 60 = 22 · 3 · 5. Die Zahl 60 besitzt die zwölf Teiler
1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
Die Summe der μ-Werte dieser Zahlen berechnet sich zu
1 − 1 − 1 + 0 − 1 + 1 + 1 + 0 + 1 + 0 − 1 + 0 = 0.
Es gilt n* = 2 · 3 · 5, sodass genau 23 = 8 der zwölf μ-Werte von 0 verschieden sind. Sie entsprechen den acht Teilern
1, 2, 3, 5, 2 · 3, 2 · 5, 3 · 5, 2 · 3 · 5.
Mit Hilfe der Teilersumme können wir nun vergleichsweise leicht ein fundamentales Ergebnis über die Möbius-Funktion beweisen:
Satz (Umkehrformel von Möbius, Möbius-Inversion)
Seien f, g : ℕ* → ℝ. Dann sind äquivalent:
(a) | g(n) = ∑d|n f (d) für alle n ≥ 1. |
(b) | f (n) = ∑d|n μ(n/d) g(d) für alle n ≥ 1. |
Aus dem Satz folgt: Jede Funktion ist die Teilersumme einer eindeutig bestimmten Funktion. Denn ist g die Teilersumme von f, so kann f mit Hilfe der Möbius-Funktion wie in (b) rekonstruiert werden. Ist umgekehrt g gegeben, so können wir f durch (b) definieren, sodass g die Teilersumme von f ist.
Beweis
(a) impliziert (b):
Es gelte (a). Sei n ≥ 1. Dann gilt
| ∑d|n μ(n/d) g(d) | = ∑d|n μ(d) g(n/d) |
| = ∑d|n μ(d) ∑c|n/d f (c) | |
| = ∑d|n ∑c|n/d μ(d) f (c) | |
| = ∑cd|n μ(d) f (c) | |
| = ∑c|n f (c) ∑d|n/c μ(d) | |
| = f (n), |
wobei wir im letzten Schritt die Teilersummeneigenschaft verwenden: Nur im Fall n/c = 1, d. h. c = n, ist die μ-Summe von Null verschieden, und in diesem Fall gleich 1.
(b) impliziert (a):
Es gelte (b). Sei n ≥ 1. Dann gilt:
| ∑d|n f (d) | = ∑d|n f (n/d) |
| = ∑d|n ∑c|n/d μ((n/d)/c) g(c) | |
| = ∑cd|n μ((n/c)/d)) g(c) | |
| = ∑c|n g(c) ∑d|n/c μ((n/c)/d) | |
| = ∑c|n g(c) ∑d|n/c μ(d) = g(n). |
Der Leser vergleiche das Ergebnis mit den vollen Partialsummen. Hier sind äquivalent:
(a) | g(n) = ∑1 ≤ d ≤ n f (n) für alle n ≥ 1. |
(b) | f (n) = g(n) − g(n − 1) für alle n ≥ 1, wobei g(0) = 0 gesetzt wird. |
Die Umkehrformel von Möbius stellt eine analoge Beziehung her, wenn die Summen auf die Teiler einer Zahl beschränkt werden. Es ist überraschend, dass dies möglich ist, und dass die Paritäten von Primzahlprodukten hier eine Schlüsselrolle spielen.
Beispiele für die Umkehrformel erhalten wir durch die folgenden zahlentheoretischen Funktionen:
Definition (Teileranzahl und Teilersummenfunktion)
Wir definieren τ : ℕ* → ℕ und σ : ℕ* → ℕ durch
τ(n) = |{ 1 ≤ d ≤ n | d ist ein Teiler von n }|,
σ(n) = „die Summe aller Teiler d von n“ für alle n ≥ 1.
Es gilt also
τ(n) = ∑d|n 1, σ(n) = ∑d|n d für alle n ≥ 1.
Die Umkehrformel liefert:
Satz (Umkehrformeln für τ und σ)
Für alle n ≥ 1 gilt:
(a) | 1 = ∑d|n μ(n/d) τ(d), |
(b) | n = ∑d|n μ(n/d) σ(d). |
Ein Beispiel für die umgekehrte Richtung liefert die Eulersche φ-Funktion. Im Abschnitt über Siebverfahren hatten wir gezeigt:
Satz (φ-Funktion und Möbius-Funktion)
Sei n ≥ 1. Dann gilt
φ(n) = n ∑d|n μ(d)/d.
Es gilt
φ(n) = n ∑d|n μ(d)/d = ∑d|n μ(d) n/d = ∑d|n μ(n/d) d für alle n ≥ 1.
Die Umkehrformel von Möbius liefert:
Satz (φ-Funktion und Möbius-Funktion, II)
Sei n ≥ 1. Dann gilt
n = ∑d|n φ(d).
Dieses Ergebnis lässt sich auch sehr ansprechend mit Hilfe der Berechnungsformel für die φ-Funktion beweisen:
Zweiter Beweis
Sei n = p1e1 … pkek die Primfaktorzerlegung von n. Dann sind die Teiler von n genau die Zahlen der Form
(+) p1c1 … pkck mit 0 ≤ ci ≤ ei für alle i = 1, …, k.
Damit erhalten wir (mit Exponenten c1, …, ck wie in (+)) durch Anwendung der Multiplikativität und des Distributivgesetzes:
| ∑d|n φ(d) | = ∑c1, …, ck φ(p1c1 … pkck) |
| = ∑c1, …, ck ∏1 ≤ i ≤ k φ(pici) | |
| = ∏1 ≤ i ≤ k (φ(1) + φ(pi) + φ(pi2) + … + φ(piei)) | |
| = ∏1 ≤ i ≤ k (1 + (pi − 1) + (pi2 − pi) + … + (piei − piei − 1)) | |
| = ∏1 ≤ i ≤ k piei = n. |
Durch diesen Beweis erhalten wir umgekehrt einen neuen Beweis der Formel
φ(n) = n ∑d|n μ(d)/d.
durch Anwendung der Umkehrformel.
Die Ergebnisse lassen die Eulersche φ-Funktion in einem neuen Licht erscheinen:
Die Phi-Funktion ist die Möbius-Inversion der Identität.
Bemerkungen zur Umkehrformel
Obwohl obiger Beweis der Umkehrformel nicht lang ist, ist es instruktiv, sich die Argumentation noch einmal etwas anschaulicher klar zu machen. Sei hierzu f : ℕ* → ℝ gegeben, und sei g : ℕ* → ℝ die Teilersumme von f, d. h.
g(n) = ∑d|n f (d) für alle n ≥ 1.
Wir betrachten nun ein festes n und bilden die Teilersumme von g, d. h.
(+) ∑d|n g(d).
Setzen wir die Definition von g in diese Summe ein, so sehen wir, dass die Summe aus Summanden der Form f (c) besteht, wobei c ein Teiler von n ist. Wir betrachten nun einen Teiler c von n und fragen:
Wie oft kommt f (c) in der Summe (+) vor?
Nach Definition kommt f (c) in einem Summanden g(d) genau dann vor, wenn c ein Teiler von d ist. Die Stellen d sind genau die Vielfachen von c, die zugleich Teiler von n sind. Damit kommt f (c) genau in den Summanden
g(ck) mit k|n/c
vor. Diese Überlegung zeigt:
∑d|n g(d) = ∑c|n τ(n/c) f (c),
wobei τ(n/c) die Anzahl der Teiler von n/c ist.
Wir verallgemeinern nun den Ansatz und betrachten eine gewichtete Teilersumme der Form
(++) ∑d|n h(d) g(d)
mit einer beliebigen Funktion h : ℕ* → ℝ anstelle der konstanten Funktion 1. Unsere Überlegung, wie oft und wo f (c) in (++) vorkommt, liefert nun die Formel
∑d|n h(d)g(d) = ∑c|n (∑k|n/c h(kc)) f (c).
Ersetzen wir h(d) durch h(n/d), so wird die Summe auf der rechten Seite etwas einfacher:
| ∑d|n h(n/d) g(d) | = ∑c|n (∑k|n/c h((n/c)/k)) f (c) |
| = ∑c|n (∑k|n/c h(k)) f (c). |
Diese Formel enthält die Umkehrformel von Möbius als Spezialfall. Denn mit der Funktion h = μ und dem Satz über die Teilersumme von μ ergibt sich
∑d|n μ(n/d) g(d) = ∑c|n (∑k|n/c μ(k)) f (c) = f (n).