Ogled vira Praštevilski izrek

{{zvezdica}}

'''Práštevílski izrèk''' (tudi '''izrèk o gostôti práštevíl''') je v [[matematika|matematiki]] [[izrek]] o [[asimptotičnost|asimptotični]] [[porazdelitev (matematika)|porazdelitvi]] [[praštevilo|praštevil]]. Praštevilski izrek podaja splošni opis kako so praštevila porazdeljena med [[pozitivno število|pozitivnimi]] [[celo število|celimi števili]]. Formalizira intuitivno zamisel, da se z večanjem ''n'' praštevila pojavljajo vse redkeje.

Praštevilski izrek v grobem pravi, da če se [[naključje|naključno]] izbere poljubno [[število]] med [[0]] in nekim velikim številom ''n'', je [[verjetnost]], da bo to število praštevilo, enaka približno 1 / ln ''n'', kjer ln ''n'' označuje [[naravni logaritem]] števila ''n''. Zaradi tega bo verjetnost, da bo naključno celo število z največ 2''n'' števkami (za dovolj velik ''n'') praštevilo za polovico manjša od verjetnosti za naključno celo število z največ ''n'' števkami. Na primer za ''n'' = 1.000 je približno eno od sedmih števil praštevilo  (ln&nbsp;10<sup>3</sup> ≈ 6.9), za ''n'' = 10.000 približno eno od devetih števil (ln&nbsp;10<sup>4</sup> ≈ 9,2), za ''n'' = 1.000.000.000 pa eno praštevilo med 21-mi izbranimi števili (ln&nbsp;10<sup>9</sup> ≈ 20,7). Med pozitivnimi celimi števili z največ 1000 števkami, bo približno eno od 2300 števil praštevilo (ln&nbsp;10<sup>1000</sup> ≈ 2302,6), med pozitivnimi celimi števili z največ 2000 števkami pa približno eno od 4600 števil (ln&nbsp;10<sup>2000</sup> ≈ 4605,2). Povprečna [[praštevilska vrzel|vrzel]] med zaporednima prašteviloma med prvimi ''n'' celimi števili je približno ln ''n''.<ref>{{sktxt|Hoffman|1998|pp=227}}.</ref>{{rp|227}}

::: Razvidno je, da so praštevila porazdeljena naključno, vendar na žalost ne vemo kaj 'naključno' pomeni. 
:::::: — R.C. Vaughan (februar 1990).

== Vsebina izreka ==
[[Slika:Prime number theorem ratio convergence.svg|thumb|right|250px|Graf, ki kaže razmerje med [[aritmetična funkcija|aritmetično funkcijo]] [[število praštevil|številom praštevil]] π(''ξ'') in dvema njenima približkoma, ''ξ'' / ln ''ξ'' in Li(''ξ''). Ko se ''ξ'' povečuje (pri tem je ''x''-os logaritemska), se obe razmerji približujeta [[1 (število)|1]]. Razmerje za ''ξ'' / ln ''ξ'' [[konvergenca|konvergira]] od zgoraj zelo počasi, razmerje za Li(''ξ'') pa konvergira hitreje od spodaj.]]
[[Slika:Prime number theorem absolute error.svg|thumb|right|250px|Graf z obema logaritemskima osema kaže [[absolutna napaka|absolutno napako]] ''ξ'' / ln ''ξ'' in Li(''ξ''), dveh približkov za število praštevil π(''ξ''). Za razliko od razmerij razliki z naraščajočim ''ξ'' naraščata brez meja.]]

π(''ξ'') je [[aritmetična funkcija]] [[število praštevil|števila praštevil]], ki podaja število praštevil manjših ali enakih ''ξ'' za poljubno [[realno število]] ''ξ''. π(10) = 4, saj so štiri praštevila (2, 3, 5 in 7) manjša ali enaka 10. Praštevilski izrek pravi, da je ''ξ'' / ln ''ξ'' dober približek za π(''ξ'') v smislu, da je [[limita]] ''kvocienta'' funkcij π(''ξ'') in ''ξ'' / ln ''ξ'' enaka 1, ko se ''ξ'' približuje [[neskončnost]]i:

: <math> \lim_{\xi\to +\infty}\frac{\pi(\xi)}{\xi/\ln\,\xi}=1 \!\, .</math>

S pomočjo [[O notacija|asimptotskega zapisa]] se lahko izrek zapiše kot:

: <math> \pi(\xi)\sim\frac{\xi}{\ln \xi} \!\, . </math>

Ta zapis in izrek sam ne povesta nič o limiti ''razlik'' dveh funkcij, ko ''ξ'' narašča v neskončnost. Obnašanje te razlike je v resnici zapleteno in je povezano z [[Riemannova domneva|Riemannovo domnevo]]. Izrek izjavlja, da je ''ξ'' / ln ''ξ'' približno enako π(''ξ'') v smislu, da se [[relativna napaka]] tega približka približuje 0, ko ''ξ'' naraste prek vseh meja.

Praštevilski izrek je enakovreden izjavi, da je ''n''-to praštevilo ''p''<sub>''n''</sub> približno enako ''n'' ln ''n'', kjer se spet relativna napaka približuje 0, ko ''n'' narašča v neskončnost.

== Eulerjeva obravnava ==

Leta 1737 je [[Leonhard Euler|Euler]] vpeljal klasično [[Riemannova funkcija zeta|Euler-Riemannovo funkcijo ζ]], določeno za vsa realna števila ''s'' večja od 1:

: <math>  \zeta(s) = \sum_{k=1}^{\infty} \frac{1}{k^{s}} =
      \frac{1}{1^{s}} + \frac{1}{2^{s}} + \frac{1}{3^{s}} +
      \frac{1}{4^{s}} + \frac{1}{5^{s}} + ... \!\, , </math>

kjer so ''k'' pozitivna cela števila. Za števila <math>s \le 1</math> (ali bolje za realni del) je gornja [[vsota]] neskončna, tako da <math>\zeta(s)</math> za taka števila ni določena. Za vsako število ''s'' > 1 ima gornja vsota določeno končno vrednost. Pokazal je, da je za vsak tak ''s'' vrednost funkcije <math>\zeta(s)</math> enaka [[neskončni produkt|neskončnemu]] [[Eulerjev produkt|Eulerjevemu produktu]]:

: <math> \zeta(s) = {\prod_{\textstyle{ p=2 \atop p \in \mathbb{P}}}^{\infty}}
 \frac{1}{1-\frac{1}{p^{s}}} =
 \frac{1}{1-\frac{1}{2^{s}}} \cdot
 \frac{1}{1-\frac{1}{3^{s}}} \cdot
 \frac{1}{1-\frac{1}{5^{s}}} \cdot
 \frac{1}{1-\frac{1}{7^{s}}} \cdot
 \frac{1}{1-\frac{1}{11^{s}}} \cdot
 \frac{1}{1-\frac{1}{13^{s}}} \cdot ... = 
{\prod_{\textstyle{ p=2 \atop p \in \mathbb{P}}}^{\infty}} \frac{p^{s}}{p^{s}-1} \!\, . </math>

Prednost produkta je v tem, da ne vsebuje [[ničla funkcije|ničel]] v [[polravnina|polravnini]]. Njegov rezultat je presenetljiv, saj povezuje funkcijo <math>\zeta(s)</math> z neskončno [[množica|množico]] [[praštevilo|praštevil]] ''P'', osnovnih gradnikov števil. Praštevila so prisotna v [[matematična analiza|analizi]], ki je odraz neskončne narave matematike. [[Infinitezimalni račun]], [[Newtonov polinom|Newtonovi polinomi]], [[funkcija gama|funkcija Γ]] in funkcija <math>\zeta</math> funkcija vse sodijo v analizo. Funkcijsko enakost funkcije <math>\zeta(s)</math> je Euler odkril leta 1761. Funkcija:

: <math> \frac{1}{\sqrt \pi^2} \Gamma\left( \frac{s}{2} \right) \zeta (s) \!\, </math>

ostaja nespremenjena, kadar se ''s'' zamenja z 1 - ''s''. Pomena enakosti se ne da videti neposredno, ker so funkcije določene v samostojnih polravninah ločenih s kritičnim trakom. Trak vsebuje [[kompleksno število|kompleksna števila]] katerih realni deli ležijo točno med 0 in 1. To pomeni, da imata tako dve funkciji [[analitično nadaljevanje|naravni nadaljevanji]] preko mej traku in ti dve sta enaki. Za funkcijo <math>\zeta(s)</math> velja [[funkcijska enačba]]:

: <math> \zeta(s) = 2^{s} \pi^{s-1} \sin \left(\frac{\pi s}{2}\right) \Gamma (s-1) \zeta(1-s) \!\, , </math>

za vse ''s'' iz <math>\mathbb{C}</math> - {0,1}. S to enačbo si je moč pomagati pri analitičnem nadaljevanju. Pri ''s'' = 1 ima funkcija <math>\zeta(s)</math> enostavni [[pol]] z ostankom 1. Euler je lahko izračunal <math>\zeta(2k)</math> za vsako [[sodo število|sodo]] celo število 2''k'' z enačbo:

: <math> \zeta(2k) = \frac{B_{2k}(2\pi)^{2k}}{2(2k)!} \!\, , </math>

kjer so <math>B_{2k}</math> [[Bernoullijevo število|Bernoullijeva števila]]. Od tu se vidi, da je <math>\zeta(2)=\pi^{2}/6</math>, <math>\zeta(4)=\pi^{4}/90</math>, <math>\zeta(6)=\pi^{6}/945</math>, <math>\zeta(8)=\pi^{8}/9450</math>, <math>\zeta(10)=\pi^{10}/93555</math> in tako naprej. Te vrednosti dajo znane neskončne vrste za [[pi|''π'']]. Na primer:

: <math> \zeta(2) = \frac{\pi^{2}}{6} = {\prod_{\textstyle{ p=2 \atop p \in \mathbb{P}}}^{\infty}} \frac{p^{2}}{p^{2}-1} = \frac{2^{2}}{2^{2}-1} \cdot \frac{3^{2}}{3^{2}-1} \cdot \frac{5^{2}}{5^{2}-1} \cdot \frac{7^{2}}{7^{2}-1} \cdot \frac{11^{2}}{11^{2}-1} \cdot ... \!\, . </math>

Euler je podal vrednosti za <math>\zeta(2)</math> do <math>\zeta(26)</math> za sode ''n''. [[Thomas Joannes Stieltjes|Stieltjes]] je leta 1887 podal na 30 [[števka|števk]] točno vrednosti za <math>\zeta(2)</math> do <math>\zeta(70)</math>. Števci <math>\zeta(2n)</math> za ''n''=1,2,3,... tvorijo [[zaporedje]] {6, 90, 945, 9450, 93555, 638512875, ...}. Primeri za [[liho število|liha]] cela števila pa niso tako enostavni. [[Srinivasa Ajangar Ramanudžan|Ramanudžan]] je z velikim uspehom raziskoval tudi takšne primere. Za ''n'' > 1 in <math>n \equiv 3 ({\rm mod} \!\, 4)</math> velja na primer:

: <math> {\zeta(n)} = \frac{2^{n-1}\pi^{n}}{(n+1)!} \sum_{k=0}^{(n+1)/2} (-1)^{k-1}
 {n+1\choose 2k} B_{n+1-2k}B_{2k} - 2 \sum_{k=1}^{\infty} \frac{1}{k^{n}(e^{2\pi k}-1)} \!\, , </math>

kjer je <math>{n\choose k}</math> [[binomski koeficient]]. Našli so še druge enačbe za nekatere lihe ''n''.

Sorodni izrek za [[harmonična vrsta|harmonično vrsto]] [[obratna vrednost|obratnih vrednosti]] [[naravno število|naravnih števil]]:

: <math> H(n) = \sum_{k=1}^{\infty} \frac{1}{k} =
      \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + ... \!\, </math>

pove, da vrsta nima končne vsote, in podobno divergira kot <math>\ln n</math>. Euler je poznal ta izrek in je pokazal, da velja:

: <math> H(n) \sim \ln n \!\, </math>

in

: <math> H(n) - \ln n \sim \gamma \!\, , </math>

kjer je <math>\gamma</math> ≈ 0,57721 56649 [[Euler-Mascheronijeva konstanta]]. Euler se je spraševal za ''praštevilsko harmonično vrsto'', ki se jo dobi, če se sešteje obratne vrednosti vseh praštevil:

: <math> P(p) = \sum_{\textstyle{ p=1 \atop p \in \mathbb{P}}}^{\infty} \frac{1}{p} =
      \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \frac{1}{13} + ... \!\, </math>

Ali ima sedaj <math>P(p)</math> končno ali neskončno vsoto? Naravni način odgovora na vprašanje je delitev harmonične vrste na dva dela: tistega, ki vsebuje vsa praštevila in preostanek harmonične vrste:

: <math> \left[ \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \frac{1}{13} + ... \right] +
      \left[ \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{9} + \frac{1}{10} + \frac{1}{12} + \frac{1}{14} + ...\right] \!\, </math>

Potem se poskuša pokazati, da ima drug del končno vsoto. To bi pomenilo, da prvi del povzroča, da ima harmonična vrsta <math>H(n)</math> neskončno vsoto. Prvi del je praštevilska harmonična vrsta in bi tako imela neskončno vsoto. To je dobra zamisel, vendar se naleti na nepričakovano težavo. Ker harmonična vrsta [[divergenca|divergira]], se je ne da na ta način deliti. Euler se je lotil težave drugače. Naj se vzame neko celo realno število ''s'', malo večje od 1, in namesto, da se opazuje harmonično vrsto <math>H(n)</math>, se opazuje raje sorodno vrsto <math>\zeta(s)</math>. Ker se je vzel ''s'' večji od 1, ima ta vrsta končno vsoto in se jo zato lahko deli na dva končna dela: tistega, ki vsebuje vsa praštevila in tistega, ki vsebuje vsa [[sestavljeno število|sestavljena števila]]:

: <math> \zeta(s) = \left[ \frac{1}{1^{s}} + \frac{1}{2^{s}} + \frac{1}{3^{s}} + \frac{1}{5^{s}} + \frac{1}{7^{s}} + \frac{1}{11^{s}} + \frac{1}{13^{s}} + ...\right] + \left[ \frac{1}{4^{s}} + \frac{1}{6^{s}} + \frac{1}{8^{s}} + \frac{1}{9^{s}} + \frac{1}{10^{s}} + \frac{1}{12^{s}} + \frac{1}{14^{s}} + ... \right] \!\, . </math>

Potem se poskuša pokazati, da, če se približuje ''s'' vedno bližje 1, bo prva vsota:

: <math> \frac{1}{1^{s}} + \frac{1}{2^{s}} + \frac{1}{3^{s}} + \frac{1}{5^{s}} + \frac{1}{7^{s}} + \frac{1}{11^{s}} + \frac{1}{13^{s}} + ... \!\, </math>

naraščala preko vsake meje in pri ''s = 1'' bo praštevilska harmonična vrsta:

: <math> P(p) = \sum_{\textstyle{ p=1 \atop p \in \mathbb{P}}}^{\infty} \frac{1}{p} =
      \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \frac{1}{13} + ... \!\, </math>

imela neskončno vsoto. Pri preučevanju <math>\zeta(s)</math> je Euler zasledoval podobno enačbo vsote [[geometrična vrsta|geometrične vrste]]:

: <math> \frac{1}{1-x} = 1 + x + x^{2} + x^{3} + x^{4} + x^{5} + ... \quad (0<x<1) \!\, . </math>

Za vsako praštevilo ''p'' in vsak ''s'' > 1 se lahko zapiše <math>x=1/p^{s}</math> kot:

: <math> \frac{1}{1-\left( \frac{1}{p}\right)^{s} } =
 \frac{1}{p^{1} } + \frac{1}{p^{s} } + \frac{1}{p^{2s} } + \frac{1}{p^{3s} } + \frac{1}{p^{4s} } + \frac{1}{p^{5s} } + ... \!\, . </math>

Izraz na levi strani je seveda izrazit člen v Eulerjevem neskončnem produktu in zgornja enačba zagotavlja neskončno vsoto za vsak člen v neskončnem produktu. Euler je naprej pomnožil vse te neskončne vsote, da bi dobil drugačno obliko svojega neskončnega produkta. Z uporabo običajnih algebrskih pravil za množenje (končnega števila končnih) vsot na neskočno mnogo neskončnih vsot se lahko vidi, če se izpiše desno stran kot eno neskončno vsoto, bodo njeni izrazi oblike:

: <math> \frac{1}{p_1^{k_1 s} ... p_n^{k_n s}} \!\, , </math>

kjer so <math>p_1, ..., p_n</math> različna praštevila in <math>k_1, ..., k_n</math> pozitivna cela števila in vsaka njihova kombinacija nastopi natanko enkrat. Po [[osnovni izrek algebre|osnovnem izreku algebre]] se lahko vsako pozitivno celo število izrazi v obliki <math>p_1^{k_1 s} ... p_n^{k_n s}</math>. Zaradi tega je desna stran preureditev vsote:

: <math> \frac{1}{1^{s}} + \frac{1}{2^{s}} + \frac{1}{3^{s}} + \frac{1}{4^{s}} + \frac{1}{5^{s}} + \frac{1}{6^{s}} + ... \!\, , </math>

oziroma <math>\zeta(s)</math>. Eulerjeva enačba neskončnega produkta za <math>\zeta(s)</math> označuje začetek [[analitična teorija števil|analitične teorije števil]].

== Dirichletova posplošitev ==

Leta 1837 je [[Johann Peter Gustav Lejeune Dirichlet|Dirichlet]] posplošil Eulerjevo metodo za dokaz ali v vsakem [[aritmetično zaporedje|aritmetičnem zaporedju]] <math>a, a+k, a+2k,a+3k,...</math>, kjer ''a'' in ''k'' nimata skupnega [[faktor]]ja (sta si [[tuje število|tuja]], oziroma relativno praštevili), obstaja neskončno število praštevil. Na [[Evklidov izrek]] se lahko gleda kot na poseben primer tega za aritmetično zaporedje 1,3,5,7, ... vseh lihih celih števil. Dirichlet je za to priložnost posplošil Euler-Riemannovo funkcijo <math>\zeta</math> tako, da so vsa praštevila ločena v posamične razrede glede na to, kakšen ostanek imajo pri deljenju s ''k''. Njegova modificirana funkcija ζ ima obliko:

: <math> L(s,\chi) = \sum_{k=1}^\infty \frac{\chi(k)}{{k^{s}}} =
     \frac{\chi(1)}{{1^{s}}} + \frac{\chi(2)}{{2^{s}}} + \frac{\chi(3)}{{3^{s}}} + \frac{\chi(4)}{{4^{s}}} + \frac{\chi(5)}{{5^{s}}} + ... \!\, , </math>

kjer je <math>\chi(n)</math> posebna oblika funkcije, ki jo je Dirichlet imenoval »[[Dirichletov karakter|karakter]]«, in ta deli praštevila na zahtevan način. Posebej velja <math>\chi(mn) = \chi(m) \chi(n)</math> za vsak <math>m,n</math>. Druga pogoja sta še, da je <math>\chi(n)</math> odvisna le od ostanka pri deljenju ''n'' s ''k'' in <math>\chi(n)=0</math>, če imata ''n'' in ''k'' skupni faktor. Vsaka funkcija oblike <math>L(s,\chi)</math>, kjer je realno število ''s'' > 1 in <math>\chi</math> karakter, je znana kot [[Dirichletova vrsta|Dirichletova L-vrsta]]. Euler-Riemannova funkcija <math>\zeta</math> je poseben primer, ki nastane, če se vzame <math>\chi(n)=1</math> za vse ''n''. Matematiki so posplošili spremenljivko ''s'' in števila <math>\chi(n)</math> v kompleksno področje in s posplošeno obliko dokazali veliko značilnosti praštevil in tako pokazali, da so L-vrste zelo močno orodje pri študiju praštevil. Ključni rezultat o L-funkcijah je ta, da se jih lahko skupaj z <math>\zeta(s)</math> izrazi kot neskončni produkt preko praštevil (Eulerjev produkt):

: <math> L(x,\chi) = {\prod_{\textstyle{ p=2 \atop p \in \mathbb{P}}}^{\infty}}
                  \frac{1}{1-\frac{\chi(p)}{p^{s}} } =
                  \frac{1}{1-\frac{\chi(2)}{2^{s}} } \cdot
                  \frac{1}{1-\frac{\chi(3)}{3^{s}} } \cdot
                  \frac{1}{1-\frac{\chi(5)}{5^{s}} } \cdot
                  \frac{1}{1-\frac{\chi(7)}{7^{s}} } \cdot
                  \frac{1}{1-\frac{\chi(11)}{11^{s}} } \cdot ... \!\, , </math>

kjer je realni del ''s'' pozitiven.

Med prvimi desetimi števili je kar polovica praštevil, med prvimi 1000 pa le približno 1/6. Zdi se, da ni kakšnega splošnega pravila, po katerem bi bila praštevila razporejena med naravnimi števili. Med 9 999 900 in 10 000 000 je na primer 9 praštevil. Med 10 000 000 in 10 000 100 pa le 2, in sicer 10 000 019 in 10 000 079. Obstajajo celo poljubno dolgi odseki zaporednih naravnih števil, med katerimi ni nobenega praštevila. Za poljuben ''n'' med številoma <math>n! +2</math> in <math>n!+n</math> ni nobenega praštevila. Matematiki menijo, da so [[prašteviski dvojček|praštevilski dvojčki]] razporejeni povsem slučajno. Celo tega se ne ve, ali je praštevilskih dvojčkov končno mnogo ali jih je neskončno.<ref>{{sktxt|Drnovšek|1997}}.</ref>

== Pregled zgodnje zgodovine izreka ==
[[Slika:Primes - distribution - up to 19 primorial.png|thumb|right|250px|Porazdelitev praštevil do [[primoriela|19#]] (9.699.690).]]

Praštevilski izrek govori o asimptotičnem obnašanju [[aritmetična funkcija|aritmetične funkcije]] <math>\pi(\xi)</math>, števila praštevil manjših ali enakih realnemu številu <math>\xi</math>. [[Adrien-Marie Legendre|Legendre]] je leta 1796 domneval in leta 1798 v knjigi ''Esai sur la Theorie des Nombres'' objavil ugotovitev za velike <math>\xi</math>:<ref name="pintz_1980">{{sktxt|Pintz|1980}}.</ref>

: <math> \pi(\xi) \sim \frac{\xi}{{A \ln \xi + B}} \!\, , </math>

kjer sta bili konstanti ''A'' in ''B'' nedoločeni. Z zapisom <math>\pi(a)=b\, </math> je zapisal: »Končno je možno, da ima stroga formula, ki da vrednost ''b'', če je ''a'' zelo velik, obliko <math>b=a/(A\log a + B)\, </math>, kjer sta ''A'' in ''B'' konstantna koeficienta, log ''a'' pa označuje naravni logaritem. Točna določitev koeficientov bo naloga posameznika, ki bo vredna vaje za ostroumnost Analitika.«<ref name="pintz_1980" />

V drugi izdaji knjige leta 1808 je podal določnejšo domnevo:

: <math> \pi(\xi) \sim \frac{\xi}{{A \ln \xi - B}} \!\, , </math>

z ''A'' = 1 in ''B'' = 1,08366, ki se včasih imenuje [[Legendrova konstanta]]. Pomagal si je z [[Eratostenovo sito|Eratostenovim sitom]] in je do tega rezultata prišel povsem empirično na podlagi preučevanja [[Anton Felkel|Felklovih]] in [[Jurij Vega|Vegovih]] razpredelnic praštevil, manjših od 400.000. Zato število ''B'' ni kaj posebnega. Legendre ga je enostavno izbral tako, da je dobil kar najboljši približek. V tretji izdaji knjige, preimenovani v ''Théorie des nombres'', je podal obliko:

: <math> \pi(\xi) = \frac{\xi}{{\ln \xi - A(\xi) + o(1)}} \!\, . </math>

Medtem ko je Legendre pripravljal svojo knjigo, je funkcijo <math>\pi(\xi)</math> preučeval tudi štirinajstletni [[Carl Friedrich Gauss|Gauss]]. Leta 1792 ali 1793 je kot 15/16-leten zapisal (objavil pa šele leta 1863):

: <math> \hbox{ Primzahlen unter } \; \xi \, (= \infty) \frac{\xi}{ \hbox{l} \, \xi} \!\, . </math>

Če se »praštevila pod <math>\xi</math>« nadomesti z enakovredno vrednostjo <math>\pi (\xi)</math>, znak l<math>\xi</math> z <math>\ln \xi</math> in <math>(= \infty)</math> z besedilom ''za velike'' <math>\xi</math>, se dobi njegovo mladostno oceno:

: <math> \pi(\xi) \sim \frac{\xi}{\ln \xi} \quad \hbox{za velike} \;\; \xi \!\, , </math>

z deljenjem s <math>\xi</math> pa obliko praštevilskega izreka. Očitno je mladi Gauss že razumel to značilnost praštevil, zakaj pa je ni razvil, se najverjetneje ne bomo nikoli izvedelo. Na Božič 1849 je v pismu [[Johann Franz Encke|Enckeju]] zapisal:

::: Kot deček sem preučeval problem koliko praštevil je do dane točke. Iz svojih preračunov sem ugotovil, da je gostota praštevil okrog ''x'' približno <math>1/\log \, x</math>.

Pozneje je domneval, da velja praštevilski izrek:

: <math> \pi(\xi) \sim {\rm Li}(\xi) = \int_2^{\xi} \frac{\mathrm{d} t}{\ln t} \!\, , </math>

kjer je Li<math>(\xi)</math> [[neelementarna funkcija]] [[logaritemski integral]] ali integralski logaritem li<math>(x)</math> brez [[Cauchyjeva glavna vrednost|Cauchyjeve glavne vrednosti]] (CGV). Logaritemski integral v kompleksnem je določen z:

: <math> {\rm li}(z) \equiv \int_{0}^z \frac{\mathrm{d} t}{\ln t} \quad \hbox{(za}\quad z>1) \!\, , </math>

Logaritemski integral v praštevilskem izreku je določen tako, da velja Li<math>(2)=0</math>:

: <math> {\rm Li}(\xi) \equiv \int_2^{\xi} \frac{\mathrm{d} t}{\ln t}
     = {\rm li}(\xi) - {\rm li}(2) \approx {\rm li}(\xi) - 1,045163780 
     = {\rm ei} (\ln \xi) \!\, , </math>

kjer je ei<math>(\xi)</math> [[eksponentni integral]]. Logaritemski integral močno namiguje na predstavo o tem da je 'gostota' praštevil okrog ''t'' enaka 1 / ln''t''. Ta funkcija je povezana z logaritmom s Poincaréjevim, oziroma asimptotičnim razvojem:

: <math> \mbox{Li}(\xi) = \frac{\xi}{\ln \xi} \sum_{k=0}^\infty \frac{k!}{(\ln \xi)^k} 
= \frac{\xi}{\ln \xi} + \frac{\xi}{(\ln \xi)^2} + \frac{2\xi}{(\ln \xi)^3} + \cdots </math>

Da se ogne singularni vrednosti v točki 1, se včasih vzame konstanto, označeno s ''c'' ali <math>\mu >1</math> tako, da velja:

: <math> CGV \int_0^\mu \frac{1}{\ln t} \mathrm{d} t = 0 \!\, . </math>

Tako se lahko pri <math>\xi >1</math> zamenja CGV<math> \int_0^{\xi} 1/\ln t \mathrm{d} t</math> z <math>\int_{\mu}^{\xi} 1/\ln t \mathrm{d} t</math>. Ta način je prvi uporabil Ramanudžan in se sedaj <math>\mu</math> ≈ 1.4513692348... imenuje [[Ramanudžan-Soldnerjeva konstanta]] ali Soldnerjeva konstanta, in predstavlja ničlo enačbe li<math>(\xi)=0</math>. Ramanudžan je dobil vrednost <math>\mu</math> ≈ 1,451363380... Ta konstanta se pojavlja v naslednji obliki praštevilskega izreka:

: <math> \pi(\xi) = \sum_{n=1}^{\infty} \frac{\mu(n)}{n}
     \int_{\mu}^{\xi} \frac{\mathrm{d} t}{\ln t} \!\, , </math>

kjer je <math>\mu(m)</math> [[Möbiusova funkcija|Möbiusova multiplikativna aritmetična funkcija]].

[[Slika:PrimeNumberTheorem.svg|thumb|right|250px|Graf, ki kaže primerjavo med  π(''ξ''), ''ξ'' / ln ''ξ'' in Li(''ξ'') ]]

Funkcija Li<math>(\xi)</math> ima glavni člen <math>n/\ln \,n</math> in je boljši priblišek od njega samega. Tako Legendreova in Gaussova enačba nakazujeta podobno domnevno asimtotično enakost med π(''ξ'') in ''ξ'' / ln ''ξ''. Sicer se izkaže da je Gaussov približek precej boljši, če upoštevamo razlike namesto količnikov. 

[[Pafnuti Lvovič Čebišov|Čebišov]] je v dveh člankih leta 1848 in 1850 poskušal dokazati porazdelitveni zakon za praštevila. Dokazal je, da sta supremum ''M'' in infimum ''n'' relacije:

: <math> \frac{\pi(\xi)}{\xi/\ln \xi} \!\, </math>

v mejah <math>0,92129\le m\le M\le 1,10555</math>. Kasneje je [[James Joseph Sylvester|Sylvester]] leta 1881 zožil dopustni interval limit z 10 % na 4 %. Delo Čebišova je pomembno zaradi uporabe funkcije zeta ζ(s), ki je naznanjalo [[Bernhard Riemann|Riemannov]] članek iz leta 1859. Čebišov je leta 1851 dokazal malo šibkejši rezultat, da če <math>\pi(\xi)/(\xi/\ln \xi)</math> res teži k limiti ko <math>\xi</math> pobegne v neskončnost, potem mora biti limita enaka 1. Ni pa mogel pokazati, da ta limita res obstaja. Čeprav Čebišov ni docela dokazal praštevilskega izreka, je z uporabo ocene za π(''ξ'') leta 1850 dokazal [[Bertrandova domneva|Bertrandovo domnevo]].

== Razpredelnica funkcij π(''ξ''), ''ξ'' / ln ''ξ'' in Li(''ξ'') ==

Naslednja razpredelnica kaže kako se obnašajo tri funkcije (π(''ξ''), ''ξ'' / ln(''ξ'') in Li(''ξ'')). Zadnji stolpec, ''ξ'' / π(''ξ'') je povprečna [[praštevilska vrzel]] za praštevila, manjša od ''ξ'': 
{| class="wikitable" style="text-align: right"
! ''ξ''                  
! π(''ξ'') <ref>{{Navedi splet
| url = http://www.research.att.com/projects/OEIS?Anum=A006880
| title = Število praštevil < 10^n (A006880)
| work = [[Spletna enciklopedija celoštevilskih zaporedij|OEIS]]
}}</ref>
! π(''ξ'') - ''ξ'' / ln(''ξ'')<ref>{{navedi splet
| url = http://www.research.att.com/projects/OEIS?Anum=A057835
| title = Razlika med pi(10^n) in celim številom, najbližjim k 10^n / log(10^n) (A057835)
| work = OEIS
}}</ref>
! π(''ξ'') / (''ξ'' / ln ''ξ'') 
! Li(''ξ'') - π(''ξ'')<ref>{{navedi splet
| url = http://www.research.att.com/projects/OEIS?Anum=A057752
| title = Razlika med Li(10^n) inPi(10^n), kjer je Li(x) - integral log(x) in Pi(x) - število praštevil <= x (A057752)
| work = OEIS
}}</ref>
! ''ξ'' / π(''ξ'')
|-
|10<sup>1</sup>  ||                             4 || -0,3                       || 0,921 || 2,2           || 2,500
|-
|10<sup>2</sup>  ||                            25 || 3,3                        || 1,151 || 5,1           || 4,000
|-
|10<sup>3</sup>  ||                           168 || 23                         || 1,161 || 10            || 5,952
|-
|10<sup>4</sup>  ||                         1.229 || 143                        || 1,132 || 17            || 8,137
|-
|10<sup>5</sup>  ||                         9.592 || 906                        || 1,104 || 38            || 10,430
|-
|10<sup>6</sup>  ||                        78.498 || 6.116                      || 1,084 || 130           || 12,740
|-
|10<sup>7</sup>  ||                       664.579 || 44.159                     || 1,071 || 339           || 15,047
|-
|10<sup>8</sup>  ||                     5.761.455 || 332.774                    || 1,061 || 754           || 17,357
|-
|10<sup>9</sup>  ||                    50.847.534 || 2.592.592                  || 1,054 || 1.701         || 19,666
|-
|10<sup>10</sup> ||                   455.052.511 || 20.758.029                 || 1,048 || 3.104         || 21,975
|-
|10<sup>11</sup> ||                 4.118.054.813 || 169.923.159                || 1,043 || 11.588        || 24,283
|-
|10<sup>12</sup> ||                37.607.912.018 || 1.416.705.193              || 1,039 || 38.263        || 26,590
|-
|10<sup>13</sup> ||               346.065.536.839 || 11.992.858.452             || 1,034 || 108.971       || 28,896
|-
|10<sup>14</sup> ||             3.204.941.750.802 || 102.838.308.636            || 1,033 || 314.890       || 31,202
|-
|10<sup>15</sup> ||            29.844.570.422.669 || 891.604.962.452            || 1,031 || 1.052.619     || 33,507
|-
|10<sup>16</sup> ||           279.238.341.033.925 || 7.804.289.844.392          || 1,029 || 3.214.632     || 35,812
|-
|10<sup>17</sup> ||         2.623.557.157.654.233 || 68.883.734.693.281         || 1,027 || 7.956.589 	  || 38,116
|-
|10<sup>18</sup> ||        24.739.954.287.740.860 || 612.483.070.893.536        || 1,025 || 21.949.555    || 40,420 
|-
|10<sup>19</sup> ||       234.057.667.276.344.607 || 5.481.624.169.369.960      || 1,024 || 99.877.775    || 42,725
|-
|10<sup>20</sup> ||     2.220.819.602.560.918.840 || 49.347.193.044.659.701     || 1,023 || 222.744.644   || 45,028
|-
|10<sup>21</sup> ||    21.127.269.486.018.731.928 || 446.579.871.578.168.707    || 1,022 || 597.394.254   || 47,332
|-
|10<sup>22</sup> ||   201.467.286.689.315.906.290 || 4.060.704.006.019.620.994  || 1,021 || 1.932.355.208 || 49,636
|-
|10<sup>23</sup> || 1.925.320.391.606.818.006.727 || 37.083.513.766.592.669.113 || 1,020 || 7.236.148.412 || 51,939
|-
|10<sup>24</sup> || 18.435.599.767.349.200.867.866 || 339.996.354.713.708.049.069 || 1,019 || 17.146.907.277 || 54,243
|-
|10<sup>25</sup> || 176.846.309.399.143.769.411.680 || 3.128.516.637.843.038.351.228 || 1,018 || 55.160.980.939 || 56,546
|-
| [[Spletna enciklopedija celoštevilskih zaporedij|OEIS]] || {{OEIS2C|id=A006880}} || {{OEIS2C|id=A057835}} || &nbsp; || {{OEIS2C|id=A057752}} || &nbsp;
|}
Vrednost za π(10<sup>24</sup>) je bila izvirno izračunana s privzetkom veljavnosti [[Riemannova domneva|Riemannove domneve]];<ref name="Franke">{{navedi splet|title= Conditional Calculation of pi(10<sup>24</sup>)|url= http://primes.utm.edu/notes/pi(10%5E24).html|publisher= Chris K. Caldwell|accessdate= 2010-08-03|language=en}}</ref> nato so jo preverili brezpogojno.<ref name="platt_2012">{{sktxt|Platt|2012}}.</ref>

Kot posledica praštevilskega izreka se dobi asimptotično oceno za ''n''-to praštevilo ''p''(''n''):

: <math>p(n)\sim n\ln(n). </math>

Vidi se lahko tudi, da bo naključno izbrano število ''n'' praštevilo z [[verjetnost]]jo 1 / ln(''n'').

== Riemannova razširitev in dokaz ==

Leta 1896 sta neodvisno drug od drugega [[Charles-Jean de La Vallée Poussin|La Vallée Poussin]] in [[Jacques Salomon Hadamard|Hadamard]] dokazala praštevilski izrek, trditev, ki je bila razvidna že iz dotedanjih izračunov. Dokazala sta, da se z »naraščajočim ''n'' vrednost izraza <math>n/\ln n</math> bolj in bolj približuje funkciji <math>\pi(\xi)</math>«. Pokazala sta da <math>\zeta(s)</math> nima nobenih ničel oblike <math>1 + it</math>, s tem, da za dokaz ni potrebno poznavanje drugih značilnosti <math>\zeta(s)</math>. Ta blesteči rezultat je enkrat za vselej in nedvoumno pokazal, da so praštevila razporejena po vzorcu, ki ga je možno opisati z matematičnimi sredstvi. Na njuno delo je močno vplival pomemben, čeprav komaj osem strani dolg [[Bernhard Riemann|Riemannov]] članek iz leta 1859 ''O številu praštevil, manjših od dane velikosti'' (''Über die Anzahl der Primzahlen unter einer gegebenen Grösse''). To edino Riemannovo delo iz [[teorije števil]] je izredno pomembno, saj je z izvirnimi postopki preučevanja naravnih števil odkril mnoge nove zakonitosti. Te metode uporabljajo še danes. Ključni prijem, ki ga je Riemann vpeljal pri preučevanju porazdelitve praštevil, je razširitev funkcije <math>\zeta(s)</math>. Euler je določil funkcijo le za realna števila, ki so večja od 1. Riemann pa je Eulerjevo določitev razširil na vsa kompleksna števila <math>s = a + bi</math> (z izjemo števila ''s'' = 1)<ref>{{sktxt|Ingham|1990|pp=2-5}}.</ref>{{rp|2-5}} Pri tem je treba uporabiti analitično nadaljevanje funkcije. Razširjena funkcija <math>\zeta(s)</math> je določena kot [[krivuljni integral]]:

: <math> \zeta(s) = \frac{\Pi(-s)}{2\pi i}\int_{C} \frac{(-x)^{s}}{e^{x}-1} \frac{\mathrm{d} x}{x} \!\, , </math>

pri čemer poteka krivulja ''C'' od <math>+\infty</math> vzdolž [[številska premica|realne premice]], se tik pred [[izhodišče]]m ustavi, ga enkrat obkroži v nasprotni smeri urinega kazalca in se spet po realni osi vrne v <math>+\infty</math>. Za vsak ''s'' > 0, pa je:

: <math> \Pi(s) = \lim_{N \to \infty} \frac{N!}{(s+1)(s+2)...(s+N)} {(N+1)^{s}} \!\, . </math>

Riemannova razširitev funkcije <math>\zeta</math>, imenovana tudi [[Riemannova funkcija zeta|Riemannova funkcija ζ]], je ključna za teorijo števil. Riemann je ugotovil, da je vrednost funkcije <math>\zeta(s)</math> za števila <math>S = -2, -4, -6, -8, ...</math> enaka 0. Reče se, da so negativna soda cela števila ničle Riemannove funkcije <math>\zeta</math>. Nadalje je ugotovil, da obstaja še neskončno mnogo kompleksnih števil ''s'', za katere je <math>\zeta(s)=0</math>, in da je realni del vseh takih števil med 0 in 1. Vsa taka števila ''s'' so oblike <math>a+bi</math>, pri čemer je <math>0<a<1</math>. [[Riemannova domneva]] govori o netrivialnih kompleksnih ničlah Riemannove funkcije <math>\zeta</math>. Riemann je domneval, čeprav je poznal komaj kakšno kompleksno ničlo te funkcije, da je realni del vseh kompleksnih ničel funkcije <math>\zeta(s)</math> enak <math>\frac{1}{2}</math>. Če je torej <math>\zeta(s)=0</math> in ''s'' sodo pozitivno število, potem je po njegovi domnevi <math>s=\frac{1}{2} + bi</math> za kakšno realno število ''b''. 

Še boljša aproksimacija in ocena napake je dana z enačbo:

: <math>\pi(\xi) = {\rm Li} (\xi) + \mathcal{O} \left(\xi e^{-\frac{1}{15}\sqrt{\ln(\xi)}}\right) </math>

za <math>\xi</math> → ∞, kjer je <math>\mathcal{O}\, </math>-zapis [[O notacija|Landauov simbol]]. Približek so še izboljšali z:

: <math>\pi(\xi)={\rm Li} (\xi) + \mathcal{O} \left(\xi \, \exp \left( -\frac{A(\ln \xi)^{3/5}}{(\ln \ln \xi)^{1/5}} \right) \right) \!\, . </math>

Izreka Hadamarda in La Vallée Poussina je kasneje v 20. stoletju postal znan kot praštevilski izrek. Zaradi povezave med Riemannovo funkcijo ζ(''s'') in π(''ξ'') ima Riemannova domneva pomembno vlogo v teoriji števil. Če bo rešena, bo moč najti mnogo točnejšo napako v praštevilskem izreku kot je na voljo sedaj. [[Helge von Koch|Von Koch]] je leta 1901<ref>{{sktxt|Von Koch|1901}}.</ref> dokazal, da je Riemannova domneva enakovredna naslednji '''močnejši obliki praštevilskega izreka''', ko <math>\xi\to\infty</math> :

: <math> \pi(\xi) = {\rm Li} (\xi) + \mathcal{O} \left(\sqrt\xi \ln\xi\right) \!\, , </math>

Če velja Riemannova domneva, je tukaj ocena napake še boljša kot zgoraj, kakšna pa je konstanta v <math>\mathcal{O}\, </math> zapisu, pa se ne ve. Ta povezava med številom praštevil in med ničlami kompleksne analitične funkcije je nabila ozračje matematike na začetku 20. stoletja. Kot je leta 1932 zapisal [[Albert Edward Ingham|Ingham]]:
::: Rešitev [zgornje enačbe] ... bo verjetno neuspešna, ker prinaša zamisli, ki so zelo drugačne od izvirnega problema. Naravno se je vprašati po dokazu praštevilskega izreka, ki ni odvisen od funkcij kompleksne spremenljivke ... Kakor zgleda bo nemogoče najti pristen dokaz z 'realnimi spremenljivkami'.

Ingham je menil, da mora vsak dokaz vsebovati [[kompleksna analiza|kompleksno analizo]]. Kako se je motil (kot tudi [[Godfrey Harold Hardy|Hardy]], [[Harald Bohr|Bohr]] in mnogi drugi). Leta 1949 sta [[Atle Selberg|Selberg]] in [[Paul Erdős|Erdős]] delno neodvisno pokazala elementarni dokaz praštevilskega izreka.

Konstanto v von Kochovi obliki je leta 1976 določil [[Lowell Schoenfeld|Schoenfeld]]<ref>{{sktxt|Schoenfeld|1976}}.</ref> in upošteval Riemannovo domnevo:

: <math>|\pi(\xi)-{\rm li}(\xi)|<\frac{\sqrt \xi\,\ln \xi}{8\pi}</math>

za vse ''ξ'' ≥ 2657. Izpeljal je tudi sorodno mejo za [[funkcija Čebišova|število praštevil Čebišova]] ψ:

: <math>|\psi(\xi)-\xi|<\frac{\sqrt \xi\,\ln^2 \xi}{8\pi}</math>

za vse ''ξ'' ≥ 73,2.

Logaritemski integral Li(''ξ'') je večji od π(''ξ'') za »majhne« vrednosti ''ξ''. Vendar je [[John Edensor Littlewood|Littlewood]] leta 1914 dokazal da temu ni vedno tako. Prva vrednost ''ξ'' za katero je π(''ξ'') večja od Li(''ξ'') je približno pri ''ξ'' = 1,397162914 · 10<sup>316</sup> ([[Patrick Demichel|Demichel]] 2005). Takšna ogromna števila so znana kot [[Skewesovo število|Skewesova števila]].

== Metodologija dokaza ==

V predavanju o praštevilih za širšo javnost je [[Terence Tao|Tao]], prejemnik [[Fieldsova medalja|Fieldsove medalje]] leta 2006, opisal pesniški pristop dokaza praštevilskega izreka s poslušanjem praštevilske »glasbe«. Začne se z »zvočnim valovanjem«, ki je »glasno« pri praštevilih in tiho pri sestavljenih številih - to je [[von Mangoldtova funkcija|von Mangoldtova]] aritmetična funkcija Λ(''n''), ki ni ne [[multiplikativna funkcija|multiplikativna]] in ne [[aditivna funkcija|aditivna]]. Potem se analizira njegove [[nota|note]], oziroma [[frekvenca|frekvence]], s procesom, sorodnim [[Fourierova transformacija|Fourierovi transformaciji]] – to je [[Mellinova transformacija]]. Potem se dokaže, kar je težek del, da se določene »note« v tej glasbi ne morejo pojaviti. Ta izključitev določenih not vodi do praštevilskega izreka. Po Tau ta dokaz vodi do bolj globljega vpogleda v porazdelitev praštevil kot elementarni dokazi, opisani spodaj <ref>[http://164.67.141.39:8080/ramgen/specialevents/math/tao/tao-20070117.smil Video] in [http://www.math.ucla.edu/~tao/preprints/Slides/primes.pdf prosojnice] Taojevega predavanja o praštevilih, UCLA, januar 2007.</ref>. 

== Teorija Dirichletovih vrst ==

Riemannova funkcija <math>\zeta</math> je določena tudi z [[Dirichletova vrsta|Dirichletovo vrsto]], kjer je <math>\zeta(s)</math> prototip, ki generira konstantno aritmetično funkcijo <math> f(n)=1</math> za vse ''n'':

: <math> \zeta(s) = \sum_{n=1}^{\infty} f(n) \frac{1}{n^{s}} \!\, . </math>

[[kvadrat (algebra)|Kvadrat]] Euler-Riemannove funkcije <math>\zeta(s)</math> generira funkcijo [[število deliteljev]] <math>\tau(n)</math>:

: <math> \zeta(s)^{2} = \sum_{n=1}^{\infty} \frac{\tau(n)}{n^{s}} \!\, . </math>

[[Obratna vrednost]] Euler-Riemannove funkcije <math>\zeta(s)</math> generira Möbiusovo aritmetično funkcijo <math>\mu(n)</math>:

: <math> \frac{1}{\zeta(s)} = \sum_{n=1}^{\infty} \frac{\mu(n)}{n^{s}} \!\, </math>

ali [[Mertensova funkcija|Mertensovo funkcijo]]:

: <math> \frac{1}{\zeta(s)} = s \int_1^{\infty} \frac{M(x)}{x^{s+1}} \mathrm{d} x \!\, . </math>

V splošnem velja, da če dve Dirichletovi vrsti <math>L(s,\chi)</math> in <math>M(s,\chi)</math> generirata aritmetični funkciji <math>f(n)</math> in <math>g(n)</math>, potem njun produkt <math>f(n) g(n)</math> generira novo aritmetično funkcijo:

: <math> {h(n)} = \sum_{d\mid n} f(d) g\left( \frac{n}{d} \right) \!\, , </math>

in se imenuje [[Dirichletov produkt]] dveh aritmetičnih funkcij <math>f(n)</math> in <math>g(n)</math>. Dirichletov produkt se dobi, če se pomnoži dve Dirichletovi vrsti in preuredi člene:

: <math> \begin{align} L(s,\chi)M(s,\chi) &= \sum_{n=1}^{\infty} \frac{f(n)}{n^{s}} \sum_{m=1}^{\infty} \frac{g(m)}{m^{s}} \\
&= \sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{f(n)g(m)}{(n m)^{s}} = \sum_{k=1}^{\infty} \frac{h(k)}{k^{s}} \!\, , \end{align} </math>

kjer je:

: <math> h(k) = \sum_{nm=k} f(n)g(m) = \sum_{d\mid k} f(d) g\left( \frac{k}{d}\right) \!\, . </math>

Enačba velja kadar vrsti <math>L(s,\chi)</math> in <math>M(s,\chi)</math> absolutno konvergirata. S produktom Dirichletovih vrst se lahko generira veliko aritmetičnih funkcij v multiplikativni teoriji števil. Na primer:

: <math> \frac{\zeta(s-1)}{\zeta(s)} = \sum_{n=1}^{\infty} \frac{\varphi(n)}{n^{s}} </math>

in 

: <math> \zeta(s)\zeta(s-\alpha) = \sum_{n=1}^{\infty} \frac{\sigma_{\alpha}(n)}{n^{s}} \!\, . </math>

V aditivni teoriji števil za [[rodovna funkcija|rodovne funkcije]] se uporabi raje [[potenčna vrsta|potenčne vrste]]. Funkcija <math>A(\chi)</math> z razvitjem v potenčno vrsto:

: <math> A(\chi) = \sum_{n=0}^{\infty} a(n) {\chi}^{n} </math> 

generira koeficiente <math>a(n)</math>. Če <math>B(\chi)</math> generira koeficiente <math>b(m)</math> tako, da je:

: <math> B(\chi) = \sum_{m=0}^{\infty} b(m) {\chi}^{m} , </math>

potem je za vse tiste <math>\chi</math>, za katere obe vrsti absolutno konvergirata, njun produkt:

: <math> A(\chi) B(\chi) = \sum_{n=0}^{\infty} a(n) {\chi}^{n}
                       \sum_{m=0}^{\infty} b(m) {\chi}^{m} =
     \sum_{n=0}^{\infty} \sum_{m=0}^{\infty} a(n) b(m) {\chi}^{n+m} =   \sum_{k=0}^{\infty} c(k) {\chi}^{k} \!\, , </math>

kjer je:

: <math> c(k) = \sum_{n+m=k}^{\infty} a(n) b(m) \!\, . </math>

Novo zaporedje se imenuje [[Cauchyjev produkt]] dveh zaporedij <math>a(n)</math> in <math>b(m)</math>. Na primer naj je <math>a(n)=1</math>, če je ''n'' kvadrat, drugače pa <math>a(n)=0</math>, tako, da je:

: <math> A(\chi) = 1 + \chi + \chi^{4} + \chi^{9} + \chi^{16} + ... + \chi^{n^2} + ... \!\, . </math>

Tako <math>A(\chi)</math> vsebuje člene, ki so kvadrati. Kvadrat <math>A(\chi)</math> je dan z vrsto:

: <math> A(\chi)^{2} = 1 + 2\chi + \chi^{2} + 2\chi^{4} + 2\chi^{5} + \chi^{8} + 2\chi^{9} + ... + b(n)\chi^{n} + ... \!\, , </math>

kjer je <math>b(n)</math> število načinov, s katerimi se lahko izrazi ''n'' kot vsoto dveh kvadratov pozitivnih celih števil, če se upošteva vrstni red [[seštevanec|seštevancev]]. [[Četrta potenca]] pa je:

: <math> A(\chi)^{4} = 1 + 4\chi + 6\chi^{2} + 4\chi^{3} + 5\chi^{4} + 12\chi^{5} + ... + c(n)\chi^{n} + ... \!\, , </math>

kjer je <math>c(n)</math> število načinov, s katerimi se lahko izrazi ''n'' kot vsoto štirih kvadratov pozitivnih celih števil. Obstaja, na primer, natanko 6 načinov, da se zapiše 2 kot vsoto štirih pozitivnih kvadratov:

: <math> 2 = 1+1+0+0 = 1+0+1+0 = 1+0+0+1 = 0+1+0+1 = 0+1+1+0 = 0+0+1+1 \!\, , </math>

zato je <math>c(2)=6</math>. Euler je opazil, da je [[Lagrangeev izrek štirih kvadratov]] enakovreden izjavi, da je <math>c(n)</math> pozitiven za vsak ''n'', ni pa uspel dokazati, da je <math>c(n)>0\, </math>. Če so dovoljeni za seštevance tudi kvadrati negativnih celih števil, je število predstavitev celega števila kot vsota kvadratov precej večje. Če so, na primer, dovoljeni kvadrati -1, obstaja 24 različnih načnov zapisa 2 kot vsote štirih kvadratov. Število predstavitev celega števila ''n'' kot vsote ''k'' kvadratov celih števil (pozitivnih, negativnih ali ničle) se označi z <math>r_{k}(n)</math>. Njegova rodovna funkcija je:

: <math> \Theta(\chi)^{k} = 1 + \sum_{n=1}^{\infty} r_{k}(n) {\chi}^{n} \!\, , </math>

kjer je funkcija <math>\Theta(\chi)</math> določena z neskončno vrsto:

: <math> \Theta(\chi) = \sum_{m=-\infty}^{\infty} {\chi}^{m^2} \!\, . </math>

Za primer <math>r_{2}(n)</math> glej zgoraj. Jacobi je pokazal, da značilnosti funkcije <math>\Theta(\chi)</math> vodijo k podatkom, ki se nanašajo na predstavitve celih števil s kvadrati. Jacobijeva enačba iz teorije [[eliptična funkcija|eliptičnih funkcij]]:

: <math> \Theta(\chi)^{2} = 1 + 4\sum_{n=1}^{\infty} \left\lbrace
      \tau_{1}(n) - \tau_{3}(n)\right\rbrace {\chi}^{n} \!\, , </math>

kjer sta <math>\tau_{1}(n)</math> in <math>\tau_{3}(n)</math> število [[delitelj]]ev ''n'' kongruentno 1 in 3 po [[modularna aritmetika|modulu]] 4. Če se primerja koeficient <math>{\chi}^{n}</math> v tej enačbi s koeficientom <math>{\chi}^{n}</math> v rodovni funkciji za <math>r_{2}(n)</math>, se dobi eksplicitno enačbo za število predstavitev ''n'' kot vsote dveh kvadratov:

: <math> r_{2}(n) = 4\left\lbrace \tau_{1}(n) - \tau_{3}(n)\right\rbrace \!\, . </math>

S podobnimi postopki je Jacobi pokazal, da je <math>r_{2}(n)=8\sigma(n)</math>, če je ''n'' sod in <math>r_{4}(n)</math> = 24-krat vsota sodih deliteljev ''n'', če je ''n'' lih. Podobne enačbe <math>r_{k}(n)</math> za <math>k=6,8,10</math> in 12 so dobili na podoben nančin, vendar so bolj zapleteni. Enačbe za <math>r_{k}(n)</math> so znane za vse lihe <math>k \le 24</math>. Za sode ''k'' je enačbe težje dobiti.

== Elementarni dokazi ==

V začetku 20. stoletja so dokaz poenostavili [[Edmund Landau|Landau]] in drugi matematiki. V prvi polovici 20. stoletja je nekaj matematikov verjelo, da obstaja hierarhija tehnik v matematiki in, da je praštevilski izrek »globoki« izrek, za katerega dokaz je potrebna [[kompleksna analiza]]. Metode s samo realnimi spremenljivkami niso veljale za ustrezne. Hardy je bil znani član te skupine. [http://www.math.columbia.edu/~goldfeld/ErdosSelbergDispute.pdf]

Formulacijo tega prepričanja je deloma omajal dokaz praštevilskega izreka, ki je temeljil na [[Wienrov tauberski izrek|Wienrovem tauberskem izreku]] iz teorije [[divergentna vrsta|divergentnih vrst]] iz leta 1932, čeprav bi bilo moč označiti »globino« Wienrovega izreka kot enako metodam kompleksne analize. Predstava »elementarnega dokaza« v teoriji števil ni točno določena, vendar se zdi da po navadi v grobem ustreza dokazom, ki jih je moč izvesti v [[Peanovi aksiomi|Peanovi aritmetiki]], in ne v močnejših teorijah kot je na primer aritmetika drugega reda. Obstajajo izjave Peanove aritmetike, ki jih je moč dokazati v [[aritmetika drugega reda|aritmetiki drugega reda]], ne pa v [[aritmetika prvega reda|aritmetiki prvega reda]]. Takšen zgled je na primer [[Paris-Harringtonov izrek]]. Drugače pa so v praksi takšni izreki redki. 

Selberg je našel [[elementarni dokaz]] praštevilskega izreka leta 1949, ki je uporabljal le prijeme iz teorije števil. Erdős je skoraj istočasno uporabil njegove zamisli in razdelal malo drugačen elementarni dokaz. Selbergovo delo je umirilo pojem »globine« za praštevilski izrek, in je pokazalo da so tehnično »elementarne« metode (oziroma Peanova aritmetika) močnejše kot so sprva pričakovali. Leta 1956 [[Basil Gordon|Gordon]] dokazal praštevilski izrek s pomočjo [[Stirlingova aproksimacija|Stirlingove aproksimacije]] za velike <math>n!</math>. Leta 2001 je Sudac pokazal, da je moč praštevilski izrek dokazati v [[primitivno rekurzivna aritmetika|primitivno rekurzivni aritmetiki]], veliko šibkejši teoriji kot je Peanova aritmetika.<ref>{{sktxt|Sudac|2001}}.</ref>

Avigad in sodelavci so leta 2005 napisali računalniško različico tega elementarnega dokaza v interaktivnem sistemu [[avtomatično dokazovanje izrekov|dokazovanja izrekov]] Isabelle.<ref>{{sktxt|Avigad|Donnelly|Gray|Raff|2005}}.</ref>

== Praštevilski izrek za aritmetična zaporedja ==

Naj <math>\pi_{d,a}(\xi)</math> označuje število praštevil v [[aritmetično zaporedje|aritmetičnem zaporedju]] ''a'', ''a'' + ''d'', ''a'' + 2''d'', ''a'' + 3''d'', … manjše od ''ξ''. Dirichlet in Legendre sta domnevala in La Vallée Poussin dokazal, da če sta ''a'' in ''d'' [[tuje število|tuji]], potem velja:

: <math> \pi_{d,a}(\xi) \sim \frac{1}{\phi(d)}\mathrm{Li}(\xi) \!\, , </math>

kjer je φ(·) [[Eulerjeva funkcija fi|Eulerjeva funkcija φ]]. Praštevila so porazdeljena enakomerno med razredi ostankov [''a''] [[modularna aritmetika|modulo]] ''d'' z D(''a'', ''d'') = 1. To je moč dokazati s podobno metodo, ki jo je uporabil Newman za svoj dokaz praštevilskega izreka.<ref>{{sktxt|Soprunov|1998}}.</ref>

Čeprav je posebej:

: <math> \pi_{4,1}(\xi) \sim \pi_{4,3}(\xi) \sim \frac{1}{2}\frac{\xi}{\log \xi} \!\, , </math>

so empirično praštevila kongruentna 3 pogostejša in v tej »praštevilski tekmi« skoraj vedno vodijo; prvi obrat nastopi sicer pri ''ξ'' = 3, nato pa šele pri ''ξ'' = 26.861.<ref name="Granville Martin MAA">{{sktxt|Granville|Martin|2006|pp=1-2}}.</ref>{{rp|1–2}} {{OEIS|id=A007350}} Vendar je Littlewood leta 1914 pokazal, da se predznak za funkcijo:

: <math> \pi_{4,1}(\xi) - \pi_{4,3}(\xi) \!\, </math>

neskončnokrat spremeni.<ref name="Granville Martin MAA" />{{rp|2}} Tako se vodstvo v tekmi izmenjuje nazaj in naprej neskončno mnogokrat. Pojav, da π<sub>4,3</sub>(''ξ'') večino časa vodi, je odkril Čebišov leta 1853, in se imenuje [[pristranost Čebišova]] ali včasih praštevilska tekma. Izraz ''praštevilska tekma'' je skoval [[Pál Turán|Turán]]. Praštevilska tekma se posploši za druge module in jo veliko raziskujejo. [[Andrew Granville|Granville]] in Martin sta podala temeljito razlago in pregled.<ref name="Granville Martin MAA" />

== Domene funkcije števila praštevil ==

Praštevilski izrek je ''asimptotičen'' rezultat. Zaradi tega se ga ne da uporabiti za določitev domene π(''ξ'').

Znane pa so nekatere meje definicijskega območja za π(''ξ''), kot je na primer [[Pierre Dusart|Dusartova]]:

: <math> \frac{\xi}{\ln \xi}\left(1+\frac{1}{\ln \xi}\right) < \pi(\xi) < \frac{\xi}{\ln \xi}\left(1+\frac{1}{\ln \xi}+\frac{2,51}{(\ln \xi)^2}\right) \!\, . </math>

Prva neenakost velja za vse ''ξ'' ≥ 599, druga pa za vse ''ξ'' ≥ 355991<ref>{{sktxt|Dusart|1998}}.</ref>.

Šibkejša, vendar včasih uporabna meja, je:

: <math> \frac {\xi}{\ln \xi + 2} < \pi(\xi) < \frac {\xi}{\ln \xi - 4} \!\, </math>

za ''ξ'' ≥ 55.<ref>{{sktxt|Rosser|1941}}.</ref> V Dusartovi disertaciji je moč najti malce močnejšo različico takšne neenakosti, ki velja za velike ''ξ''.

Dokaz La Vallée Poussina nakazuje naslednje. Za vsak ε > 0 obstaja takšen ''S'', da za vse ''x'' > ''S'' velja:

: <math> \frac {\xi}{\ln \xi - (1-\varepsilon)} < \pi(\xi) < \frac {\xi}{\ln \xi - (1+\varepsilon)} \!\, . </math>

== Približki za ''n''-to praštevilo ==

Kot posledica praštevilskega izreka izhaja asimptotičen izraz za ''n''-to praštevilo, označen kot ''p''<sub>''n''</sub>:

: <math>p_n \sim n \ln n \!\, .</math>

Boljši približek je:

: <math> p_n = n \ln n +  n \ln \ln n + \frac{n}{\ln n} \big( \ln \ln n - \ln n- 2 \big) 
+ \mathcal{O} \left( \frac {n (\ln \ln n)^2} {(\ln n)^2}\right).</math><ref>{{sktxt|Cipolla|1902}}.</ref>

[[Rosserjev izrek]] pravi, da je ''p''<sub>''n''</sub> večji od ''n'' ln ''n''. To je moč izboljšati z naslednjim parom mej<ref>{{sktxt|Bach|Shallit|1996|pp=233}}.</ref>{{rp|233}}:

: <math> n \ln n + n(\ln\ln n - 1) < p_n <  n \ln n + n \ln \ln n \quad\mbox{za } n \ge 6 \!\, . </math>

Leva neenakost je Dusartova in velja za ''n'' ≥ 2.<ref>{{sktxt|Dusart|1999}}.</ref>

== Podobnost za nerazcepne polinome v končnem obsegu ==

Obstaja podobna oblika praštevilskega izreka, ki opisuje »porazdelitev« [[nerazcepni polinom|nerazcepnih polinomov]] v [[kočni obseg|končnem obsegu]]. Ta oblika je na vso moč podobna klasičnemu praštevilskemu izreku.

Naj je ''F'' = GF(''q'') končni obseg s številom elementov ''q'', za poljubni ''q'' in naj je ''N''<sub>''n''</sub> število ''nerazcepnih'' [[polinom]]ov 1. reda v ''F'', katerega  [[stopnja polinoma|stopnja]] je enaka ''n''. Išče se takšne polinome s koeficienti izbranimi iz ''F'', ki se jih ne da zapisati kot produkte polinomov manjše stopnje. V tem primeru ti polinomi igrajo vlogo praštevil, saj so vsi polinomi 1. reda sestavljeni iz njihovih produktov. Pokazati je moč, da velja:

: <math>N_n \sim \frac{q^n}{n} \!\, . </math>

Če se piše ''ξ'' = ''q''<sup>''n''</sup>, potem je desna stran enaka:

: <math>\frac{\xi}{\log_q \xi} \!\, , </math>

kjer je podobnost bolj vidna. Ker obstaja natanko ''q''<sup>''n''</sup> polinomov 1. reda stopnje ''n'' (vključno z razcepnimi), se lahko zgoraj zapisano pove še drugače: če se naključno izbere polinom 1. reda stopnje ''n'', potem je verjetnost, da je nerazcepen, enaka približno 1/''n''.

Podobno obliko ima Riemannova domneva:

: <math> N_n = \frac{q^n}n + O\left(\frac{q^{n/2}}{n}\right) \!\, . </math>

Dokazi v takšnih oblikah so veliko preprostejši od klasičnih. Premisliti je treba po kombinatorični poti. Vsak element stopnje ''n'' razširitve ''F'' je koren nekega nerazcepnega polinoma, katerega stopnja ''d'' deli ''n''. S štetjem teh korenov na dva načina se izkaže, da velja:

: <math>q^n = \sum_{d\mid n} d N_d \!\, , </math>

kjer vsota poteka prek vseh [[delitelj]]ev ''d'' od ''n''.  [[Möbiusova inverzna formula|Möbiusov obrat]] potem vodi do:

: <math>N_n = \frac1n \sum_{d\mid n} \mu(n/d) q^d \!\, , </math>

kjer je μ(k) Möbiusova funkcija. To enačbo je poznal tudi Gauss. Glavni člen se pojavi pri ''d'' = ''n'', in ni težko omejiti preostalih členov. Izjava »Riemannove domneve« je odvisna od dejstva, da največji [[pravi delitelj]] ''n'' ne more biti večji od ''n''/2.

== Glej tudi ==

* [[abstraktna analitična teorija števil]]
* [[Landauov izrek o praštevilskih idealih]]
* [[Dirichletov praštevilski izrek]]
* [[Erdős-Kacev izrek]]

== Sklici ==

{{sklici|3}}

== Viri ==

{{refbegin|2}}
* {{navedi arXiv|last1= Avigad|first1= Jeremy|last2= Donnelly|first2= Kevin|last3= Gray|first3= David|last4= Raff|first4= Paul|title= A formally verified proof of the prime number theorem|arxiv= cs.AI/0509025|year= 2005|ref= harv}}
* {{navedi knjigo|last1= Bach|first1= Eric|authorlink1= Eric Bach|last2= Shallit|first2= Jeffrey|authorlink2= Jeffrey Shallit|title= Algorithmic Number Theory|volume= 1|year= 1996|publisher= MIT Press|isbn= 0-262-02405-5|ref= harv}}
* {{navedi revijo|last1= Cipolla|first1= Michele|title= La determinazione assintotica dell'n<sup>imo</sup> numero primo|year= 1902|journal= Matematiche Napoli|volume= 3|pages= 132-166|ref= harv}}
* {{navedi revijo|last1= Drnovšek|first1= Roman|authorlink1= Roman Drnovšek|title= Praštevilski dvojčki in procesor Pentium|journal= [[Presek (revija)|Presek]]|year= 1997|volume= 25|issue= 3|pages= 162-166|url= http://www.dlib.si/?URN=URN:NBN:SI:DOC-3TPWNTWN|accessdate= 2012-07-12|cobiss= 7866457|ref= harv}}
* {{navedi revijo|last1= Dusart|first1= Pierre|authorlink1= Pierre Dusart|title= Autour de la fonction qui compte le nombre de nombres premiers|url= http://www.unilim.fr/laco/theses/1998/T1998_01.html|work= Doktorska disertacija na [[Univerza v Limogesu|Univerzi v Limogesu]] (l'Université de Limoges)|year= 1998|ref= harv}}
* {{navedi revijo|last1= Dusart|first1= Pierre|url= http://www.ams.org/mcom/1999-68-225/S0025-5718-99-01037-6/S0025-5718-99-01037-6.pdf|title= The ''k''th prime is greater than ''k(ln k + ln ln k-1)'' for ''k''>=2|journal= [[Mathematics of Computation]]|year= 1999|volume= 68|page= 411–415|ref= harv}}
* {{navedi revijo|last1= Granville|first1= Andrew|authorlink1= Andrew Granville|title= Harald Cramér and the distribution of prime numbers|journal= Scandinavian Actuarial Journal|year= 1995|volume= 1|issue= |pages= 12–28|url= http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf|format= PDF|accessdate= 2012-07-12|ref= harv}}
* {{navedi revijo|last1= Granville|first1= Andrew|last2= Martin|first2= Greg|doi= 10.2307/27641834|date= 2006-01|title= Prime Number Races|journal= [[American Mathematical Monthly]]|volume= 113|issue= 1|pages= 1–33|url= http://www.dms.umontreal.ca/%7Eandrew/PDF/PrimeRace.pdf|jstor= 27641834|accessdate= 2012-07-13|ref= harv}}
* {{navedi revijo|last1= Hardy |first1= Godfrey Harold|authorlink1=Godfrey Harold Hardy|last2= Littlewood|first2= John Edensor|authorlink2=John Edensor Littlewood|lastauthoramp= yes|year= 1916|title= Contributions to the Theory of the Riemann Zeta-Function and the Theory of the Distribution of Primes|journal= [[Acta Mathematica]]|volume= 41|issue= |pages=119–196 |doi=10.1007/BF02422942|ref= harv}}
* {{navedi knjigo|last1= Hoffman|first1= Paul|title= The Man Who Loved Only Numbers|publisher= Hyperion|year= 1998|page= 227|isbn= 0-7868-8406-1|ref= harv}}
* {{navedi knjigo|last1= Ingham|first1= Albert Edward|authorlink1= Albert Edward Ingham|title= The Distribution of Prime Numbers|publisher= Cambridge University Press|date= 1990|isbn= 0-521-39789-8|ref= harv}}
* {{navedi revijo|last1= Platt|first1= David J.|title= Computing π(x) Analytically)|url= http://arxiv.org/abs/1203.5712|accessdate= 2012-07-25|id={{arxiv|1203.5712}}|ref= harv}}
* {{navedi revijo|last1= Pintz|first1= János|authorlink1= János Pintz|title= On Legendre's prime number formula|url= http://www.jstor.org/stable/2321863|journal= [[American Mathematical Monthly]]|date= 1980-09|volume= 87|issue= 9|pages= 733-735|ref= harv}}
* {{navedi revijo|last1= Rosser|first1= John Barkley|authorlink1= John Barkley Rosser|title= Explicit Bounds for Some Functions of Prime Numbers|journal= [[American Journal of Mathematics]]|volume= 63|issue= 1|year= 1941-01|pages= 211-232|ref= harv}}
* {{navedi revijo|last1= Schoenfeld|first1= Lowell|authorlink1= Lowell Schoenfeld|title= Sharper Bounds for the Chebyshev Functions θ(''x'') and ψ(''x''), II|journal= Mathematics of Computation|date= 1976-04|volume= 30|issue= 134|pages= 337–360|ref= harv}}
* {{navedi splet|last1= Soprunov|first1= Ivan|title= A short proof of the Prime Number Theorem for arithmetic progressions|url= http://www.math.umass.edu/~isoprou/pdf/primes.pdf|year= 1998|accessdate= 2012-07-13|language= en|ref= harv}}
* {{navedi revijo|last1= Sudac|first1= Olivier|title= The prime number theorem is PRA-provable|year= 2001-04|journal= Theoretical Computer Science|volume= 257|issue= 1–2|pages= 185-239|ref= harv}}
* {{navedi knjigo|last1= Vardi|first1= Ilan|title= An introduction to Analytic Number Theory|year= 1998|publisher= |location= |url= http://www.maths.ex.ac.uk/~mwatkins/zeta/vardi.html|ref= harv}}
* {{navedi revijo||last1= Von Koch|first1= Helge|authorlink1= Helge von Koch|title= Sur la distribution des nombres premiers|journal= Acta Mathematica|volume= 24|issue= 1|year= 1901-12|pages= 159-182|ref= harv}}
{{refend}}

== Zunanje povezave ==

* [http://www.scs.uiuc.edu/~mainzv/exhibitmath/exhibit/felkel.htm Razpredelnica praštevil Antona Felkla] {{ikona en}}
* {{MathWorld|urlname=PrimeFormulas|title=Prime Formulas}}
* {{MathWorld|urlname=PrimeNumberTheorem|title=Prime Number Theorem}}
* [http://planetmath.org/?op=getobj&from=objects&id=199 Praštevilski izrek] na [[PlanetMath]] {{ikona en}}
* [http://primes.utm.edu/howmany.shtml How Many Primes Are There?] in [http://primes.utm.edu/notes/gaps.html The Gaps between Primes], Chris Caldwell, [[Univerza Tennesseeja v Martinu]] (University of Tennessee at Martin) {{ikona en}}
* [http://www.ieeta.pt/~tos/primes.html Preglednice funkcij števil praštevil], Tomás Oliveira e Silva {{ikona en}}

[[Kategorija:Analitična teorija števil]]
[[Kategorija:Matematični izreki]]
[[Kategorija:Praštevila]]
[[Kategorija:Logaritmi]]
[[Kategorija:1896 v znanosti]]


[[pl:Liczba pierwsza#Twierdzenie o liczbach pierwszych]]