Satz von Erdős-Kac

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 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 .

Genauer 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

[Bearbeiten | Quelltext bearbeiten]

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.

Histogramm von Ω(n) mit n = 1, …, 107

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.

  • 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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. G. H. Hardy, S. Ramanujan: The normal number of prime factors of a number. Quart. J. Math. 48 (1917), S. 76–92.
  2. Bruce Schechter: Mein Geist ist offen. Birkhäuser, Basel 1999.
  3. Mark Kac: Enigmas of Chance. University of California Press, Berkeley 1974.