Erdős–Kac-tétel

Az Erdős–Kac-tétel a valószínűségszámítás és a számelmélet területén azt állítja, hogy ha ω(n) egy n szám egymástól különböző prímtényezőinek száma, és, ha az n számot 1 és N között egyenlő eséllyel sorsoljuk ki, akkor az

${\frac {\omega (n)-\log \log N}{\sqrt {\log \log N}}}$ véletlen érték

valószínűség-eloszlása standard normális eloszlást mutat, amennyiben N elég nagy.

Ez a tétel a Hardy–Ramanujan-tétel kiterjesztése, mely azt állítja, hogy ω(n) átlagértéke log log N, a szórás pedig ${\sqrt {\log \log N}}$. Pontosabban kifejtve a < b esetre:

$\lim _{x\rightarrow \infty }\left({\frac {1}{x}}\cdot \#\left\{n\leq x:a\leq {\frac {\omega (n)-\log \log N}{\sqrt {\log \log N}}}\leq b\right\}\right)=\Phi (a,b)$

ahol $\Phi (a,b)$ a normális eloszlás, vagy más néven Gauss-eloszlás: $\Phi (a,b)={\frac {1}{\sqrt {2\pi }}}\int _{a}^{b}e^{-t^{2}/2}\,dt.$ Amit Erdős és Kac bizonyít, az az, hogy ha n egy tetszőlegesen kiválasztott nagy egész, akkor n egymástól különböző prímtényezőinek száma közelítően normális eloszlású lesz, log log N variancia és várható értékkel. Ez azt jelenti, hogy például egy milliárd nagyságrendű szám felépíthető átlagosan 3 prímszámból. Például: 1 000 000 003 = 23 × 307 × 141 623.

n	n számjegyeinek száma	Prímszámok átlagos száma	szórás
1000	4	2	1,4
1 000 000 000	10	3	1,7
1 000 000 000 000 000 000 000 000	25	4	2
1065	66	5	2,2
109566	9567	10	3,2
10210 704 568	210 704 569	20	4,5
101022	1022+1	50	7,1
101044	1044+1	100	10
1010434	10434+1	1000	31,6

A 10 000 számjegyből álló számok kb. 12,6%-a 10 prímből felépíthető, és 68% (±σ) 7–13 prímből. Egy 186 számjegyből álló szám átlagosan 6 prímből felépíthető.

Irodalom

• Paul Erdős - Mark Kac: The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions. (hely nélkül): American Journal of Mathematics, volume 62, No. 1/4. 1940. 738–742. o.  

Kapcsolódó szócikkek

• http://mathworld.wolfram.com/Erdos-KacTheorem.html
• http://www.renyi.hu/~p_erdos/1940-12.pdf
• Eloszlásfüggvény
• Valószínűségszámítás
• Statisztika
• Matematikai statisztika