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 približno 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 8512677386048191063,[2] i (2×1017)log(2×1017) zaokružuje se na 7967418752291744388, 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 1229 143.0 1.132 17.0 8.137
105 9592 906.0 1.104 38.0 10.425
106 78498 6116.0 1.084 130.0 12.740
107 664579 44158.0 1.071 339.0 15.047
108 5761455 332774.0 1.061 754.0 17.357
109 50847534 2592592.0 1.054 1701.0 19.667
1010 455052511 20758029.0 1.048 3104.0 21.975
1011 4118054813 169923159.0 1.043 11588.0 24.283
1012 37607912018 1416705193.0 1.039 38263.0 26.590
1013 346065536839 11992858452.0 1.034 108971.0 28.896
1014 3204941750802 102838308636.0 1.033 314890.0 31.202
1015 29844570422669 891604962452.0 1.031 1052619.0 33.507
1016 279238341033925 7804289844393.0 1.029 3214632.0 35.812
1017 2623557157654233 68883734693281.0 1.027 7956589.0 38.116
1018 24739954287740860 612483070893536.0 1.025 21949555.0 40.420
1019 234057667276344607 5481624169369960.0 1.024 99877775.0 42.725
1020 2220819602560918840 49347193044659701.0 1.023 222744644.0 45.028
1021 21127269486018731928 446579871578168707.0 1.022 597394254.0 47.332
1022 201467286689315906290 4060704006019620994.0 1.021 1932355208.0 49.636
1023 1925320391606803968923 37083513766578631309.0 1.020 7250186216.0 51.939
1024 18435599767349200867866 339996354713708049069.0 1.019 17146907278.0 54.243
1025 176846309399143769411680 3128516637843038351228.0 1.018 55160980939.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. Архивирано из оригинала 25. 09. 2014. г. Приступљено 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