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 $\omega (n)$ število različnih prafaktorjev števila $n$, potem je prosto rečeno verjetnostna porazdelitev:

$\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 $\omega (n)$ enak $\log \log n$ s tipično napako velikosti $\sqrt{\log \log n}$.

Točnejša definicija

Bolj formalno izrek pravi, da za poljubna $a<b$ velja:

$\underset{x\to \mathrm{\infty }}{\lim }(\frac{1}{x}\cdot \mathrm{\#}\{n\le x:a\le \frac{\omega (n)-\log \log n}{\sqrt{\log \log n}}\le b\})=\mathrm{\Phi }(a,b),$

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

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

V splošnem, če je $f(n)$ močno aditivna funkcija ($f(p_1^{a_1}\cdots p_k^{a_k})=f(p_1)+\cdots +f(p_k)$) z$|f(p)|\le 1$ za vsa praštevila $p$, potem velja:

$\underset{x\to \mathrm{\infty }}{\lim }(\frac{1}{x}\cdot \mathrm{\#}\{n\le x:a\le \frac{f(n)-A(n)}{B(n)}\le b\})=\mathrm{\Phi }(a,b),$

kjer je:

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

Kacev izvirni hevristični prijem

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

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

$I_{n_2}+I_{n_3}+I_{n_5}+I_{n_7}+\dots$

Ta vsota šteje koliko različnih prafaktorjev ima to naključno naravno število $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 $n$ z naraščajočim $n$.

Histogram števila različnih prafaktorjev $\omega (n)$ za $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
1065	66	5	2,2
109.566	9.567	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

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 $n$ približno enak $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 $O\left(\frac{1}{\sqrt{\log \log n}}\right)$.

Glej tudi

• praštevilski izrek

Viri

• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat
• Predloga:Citat

Zunanje povezave

• Predloga: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 Predloga:Ikona en