Satz von Erdős-Kac

Der Satz von Erdős–Kac [ˈɛrdøːʃ-kaʦ] von Paul Erdős und Mark Kac ist ein Satz aus der Zahlentheorie und besagt, dass die Anzahl der verschiedenen Primfaktoren $\omega (n)$ einer zufällig gezogenen Zahl $n$ aus der Menge $\{1,2,3,\dotsc ,N\}$ für große $N\in \mathbb {N}$ annähernd normalverteilt ist. Das gleiche Resultat gilt für die mit Vielfachheit gezählten Primfaktoren $\Omega (n)$.

Genauer gilt, wenn $\omega (n)$ die Anzahl der voneinander verschiedenen Primfaktoren der Zahl $n\in \mathbb {N}$ bezeichnet, für feste $a,b\in \mathbb {R}$ mit $a<b$

$\lim _{N\to \infty }{\frac {1}{N}}\left|\left\{n\in \{1,\dotsc ,N\}\mid a\leq {\frac {\omega (n)-\ln \ln N}{\sqrt {\ln \ln N}}}\leq b\right\}\right|=\int _{a}^{b}\varphi (u)\,{\rm {d}}u$,

wobei $|\cdot |$ die Kardinalität bedeutet und

$\varphi (u)={\frac {1}{\sqrt {2\pi }}}e^{-u^{2}/2}$

die Wahrscheinlichkeitsdichtefunktion der Standardnormalverteilung ist, die in der Wahrscheinlichkeitstheorie und Statistik häufig als Grenzwert von Verteilungen auftritt.

Heuristische Motivation

Sind $p$ und $q$ zwei verschiedene Primzahlen und ist $N$ eine große Zahl, so ist jede aus den Zahlen von 1 bis $N$ gleich wahrscheinlich gezogene Zahl $n$ ungefähr mit Wahrscheinlichkeit ${\frac {1}{p}}$ durch $p$, ungefähr mit Wahrscheinlichkeit ${\frac {1}{q}}$ durch $q$ und ungefähr mit Wahrscheinlichkeit ${\frac {1}{pq}}$ durch $p$ und $q$ teilbar. Die Ereignisse $\{n\mid p{\text{ teilt }}n\}$ und $\{n\mid q{\text{ teilt }}n\}$ sind also annähernd stochastisch unabhängig. Die Funktion $\omega (n)$ lässt sich als Summe annähernd unabhängiger Indikatorfunktionen

$\omega (n)=\sum _{p\colon p{\text{ ist prim}}}1_{\{n\mid p{\text{ teilt }}n\}}$

darstellen und sollte daher für große $N$ durch die Normalverteilung approximiert werden.

Geschichte

Histogramm von Ω(n) mit n = 1, …, 10⁷

Der Satz ist eine Verallgemeinerung des Satzes von Hardy-Ramanujan über die durchschnittliche asymptotische Anzahl der Primfaktoren. Erdős hörte Kac den Satz als Vermutung in einer Vorlesung in Princeton aussprechen und kam mit dem Beweis kurz nach Ende des Vortrags. Der Satz wurde 1940 von Erdős und Kac veröffentlicht, blieb für zehn Jahre weitgehend unbeachtet und wurde 1958 von Alfréd Rényi und Paul Turán in einer Version mit explizitem Fehlerterm bewiesen. Nach Einschätzung von Kac markiert der Satz „den Einzug des Gesetzes der Normalverteilung […] in die Zahlentheorie und war die Geburtsstunde eines neuen Zweiges dieser altehrwürdigen Disziplin“, der probabilistischen Zahlentheorie.

Quellen

• Paul Erdős and Mark Kac: The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions. In: American Journal of Mathematics. Band 62, Nr. 1/4, (1940), Seiten 738–742.
• Mark Kac: Statistical Independence in Probability, Analysis and Number Theory. Wiley, New York 1959.

Weblinks

• Eric W. Weisstein: Erdős-Kac Theorem. In: MathWorld (englisch).
• Die Originalarbeit (PDF; 863 kB) auf den Seiten des Alfréd Rényi Institute of Mathematics (englisch).