Ogled vira Erdős-Kacev izrek

'''Erdős-Kacev izrek''' v [[teorija števil|teoriji števil]], znan tudi kot osnovni izrek [[verjetnostna teorija števil|verjetnostne teorije števil]], je [[izrek]], ki pravi, da, če je <math>\omega(n)\, </math> število različnih [[prafaktor]]jev števila <math>n\, </math>, potem je prosto rečeno [[verjetnostna porazdelitev]]:

: <math> \frac{\omega(n) - \log\log n}{\sqrt{\log\log n}} \!\, </math>

standardna [[normalna porazdelitev]]. Izrek se imenuje po [[Paul Erdős|Paulu Erdősu]] in [[Mark Kac|Marku Kacu]]. Izrek je Kac postavil leta [[1940 v znanosti|1940]], strogo pa ga je [[matematični dokaz|dokazal]] Erdős istega leta. To je razširitev [[Hardy-Ramanudžanov izrek|Hardy-Ramanudžanovega izreka]], ki pravi, da je [[normalni red aritmetične funkcije|normalni red]] <math>\omega(n)\, </math> enak <math>\log\log n\, </math> s tipično napako velikosti <math>\sqrt{\log\log n}</math>.<ref>{{sktxt|Hardy|Ramanudžan|1917}}.</ref>

== Točnejša definicija ==

Bolj formalno izrek pravi, da za poljubna <math>a < b\, </math> velja:

: <math>\lim_{x \rightarrow \infty}  \left ( \frac {1}{x} \cdot \#\left\{ n \leq x : a \le \frac{\omega(n) - \log \log n}{\sqrt{\log \log n}} \le b \right\} \right ) = \Phi(a,b) \!\, , </math>

kjer je <math>\Phi(a,b)</math> normalna (ali Gaussova) porazdelitev, definirana kot:

: <math>\Phi(a,b)= \frac{1}{\sqrt{2\pi}}\int_a^b e^{-t^2/2} \,\mathrm{d} t \!\, . </math>

V splošnem, če je <math>f(n)</math> močno [[aditivna funkcija]] (<math>\scriptstyle f(p_1^{a_1}\cdots p_k^{a_k})=f(p_1)+\cdots+f(p_k)</math>) z<math>\scriptstyle |f(p)|\le1</math> za vsa [[praštevilo|praštevila]] <math>p\, </math>, potem velja:

: <math> \lim_{x \rightarrow \infty}  \left ( \frac {1}{x} \cdot \#\left\{ n \leq x : a \le \frac{f(n) - A(n)}{B(n)} \le b \right\} \right ) = \Phi(a,b) \!\, , </math>

kjer je:

: <math> A(n)=\sum_{p\le n}\frac{f(p)}{p},\qquad B(n)=\sqrt{\sum_{p\le n}\frac{f(p)^2}{p}} \!\, . </math>

== Kacev izvirni hevristični prijem ==

Intuitivno je Kac hevristično za rezultat rekel, da če je <math>n\, </math> naključno izbrano veliko [[celo število]], je število različnih prafaktorjev <math>n\, </math> približno normalno porazdeljeno z [[aritmetična sredina|aritmetično sredino]] in [[varianca|varianco]] <math>\log\log n\, </math>. To izhaja iz dejstva, da sta dogodka, da je za poljubno [[naravno število]] <math>n\, </math> »število« <math>n\, </math> [[deljivost|deljivo]] s kakšnim praštevilom <math>p\, </math> za vsako praštevilo <math>p\, </math> obojestransko [[neodvisnost (statistika)|neodvisna]].

Če se sedaj označi dogodek, da je »število« <math>n\, </math> deljivo s <math>p\, </math> z <math>n_{p}</math>, je vsota naznačenih [[naključna spremenljivka|naključnih spremenljivk]] enaka:

: <math> I_{n_{2}} + I_{n_{3}} + I_{n_{5}} + I_{n_{7}} + \ldots \!\, </math>

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

Dejanski Erdősev dokaz s pomočjo [[teorija sit|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&nbsp;·&nbsp;307&nbsp;·&nbsp;141623.

Naslednja razpredelnica podaja numerični seštevek rasti povprečnega števila različnih prafaktorjev naravnega števila <math>n\, </math> z naraščajočim <math>n\, </math>.
[[slika:Bigomegahist1e7.svg|thumb|right|250px|Histogram števila različnih [[prafaktor]]jev <math>\omega(n)\, </math> za <math>n =1,\cdots , 10^{7}\, </math>]]

{| class="wikitable" style="text-align:center"
|-
!  ''n''
! število
števk v ''n''
! povprečno število
različnih praštevil

! [[standardni odklon|standardni <br />
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<sup>65</sup>
|66
|5
|2,2
|-
|10<sup>9.566</sup>
|9.567
|10
|3,2
|-
|10<sup>210.704.568</sup>
|210.704.569
|20
|4,5
|-
|10<sup>10<sup>22</sup></sup>
|10<sup>22</sup>+1
|50
|7,1
|-
|10<sup>10<sup>44</sup></sup>
|10<sup>44</sup>+1
|100
|10
|-
|10<sup>10<sup>434</sup></sup>
|10<sup>434</sup>+1
|1000
|31,6
|}
<!-- [[slika:EKT plot.svg|thumb|right|250px|Normalna porazdelitev različnih praštevil, ki ilustrira Erdős-Kacev izrek]] -->

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<sup>33</sup> zrnc. Prostornina [[opazljivo vesolje|opazljivega vesolja]] bi imela približno 10<sup>93</sup> zrnc peska. V takšnem [[vesolje|vesolju]] bi bilo prostora za 10<sup>185</sup> kvantnih [[teorija strun|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 <math>n</math> približno enak <math>10^{100}</math>. [[Alfréd Rényi|Rényi]] in [[Pál Turán|Turán]] sta točneje pokazala, da je najboljša možna enakomerna asimptotična meja napake v približku za normalno porazdelitev enaka <math>O\left(\frac{1}{\sqrt{\log \log n}}\right)</math>.<ref>{{sktxt|Rényi|Turán|1958}}.</ref>

== Glej tudi ==

* [[praštevilski izrek]]

== Sklici ==

{{sklici|2}}

== Viri ==

{{refbegin|2}}
* {{citat|last1= Erdős|first1= Paul|authorlink1= Paul Erdős|last2= Kac|first2= Mark|authorlink2= Mark Kac|title= The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions|journal= [[American Journal of Mathematics]]|date= 1940|volume= 62|issue= 1/4|pages= 738–742|zbl= 0024.10203|issn= 0002-9327|doi= 10.2307/2371483}}
* {{citat|last1= Erdős|first1= Paul|authorlink1= |last2= Wintner|first2= Aurel|authorlink2= Aurel Wintner|title= Additive arithmetic functions and statistical independence|journal= American Journal of Mathematics|date= 1939|volume= 61|issue= 3|pages= 713–722|zbl= 0022.00903|issn= 0002-9327|doi= 10.2307/2371326}}
* {{citat|last1= Hardy|first1= Godfrey Harold|authorlink1= Godfrey Harold Hardy|last2= Ramanudžan|first2= Srinivasa|authorlink2= Srinivasa Ajangar Ramanudžan|title= The normal number of prime factors of a number|journal= Quart. J. Math.|date= 1917|volume= 48|issue= |pages= 76–92}}
* {{citat|last1= Kac|first1= Mark|title= Statistical Independence in Probability, Analysis and Number Theory|date= 1959|publisher= John Wiley and Sons, Inc. }}
* {{citat|last1= Kuo|first1= Wentang|last2= Liu|first2= Yu-Ru|chapter= The Erdős–Kac theorem and its generalizations|pages= 209–216|editor1-last= De Koninck|editor1-first= Jean-Marie|editor2-last= Granville|editor2-first= Andrew|editor2-link= Andrew Granville|editor3-last= Luca|editor3-first= Florian|title= Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13--17, 2006|location= Providence, RI|publisher= [[Ameriško matematično društvo]]|series= CRM Proceedings and Lecture Notes|date= 2008|volume= 46|isbn= 978-0-8218-4406-9|zbl= 1187.11024}}
* {{citat|last1= Rényi|first1= Alfréd|authorlink1= Alfréd Rényi|last2= Turán|first2= Pál|authorlink2= Pál Turán|title= On a theorem of Erdös-Kac|journal= [[Acta Arithmetica]]|date= 1958|volume= 4|issue= 1|pages= 71–84|url= http://matwbn.icm.edu.pl/ksiazki/aa/aa4/aa417.pdf}}
{{refend}}

== Zunanje povezave ==

* {{MathWorld|urlname=Erdos-KacTheorem|title=Erdős–Kac Theorem}}
* [https://www.youtube.com/watch?v=4ivoaFLQ4vM#generator Timothy Gowers: The Importance of Mathematics (part 6, 4 mins in) and (part 7)]
* [http://www.renyi.hu/~p_erdos/1940-12.pdf Izvirni Erdősev in Kacev članek] (PDF; 863&nbsp;kB) s strani [http://www.renyi.hu Matematičnega inštituta Alfréda Rényia] {{ikona en}}

{{DEFAULTSORT:Erdos-Kacev izrek}}

[[Kategorija:Paul Erdős]]
[[Kategorija:Normalna porazdelitev]]
[[Kategorija:Matematični izreki]]
[[Kategorija:1940 v znanosti]]