U teoriji brojeva, teorema prostih brojeva (, -{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 , gde je funkcija raspodele prostih brojeva i je prirodni logaritam od . To znači da za dovoljno veliko , verovatnoća da je slučajni celi broj koji nije veći od prost broj vrlo blizu . Sledstveno tome, za slučajni celi broj sa najviše cifara (za dovoljno veliko ) postoji približno upola manja verovatnoća da će on biti prost broj kao slučajni celi broj sa najviše cifara. Na primer, među pozitivnim celim brojevima od najviše 1000 cifara, jedan od 2300 je prost broj (), dok je među pozitivnim celim brojevima sa najviše 2000 cifara, približno jedan od 4600 prost broj (). Drugim rečima, prosečni razmak između uzastopnih prostih brojeva među prvih celih brojevima je oko .
Iskaz thumb|300px|Grafikon koji prikazuje odnos funkcije raspodele prostih brojeva i dve njene aproksimacije, i . Kako se povećava (napomena: osa je logaritamska), oba se odnosa kreću prema 1. Odnos za konvergira odozgo vrlo sporo, dok odnos za brže konvergira odozdo. thumb|300px|Log-log grafikon prikazuje apsolutnu grešku od i , dve aproksimacije funkcije raspodele prostih brojeva . Za razliku od odnosa, razlika između i se povećava bez ograničenja kako se povećava. S druge strane, manja znak beskonačno mnogo puta.
Neka je funkcija raspodele prostih brojeva koja daje broj prostih brojeva manji ili jednak sa , za svaki realni broj . Na primer, , jer postoje četiri prosta broja (2, 3, 5 i 7) manja ili jednaka od 10. Prema teoremi prostih brojeva tada je dobra aproksimacija za (gde log značava prirodni logaritam), u smislu da je limit količnika dve funkcije i kako se 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 povećava bez ograničenja. Umesto toga, teorema navodi da aproksimira u smislu da se relativna greška ove aproksimacije približava 0, kada se povećava bez ograničenja.
Teorema prostih brojeva je ekvivalentna tvrđenju da -ti prosti broj zadovoljava
asimptotska notacija ponovo ukazuje na to da relativna greška ove aproksimacije pristupa 0 kad se povećava bez ograničenja. Na primer, -ti prosti broj je , i ()log() zaokružuje se na , 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 , , and
U ovoj tabeli su upoređene vrednosti sa dve aproksimacije i . Zadnja kolna, , je prosek razmaka između prostih brojeva ispod . {| class="wikitable" style="text-align: right" ! ! ! ! ! ! |- | 10 | 4 | −0.3 | 0.921 | 2.2 | 2.5 |- | 102 | 25 | 3.3 | 1.151 | 5.1 | 4 |- | 103 | 168 | 23 | 1.161 | 10 | 5.952 |- | 104 | | 143 | 1.132 | 17 | 8.137 |- | 105 | | 906 | 1.104 | 38 | 10.425 |- | 106
| 1.084 | 130 | 12.740 |- | 107
| 1.071 | 339 | 15.047 |- | 108
| 1.061 | 754 | 17.357 |- | 109
| 1.054 | | 19.667 |- | 1010
| 1.048 | | 21.975 |- | 1011
| 1.043 | | 24.283 |- | 1012
| 1.039 | | 26.590 |- | 1013
| 1.034 | | 28.896 |- | 1014
| 1.033 | | 31.202 |- | 1015
| 1.031 | | 33.507 |- | 1016
| 1.029 | | 35.812 |- | 1017
| 1.027 | | 38.116 |- | 1018
| 1.025 | | 40.420 |- | 1019
| 1.024 | | 42.725 |- | 1020
| 1.023 | | 45.028 |- | 1021
| 1.022 | | 47.332 |- | 1022
| 1.021 | | 49.636 |- | 1023
| 1.020 | | 51.939 |- | 1024
| 1.019 | | 54.243 |- | 1025
| 1.018 | | 56.546 |- | OEIS
Vrednost za bila je originalno izračunata koristeći Rimanovu hipotezu. Od tada su bezuslovno verifikovane.
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 konačno polje sa elemenata, za neko fiksno , i da je broj monijskih nesažimljivih polinoma preko čiji je stepen jednak . To jest, razmatraju se polinomi sa koeficijentima odabranim iz , 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 , onda je desna strana samo
čime se pojašnjava analogija. Kako postoji tačno monijskih polinoma stepena (uključujući one koji su sažimljivi), to se može preformulirati na sledeći način: ako je monijski polinom stepena randomno izabran, onda je verovatnoća da je on nesažimljiv oko .
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, sumirano na sledeći način: svaki element stepena proširenja je koren nekog nesažimljivog polinoma čiji stepen deli ; pri prebrojavanu ovih korena su uspostavljena dva različita pristupa
gde suma obuhvata sve dilioce od . Mebijusova inverzija onda daje
gde je Mebijusova funkcija. (Ova formula je bila poznata Gausu.) Glavni član se javlja za , i nije teško vezati preostale članove. Izraz „Rimanove hipoteze” zavisi od činjenice da najveći svojstveni dililac od ne može da bude veći od .
Reference
Literatura
. Reprinted 1990, ,
Spoljašnje veze
-{Table of Primes by Anton Felkel}-. -{Short video visualizing the Prime Number Theorem.}- -{Prime formulas and Prime number theorem at MathWorld.}-
-{How Many Primes Are There? and The Gaps between Primes by Chris Caldwell, University of Tennessee at Martin.}- -{Tables of prime-counting functions by Tomás Oliveira e Silva}-
Категорија:Аналитичка теорија бројева Категорија:Логаритми