Erdős-Kac's theorem

The Erdős – Kac theorem [ ˈɛrdøːʃ-kaʦ ] by Paul Erdős and Mark Kac is a theorem from number theory and says that the number of different prime factors of a number drawn at random from the set for large is approximately normally distributed . The same result applies to the prime factors counted with multiplicity . ${\displaystyle \omega (n)}$ ${\displaystyle n}$ ${\displaystyle \{1,2,3,\dotsc ,N\}}$ ${\displaystyle N\in \mathbb {N} }$ ${\displaystyle \Omega (n)}$

More precisely, if the number of mutually different prime factors denotes the number , then for fixed with ${\displaystyle \omega (n)}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle a,b\in \mathbb {N} }$ ${\displaystyle a<b}$

${\displaystyle \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}$,

in which

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

is the probability density function of the standard normal distribution, which often appears in probability theory and statistics as the limit value of distributions.

Heuristic motivation

If and are two different prime numbers and is a large number, then each number drawn from the numbers from 1 to equally probable is approximately with probability by , approximately with probability by and approximately with probability by and divisible. The events and are therefore approximately stochastically independent . The function can be seen as the sum of approximately independent indicator functions ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle n}$ ${\displaystyle {\frac {1}{p}}}$ ${\displaystyle p}$ ${\displaystyle {\frac {1}{q}}}$ ${\displaystyle q}$ ${\displaystyle {\frac {1}{pq}}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \{n\mid p{\text{ teilt }}n\}}$ ${\displaystyle \{n\mid q{\text{ teilt }}n\}}$ ${\displaystyle \omega (n)}$

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

and should therefore be approximated for large by the normal distribution. ${\displaystyle N}$

history

Histogram of Ω (n) with n = 1, ..., 10 ⁷

The theorem is a generalization of the Hardy-Ramanujan theorem about the average asymptotic number of prime factors. Erdős heard Kac pronounce the sentence as a conjecture in a Princeton lecture and came up with the proof shortly after the lecture had ended. The theorem was published by Erdős and Kac in 1940, remained largely unnoticed for ten years and was proven in 1958 by Alfréd Rényi and Paul Turán in a version with an explicit error term. According to Kac, the sentence "marks the entry of the law of normal distribution [...] into number theory and marked the birth of a new branch of this time-honored discipline", probabilistic number theory.

swell

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

Web links

• Eric W. Weisstein : Erdős-Kac theorem . In: MathWorld (English).
• The original work (PDF; 863 kB) on the website of the Alfréd Rényi Institute of Mathematics (English).

Individual evidence

1. ^ GH Hardy, S. Ramanujan: The normal number of prime factors of a number. Quart. J. Math. 48 (1917), pp. 76-92.
2. ↑ Bruce Schechter: My mind is open. Birkhäuser, Basel 1999.
3. ↑ Mark Kac: Enigmas of Chance. University of California Press, Berkeley 1974.