Satz von Erdős-Kac
Der Satz von Erdős–Kac [Paul Erdős und Mark Kac ist ein Satz aus der Zahlentheorie und besagt, dass die Anzahl der verschiedenen Primfaktoren einer zufällig gezogenen Zahl aus der Menge für große annähernd normalverteilt ist. Das gleiche Resultat gilt für die mit Vielfachheit gezählten Primfaktoren .
] vonGenauer gilt, wenn die Anzahl der voneinander verschiedenen Primfaktoren der Zahl bezeichnet, für feste mit
- ,
wobei die Kardinalität bedeutet und
die Wahrscheinlichkeitsdichtefunktion der Standardnormalverteilung ist, die in der Wahrscheinlichkeitstheorie und Statistik häufig als Grenzwert von Verteilungen auftritt.
Heuristische Motivation
Sind und zwei verschiedene Primzahlen und ist eine große Zahl, so ist jede aus den Zahlen von 1 bis gleich wahrscheinlich gezogene Zahl ungefähr mit Wahrscheinlichkeit durch , ungefähr mit Wahrscheinlichkeit durch und ungefähr mit Wahrscheinlichkeit durch und teilbar. Die Ereignisse und sind also annähernd stochastisch unabhängig. Die Funktion lässt sich als Summe annähernd unabhängiger Indikatorfunktionen
darstellen und sollte daher für große durch die Normalverteilung approximiert werden.
Geschichte
Der Satz ist eine Verallgemeinerung des Satzes von Hardy-Ramanujan[1] ü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.[2] 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“,[3] 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
- G. H. Hardy, S. Ramanujan: The normal number of prime factors of a number. Quart. J. Math. 48 (1917), S. 76–92.
- Bruce Schechter: Mein Geist ist offen. Birkhäuser, Basel 1999.
- Mark Kac: Enigmas of Chance. University of California Press, Berkeley 1974.