Teorema prostih brojeva

U teoriji brojeva, teorema prostih brojeva (engl. prime number theorem, PNT) opisuje asimptotsku distribuciju prostih brojeva među pozitivnim celim brojevima. To formalizuje intuitivnu ideju da prosti brojevi postaju manje zastupljeni kako postaju veći u skladu sa precizno kvantifikovanom stopom kojom do toga dolazi. Teoremu su nezavisno dokazali Žak Adamar i Šarl Žan de la Vale-Pusen 1896. godine, koristeći ideje koje je uveo Bernhard Riman (naročito Rimanovu zeta funkciju).

Prva takva raspodela je π(N) ~ N/log(N), gde je π(N) funkcija raspodele prostih brojeva i log(N) je prirodni logaritam od N. To znači da za dovoljno veliko N, verovatnoća da je slučajni celi broj koji nije veći od N prost broj vrlo blizu 1 / log(N). Sledstveno tome, za slučajni celi broj sa najviše 2n cifara (za dovoljno veliko n) postoji aproksimativno upola manja verovatnoća da će on biti prost broj kao slučajni celi broj sa najviše n cifara. Na primer, među pozitivnim celim brojevima od najviše 1000 cifara, jedan od 2300 je prost broj (log(101000) ≈ 2302,6), dok je među pozitivnim celim brojevima sa najviše 2000 cifara, približno jedan od 4600 prost broj (log(102000) ≈ 4605,2). Drugim rečima, prosečni razmak između uzastopnih prostih brojeva među prvih N celih brojevima je oko log(N).[1]

IskazУреди

 
Grafikon koji prikazuje odnos funkcije raspodele prostih brojeva π(x) i dve njene aproksimacije, x / log x i Li(x). Kako se x povećava (napomena: x osa je logaritamska), oba se odnosa kreću prema 1. Odnos za x / log x konvergira odozgo vrlo sporo, dok odnos za Li(x) brže konvergira odozdo.
 
Log-log grafikon prikazuje apsolutnu grešku od x / log x i Li(x), dve aproksimacije funkcije raspodele prostih brojeva π(x). Za razliku od odnosa, razlika između π(x) i x / log x se povećava bez ograničenja kako se x povećava. S druge strane, Li(x) − π(x) manja znak beskonačno mnogo puta.

Neka je π(x) funkcija raspodele prostih brojeva koja daje broj prostih brojeva manji ili jednak sa x, za svaki realni broj x. Na primer, π(10) = 4, jer postoje četiri prosta broja (2, 3, 5 i 7) manja ili jednaka od 10. Prema teoremi prostih brojeva tada je x / log x dobra aproksimacija za π(x) (gde log značava prirodni logaritam), u smislu da je limit količnika dve funkcije π(x) i x / log x kako se x povećava bez ograničenja jednak 1:

 

Ovo je poznato kao asimptotski zakon distribucije prostih brojeva. Koristeći asimptotsku notaciju ovaj rezultat se može napisati kao

 

Ova notacija (i teorema) ne govori o limitu razlike dve funkcije kad se x povećava bez ograničenja. Umesto toga, teorema navodi da x / log x aproksimira π(x) u smislu da se relativna greška ove aproksimacije približava 0, kada se x povećava bez ograničenja.

Teorema prostih brojeva je ekvivalentna tvrđenju da n-ti prosti broj pn zadovoljava

 

asimptotska notacija ponovo ukazuje na to da relativna greška ove aproksimacije pristupa 0 kad se n povećava bez ograničenja. Na primer, 2×1017-ti prosti broj je 8,512,677,386,048,191,063,[2] i (2×1017)log(2×1017) zaokružuje se na 7,967,418,752,291,744,388, sa relativnom greškom od oko 6,4%.

Teorema prostih brojeva je isto tako ekvivalentna sa

 

gde su ϑ i ψ prva i druga Čebiševa funkcija, respektivno.

Tabela π(x), x / log x, and li(x)Уреди

U ovoj tabeli su upoređene vrednosti π(x) sa dve aproksimacije x / log x i li(x). Zadnja kolna, x / π(x), je prosek razmaka između prostih brojeva ispod x.

x π(x) π(x) − x/log x π(x)/x / log x li(x) − π(x) x/π(x)
10 4 −0.3 0.921 2.2 2.500
102 25 3.3 1.151 5.1 4.000
103 168 23.0 1.161 10.0 5.952
104 1,229 143.0 1.132 17.0 8.137
105 9,592 906.0 1.104 38.0 10.425
106 78,498 6,116.0 1.084 130.0 12.740
107 664,579 44,158.0 1.071 339.0 15.047
108 5,761,455 332,774.0 1.061 754.0 17.357
109 50,847,534 2,592,592.0 1.054 1,701.0 19.667
1010 455,052,511 20,758,029.0 1.048 3,104.0 21.975
1011 4,118,054,813 169,923,159.0 1.043 11,588.0 24.283
1012 37,607,912,018 1,416,705,193.0 1.039 38,263.0 26.590
1013 346,065,536,839 11,992,858,452.0 1.034 108,971.0 28.896
1014 3,204,941,750,802 102,838,308,636.0 1.033 314,890.0 31.202
1015 29,844,570,422,669 891,604,962,452.0 1.031 1,052,619.0 33.507
1016 279,238,341,033,925 7,804,289,844,393.0 1.029 3,214,632.0 35.812
1017 2,623,557,157,654,233 68,883,734,693,281.0 1.027 7,956,589.0 38.116
1018 24,739,954,287,740,860 612,483,070,893,536.0 1.025 21,949,555.0 40.420
1019 234,057,667,276,344,607 5,481,624,169,369,960.0 1.024 99,877,775.0 42.725
1020 2,220,819,602,560,918,840 49,347,193,044,659,701.0 1.023 222,744,644.0 45.028
1021 21,127,269,486,018,731,928 446,579,871,578,168,707.0 1.022 597,394,254.0 47.332
1022 201,467,286,689,315,906,290 4,060,704,006,019,620,994.0 1.021 1,932,355,208.0 49.636
1023 1,925,320,391,606,803,968,923 37,083,513,766,578,631,309.0 1.020 7,250,186,216.0 51.939
1024 18,435,599,767,349,200,867,866 339,996,354,713,708,049,069.0 1.019 17,146,907,278.0 54.243
1025 176,846,309,399,143,769,411,680 3,128,516,637,843,038,351,228.0 1.018 55,160,980,939.0 56.546
OEIS A006880 A057835 A057752

Vrednost za π(1024) bila je originalno izračunata koristeći Rimanovu hipotezu.[3] Od tada su bezuslovno verifikovane.[4]

Analog za nesvodljive polinome na konačnom poljuУреди

Postoji analogna teorema prostih brojeva koja opisuje „raspodelu” nesažimljivih polinoma preko konačnog polja; njen oblik je upadljivo sličan sa klasičnom teoremom prostih brojeva.

Da bi se to precizno izrazilo, može se uzeti da je F = GF(q) konačno polje sa q elemenata, za neko fiksno q, i da je Nn broj monijskih nesažimljivih polinoma preko F čiji je stepen jednak n. To jest, razmatraju se polinomi sa koeficijentima odabranim iz F, koji se ne mogu zapisati kao proizvodi polinoma nižeg stepena. U ovom okruženju, ti polinomi igraju ulogu prostih brojeva, jer su svi drugi monijski polinomi izgrađeni od njihovih proizvoda. Onda se može dokazati da je

 

Ako se uradi supstitucija x = qn, onda je desna strana samo

 

čime se pojašnjava analogija. Kako postoji tačno qn monijskih polinoma stepena n (uključujući one koji su sažimljivi), to se može preformulirati na sledeći način: ako je monijski polinom stepena n randomno izabran, onda je verovatnoća da je on nesažimljiv oko 1/n.

Moguće je dokazati i analognu verziju Rimanove hipoteze, naime da je

 

Dokazi ovih tvrdnji daleko su jednostavniji nego u klasičnom slučaju. To obuhvata kratako kombinatorično razmatranje,[5] sumirano na sledeći način: svaki element stepena n proširenja F je koren nekog nesažimljivog polinoma čiji stepen d deli n; pri prebrojavanu ovih korena su uspostavljena dva različita pristupa

 

gde suma obuhvata sve dilioce d od n. Mebijusova inverzija onda daje

 

gde je μ(k) Mebijusova funkcija. (Ova formula je bila poznata Gausu.) Glavni član se javlja za d = n, i nije teško vezati preostale članove. Izraz „Rimanove hipoteze” zavisi od činjenice da najveći svojstveni dililac od n ne može da bude veći od n/2.

ReferenceУреди

  1. ^ Hoffman, Paul (1998). The Man Who Loved Only Numbers . New York: Hyperion Books. стр. 227. ISBN 978-0-7868-8406-3. MR 1666054. 
  2. ^ „Prime Curios!: 8512677386048191063”. Prime Curios!. University of Tennessee at Martin. 9. 10. 2011. 
  3. ^ „Conditional Calculation of π(1024). Chris K. Caldwell. Приступљено 3. 8. 2010. 
  4. ^ Platt, David (2015). „Computing π(x) analytically”. Mathematics of Computation. 84 (293): 1521—1535. MR 3315519. arXiv:1203.5712 . doi:10.1090/S0025-5718-2014-02884-6. 
  5. ^ Chebolu, Sunil; Mináč, Ján (decembar 2011). „Counting Irreducible Polynomials over Finite Fields Using the Inclusion π Exclusion Principle”. Mathematics Magazine. 84 (5): 369—371. JSTOR 10.4169/math.mag.84.5.369. arXiv:1001.0409 . doi:10.4169/math.mag.84.5.369. 

LiteraturaУреди

Spoljašnje vezeУреди