2. Die Dirichlet-Faltung

Es ist möglich, die Ergebnisse über die Möbius-Funktion in einer ebenso kompakten wie suggestiven algebraischen Form zu präsentieren. Wir führen hierzu eine neue multiplikative Operation für zahlentheoretische Funktionen ein.

Definition (Dirichlet-Faltung)

Seien f, g : ℕ* → ℝ. Dann ist die Dirichlet-Faltung f ∗ g : ℕ* → ℝ definiert durch

(f ∗ g)(n) = ∑_d|n f (d/n) g(d) für alle n ≥ 1.

Bemerkung

Wir beschränken uns wieder auf reellwertige Funktionen. Die folgenden Ergebnisse gelten auch für komplexwertige Funktionen auf ℕ*.

Nach Definition gilt

(f ∗ g)(n) = ∑_ab = n f (a) g(b) für alle n ≥ 1.

Wir summieren über alle multiplikativen Zerlegungen von n in zwei Faktoren, wobei wir auf den ersten Faktor f und auf den zweiten Faktor g anwenden.

Beispiele

(1)	(f ∗ g)(1) = f (1) g(1).

(2)	(f ∗ g)(2) = f (1) g(2) + f (2) g(1).

(3)	Ist p prim, so gilt (f ∗ g)(p) = f (1) g(p) + f (p) g(1). (f ∗ g)(p²) = f (1) g(p²) + f (p) g(p) + f (p²) g(1).

(4)	Sind p, q zwei verschiedene Primzahlen, so gilt (f ∗ g)(pq) = f (1) g(pq) + f (p) g(q) + f (q) g(p) + f (1) g(pq).

Nachrechnen zeigt, dass die Dirichlet-Faltung assoziativ und kommutativ ist:

Satz (Eigenschaften der Dirichlet-Faltung)

Für alle f, g, h : ℕ* → ℝ gilt

f ∗ (g ∗ h) = (f ∗ g) ∗ h(Assoziativität)

f ∗ g = g ∗ f(Kommutativität)

Weiter definieren wir eine spezielle Funktion, die nur an der Stelle 1 mit Wert 1 ausschlägt und ansonsten 0 ist:

Definition (die ε-Funktion)

Wir definieren ε : ℕ* → ℝ durch

$ε (n) = { \begin{matrix} 1 & falls n = 1 \\ 0 & sonst. \end{matrix}$

Diese Funktion ist, wie man leicht überprüft, neutral für die Dirichlet-Faltung:

Satz (Neutralität von ε)

Für alle f : ℕ* → ℝ gilt

f ∗ ε = f = ε ∗ f.(Neutralität von ε)

Neben der multiplikativen Dirichlet-Faltung steht uns die punktweise Addition zur Verfügung: Sind f, g : ℕ* → ℝ, so ist die Funktion f + g : ℕ* → ℝ definiert durch (f + g)(n) = f (n) + g(n) für alle n ≥ 1. Für Leser mit algebraischen Grundkenntnissen halten wir fest:

Satz (Ring der zahlentheoretischen Funktionen)

Die reellwertigen Funktionen auf ℕ* bilden mit der punktweisen Addition + und der Dirichlet-Faltung ∗ einen kommutativen Ring mit Einselement ε. Das Gleiche gilt für die komplexwertigen Funktionen oder allgemeiner für Funktionen auf ℕ* mit Werten in einem kommutativen Ring.

Der Beweis ergibt sich durch Nachweis der noch nicht nachgewiesenen Ringaxiome. So gilt zum Beispiel für alle f, g, h, dass

(f + g) ∗ h = f ∗ h + g ∗ h.(Distributivgesetz)

Wir setzen

ZF(ℝ) = { f | f : ℕ* → ℝ }

und nennen ZR(ℝ) mit obigen Operationen auch den Ring der reellwertigen zahlentheoretischen Funktionen. Analoges gilt für ZR(ℂ).

Konstante Funktionen bezeichnen wir kurz durch ihren konstanten Wert. Damit ist speziell f ∗ 1 die Teilersumme von f, da

(f ∗ 1)(n) = ∑_d|n f (d) 1 = ∑_d|n f (d) für alle n ≥ 1.

Unser Ergebnis über die Teilersumme von μ können wir nun neu formulieren:

Satz (Teilersumme der Möbius-Funktion, Umformulierung)

Es gilt μ ∗ 1 = ε.

Die Möbius-Funktion und die konstante Eins-Funktion sind also im Ring ZF(ℝ) invers zueinander. Diesen Satz beweisen wir wie früher. Die Umkehrformel ergibt sich nun in wenigen Zeilen durch Anwendung der algebraischen Eigenschaften der Dirichlet-Faltung:

Satz (Umkehrformel von Möbius)

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.

Mit anderen Worten:

g = 1 ∗ f genau dann, wenn f = μ ∗ g.

Zweiter Beweis

Ist g = 1 ∗ f, so gilt

μ ∗ g = μ ∗ 1 ∗ f = ε ∗ f = f.

Ist umgekehrt f = μ ∗ g, so gilt

1 ∗ f = 1 ∗ μ ∗ g = ε ∗ g = g.

Die Dirichlet-Faltung und die Umkehrformel von Möbius liefern viele Identitäten in spielerischer Weise. Einige davon sind:

Satz (Zusammenhänge zwischen zahlentheoretischen Funktionen)

Es gilt:

(a)	ε = 1 ∗ μ, μ = μ ∗ ε

(b)	τ = 1 ∗ 1, 1 = μ ∗ τ

(c)	σ = 1 ∗ id, id = μ ∗ σ

(d)	id = 1 ∗ φ, φ = μ ∗ id

(e)	σ ∗ φ = id ∗ id = id · τ

Beweis

Es bleibt (e) zu zeigen. Diese Aussage ergibt sich aus

σ ∗ φ = σ ∗ μ ∗ id = id ∗ id

sowie der für alle n ≥ 1 gültigen Berechnung

(id ∗ id)(n) = ∑_d|n id(n/d) id(d) = ∑_d|n n = n · τ(n).

Ist f : ℕ* → ℝ, so ist 1 ∗ f die Teilersumme von f. Mit Hilfe der Möbius-Funktion können wir zu einer Funktion g : ℕ* → ℝ die eindeutige Funktion f berechnen, deren Teilersumme g ist. Mit der 1-Funktion gehen wir in diesem Sinne einen Schritt vorwärts, mit μ einen zurück.

Invertierbare Funktionen

Eine natürliche algebraische Frage ist, welche zahlentheoretischen Funktionen sich bzgl. der Dirichlet-Faltung invertieren lassen: Für welche f gibt es ein g mit g ∗ f = ε? Die Antwort ist überraschend einfach:

Satz (Invertierbarkeitskriterium)

Sei f : ℕ* → ℝ. Dann sind äquivalent:

(a)	Es gibt ein g : ℕ* → ℝ mit g ∗ f = ε.

(b)	f (1) ≠ 0.

Weiter ist g im Fall der Existenz eindeutig bestimmt.

Beweis

(a) impliziert (b):

Sei g derart, dass g ∗ f = ε. Dann gilt

1 = ε(1) = (g ∗ f)(1) = ∑_d|1 g(1/d) f (d) = g(1) f (1).

Folglich ist f (1) ≠ 0.

(b) impliziert (a):

Es gelte f (1) ≠ 0. Wir definieren g : ℕ* → ℝ rekursiv durch:

g(1) = ¹_f (1), g(n) = − $\frac{\sum _{d|n, d \neq 1} g (n / d) f (d)}{f (1)}$ für alle n ≥ 2.

Dann gilt

(g ∗ f)(1) = g(1) f (1) = 1,

(g ∗ f)(n)	= ∑_d\|n g(n/d) f (d)
	= ∑_{d\|n, d ≠ 1} g(n/d) f (d) + g(n)f (1) = 0 für alle n ≥ 2.

Die Rechnung im zweiten Teil des Beweises zeigt, dass eine Funktion g′ mit der Eigenschaft g′ ∗ f = ε die rekursive Definition von g erfüllt. Dies zeigt die Eindeutigkeit.

Aus algebraischer Sicht bilden die zahlentheoretischen Funktion f : ℕ* → ℝ, die an der Stelle 1 von 0 verschieden sind mit der Dirichlet-Faltung eine Abelsche Gruppe mit neutralem Element ε. Das Gleiche gilt für die normierten zahlentheoretischen Funktionen, d. h. die Funktionen f : ℕ* → ℝ mit f (1) = 1.

Multiplikative Funktionen

Für teilerfremde n, m gilt φ(nm) = φ(n) φ(m). Analoges gilt für die Möbius-Funktion μ und die Primzahlfaktorzählfunktionen ω und Ω. Wir definieren nun allgemein:

Definition (multiplikative Funktion)

Sei f : ℕ* → ℝ. Dann heißt f multiplikativ, falls gilt:

(a)	f ist nicht die Nullfunktion, d. h. es gibt ein n mit f (n) ≠ 0.

(b)	f (nm) = f (n) f (m) für alle teilerfremden n, m ≥ 1.

Gilt (a) und stärker f (nm) = f (n)f (m) für alle n, m ≥ 1, so heißt f stark multiplikativ.

Ist f multiplikativ und ist f (n) ≠ 0, so gilt f (n) = f(1 · n) = f (1) f (n), sodass f (1) = 1. Eine multiplikative Funktion ist damit notwendig normiert. Wir können die Bedingung (a) äquivalent durch „f ist normiert“ ersetzen.

Aus der Definition folgt, dass eine multiplikative Funktion durch ihre Werte auf den Primzahlpotenzen eindeutig bestimmt ist. Denn es gilt f (1) = 1 und ist p₁^e₁ … p_k^e_k die Primfaktorzerlegung einer Zahl n ≥ 2, so gilt

(+) f (n) = f (p₁^e₁) … f (p_k^e_k).

Umgekehrt können wir eine multiplikative Funktion f definieren, indem wir f (1) = 1 setzen, die Werte f (p^k) für alle Primzahlen p und Exponenten k ≥ 1 beliebig vorschreiben und dann die restlichen Werte durch (+) definieren.

Wir zeigen nun:

Satz (Erhalt der Multiplikativität bei Dirichlet-Faltung)

Seien f, g multiplikativ. Dann ist auch f ∗ g multiplikativ.

Beweis

Seien n, m ≥ 1 relativ prim. Dann lässt sich jeder Teiler d des Produkts nm eindeutig in der Form d = d₁ d₂ schreiben mit d₁|n und d₂|m. Zudem sind die Zahlen d₁ und d₂ wieder relativ prim, und das Gleiche gilt für n/d₁ und m/d₂. Zusammen mit dem Distributivgesetz ergibt sich:

(f ∗ g)(nm)	= ∑_d\|nm f (nm/d) g(d)
	= ∑_d₁\|n ∑_d₂\|m f (nm/(d₁d₂)) g(d₁d₂)
	= ∑_d₁\|n ∑_d₂\|m f (n/d₁) f (m/d₂) g(d₁) g(d₂)
	= (∑_d₁\|n f (n/d₁) g(d₁)) (∑_d₂\|m f (m/d₂) g(d₂))
	= (f ∗ g)(n) · (f ∗ g)(m).

Damit erhalten wir sehr elegant:

Korollar (Multiplikativität von τ, σ und φ)

Die Funktionen τ, σ, φ sind multiplikativ.

Beweis

Die Funktionen 1, id und μ sind multiplikativ und es gilt

τ = 1 ∗ 1, σ = 1 ∗ id, φ = μ ∗ id.

Schließlich zeigen wir noch:

Satz (Multiplikativität des Inversen)

Sei f : ℕ* → ℝ multiplikativ, und sei g : ℕ* → ℝ invers zu f. Dann ist g multiplikativ.

Beweis

Sei h : ℕ* → ℝ die eindeutige multiplikative Funktion mit

h(p^k) = g(p^k) für alle Primzahlen p und Exponenten k ≥ 0.

Nach dem vorangehenden Satz ist h ∗ f multiplikativ. Wir zeigen, dass h = g. Ist p prim und k ≥ 0, so gilt

(h ∗ f)(p^k) = ∑_d|p^k h(p^k/d) f (d) = ∑_d|p^k g(p^k/d) f (d) = (g ∗ f)(p^k) = ε(p^k),

denn jeder Teiler einer Primzahlpotenz ist eine Primzahlpotenz. Damit stimmen die Funktionen h ∗ f und ε auf den Primzahlpotenzen überein. Da beide Funktionen multiplikativ sind, stimmen sie überall überein, d. h. es gilt h ∗ f = ε. Da das Inverse von f eindeutig bestimmt ist, gilt h = g.

Aus algebraischer Sicht bilden die multiplikativen Funktionen also eine Untergruppe der Gruppe aller normierten zahlentheoretischen Funktionen.

(f ∗ g)(nm)	= ∑_d\|nm f (nm/d) g(d)
	= ∑_d₁\|n ∑_d₂\|m f (nm/(d₁d₂)) g(d₁d₂)
	= ∑_d₁\|n ∑_d₂\|m f (n/d₁) f (m/d₂) g(d₁) g(d₂)
	= (∑_d₁\|n f (n/d₁) g(d₁)) (∑_d₂\|m f (m/d₂) g(d₂))
	= (f ∗ g)(n) · (f ∗ g)(m).