Satz von Erdős-Kac
Der Satz von Erdős–Kac [<templatestyles src="IPA/styles.css" />] von Paul Erdős und Mark Kac ist ein Satz aus der Zahlentheorie und besagt, dass die Anzahl der verschiedenen Primfaktoren <math>\omega(n)</math> einer zufällig gezogenen Zahl <math>n</math> aus der Menge <math>\{1, 2, 3, \dotsc, N\}</math> für große <math>N \in \N</math> annähernd normalverteilt ist. Das gleiche Resultat gilt für die mit Vielfachheit gezählten Primfaktoren <math>\Omega(n)</math>.
Genauer gilt, wenn <math>\omega(n)</math> die Anzahl der voneinander verschiedenen Primfaktoren der Zahl <math>n \in \N</math> bezeichnet, für feste <math>a, b \in \R</math> mit <math>a < b</math>
- <math>\lim_{N \to \infty} \frac {1}{N} \left | \left\{ n \in \{1, \dotsc, N\} \mid a \le \frac{\omega(n) - \ln \ln N}{\sqrt{\ln \ln N}} \le b \right\} \right | = \int_a^b \varphi(u)\,{\rm d}u</math>,
wobei <math>|\cdot|</math> die Kardinalität bedeutet und
- <math>\varphi(u) = \frac{1}{\sqrt{2\pi}} e^{-u^2/2}</math>
die Wahrscheinlichkeitsdichtefunktion der Standardnormalverteilung ist, die in der Wahrscheinlichkeitstheorie und Statistik häufig als Grenzwert von Verteilungen auftritt.
Heuristische Motivation
Sind <math>p</math> und <math>q</math> zwei verschiedene Primzahlen und ist <math>N</math> eine große Zahl, so ist jede aus den Zahlen von 1 bis <math>N</math> gleich wahrscheinlich gezogene Zahl <math>n</math> ungefähr mit Wahrscheinlichkeit <math>\frac{1}{p}</math> durch <math>p</math>, ungefähr mit Wahrscheinlichkeit <math>\frac{1}{q}</math> durch <math>q</math> und ungefähr mit Wahrscheinlichkeit <math>\frac{1}{pq}</math> durch <math>p</math> und <math>q</math> teilbar. Die Ereignisse <math>\{n \mid p \text{ teilt } n\}</math> und <math>\{n \mid q \text{ teilt } n\}</math> sind also annähernd stochastisch unabhängig. Die Funktion <math>\omega(n)</math> lässt sich als Summe annähernd unabhängiger Indikatorfunktionen
- <math>\omega(n) = \sum_{p\colon p \text{ ist prim}} 1_{\{n \mid p\text{ teilt } n\}}</math>
darstellen und sollte daher für große <math>N</math> durch die Normalverteilung approximiert werden.
Geschichte
Der Satz ist eine Verallgemeinerung des Satzes von Hardy-Ramanujan<ref>G. H. Hardy, S. Ramanujan: The normal number of prime factors of a number. Quart. J. Math. 48 (1917), S. 76–92.</ref> ü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.<ref>Bruce Schechter: Mein Geist ist offen. Birkhäuser, Basel 1999.</ref> 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“,<ref name="Enigmas of Chance">Mark Kac: Enigmas of Chance. University of California Press, Berkeley 1974.</ref> 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).
Einzelnachweise
<references />