Teorema prostih brojeva

U teoriji brojeva, teorema prostih brojeva (Шаблон:Jez-eng-lat, -{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 Шаблон:Math, gde je Шаблон:Math funkcija raspodele prostih brojeva i Шаблон:Math je prirodni logaritam od Шаблон:Mvar. To znači da za dovoljno veliko Шаблон:Mvar, verovatnoća da je slučajni celi broj koji nije veći od Шаблон:Mvar prost broj vrlo blizu Шаблон:Math. Sledstveno tome, za slučajni celi broj sa najviše Шаблон:Math cifara (za dovoljno veliko Шаблон:Mvar) postoji približno upola manja verovatnoća da će on biti prost broj kao slučajni celi broj sa najviše Шаблон:Mvar cifara. Na primer, među pozitivnim celim brojevima od najviše 1000 cifara, jedan od 2300 je prost broj (Шаблон:Math), dok je među pozitivnim celim brojevima sa najviše 2000 cifara, približno jedan od 4600 prost broj (Шаблон:Math). Drugim rečima, prosečni razmak između uzastopnih prostih brojeva među prvih Шаблон:Mvar celih brojevima je oko Шаблон:Math.

Iskaz

Grafikon koji prikazuje odnos funkcije raspodele prostih brojeva Шаблон:Math i dve njene aproksimacije, Шаблон:Math i Шаблон:Math. Kako se Шаблон:Mvar povećava (napomena: Шаблон:Mvar osa je logaritamska), oba se odnosa kreću prema 1. Odnos za Шаблон:Math konvergira odozgo vrlo sporo, dok odnos za Шаблон:Math brže konvergira odozdo.

Log-log grafikon prikazuje apsolutnu grešku od Шаблон:Math i Шаблон:Math, dve aproksimacije funkcije raspodele prostih brojeva Шаблон:Math. Za razliku od odnosa, razlika između Шаблон:Math i Шаблон:Math se povećava bez ograničenja kako se Шаблон:Mvar povećava. S druge strane, Шаблон:Math manja znak beskonačno mnogo puta.

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

$\underset{x\to \mathrm{\infty }}{\lim }\frac{\pi (x)}{\left[\frac{x}{\log (x)}\right]}=1,$

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

$\pi (x)\sim \frac{x}{\log x}.$

Ova notacija (i teorema) ne govori o limitu razlike dve funkcije kad se Шаблон:Mvar povećava bez ograničenja. Umesto toga, teorema navodi da Шаблон:Math aproksimira Шаблон:Math u smislu da se relativna greška ove aproksimacije približava 0, kada se Шаблон:Mvar povećava bez ograničenja.

Teorema prostih brojeva je ekvivalentna tvrđenju da Шаблон:Mvar-ti prosti broj Шаблон:Mvar zadovoljava

$p_n\sim n\log (n),$

asimptotska notacija ponovo ukazuje na to da relativna greška ove aproksimacije pristupa 0 kad se Шаблон:Mvar povećava bez ograničenja. Na primer, Шаблон:Val-ti prosti broj je Шаблон:Val, i (Шаблон:Val)log(Шаблон:Val) zaokružuje se na Шаблон:Val, sa relativnom greškom od oko 6,4%.

Teorema prostih brojeva je isto tako ekvivalentna sa

$\underset{x\to \mathrm{\infty }}{\lim }\frac{\vartheta (x)}{x}=\underset{x\to \mathrm{\infty }}{\lim }\frac{\psi (x)}{x}=1,$

gde su Шаблон:Mvar i Шаблон:Mvar prva i druga Čebiševa funkcija, respektivno.

Tabela Шаблон:Math, Шаблон:Math, and Шаблон:Math

U ovoj tabeli su upoređene vrednosti Шаблон:Math sa dve aproksimacije Шаблон:Math i Шаблон:Math. Zadnja kolna, Шаблон:Math, je prosek razmaka između prostih brojeva ispod Шаблон:Mvar.

Шаблон:Mvar	Шаблон:Math	Шаблон:Math	Шаблон:Math	Шаблон:Math	Шаблон:Math
10	4	−0.3	0.921	2.2	2.5Шаблон:0
102	25	3.3	1.151	5.1	4Шаблон:0
103	168	23Шаблон:0	1.161	10Шаблон:0	5.952
104	Шаблон:Val	143Шаблон:0	1.132	17Шаблон:0	8.137
105	Шаблон:Val	906Шаблон:0	1.104	38Шаблон:0	10.425
106	Шаблон:Val	Шаблон:ValШаблон:0	1.084	130Шаблон:0	12.740
107	Шаблон:Val	Шаблон:ValШаблон:0	1.071	339Шаблон:0	15.047
108	Шаблон:Val	Шаблон:ValШаблон:0	1.061	754Шаблон:0	17.357
109	Шаблон:Val	Шаблон:ValШаблон:0	1.054	Шаблон:ValШаблон:0	19.667
1010	Шаблон:Val	Шаблон:ValШаблон:0	1.048	Шаблон:ValШаблон:0	21.975
1011	Шаблон:Val	Шаблон:ValШаблон:0	1.043	Шаблон:ValШаблон:0	24.283
1012	Шаблон:Val	Шаблон:ValШаблон:0	1.039	Шаблон:ValШаблон:0	26.590
1013	Шаблон:Val	Шаблон:ValШаблон:0	1.034	Шаблон:ValШаблон:0	28.896
1014	Шаблон:Val	Шаблон:ValШаблон:0	1.033	Шаблон:ValШаблон:0	31.202
1015	Шаблон:Val	Шаблон:ValШаблон:0	1.031	Шаблон:ValШаблон:0	33.507
1016	Шаблон:Val	Шаблон:ValШаблон:0	1.029	Шаблон:ValШаблон:0	35.812
1017	Шаблон:Val	Шаблон:ValШаблон:0	1.027	Шаблон:ValШаблон:0	38.116
1018	Шаблон:Val	Шаблон:ValШаблон:0	1.025	Шаблон:ValШаблон:0	40.420
1019	Шаблон:Val	Шаблон:ValШаблон:0	1.024	Шаблон:ValШаблон:0	42.725
1020	Шаблон:Val	Шаблон:ValШаблон:0	1.023	Шаблон:ValШаблон:0	45.028
1021	Шаблон:Val	Шаблон:ValШаблон:0	1.022	Шаблон:ValШаблон:0	47.332
1022	Шаблон:Val	Шаблон:ValШаблон:0	1.021	Шаблон:ValШаблон:0	49.636
1023	Шаблон:Val	Шаблон:ValШаблон:0	1.020	Шаблон:ValШаблон:0	51.939
1024	Шаблон:Val	Шаблон:ValШаблон:0	1.019	Шаблон:ValШаблон:0	54.243
1025	Шаблон:Val	Шаблон:ValШаблон:0	1.018	Шаблон:ValШаблон:0	56.546
OEIS	Шаблон:OEIS link	Шаблон:OEIS link		Шаблон:OEIS link

Vrednost za Шаблон:Math 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 Шаблон:Math konačno polje sa Шаблон:Mvar elemenata, za neko fiksno Шаблон:Mvar, i da je Шаблон:Mvar broj monijskih nesažimljivih polinoma preko Шаблон:Mvar čiji je stepen jednak Шаблон:Mvar. To jest, razmatraju se polinomi sa koeficijentima odabranim iz Шаблон:Mvar, 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

$N_n\sim \frac{q^n}{n}.$

Ako se uradi supstitucija Шаблон:Math, onda je desna strana samo

$\frac{x}{{\log }_{q}x},$

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

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

$N_n=\frac{q^n}{n}+O\left(\frac{q^{\frac{n}{2}}}{n}\right).$

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 Шаблон:Mvar proširenja Шаблон:Mvar je koren nekog nesažimljivog polinoma čiji stepen Шаблон:Mvar deli Шаблон:Mvar; pri prebrojavanu ovih korena su uspostavljena dva različita pristupa

$q^n=\sum _{d\mid n}d{N}_d,$

gde suma obuhvata sve dilioce Шаблон:Mvar od Шаблон:Mvar. Mebijusova inverzija onda daje

$N_n=\frac{1}{n}\sum _{d\mid n}\mu \left(\frac{n}{d}\right)q^d,$

gde je Шаблон:Math Mebijusova funkcija. (Ova formula je bila poznata Gausu.) Glavni član se javlja za Шаблон:Math, i nije teško vezati preostale članove. Izraz „Rimanove hipoteze” zavisi od činjenice da najveći svojstveni dililac od Шаблон:Mvar ne može da bude veći od Шаблон:Math.

Literatura

• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Citation
• Шаблон:Citation. Reprinted 1990, Шаблон:Isbn, Шаблон:MathSciNet
• Шаблон:Citation
• Шаблон:Citation.

Spoljašnje veze

• Шаблон:Springer
• -{Table of Primes by Anton Felkel}-.
• -{Short video visualizing the Prime Number Theorem.}-
• -{Prime formulas and Prime number theorem at MathWorld.}-
• Шаблон:Planetmath reference
• -{How Many Primes Are There?Шаблон:Wayback and The Gaps between Primes by Chris Caldwell, University of Tennessee at Martin.}-
• -{Tables of prime-counting functions by Tomás Oliveira e Silva}-