Teorema prostih brojeva — разлика између измена

Садржај обрисан Садржај додат

Инлајн

Верзија на датум 18. фебруар 2020. у 06:31

U teoriji brojeva, teorema prostih brojeva (engl. prime number theorem, PNT) opisuje asimptotsku distribuciju prostih brojeva među positivnim celim brojevima. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896 using ideas introduced by Bernhard Riemann (in particular, the Riemann zeta function).

The first such distribution found is $π(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)$ , where $π (N)$ is the prime-counting function and $log(N)$ is the natural logarithm of $N$ . This means that for large enough $N$ , the probability that a random integer not greater than $N$ is prime is very close to $1 / log(N)$ . Consequently, a random integer with at most $2 n$ digits (for large enough $n$ ) is about half as likely to be prime as a random integer with at most $n$ digits. For example, among the positive integers of at most 1000 digits, about one in 2300 is prime ( $log(10 1000) \approx 2302.6$ ), whereas among positive integers of at most 2000 digits, about one in 4600 is prime ( $log(10 2000) \approx 4605.2$ ). In other words, the average gap between consecutive prime numbers among the first $N$ integers is roughly $log(N)$ .^[1]

Iskaz

Neka je $π (x)$ funkcija brojanja 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

There is an analogue of the prime number theorem that describes the "distribution" of irreducible polynomials over a finite field; the form it takes is strikingly similar to the case of the classical prime number theorem.

To state it precisely, let $F = GF(q)$ be the finite field with $q$ elements, for some fixed $q$ , and let $N n$ be the number of monic irreducible polynomials over $F$ whose degree is equal to $n$ . That is, we are looking at polynomials with coefficients chosen from $F$ , which cannot be written as products of polynomials of smaller degree. In this setting, these polynomials play the role of the prime numbers, since all other monic polynomials are built up of products of them. One can then prove that

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

If we make the substitution $x = q n$ , then the right hand side is just

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

which makes the analogy clearer. Since there are precisely $q n$ monic polynomials of degree $n$ (including the reducible ones), this can be rephrased as follows: if a monic polynomial of degree $n$ is selected randomly, then the probability of it being irreducible is about $1 / n$ .

One can even prove an analogue of the Riemann hypothesis, namely that

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

The proofs of these statements are far simpler than in the classical case. It involves a short combinatorial argument,^[5] summarised as follows: every element of the degree $n$ extension of $F$ is a root of some irreducible polynomial whose degree $d$ divides $n$ ; by counting these roots in two different ways one establishes that

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

where the sum is over all divisors $d$ of $n$ . Möbius inversion then yields

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

where $μ (k)$ is the Möbius function. (This formula was known to Gauss.) The main term occurs for $d = n$ , and it is not difficult to bound the remaining terms. The "Riemann hypothesis" statement depends on the fact that the largest proper divisor of $n$ can be no larger than $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. 2011-10-09.
^ „Conditional Calculation of $π (10 24)$ ”. Chris K. Caldwell. Приступљено 2010-08-03.
^ 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 (децембар 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.
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. (2014-08-21), „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 .

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? 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. 2011-10-09.

[Franke-3] „Conditional Calculation of $π (10 24)$ ”. Chris K. Caldwell. Приступљено 2010-08-03.

[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 (децембар 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]

@@ Ред 6: / Ред 6: @@
 == Iskaz ==
-[[File:Prime number theorem ratio convergence.svg|thumb|300px|Graph showing ratio of the prime-counting function {{math|''π''(''x'')}} to two of its approximations, {{math|''x'' / log ''x''}} and {{math|Li(''x'')}}. As {{mvar|x}} increases (note {{mvar|x}} axis is logarithmic), both ratios tend towards 1. The ratio for {{math|''x'' / log ''x''}} converges from above very slowly, while the ratio for {{math|Li(''x'')}} converges more quickly from below.]]
+[[File:Prime number theorem ratio convergence.svg|thumb|300px|Grafikon koji prikazuje odnos funkcije brojanja prostih brojeva {{math|''π''(''x'')}} i dve njene aproksimacije, {{math|''x'' / log ''x''}} i {{math|Li(''x'')}}. Kako se {{mvar|x}} povećava (napomena: {{mvar|x}} osa je logaritamska), oba se odnosa kreću prema 1. Odnos za {{math|''x'' / log ''x''}} konvergira odozgo vrlo sporo, dok odnos za  {{math|Li(''x'')}} brže konvergira odozdo.]]
-[[File:Prime number theorem absolute error.svg|thumb|300px|Log-log plot showing absolute error of {{math|''x'' / log ''x''}} and {{math|Li(''x'')}}, two approximations to the prime-counting function {{math|''π''(''x'')}}. Unlike the ratio, the difference between {{math|''π''(''x'')}} and {{math|''x'' / log ''x''}} increases without bound as {{mvar|x}} increases. On the other hand, {{math|Li(''x'') − ''π''(''x'')}} switches sign infinitely many times.]]
+[[File:Prime number theorem absolute error.svg|thumb|300px|Log-log grafikon prikazuje apsolutnu grešku od {{math|''x'' / log ''x''}} i {{math|Li(''x'')}}, dve aproksimacije funkciji brojanja prostih brojeva {{math|''π''(''x'')}}. Za razliku od odnosa, razlika između {{math|''π''(''x'')}} i {{math|''x'' / log ''x''}} se povećava bez ograničenja kako se {{mvar|x}} povećava. S druge strane, {{math|Li(''x'') − ''π''(''x'')}} manja znak beskonačno mnogo puta.]]
-Let {{math|''π''(''x'')}} be the [[prime-counting function]] that gives the number of primes less than or equal to {{mvar|x}}, for any real number&nbsp;{{mvar|x}}. For example, {{math|''π''(10) {{=}} 4}} because there are four prime numbers (2, 3, 5 and 7) less than or equal to 10. The prime number theorem then states that {{math|''x'' / log ''x''}} is a good approximation to {{math|''π''(''x'')}} (where log here means the natural logarithm), in the sense that the [[limit of a function|limit]] of the ''quotient'' of the two functions {{math|''π''(''x'')}} and {{math|''x'' / log ''x''}} as {{mvar|x}} increases without bound is 1:
+Neka je {{math|''π''(''x'')}} [[prime-counting function|funkcija brojanja prostih brojeva]] koja daje broj prostih brojeva manji ili jednak sa {{mvar|x}}, za svaki realni broj&nbsp;{{mvar|x}}. Na primer, {{math|''π''(10) {{=}} 4}}, jer postoje četiri prosta broja (2, 3, 5 i 7) manja ili jednaka od 10. Prema teoremi prostih brojeva tada je {{math|''x'' / log ''x''}} dobra aproksimacija za {{math|''π''(''x'')}} (gde log značava prirodni logaritam), u smislu da je [[limit of a function|limit]] količnika dve funkcije {{math|''π''(''x'')}} i {{math|''x'' / log ''x''}} kako se {{mvar|x}} povećava bez ograničenja jednak 1:
 : <math>\lim_{x\to\infty}\frac{\;\pi(x)\;}{\;\left[ \frac{x}{\log(x)}\right]\;} = 1,</math>
+Ovo je poznato kao '''asimptotski zakon distribucije prostih brojeva'''. Koristeći [[Велико О|asimptotsku notaciju]] ovaj rezultat se može napisati kao
-known as '''the asymptotic law of distribution of prime numbers'''. Using [[asymptotic notation]] this result can be restated as
 :<math>\pi(x)\sim \frac{x}{\log x}.</math>
-This notation (and the [[theorem]]) does ''not'' say anything about the limit of the ''difference'' of the two functions as {{mvar|x}} increases without bound. Instead, the theorem states that {{math|''x'' / log ''x''}} approximates {{math|''π''(''x'')}} in the sense that the [[relative error]] of this approximation approaches 0 as {{mvar|x}} increases without bound.
+Ova notacija (i [[teorema]]) ''ne'' govori o limitu ''razlike'' dve funkcije kad se {{mvar|x}} povećava bez ograničenja. Umesto toga, teorema navodi da {{math|''x'' / log ''x''}} aproksimira {{math|''π''(''x'')}} u smislu da se [[Грешка у апроксимацији|relativna greška]] ove aproksimacije približava 0, kada se {{mvar|x}} povećava bez ograničenja.
-The prime number theorem is equivalent to the statement that the {{mvar|n}}th prime number {{mvar|p<sub>n</sub>}} satisfies
+Teorema prostih brojeva je ekvivalentna tvrđenju da {{mvar|n}}-ti prosti broj {{mvar|p<sub>n</sub>}} zadovoljava
 :<math>p_n \sim n\log(n),</math>
-the asymptotic notation meaning, again, that the relative error of this approximation approaches 0 as {{mvar|n}} increases without bound. For example, the {{val|2|e=17}}th prime number is {{val|8512677386048191063}},<ref>{{cite web|title=Prime Curios!: 8512677386048191063|url=http://primes.utm.edu/curios/cpage/24149.html|work=Prime Curios!|publisher=University of Tennessee at Martin|date=2011-10-09}}</ref> and ({{val|2|e=17}})log({{val|2|e=17}}) rounds to {{val|7967418752291744388}}, a relative error of about 6.4%.
+asimptotska notacija ponovo ukazuje na to da relativna greška ove aproksimacije pristupa 0 kad se {{mvar|n}} povećava bez ograničenja. Na primer, {{val|2|e=17}}-ti prosti broj je {{val|8512677386048191063}},<ref>{{cite web|title=Prime Curios!: 8512677386048191063|url=http://primes.utm.edu/curios/cpage/24149.html|work=Prime Curios!|publisher=University of Tennessee at Martin|date=2011-10-09}}</ref> i ({{val|2|e=17}})log({{val|2|e=17}}) zaokružuje se na {{val|7967418752291744388}}, sa relativnom greškom od oko 6,4%.
+Teorema prostih brojeva je isto tako ekvivalentna sa
-The prime number theorem is also equivalent to
 :<math>\lim_{x\to\infty} \frac{\vartheta (x)}x = \lim_{x\to\infty} \frac{\psi(x)}x=1,</math>
-where {{mvar|ϑ}} and {{mvar|ψ}} are [[Chebyshev function|the first and the second Chebyshev functions]] respectively.
+gde su {{mvar|ϑ}} i {{mvar|ψ}} prva i druga [[Chebyshev function|Čebiševa funkcija]], respektivno.
 == Tabela {{math|''π''(''x'')}}, {{math|''x'' / log ''x''}}, and {{math|li(''x'')}} ==