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 ω(n) einer zufällig gezogenen Zahl n aus der Menge $\{1, 2, 3, \ldots, 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 Ω(n).

Genauer gilt, wenn ω(n) die Anzahl der voneinander verschiedenen Primfaktoren der Zahl $n \in \mathbb N$ bezeichnet, für festes $a, b \in \mathbb N$ mit a < b

$\lim_{N \rightarrow \infty} \frac {1}{N} \left | \left\{ n \in \{1, ...,N\} : a \le \frac{\omega(n) - \ln \ln N}{\sqrt{\ln \ln N}} \le b \right\} \right | = \int_a^b \varphi(u)\,{\rm d}u$,

wobei

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

die Wahrscheinlichkeitsdichtefunktion der Standard-Normalverteilung ist, welche 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 gleichwahrscheinlich 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 teilbar durch p} und {n teilbar durch q} sind also annähernd stochastisch unabhängig. Die Funktion ω(n) lässt sich als Summe annähernd unabhängiger Indikatorfunktionen

ω(n) =	∑	1{n teilbar durch p}
	p:p ist prim

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

Geschichte

Histogramm von Ω(n), n=1,...,10e+6

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.

Einzelnachweise

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.

Quellen

• Paul Erdős and Mark Kac, The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions, 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

• Erdős–Kac Theorem bei Mathworld (engl.)
• Die Originalarbeit (pdf) auf den Seiten des Alfréd Rényi Institute of Mathematics (engl.)