6. Die Psi-Funktion von Chebychev
Bei der Diskussion des Satzes von Legendre hatten wir bereits die von Mangoldt und die Psi-Funktion eingeführt. Diese Funktionen untersuchen wir nun genauer. Zur Erinnerung:
Definition (Lambda-Funktion und Psi-Funktion)
Die von Mangoldt-Funktion Λ : ℕ* → ℝ und die Chebychev-Funktion ψ : [ 1, ∞ [ → ℝ sind wie folgt definiert:
Ist p prim und k ≥ 1, so setzen wir
Λ(pk) = log(p).
Für alle anderen n ≥ 0 setzen wir Λ(n) = 0. Damit definieren wir nun
ψ(x) = ∑n ≤ x Λ(n) für alle x ≥ 1.
Verlauf der Λ-Funktion bis x = 64 (blaue Punkte), zusammen mit konstanten Funktionen log(p), p prim
Diagramme der ψ-Funktion zeigen einen quasilinearen Verlauf:
Die Funktion ψ (blau) sowie die Identität (gelb) bis x = 1000
Es scheint beinahe so, als ob die Identität die ψ-Funktion anziehen würde. Dies wird noch deutlicher, wenn wir die Differenzfunktion betrachten:
Die Werte ψ(x) − x bis x = 1000
Im Abschnitt über den Primzahlsatz werden wir auf diese Phänomene zurückkommen und sie mit elementaren Methoden plausibel machen können.
Eigenschaften der von Mangoldt-Funktion
Die von Mangoldt-Funktion hat genau für die Primzahlpotenzen positive Werte. Sie ignoriert den Exponenten und liefert log(p). Hieraus ergibt sich die folgende grundlegende Eigenschaft:
Satz (erste Summenformel für Λ)
Sei n ≥ 1. Dann gilt
(a) | log(n) = ∑d|n Λ(d), |
(b) | Λ(n) = ∑d|n μ(n/d) log(d). |
Mit anderen Worten:
log = 1 ∗ Λ, Λ = μ ∗ log.
Beweis
Ist p prim und d ein Teiler von n, so gilt Λ(d) = log(p) genau dann, wenn d eine der Primzahlpotenzen p, p2, …, pexp(n) ist. Damit sind genau exp(n) viele Summanden von ∑d|n Λ(d) gleich log(p). Anwendung der Logarithmusregeln liefert (a). Aus der Umkehrformel von Möbius erhalten wir (b). Der Zusatz ergibt sich aus der Definition der Dirichlet-Faltung.
Überraschend ist, dass wir in der Aussage (b) des Satzes μ(n/d) durch μ(d) ersetzen können − abgesehen von einem Vorzeichen:
Satz (zweite Summenformel für Λ)
Sei n ≥ 1. Dann gilt
(a) | μ(n) log(n) = − ∑d|n μ(n/d) Λ(n), |
(b) | Λ(n) = − ∑d|n μ(d) log(d). |
Mit anderen Worten:
− μ · log = μ ∗ Λ, − Λ = 1 ∗ (μ · log).
Beweis
Wir zeigen (b); die Aussage (a) ergibt sich aus (b) durch Anwendung der Umkehrformel auf die Funktion − μ · log. Sei also n ≥ 1. Nach dem vorangehenden Satz gilt
| Λ(n) | = ∑d|n μ(n/d) log(d) = ∑d|n μ(d) log(n/d) |
| = ∑d|n μ(d)(log(n) − log(d)) | |
| = log(n) ∑d|n μ(d) − ∑d|n μ(n) log(d) | |
| = − ∑d|n μ(n) log(d) |
Dabei verwenden wir im letzten Schritt den Satz über die Teilersumme von μ sowie log(1) = 0 im Fall n = 1.
Etwas länger, aber direkter und kombinatorisch lehrreich ist:
Zweiter Beweis
Wir zeigen wieder (b). Die Aussage ist klar für n = 1. Sei also n ≥ 2, und sei n* = p1 … pk das Produkt der Primteiler p1 < … < pk von n. Dann gilt
∑d | n μ(d) log(d) = ∑d|n* μ(d) log(d).
Ist k = 1, so ist n* = p1 und
∑d|n* μ(d) log(d) = μ(1) log(1) + μ(p1) log(p1) = − log(p1) = − Λ(n).
Sei also k ≥ 2. Sei A = { p1, …, pk } und sei p ∈ A. Dann gilt:
(+) |{ B ⊆ A | p ∈ B, |B| gerade }| = |{ B ⊆ A | p ∈ B, |B| ungerade }|.
Zum Beweis von (+) sei p* ∈ A − { p }. Ist B ⊆ A − { p* } mit p ∈ B, so hat B ∪ { p* } eine andere Parität als B. Hieraus folgt (+) (alternativ durch Induktion). Nach den Logarithmusregeln und (+) gilt nun
∑d|n* μ(d) log(d) = ∑d|n* ∑p|d μ(d) log(p) = ∑p|n* 0 = 0 = − Λ(n).
Denn die Teiler von n* entsprechen den Teilmengen von A, und für jedes p ∈ A erscheint der Term log(p) nach (+) genauso oft mit einem positiven wie mit einem negativen Vorzeichen in der Doppelsumme.
Kombinieren wir die Aussagen der beiden Sätze, so erhalten wir:
Korollar
Sei n ≥ 1. Dann gilt
∑d|n (μ(d) + μ(n/d)) log(d) = 0.
Beispiele
Sei n = 26 = 64. Die Teiler von n sind 1, 2, 4, 8, 16, 32, 64. Es gilt
∑d|n μ(d) log(d) = − log(2),
∑d|n μ(n/d) log(d) = − log(32) + log(64) = (−5 + 6) log(2) = log(2)
Für n = 80 = 24 · 5 mit den Teilern 1, 2, 4, 5, 8, 10, 16, 20, 40, 80 gilt
∑d|n μ(d) log(d) = − log(2) − log(5) + log(10)
∑d|n μ(n/d) log(d) = log(8) − log(16) − log(40) + log(80)
Eigenschaften der Psi-Funktion
Ein einfaches, aber bemerkenswertes Ergebnis über die ψ-Funktion ist:
Satz (kgV-Eigenschaft von ψ)
Sei x ≥ 1, und sei v = kgV({ 1, …, ⌊x⌋ }). Dann gilt ψ(x) = log(v).
Beweis
Sei p prim. Dann ist exp(v) das Maximum der p-Exponenten aller n ≤ x und damit das größte e ≥ 0 mit pe ≤ x. In
ψ(x) = ∑n ≤ x Λ(n)
taucht der Summand log(p) genau e oft auf (an den Stellen p, p2, …, pe). Hieraus folgt die Behauptung.
Aus der Definition von ψ und dem Additionstheorem der Exponentialfunktion folgt, dass eψ(x) ein Produkt von Primzahlen ist. Der Satz identifiziert dieses Produkt: De Zahl eψ(x) ist das kleinste gemeinsame Vielfache der natürlichen Zahlen bis einschließlich x.
Im Essay über den Satz von Legendre hatten wir bereits gezeigt:
Satz (Chebychev-Identität)
Sei x ≥ 1. Dann gilt:
∑n ≤ x ψ(x/n) = log(⌊x⌋!) = ∑n ≤ x log(n).
Bemerkung
Die Chebychev-Identität können wir mit Hilfe der Delta-Operation wie folgt schreiben:
1 Δ ψ = logfac,
wobei logfac(x) = log(⌊x⌋!) für alle x ≥ 1. Umkehrung liefert
ψ = μ Δ logfac.
Wir geben noch einen direkteren Beweis für dieses wichtige Ergebnis (der aber im Wesentlichen die Legendre-Argumentation wiederholt):
Zweiter Beweis der Chebychev-Identität
Es gilt
| ∑n ≤ x ψ(x/n) | = ∑n ≤ x ∑d ≤ x/n Λ(d) |
| = ∑d ≤ x ⌊x/d⌋ Λ(d) | |
| = ∑n ≤ x ∑d|n Λ(d) | |
| = ∑n ≤ x log(n). |
Die erste Identität gilt nach Definition von ψ. Für die zweite Identität zählen wir für jedes d, wie oft der Summand Λ(d) in der Summe auftaucht. Da d ≤ x/n äquivalent zu n ≤ x/d ist, ist diese Anzahl gleich ⌊x/d⌋. Die dritte Identität ergibt sich aus der spalten- bzw. zeilenweisen Summation der Funktion f mit f(d, n) = Λ(d) für alle (d, n) mit d|n (vgl. die Teilbarkeitsdiagramme). Für die letzte Identität verwenden wir den Satz über die Teilersumme von Λ.
Aus der Untersuchung des Sprungverhaltens der beteiligten Funktionen ergibt sich ein induktives Argument:
Dritter Beweis der Chebychev-Identität
Seien f (x) = ∑n ≤ x ψ(x/n), g(x) = ∑n ≤ x log(n) für x ≥ 1. Wir zeigen durch Induktion, dass f (m) = g(m) für alle natürlichen Zahlen m ≥ 1 gilt. Dies genügt, da beide Funktionen nur für natürliche Zahlen springen. Zunächst gilt f (1) = 1 = g(1). Im Induktionsschritt von m − 1 nach m nehmen wir an, dass f (m − 1) = g(m − 1). An der Stelle m springt die Funktion g um log(m). Die Funktion f springt um ∑d|m Λ(d), denn die ganzzahligen Glieder der Folge m, m/2, m/3, … sind genau die Teiler von m. Aus ∑d|m Λ(d) = log(m) und der Induktionsvoraussetzung folgt, dass f (n) = g(n).