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) ~ .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}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 $2 n$ 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 1000) \approx 2302,6$ ), dok je među pozitivnim celim brojevima sa najviše 2000 cifara, približno jedan od 4600 prost broj ( $log(10 2000) \approx 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:

\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

\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

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

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

Vrednost za $π (10 24)$ 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

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

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

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

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

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

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

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

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

^ Hoffman, Paul (1998). The Man Who Loved Only Numbers . New York: Hyperion Books. стр. 227. ISBN 978-0-7868-8406-3. MR 1666054.
^ „Prime Curios!: 8512677386048191063”. Prime Curios!. University of Tennessee at Martin. 9. 10. 2011.
^ „Conditional Calculation of $π (10 24)$ ”. Chris K. Caldwell. Архивирано из оригинала 25. 09. 2014. г. Приступљено 3. 8. 2010.
^ 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.
^ 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

Hardy, G. H.; Littlewood, J. E. (1916). „Contributions to the Theory of the Riemann Zeta-Function and the Theory of the Distribution of Primes” (PDF). Acta Mathematica. 41: 119—196. doi:10.1007/BF02422942.
Granville, Andrew (1995). „Harald Cramér and the distribution of prime numbers” (PDF). Scandinavian Actuarial Journal. 1: 12—28. CiteSeerX 10.1.1.129.6847  . doi:10.1080/03461238.1995.10413946. Архивирано из оригинала (PDF) 23. 09. 2015. г. Приступљено 18. 02. 2020.
Burris, Stanley N. (2001). Number theoretic density and logical limit laws. Mathematical Surveys and Monographs. 86. Providence, RI: American Mathematical Society. ISBN 0-8218-2666-2. Zbl 0995.11001.
Knopfmacher, John (1990) [1975]. Abstract Analytic Number Theory (2nd изд.). New York, NY: Dover Publishing. ISBN 0-486-66344-2. Zbl 0743.11002.
Montgomery, Hugh L.; Vaughan, Robert C. (2007). Multiplicative number theory I. Classical theory. Cambridge studies in advanced mathematics. 97. стр. 278. ISBN 0-521-84903-9. Zbl 1142.11001.
Alina Carmen Cojocaru; M. Ram Murty. An introduction to sieve methods and their applications. London Mathematical Society Student Texts. 66. Cambridge University Press. стр. 35—38. ISBN 0-521-61275-6.
Landau, Edmund (1903). „Neuer Beweis des Primzahlsatzes und Beweis des Primidealsatzes”. Mathematische Annalen. 56 (4): 645—670. doi:10.1007/BF01444310.
Dudek, Adrian W. (21. 8. 2014), „On the Riemann hypothesis and the difference between primes”, International Journal of Number Theory, 11 (3): 771—778, Bibcode:2014arXiv1402.6417D, ISSN 1793-0421, arXiv:1402.6417  , doi:10.1142/S1793042115500426
Ingham, A.E. (1932), The Distribution of Prime Numbers, Cambridge Tracts in Mathematics and Mathematical Physics, 30, Cambridge University Press . Reprinted 1990, ISBN 978-0-521-39789-6, MR 1074573
Mazur, Barry; Stein, William (2015), Prime Numbers and the Riemann Hypothesis
Nicely, Thomas R. (1999), „New maximal prime gaps and first occurrences”, Mathematics of Computation, 68 (227): 1311—1315, Bibcode:1999MaCom..68.1311N, MR 1627813, doi:10.1090/S0025-5718-99-01065-0, Архивирано из оригинала 30. 12. 2014. г., Приступљено 18. 2. 2020 .

Spoljašnje veze

Hazewinkel Michiel, ур. (2001). „Distribution of prime numbers”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104.
Table of Primes by Anton Felkel.
Short video visualizing the Prime Number Theorem.
Prime formulas and Prime number theorem at MathWorld.
„Prime number theorem”. PlanetMath.
How Many Primes Are There?Архивирано на сајту Wayback Machine (15. октобар 2012) and The Gaps between Primes by Chris Caldwell, University of Tennessee at Martin.
Tables of prime-counting functions by Tomás Oliveira e Silva

[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.

[Franke-3] „Conditional Calculation of $π (10 24)$ ”. Chris K. Caldwell. Архивирано из оригинала 25. 09. 2014. г. Приступљено 3. 8. 2010.

[PlattARXIV2012-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.

[1]

[2]

[3]

[4]

[5]