Pojdi na vsebino

Erdős-Kacev izrek

Iz Wikipedije, proste enciklopedije

Erdős-Kacev izrek v teoriji števil, znan tudi kot osnovni izrek verjetnostne teorije števil, je izrek, ki pravi, da, če je število različnih prafaktorjev števila , potem je prosto rečeno verjetnostna porazdelitev:

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 enak s tipično napako velikosti .[1]

Točnejša definicija

[uredi | uredi kodo]

Bolj formalno izrek pravi, da za poljubna velja:

kjer je normalna (ali Gaussova) porazdelitev, definirana kot:

V splošnem, če je močno aditivna funkcija () z za vsa praštevila , potem velja:

kjer je:

Kacev izvirni hevristični prijem

[uredi | uredi kodo]

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

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

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

[uredi | uredi kodo]

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 z naraščajočim .

Histogram števila različnih prafaktorjev za
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 1033 zrnc. Prostornina opazljivega vesolja bi imela približno 1093 zrnc peska. V takšnem vesolju bi bilo prostora za 10185 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 približno enak . 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 .[2]

Glej tudi

[uredi | uredi kodo]

Sklici

[uredi | uredi kodo]
  • 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

[uredi | uredi kodo]