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.^[1]

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
10⁶⁵	66	5	2,2
10⁹⁵⁶⁶	9567	10	3,2
10^{210 704 568}	210 704 569	20	4,5
10^10²²	10²²+1	50	7,1
10^10⁴⁴	10⁴⁴+1	100	10
10^10⁴³⁴	10⁴³⁴+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

Jegyzetek

↑ http://www.dms.umontreal.ca/~andrew/PDF/ErdosKac.pdf

[1] ttp://www.dms.umontreal.ca/~andrew/PDF/ErdosKac.pdf

[1]