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(10¹⁰⁰⁰) ≈ 2302,6), dok je među pozitivnim celim brojevima sa najviše 2000 cifara, približno jedan od 4600 prost broj (log(10²⁰⁰⁰) ≈ 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

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:

${\displaystyle \lim _{x\to \infty }{\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

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

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 p_n zadovoljava

${\displaystyle p_{n}\sim n\log(n),}$

asimptotska notacija ponovo ukazuje na to da relativna greška ove aproksimacije pristupa 0 kad se n povećava bez ograničenja. Na primer, 7017200000000000000♠2×10¹⁷-ti prosti broj je 7018851267738604819♠8512677386048191063,^[2] i (7017200000000000000♠2×10¹⁷)log(7017200000000000000♠2×10¹⁷) zaokružuje se na 7018796741875229174♠7967418752291744388, sa relativnom greškom od oko 6,4%.

Teorema prostih brojeva je isto tako ekvivalentna sa

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

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	7003122900000000000♠1229	143.0	1.132	17.0	8.137
105	7003959200000000000♠9592	906.0	1.104	38.0	10.425
106	7004784980000000000♠78498	7003611600000000000♠6116.0	1.084	130.0	12.740
107	7005664579000000000♠664579	7004441580000000000♠44158.0	1.071	339.0	15.047
108	7006576145500000000♠5761455	7005332774000000000♠332774.0	1.061	754.0	17.357
109	7007508475340000000♠50847534	7006259259200000000♠2592592.0	1.054	7003170100000000000♠1701.0	19.667
1010	7008455052511000000♠455052511	7007207580290000000♠20758029.0	1.048	7003310400000000000♠3104.0	21.975
1011	7009411805481300000♠4118054813	7008169923159000000♠169923159.0	1.043	7004115880000000000♠11588.0	24.283
1012	7010376079120180000♠37607912018	7009141670519300000♠1416705193.0	1.039	7004382630000000000♠38263.0	26.590
1013	7011346065536839000♠346065536839	7010119928584520000♠11992858452.0	1.034	7005108971000000000♠108971.0	28.896
1014	7012320494175080200♠3204941750802	7011102838308636000♠102838308636.0	1.033	7005314890000000000♠314890.0	31.202
1015	7013298445704226690♠29844570422669	7011891604962452000♠891604962452.0	1.031	7006105261900000000♠1052619.0	33.507
1016	7014279238341033925♠279238341033925	7012780428984439300♠7804289844393.0	1.029	7006321463200000000♠3214632.0	35.812
1017	7015262355715765423♠2623557157654233	7013688837346932810♠68883734693281.0	1.027	7006795658900000000♠7956589.0	38.116
1018	7016247399542877408♠24739954287740860	7014612483070893536♠612483070893536.0	1.025	7007219495550000000♠21949555.0	40.420
1019	7017234057667276344♠234057667276344607	7015548162416936996♠5481624169369960.0	1.024	7007998777750000000♠99877775.0	42.725
1020	7018222081960256091♠2220819602560918840	7016493471930446597♠49347193044659701.0	1.023	7008222744644000000♠222744644.0	45.028
1021	7019211272694860187♠21127269486018731928	7017446579871578168♠446579871578168707.0	1.022	7008597394254000000♠597394254.0	47.332
1022	7020201467286689315♠201467286689315906290	7018406070400601962♠4060704006019620994.0	1.021	7009193235520800000♠1932355208.0	49.636
1023	7021192532039160680♠1925320391606803968923	7019370835137665786♠37083513766578631309.0	1.020	7009725018621600000♠7250186216.0	51.939
1024	7022184355997673492♠18435599767349200867866	7020339996354713708♠339996354713708049069.0	1.019	7010171469072780000♠17146907278.0	54.243
1025	7023176846309399143♠176846309399143769411680	7021312851663784303♠3128516637843038351228.0	1.018	7010551609809390000♠55160980939.0	56.546
OEIS	A006880	A057835		A057752

Vrednost za π(10²⁴) 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 N_n 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

${\displaystyle N_{n}\sim {\frac {q^{n}}{n}}.}$

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

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

čime se pojašnjava analogija. Kako postoji tačno qⁿ 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

${\displaystyle 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,^[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

${\displaystyle q^{n}=\sum _{d\mid n}dN_{d},}$

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

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

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

Literatura

Spoljašnje veze