Erdős-Kacev izrek

Erdős-Kacev izrek v teoriji števil, znan tudi kot osnovni izrek verjetnostne teorije števil, je izrek, ki pravi, da, če je ${\displaystyle \omega (n)\,}$ število različnih prafaktorjev števila ${\displaystyle n\,}$, potem je prosto rečeno verjetnostna porazdelitev:

${\displaystyle {\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}}\!\,}$

standardna normalna porazdelitev. Izrek se imenuje po Paulu Erdősu in Marku Kacu. Izrek je Kac postavil leta 1940, strogo pa ga je dokazal Erdős istega leta. To je razširitev Hardy-Ramanudžanovega izreka, ki pravi, da je normalni red ${\displaystyle \omega (n)\,}$ enak ${\displaystyle \log \log n\,}$ s tipično napako velikosti ${\displaystyle {\sqrt {\log \log n}}}$.^[1]

Točnejša definicija

Bolj formalno izrek pravi, da za poljubna ${\displaystyle a<b\,}$ velja:

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

kjer je ${\displaystyle \Phi (a,b)}$ normalna (ali Gaussova) porazdelitev, definirana kot:

${\displaystyle \Phi (a,b)={\frac {1}{\sqrt {2\pi }}}\int _{a}^{b}e^{-t^{2}/2}\,\mathrm {d} t\!\,.}$

V splošnem, če je ${\displaystyle f(n)}$ močno aditivna funkcija (${\displaystyle \scriptstyle f(p_{1}^{a_{1}}\cdots p_{k}^{a_{k}})=f(p_{1})+\cdots +f(p_{k})}$) z${\displaystyle \scriptstyle |f(p)|\leq 1}$ za vsa praštevila ${\displaystyle p\,}$, potem velja:

${\displaystyle \lim _{x\rightarrow \infty }\left({\frac {1}{x}}\cdot \#\left\{n\leq x:a\leq {\frac {f(n)-A(n)}{B(n)}}\leq b\right\}\right)=\Phi (a,b)\!\,,}$

kjer je:

${\displaystyle A(n)=\sum _{p\leq n}{\frac {f(p)}{p}},\qquad B(n)={\sqrt {\sum _{p\leq n}{\frac {f(p)^{2}}{p}}}}\!\,.}$

Kacev izvirni hevristični prijem

Intuitivno je Kac hevristično za rezultat rekel, da če je ${\displaystyle n\,}$ naključno izbrano veliko celo število, je število različnih prafaktorjev ${\displaystyle n\,}$ približno normalno porazdeljeno z aritmetično sredino in varianco ${\displaystyle \log \log n\,}$. To izhaja iz dejstva, da sta dogodka, da je za poljubno naravno število ${\displaystyle n\,}$ »število« ${\displaystyle n\,}$ deljivo s kakšnim praštevilom ${\displaystyle p\,}$ za vsako praštevilo ${\displaystyle p\,}$ obojestransko neodvisna.

Če se sedaj označi dogodek, da je »število« ${\displaystyle n\,}$ deljivo s ${\displaystyle p\,}$ z ${\displaystyle n_{p}}$, je vsota naznačenih naključnih spremenljivk enaka:

${\displaystyle I_{n_{2}}+I_{n_{3}}+I_{n_{5}}+I_{n_{7}}+\ldots \!\,}$

Ta vsota šteje koliko različnih prafaktorjev ima to naključno naravno število ${\displaystyle n\,}$. Lahko se pokaže, da za to vsoto velja Lindebergov pogoj, in tako Lindebergov centralni limitni izrek zagotavlja, da bo po ustrezni umeritvi, zgornji izraz normalno porazdeljen.

Dejanski Erdősev dokaz s pomočjo teorije sit strogo dokaže zgornjo intuicijo.

Numerični zgledi

Erdős-Kacev izrek pomeni, da konstrukcija števila okrog ene milijarde zahteva v povprečju tri praštevila. Velja na primer: 1.000.000.003 = 23 · 307 · 141623.

Naslednja razpredelnica podaja numerični seštevek rasti povprečnega števila različnih prafaktorjev naravnega števila ${\displaystyle n\,}$ z naraščajočim ${\displaystyle n\,}$.

Histogram števila različnih prafaktorjev ${\displaystyle \omega (n)\,}$ za ${\displaystyle n=1,\cdots ,10^{7}\,}$

n	število števk v n	povprečno število različnih praštevil	standardni odklon
1.000	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^65	66	5	2,2
10^9.566	9.567	10	3,2
10^210.704.568	210.704.569	20	4,5
10^1022	10^22+1	50	7,1
10^1044	10^44+1	100	10
10^10434	10^434+1	1000	31,6

Približno 12,6 % od 10.000 števčnih števil se skonstruira iz 10-ih različnih praštevil in približno 68 % iz od 7 do 13 praštevil.

Votla sfera velikosti planeta Zemlja napolnjena s finim peskom bi imela približno 10³³ zrnc. Prostornina opazljivega vesolja bi imela približno 10⁹³ zrnc peska. V takšnem vesolju bi bilo prostora za 10¹⁸⁵ kvantnih strun. Število takšne velikosti s 186 števkami bi za konstrukcijo zahtevalo v povprečju le 6 praštevil.

Zelo težko je, če ne nemogoče, odkriti takšen rezultat empirično, saj se normalna porazdelitev kaže le kadar je ${\displaystyle n}$ približno enak ${\displaystyle 10^{100}}$. Rényi in Turán sta točneje pokazala, da je najboljša možna enakomerna asimptotična meja napake v približku za normalno porazdelitev enaka ${\displaystyle O\left({\frac {1}{\sqrt {\log \log n}}}\right)}$.^[2]

Glej tudi

• praštevilski izrek

Sklici

1. Hardy; Ramanudžan (1917).
2. Rényi; Turán (1958).

Viri

• Erdős, Paul; Kac, Mark (1940), »The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions«, American Journal of Mathematics, 62 (1/4): 738–742, doi:10.2307/2371483, ISSN 0002-9327, Zbl 0024.10203
• Erdős, Paul; Wintner, Aurel (1939), »Additive arithmetic functions and statistical independence«, American Journal of Mathematics, 61 (3): 713–722, doi:10.2307/2371326, ISSN 0002-9327, Zbl 0022.00903
• Hardy, Godfrey Harold; Ramanudžan, Srinivasa (1917), »The normal number of prime factors of a number«, Quart. J. Math., 48: 76–92
• Kac, Mark (1959), Statistical Independence in Probability, Analysis and Number Theory, John Wiley and Sons, Inc.
• Kuo, Wentang; Liu, Yu-Ru (2008), »The Erdős–Kac theorem and its generalizations«, v De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian (ur.), Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13--17, 2006, CRM Proceedings and Lecture Notes, zv. 46, Providence, RI: Ameriško matematično društvo, str. 209–216, ISBN 978-0-8218-4406-9, Zbl 1187.11024
• Rényi, Alfréd; Turán, Pál (1958), »On a theorem of Erdös-Kac« (PDF), Acta Arithmetica, 4 (1): 71–84

Zunanje povezave

• Weisstein, Eric Wolfgang. »Erdős–Kac Theorem«. MathWorld.
• Timothy Gowers: The Importance of Mathematics (part 6, 4 mins in) and (part 7)
• Izvirni Erdősev in Kacev članek (PDF; 863 kB) s strani Matematičnega inštituta Alfréda Rényia (angleško)