Primtalssatsen

Inom matematiken beskriver primtalssatsen (PNT) den asymptotiska fördelningen av primtalen bland de positiva heltalen . Det formaliserar den intuitiva idén att primtal blir mindre vanliga när de blir större genom att exakt kvantifiera hastigheten med vilken detta inträffar. Satsen bevisades oberoende av Jacques Hadamard och Charles Jean de la Vallée Poussin 1896 med hjälp av idéer som introducerades av Bernhard Riemann (i synnerhet Riemanns zeta-funktion ).

Den första sådan fördelning som hittats är π ( N ) ~ N / log( N ) , där π ( N ) är primtalsfunktionen (antalet primtal mindre än eller lika med N ) och log( N ) är den naturliga logaritmen av N. _ Detta betyder att för tillräckligt stor N är sannolikheten att ett slumpmässigt heltal som inte är större än N är primtal mycket nära 1 / log( N ) . Följaktligen är ett slumpmässigt heltal med högst 2 n siffror (för tillräckligt stort n ) ungefär hälften så troligt att vara primtal som ett slumpmässigt heltal med högst n siffror. Till exempel, bland de positiva heltal på högst 1000 siffror, är ungefär en av 2300 primtal ( log(10 ¹⁰⁰⁰ ) ≈ 2302.6) , medan bland positiva heltal på högst 2000 siffror är ungefär en av 4600 primtal ( log(10 ^{2000 )} ) ≈ 4605,2 ). Med andra ord, det genomsnittliga gapet mellan på varandra följande primtal bland de första N heltal är ungefär log( N ) .

Påstående

Graf som visar förhållandet mellan primräkningsfunktionen π ( x ) och två av dess approximationer, x / log x och Li( x ) . När x ökar (notera att x -axeln är logaritmisk) tenderar båda förhållandena mot 1. Förhållandet för x / log x konvergerar ovanifrån mycket långsamt, medan förhållandet för Li( x ) konvergerar snabbare underifrån.

Log-log plot visar absolut fel av x / log x och Li( x ) , två approximationer till primräkningsfunktionen π ( x ) . Till skillnad från förhållandet ökar skillnaden mellan π ( x ) och x / log x utan gräns när x ökar. Å andra sidan Li( x ) − π ( x ) tecken oändligt många gånger.

Låt π ( x ) vara primräkningsfunktionen definierad som antalet primtal mindre än eller lika med x , för ett reellt tal x . Till exempel, π (10) = 4 eftersom det finns fyra primtal (2, 3, 5 och 7) mindre än eller lika med 10. Primtalssatsen säger då att x / log x är en bra approximation till π ( x ) (där log här betyder den naturliga logaritmen), i den meningen att gränsen för kvoten av de två funktionerna π ( x ) och x / log x när x ökar utan gräns är 1:

$\lim _{x\to \infty }{\frac {\;\pi (x)\;}{\;\ vänster[{\frac {x}{\log(x)}}\right]\;}}=1,$

känd som den asymptotiska lagen om fördelningen av primtal . Med hjälp av asymptotisk notation kan detta resultat räknas om som

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

Denna notation (och satsen) säger inget om gränsen för skillnaden mellan de två funktionerna när x ökar utan gräns. Istället säger satsen att x / log x approximerar π ( x ) i den meningen att det relativa felet för denna approximation närmar sig 0 när x ökar utan gräns.

Primtalssatsen är ekvivalent med påståendet att det n: te primtalet p _n uppfyller

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

den asymptotiska notationen betyder återigen att det relativa felet för denna approximation närmar sig 0 när n ökar utan gräns. Till exempel 2 × 10 ¹⁷ :e primtalet 8 512 677 386 048 191 063 och ( 2 × 10 ¹⁷ )log( 2 × 10 ¹⁷ ) avrundas till 7 967 418 752 4 4 8 relativa fel av 7 a 4 4 4 8 relativt. %.

Å andra sidan är följande asymptotiska relationer logiskt ekvivalenta:

${\begin{aligned}\lim _{x\rightarrow \ infty }{\frac {\pi (x)\log x}{x}}&=1,\\\lim _{x\högerpil \infty }{\frac {\pi (x)\log \pi (x )}{x}}&=1.\end{aligned}}$

Som beskrivs nedan är primtalssatsen också ekvivalent med

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

där ϑ och ψ är den första och den andra Chebyshev-funktionen respektive, och till

$\lim _{x\to \infty }{\frac {M(x)}{x}}=0,$

där $M(x)=\summa _{n\leq x}\mu (n)$ är Mertens-funktionen .

Historien om beviset för den asymptotiska lagen om primtal

Baserat på tabellerna av Anton Felkel och Jurij Vega antog Adrien-Marie Legendre 1797 eller 1798 att π ospecificerade ( a ) approximeras av funktionen a / ( A log a + B ) , där A och B är konstanter. I den andra upplagan av sin bok om talteori (1808) gjorde han sedan en mer exakt gissning , med A = 1 och B = -1,08366 . Carl Friedrich Gauss övervägde samma fråga vid 15 eller 16 års ålder "år 1792 eller 1793", enligt sitt eget minne 1849. År 1838 kom Peter Gustav Lejeune Dirichlet med sin egen approximationsfunktion, den logaritmiska integralen li( x ) (under den något annorlunda formen av en serie, som han förmedlade till Gauss). Både Legendres och Dirichlets formler innebär samma förmodade asymptotiska ekvivalens av π ( x ) och x / log( x ) som anges ovan, även om det visade sig att Dirichlets approximation är betydligt bättre om man tar hänsyn till skillnaderna istället för kvoter.

I två artiklar från 1848 och 1850 försökte den ryske matematikern Pafnuty Chebyshev bevisa den asymptotiska lagen för distribution av primtal. Hans arbete är anmärkningsvärt för användningen av zeta-funktionen ζ ( s ) , för verkliga värden av argumentet " s ", som i verk av Leonhard Euler , så tidigt som 1737. Chebyshevs papper föregick Riemanns berömda memoarbok från 1859, och han lyckades att bevisa en något svagare form av den asymptotiska lagen, nämligen att om gränsen som x går till oändligheten av π ( x ) / ( x / log( x )) överhuvudtaget existerar, så är den nödvändigtvis lika med ett. Han kunde villkorslöst bevisa att detta förhållande är begränsat ovanför och under av två uttryckligen givna konstanter nära 1, för alla tillräckligt stora x . Även om Chebyshevs papper inte bevisade primtalssatsen, var hans uppskattningar för π ( x ) tillräckligt starka för att han skulle bevisa Bertrands postulat att det finns ett primtal mellan n och 2 n för vilket heltal som helst n ≥ 2 .

En viktig artikel angående fördelningen av primtal var Riemanns memoarer från 1859 " Om antalet primtal mindre än en given magnitude ", den enda tidningen han någonsin skrivit om ämnet. Riemann introducerade nya idéer i ämnet, främst att fördelningen av primtal är intimt kopplad till nollorna i den analytiskt utökade Riemann zetafunktionen för en komplex variabel. I synnerhet är det i denna artikel som idén att tillämpa metoder för komplex analys för att studera den verkliga funktionen π ( x ) uppstår. För att utvidga Riemanns idéer, hittades två bevis för den asymptotiska lagen om fördelningen av primtal oberoende av Jacques Hadamard och Charles Jean de la Vallée Poussin och dök upp samma år (1896). Båda bevisen använde metoder från komplex analys, och fastställde som ett huvudsteg i beviset att Riemanns zeta-funktion ζ ( s ) är icke-noll för alla komplexa värden av variabeln s som har formen s = 1 + it med t > 0 .

Under 1900-talet blev Hadamards och de la Vallée Poussins sats också känd som Prime Number Theorem. Flera olika bevis på det hittades, inklusive de "elementära" bevisen från Atle Selberg och Paul Erdős (1949). Hadamards och de la Vallée Poussins originalbevis är långa och genomarbetade; senare bevis introducerade olika förenklingar genom användningen av Tauberiska teorem men förblev svårsmälta. Ett kort bevis upptäcktes 1980 av den amerikanske matematikern Donald J. Newman . Newmans bevis är utan tvekan det enklaste kända beviset för satsen, även om det är icke-elementärt i den meningen att det använder Cauchys integralsats från komplex analys.

Bevisskiss

Här är en skiss av beviset som refereras till i en av Terence Taos föreläsningar. Liksom de flesta bevis på PNT börjar den med att omformulera problemet i termer av en mindre intuitiv, men bättre uppförd, primtalsräkningsfunktion. Tanken är att räkna primtal (eller en relaterad mängd som primtalsmängden) med vikter för att komma fram till en funktion med jämnare asymptotiskt beteende. Den vanligaste sådana generaliserade räknefunktionen är Chebyshev-funktionen ψ ( x ) , definierad av

$\psi (x)=\!\!\!\!\sum _{\stackrel {p^{k}\leq x,}{p{\text{ är primtal}}}}\!\! \!\!\log p\;.$

Detta skrivs ibland som

$\psi (x)=\summa _{n\leq x}\Lambda (n)\;,$

där Λ ( n ) är von Mangoldt-funktionen , nämligen

$\Lambda (n)={\begin{cases}\log p&{\text{ if }}n=p^{k}{\text{ för något primtal }}p{\text{ och heltal }} k\geq 1,\\0&{\text{annars.}}\end{fall}}$

Det är nu relativt enkelt att kontrollera att PNT motsvarar påståendet att

$\lim _{x\to \infty }{\frac {\psi (x)}{x}}=1\;.$

Detta följer faktiskt av de lätta uppskattningarna

$\psi (x) =\summa _{\stackrel {p\leq x}{p{\text{ är primtal}}}}\log p\left\lfloor {\frac {\log x}{\log p}}\right\rfloor \leq \sum _{\stackrel {p\leq x}{p{\text{ är primtal}}}}\log x=\pi (x)\log x$

och (med stor O- notation ) för valfri ε > 0 ,

$\psi (x)\geq \!\!\!\!\sum _{\stackrel {x^{1-\varepsilon }\leq p\leq x}{p{\text{ är primtal}} }}\!\!\!\!\log p\geq \!\!\!\!\summa _{\stackrel {x^{1-\varepsilon }\leq p\leq x}{p{\text { är primtal}}}}\!\!\!\!(1-\varepsilon )\log x=(1-\varepsilon )\left(\pi (x)+O\left(x^{1-\ varepsilon }\right)\right)\log x\;.$

Nästa steg är att hitta en användbar representation för ψ ( x ) . Låt ζ ( s ) vara Riemanns zeta-funktion. Det kan visas att ζ ( s ) är relaterat till von Mangoldt - funktionen Λ ( n ) , och därmed till ψ ( x ) , via relationen

$-{\frac {\zeta '(s)}{\zeta (s)}}=\sum _{n=1}^{\infty }\Lambda (n)\,n^{-s} \;.$

En delikat analys av denna ekvation och relaterade egenskaper hos zetafunktionen, med hjälp av Mellin-transformen och Perrons formel , visar att för icke-heltal x ekvationen

$\psi (x)=x\;-\;\log(2\pi )\;- \sum \limits _{\rho :\,\zeta (\rho )=0}{\frac {x^{\rho }}{\rho }}$

gäller, där summan är över alla nollor (triviala och icke-triviala) i zetafunktionen. Denna slående formel är en av de så kallade explicita formlerna för talteorin och antyder redan det resultat vi vill bevisa, eftersom termen x (som hävdas vara den korrekta asymptotiska ordningen av ψ ( x ) ) visas till höger -hand sida, följt av (förmodligen) asymptotiska termer av lägre ordning.

Nästa steg i bevisningen innebär en studie av zetafunktionens nollor. De triviala nollorna −2, −4, −6, −8, ... kan hanteras separat:

$\sum _{n=1}^{\infty }{\frac {1}{2n\ ,x^{2n}}}=-{\frac {1}{2}}\log \left(1-{\frac {1}{x^{2}}}\right),$

som försvinner för stora x . De icke-triviala nollorna, nämligen de på den kritiska remsan 0 ≤ Re( s ) ≤ 1 , kan potentiellt vara av en asymptotisk ordning jämförbar med huvudtermen x om Re( ρ ) = 1 , så vi måste visa att alla nollor har reella del strikt mindre än 1.

Icke-försvinnande på Re( s ) = 1

För att göra detta tar vi för givet att ζ ( s ) är meromorf i halvplanet Re( s ) > 0 , och är analytisk där förutom en enkel pol vid s = 1 , och att det finns en produktformel

$\zeta (s)=\prod _{p}{\frac {1}{1-p^{-s}}}$

för Re ( s ) > 1 . Denna produktformel följer av förekomsten av unik primfaktorisering av heltal, och visar att ζ ( s ) aldrig är noll i denna region, så att dess logaritm definieras där och

$\log \zeta (s)=-\summa _{p}\log \left(1-p^{-s}\right)=\summa _{p,n}{\frac {p^{ -ns}}{n}}\;.$

Skriv s = x + iy ; sedan

${\big |}\zeta (x+iy){\big |}=\exp \left(\summa _{n,p}{\frac {\cos ny\log p}{np^{nx }}}\höger)\;.$

Observera nu identiteten

$3+4\cos \phi +\cos 2\phi =2(1+\cos \phi )^ {2}\geq 0\;,$

så att

$\left|\zeta (x)^ {3}\zeta (x+iy)^{4}\zeta (x+2iy)\right|=\exp \left(\summa _{n,p}{\frac {3+4\cos(ny\ log p)+\cos(2ny\log p)}{np^{nx}}}\right)\geq 1$

för alla x > 1 . Antag nu att ζ (1 + iy ) = 0 . Visst y inte noll, eftersom ζ ( s ) har en enkel pol vid s = 1 . Antag att x > 1 och låt x tendera mot 1 uppifrån. Eftersom $\zeta (s)$ har en enkel pol vid s = 1 och ζ ( x + 2 iy ) förblir analytisk, tenderar den vänstra sidan i föregående olikhet till 0, en motsägelse.

Slutligen kan vi dra slutsatsen att PNT är heuristiskt sant. För att noggrant slutföra beviset finns det fortfarande allvarliga tekniska detaljer att övervinna, på grund av det faktum att summeringen över zeta-nollor i den explicita formeln för ψ ( x ) inte konvergerar absolut utan endast villkorligt och i en "huvudvärde"-bemärkelse. Det finns flera sätt att kringgå detta problem, men många av dem kräver ganska känsliga komplex-analytiska uppskattningar. Edwards bok ger detaljerna. En annan metod är att använda Ikeharas Tauberian-sats , även om denna sats i sig är ganska svår att bevisa. DJ Newman observerade att den fulla styrkan av Ikeharas sats inte behövs för primtalssatsen, och man kan komma undan med ett specialfall som är mycket lättare att bevisa.

Newmans bevis för primtalssatsen

DJ Newman ger ett snabbt bevis på primtalssatsen (PNT). Beviset är "icke-elementärt" i kraft av att det förlitar sig på komplex analys, men använder endast elementära tekniker från en första kurs i ämnet: Cauchys integralformel , Cauchys integralsats och uppskattningar av komplexa integraler. Här är en kort skiss av detta bevis. Se för fullständiga detaljer.

Beviset använder samma förberedelser som i föregående avsnitt förutom i stället för funktionen ${\textstyle \psi }$ , Chebyshev -funktionen ${\textstyle \quad \vartheta (x)= \sum _{p\leq x}\log p}$ används, vilket erhålls genom att ta bort några av termerna från serien för ${\textstyle \psi }$ . Det är lätt att visa att PNT är ekvivalent med $\lim _{x\to \infty }\vartheta (x)/x=1$ . Likaså istället för $-{\frac {\zeta '(s)}{\zeta (s)}}$ funktionen ${\displaystyle \Phi (s)=\sum _{p\leq x}\log p\,\,p^{-s}} används, vilket erhålls genom att ta bort några termer$ i serien för $-{\frac {\zeta '(s)}{\zeta (s)}}$ . Funktionerna $\Phi (s)$ och $-\zeta '(s)/\zeta (s)$ skiljer sig åt med en holomorf funktion på $\Re s=1$ . Eftersom, som visats i föregående avsnitt, $\zeta (s)$ inga nollor på linjen $\Re s=1$ , $\Phi (s)-{\frac {1}{s-1}}$ har inga singulariteter på $\Re s=1$ .

En ytterligare information som behövs i Newmans bevis, och som är nyckeln till uppskattningarna i hans enkla metod, är att $\vartheta (x)/x$ är avgränsad. Detta bevisas med en genialisk och enkel metod tack vare Chebyshev.

Integration med delar visar hur $\vartheta (x)$ och $\Phi (s)$ är relaterade. För $\Re s>1$ ,

$\Phi (s)=\int _{1}^{\infty }x^{-s}d\vartheta (x)=s\int _{1}^{\infty }\vartheta (x) x^{-s-1}\,dx=s\int _{0}^{\infty }\vartheta (e^{t})e^{-st}\,dt.$

Newmans metod bevisar PNT genom att visa integralen

$I=\int _{0}^{\infty }\left({\frac {\vartheta (e^{t})}{e^{t}}}-1\right)\,dt.$

konvergerar, och därför går integranden till noll som ${\displaystyle t\to \infty } ,$ som är PNT. I allmänhet innebär inte konvergensen av den felaktiga integralen att integranden går till noll i oändligheten, eftersom den kan svänga, men eftersom $\vartheta$ ökar är det lätt att visa i detta fall.

För att visa konvergensen av ${\displaystyle I} ,$ låt för $\Re z>0$

$g_{T}(z)=\int _{0}^{T}f(t)e^{-zt}\ ,dt$ och $g(z)=\int _{0}^{\infty }f(t)e^{-zt} \,dt$ där $f(t)={\frac {\vartheta (e^{t})}{e^{t}}}- 1$

sedan

$\lim _{T\to \infty }g_{T}(z )=g(z)={\frac {\Phi (s)}{s}}-{\frac {1}{s-1}}\quad \quad {\text{där}}\quad z=s -1$

som är lika med en funktion holomorf på linjen $\Re z=0$ .

Konvergensen av integralen $I$ , och därmed PNT, bevisas genom att visa att $\lim _{T\to \infty }g_{T }(0)=g(0)$ . Detta innebär att gränserna ändras eftersom det kan skrivas ${\textstyle \lim _{T\to \infty } \lim _{z\to 0}g_{T}(z)=\lim _{z\to 0}\lim _{T\to \infty }g_{T}(z)} och därför klassificerad som$ en tauberian sats.

Skillnaden $g(0)-g_{T}(0)$ uttrycks med Cauchys integralformel och visas sedan som liten för $T$ stor genom att uppskatta integranden . Fixa $R>0$ och $\delta >0$ så att $g(z)$ är holomorft i regionen där ${\displaystyle |z|\leq R{\text{ och }}\Re z\geq -\delta } ,$ och låt $C$ vara gränsen för denna region. Eftersom 0 är i det inre av regionen, ger Cauchys integralformel

$g(0)-g_{T}(0)={\frac {1}{2\pi i}}\int _{C}\left(g(z)-g_ {T}(z)\right){\frac {dz}{z}}={\frac {1}{2\pi i}}\int _{C}\left(g(z)-g_{T }(z)\höger)F(z){\frac {dz}{z}}$

där $F(z)=e^{zT}\left(1+{\frac {z^{2}}{R^{2 }}}\right)$ är faktorn som introduceras av Newman, som inte ändrar integralen eftersom $F$ är hel och $F(0)=1$ .

För att uppskatta integralen, bryt konturen $C$ i två delar, $C=C_{+}+C_{-}$ där ${\displaystyle C_{+}=C\cap \left\{z\,\vert \,\Re z>0\right\}} och C − ∩$ { ${ -}\cap \left\{\Re z\leq 0\right\}}$ . Sedan $g(0)-g_{T}(0)=\int _{C_{+}}\int _{T}^{\infty }H(t, z)dtdz-\int _{C_{-}}\int _{0}^{T}H(t,z)dtdz+\int _{C_{-}}g(z)F(z){\frac {dz}{2\pi iz}}$ där $H(t,z)=f(t)e ^{-tz}F(z)/2\pi i$ . Eftersom $\vartheta (x)/x$ , och därmed $f(t)$ , är begränsad, låt $B$ vara en övre gräns för absolutvärdet av $f(t)$ . Detta bundna tillsammans med uppskattningen $|F|\leq 2\exp(T\Re z)|\Re z|/R$ för $|z|=R$ ger att den första integralen i absolut värde är $\leq B/R$ . Integranden över $C_{-}$ i den andra integralen är hel , så med Cauchys integralsats kan konturen $C_{-}$ modifieras till en halvcirkel med radien $R$ i det vänstra halvplanet utan att ändra integralen, och samma argument som för den första integralen ger absolutvärdet för den andra integralen är $\leq B/R$ . Om man slutligen låter $T\to \infty$ , går den tredje integralen till noll eftersom $e^{zT}$ och därmed $F$ går till noll på konturen. Kombinera de två uppskattningarna och gränsen får

$\limsup _{T\to \infty }|g(0)-g_{T}(0)|\leq {\frac {2B}{R}}.$

Detta gäller för alla $R$ så $\lim _{T\to \infty }g_{T}(0)=g(0)$ , och PNT följer.

Primräkningsfunktion i termer av den logaritmiska integralen

I en handskriven anteckning om ett nytryck av sin tidning från 1838 " Sur l'usage des séries infinies dans la théorie des nombres ", som han skickade till Gauss, gissade Dirichlet (under en något annorlunda form som tilltalar en serie snarare än en integral) att en ännu bättre approximation till π ( x ) ges av den offset logaritmiska integralfunktionen Li ( x ) , definierad av

$\operatörsnamn {Li} (x)=\int _{2}^{x}{\frac {dt}{\log t}}=\operatörsnamn {li} (x)-\operatörsnamn {li} ( 2).$

Faktum är att denna integral starkt tyder på uppfattningen att "densiteten" av primtal runt t bör vara 1 / log t . Denna funktion är relaterad till logaritmen genom den asymptotiska expansionen

$\operatorname {Li} (x)\sim {\frac {x}{ \log x}}\summa _{k=0}^{\infty }{\frac {k!}{(\log x)^{k}}}={\frac {x}{\log x}} +{\frac {x}{(\log x)^{2}}}+{\frac {2x}{(\log x)^{3}}}+\cdots$

Så, primtalssatsen kan också skrivas som π ( x ) ~ Li( x ) . Faktum är att i en annan tidning 1899 bevisade de la Vallée Poussin det

$\pi (x)=\operatörsnamn {Li} (x)+O\left(xe^{ -a{\sqrt {\log x}}}\right)\quad {\text{som }}x\to \infty$

för någon positiv konstant a , där O (...) är den stora O- notationen . Detta har förbättrats till

$\pi (x)=\operatörsnamn {li } (x)+O\left(x\exp \left(-{\frac {A(\log x)^{\frac {3}{5}}}{(\log \log x)^{\frac {1}{5}}}}\right)\right)$ där $A=0,2098$ .

Under 2016 visade Trudgian en explicit övre gräns för skillnaden mellan $\pi (x)$ och $\operatorname {li} (x)$ :

${\big |}\pi (x)-\operatörsnamn {li} (x){\big |}\leq 0,2795 {\frac {x}{(\log x)^{3/4}}}\exp \left(-{\sqrt {\frac {\log x}{6.455}}}\right)$

för $x\geq 229$ .

Kopplingen mellan Riemanns zeta-funktion och π ( x ) är en anledning till att Riemann-hypotesen har stor betydelse i talteorin: om den etableras skulle den ge en mycket bättre uppskattning av felet i primtalssatsen än vad som är tillgängligt idag. Mer specifikt Helge von Koch 1901 att om Riemann-hypotesen är sann kan feltermen i ovanstående relation förbättras till

$\pi (x)=\operatörsnamn {Li} (x)+O\left({\sqrt {x}}\log x \höger)$

(denna sista uppskattning motsvarar faktiskt Riemanns hypotes). Konstanten som är involverad i den stora O- notationen uppskattades 1976 av Lowell Schoenfeld : antar Riemann-hypotesen,

${\big |}\pi (x)-\operatörsnamn {li} (x){\big |}<{\frac {{\sqrt {x}}\log x} {8\pi }}$

för alla x ≥ 2657 . Han härledde också en liknande gräns för Chebyshev primräkningsfunktionen ψ :

${\big |}\psi (x)-x{\big |}<{\frac {{\sqrt {x}}(\log x)^{2 }}{8\pi }}$

  för alla x ≥ 73,2 . Denna senare gräns har visat sig uttrycka en varians till medelpotenslag (när den betraktas som en slumpmässig funktion över heltal) och 1 /   f -   brus och även motsvara Tweedie-föreningens Poisson-fördelning . (Tweedie-fördelningarna representerar en familj av skalinvarianta fördelningar som fungerar som konvergensfokus för en generalisering av den centrala gränssatsen .)

Den logaritmiska integralen li( x ) är större än π ( x ) för "små" värden på x . Detta beror på att det (i någon mening) inte räknas primtal, utan primtal, där en potens p ⁿ av ett primtal p räknas som 1 /   n   av ett primtal. Detta tyder på att li( x ) vanligtvis bör vara större än π ( x ) med ungefär $\ {\tfrac {1}{2}}\operatörsnamn {li} ({\sqrt { x}})\ ,$ och bör i synnerhet alltid vara större än π ( x ) . Men 1914 bevisade JE Littlewood att $\ \pi (x)-\operatörsnamn {li} (x)\$ ändrar tecken oändligt ofta. Det första värdet på x där π ( x ) överstiger li( x ) är förmodligen runt x ~ 10 ³¹⁶ ; se artikeln om Skewes nummer för mer information. (Å andra sidan är den offsetlogaritmiska integralen Li( x ) mindre än π ( x ) redan för x = 2 ; faktiskt, Li(2) = 0 , medan π (2) = 1 .)

Elementära bevis

Under första hälften av 1900-talet trodde vissa matematiker (särskilt GH Hardy ) att det finns en hierarki av bevismetoder i matematik beroende på vilken typ av tal ( heltal , reella , komplexa ) ett bevis kräver, och att primtalssatsen (PNT) är ett "djupt" teorem på grund av att det kräver komplex analys . Denna övertygelse skakades något av ett bevis för PNT baserat på Wieners tauberiska teorem , även om detta kunde sättas åt sidan om Wieners teorem ansågs ha ett "djup" som motsvarar det för komplexa variabla metoder.

I mars 1948 etablerade Atle Selberg , med "elementära" medel, den asymptotiska formeln

$\vartheta (x)\log(x) +\summa \limits _{p\leq x}{\log(p)}\ \vartheta \left({\frac {x}{p}}\right)=2x\log(x)+O(x)$

var

$\vartheta (x)=\summa \limits _{p\leq x}{\log(p)}$

för primtal s . I juli samma år hade Selberg och Paul Erdős erhållit elementära bevis för PNT, båda med Selbergs asymptotiska formel som utgångspunkt. Dessa bevis lade effektivt upp föreställningen att PNT var "djup" i den meningen, och visade att tekniskt "elementära" metoder var mer kraftfulla än vad man trodde var fallet. Se en artikel av Dorian Goldfeld om historien om PNT:s elementära bevis, inklusive Erdős–Selbergs prioritetstvist .

Det finns en viss debatt om betydelsen av Erdős och Selbergs resultat. Det finns ingen rigorös och allmänt accepterad definition av begreppet elementärt bevis i talteorin, så det är inte klart exakt i vilken mening deras bevis är "elementärt". Även om den inte använder komplex analys, är den i själva verket mycket mer teknisk än standardbeviset för PNT. En möjlig definition av ett "elementärt" bevis är "ett som kan utföras i första ordningens Peano-aritmetik ." Det finns talteoretiska påståenden (till exempel Paris–Harrington-satsen ) som kan bevisas med andra ordningens men inte första ordningens metoder, men sådana satser är sällsynta hittills. Erdős och Selbergs bevis kan säkert formaliseras i Peano-arithmetik, och 1994 bevisade Charalambos Cornaros och Costas Dimitracopoulos att deras bevis kan formaliseras i ett mycket svagt fragment av PA, nämligen ₀ I Δ + exp . Detta tar dock inte upp frågan om huruvida standardbeviset för PNT kan formaliseras i PA.

Datorverifieringar

År 2005, Avigad et al. använde Isabelles teorembevisare för att ta fram en datorverifierad variant av Erdős–Selberg-beviset för PNT. Detta var det första maskinverifierade beviset för PNT. Avigad valde att formalisera Erdős–Selberg-beviset snarare än ett analytiskt bevis, för även om Isabelles bibliotek vid den tiden kunde implementera begreppen gräns, derivat och transcendental funktion , hade det nästan ingen teori om integration att tala om.

2009 använde John Harrison HOL Light för att formalisera ett bevis med komplex analys . Genom att utveckla det nödvändiga analytiska maskineriet, inklusive Cauchy-integralformeln , kunde Harrison formalisera "ett direkt, modernt och elegant bevis istället för det mer involverade 'elementära' Erdős–Selberg-argumentet".

Primtalssats för aritmetiska progressioner

Låt π _{d , a} ( x ) beteckna antalet primtal i det aritmetiska forloppet a , a + d , a + 2 d , a + 3 d , ... som är mindre än x . Dirichlet och Legendre gissade, och de la Vallée Poussin bevisade, att om a och d är coprime , då

$\pi _{d,a}(x)\sim {\frac {\operatörsnamn {Li} (x)}{\varphi (d)}}\ ,$

där φ är Eulers totientfunktion . Med andra ord är gcd( a , d ) = 1 primtalen fördelade jämnt mellan restklasserna [ a ] ​​modulo d med . Detta är starkare än Dirichlets sats om aritmetiska progressioner (som bara säger att det finns en oändlighet av primtal i varje klass) och kan bevisas med liknande metoder som Newman använder för sitt bevis på primtalssatsen.

Siegel –Walfisz-satsen ger en bra uppskattning för fördelningen av primtal i restklasser.

Bennett et al. bevisade följande uppskattning som har explicita konstanter A och B (sats 1.3): Låt d $\geq 3$ vara ett heltal och låt a vara ett heltal som är coprime till d . Sedan finns det positiva konstanter A och B så att

$\left|\pi _{d,a}(x)-{\frac {\ \operatörsnamn {Li} (x)\ }{\ \varphi (d)\ }}\right|<{\frac {A\ x}{\ (\log x)^{2}\ }}\quad {\text{ för alla }}\quad x\geq B \ ,$

var

$A={\frac {1}{\ 840\ }}\quad {\text{ if }}\quad 3\leq d\leq 10^{4}\quad {\text{ och }}\quad A={\frac {1}{\ 160\ }}\quad {\text{ if }}\quad d>10 ^{4}~,$

och

$B=8\cdot 10^{9}\quad {\text{ if }}\quad 3\leq d\leq 10^{5}\quad {\text{ och }}\quad B=\exp (\ 0.03\ {\sqrt {d\ }}\ (\log {d})^{3}\ )\quad {\text{ if }}\quad d>10^{5}\ .$

Primtalslopp

Rita av funktionen $\ \pi (x;4,3)-\pi (x;4,1)\$ för n ≤ 30000

Även om vi har i synnerhet

$\pi _{4,1}(x)\sim \pi _{4,3}(x)\ ,$

empiriskt är de primtal som är kongruenta med 3 fler och ligger nästan alltid före i denna "primtalsras"; den första omkastningen sker vid x = 26861 . Men Littlewood visade 1914 att det finns oändligt många teckenändringar för funktionen

$\pi _{4,1}(x)-\pi _{4,3}(x)~,$

så ledningen i loppet växlar fram och tillbaka oändligt många gånger. Fenomenet att π _4,3 ( x ) ligger före för det mesta kallas Chebyshevs bias . Primtalsrasen generaliserar till andra moduler och är föremål för mycket forskning; Pál Turán frågade om det alltid är så att π ( x ; a , c ) och π ( x ; b , c ) byter plats när a och b är coprime till c . Granville och Martin ger en grundlig utläggning och översikt.

Icke-asymptotiska gränser för primräkningsfunktionen

Primtalssatsen är ett asymptotiskt resultat. Det ger en ineffektiv gräns på π ( x ) som en direkt konsekvens av definitionen av gränsen: för alla ε > 0 finns ett S så att för alla x > S ,

$(1-\varepsilon ){\frac {x}{\log x}}\;<\;\pi (x)\;<\;(1+\varepsilon ){\frac {x}{\ log x}}\;.$

Men bättre gränser för π ( x ) är kända, till exempel Pierre Dusarts

${\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}\right)\;<\;\pi (x)\;<\; {\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}+{\frac {2.51}{(\log x)^{2}}}\right )\;.$

Den första olikheten gäller för alla x ≥ 599 och den andra för x ≥ 355991 .

En svagare men ibland användbar gräns för x ≥ 55 är

${\frac {x}{\log x+2}}\;<\;\pi (x)\;<\;{\frac {x}{\log x-4}}\;.$

I Pierre Dusarts avhandling finns starkare versioner av denna typ av ojämlikhet som är giltiga för större x . Senare under 2010 bevisade Dusart:

${\begin{aligned}{\frac {x}{\log x-1}}\;&<\;\pi (x)&&{\text{ för }}x\geq 5393\;,{ \text{ och }}\\\pi (x)\;&<\;{\frac {x}{\log x-1.1}}&&{\text{ för }}x\geq 60184\;.\end {Justerat}}$

Beviset av de la Vallée Poussin innebär följande: För varje ε > 0 , finns det ett S så att för alla x > S ,

${\frac {x}{\log x-(1-\varepsilon )}}\;<\;\pi (x)\;<\;{\frac {x}{\log x-(1 +\varepsilon )}}\;.$

Approximationer för det n: te primtalet

Som en konsekvens av primtalssatsen får man ett asymptotiskt uttryck för det n :te primtalet, betecknat med p _n :

$p_{n}\sim n\log n.$

En bättre uppskattning är

${\frac {p_{n}}{n}}=\log n+\log \log n-1+{\frac {\log \log n-2}{\log n}}-{\frac {(\log \log n)^{2}-6\log \log n+11}{2(\log n)^{2}}}+o\left({\frac {1}{(\log n)^{2}}}\höger).$

Återigen med tanke på det 2 × 10 ^{17 :} e primtalet 8 512 677 386 048 191 063 , ger detta en uppskattning på 8 512 681 315 554 715 386 ; de första 5 siffrorna matchar och det relativa felet är cirka 0,00005 %.

Rossers teorem säger det

$p_{n}>n\log n.$

Detta kan förbättras med följande par av gränser:

$\log n+\log \log n-1<{\frac {p_{ n}}{n}}<\log n+\log \log n\quad {\text{för }}n\geq 6.$

Tabell över π ( x ) , x / log x , och li( x )

Tabellen jämför exakta värden för π ( x ) med de två approximationerna x / log x och li( x ) . Den sista kolumnen, x / π ( x ) , är det genomsnittliga primtalsgapet under 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,5 00
10 2	25	3.3	1,151	5.1	4 000
10 3	168	23 , .0	1,161	10 , .0	5,952
10 4	1 229	143,0 _	1,132	17 , .0	8,137
10 5	9 592	906,0 _	1,104	38 , .0	10,425
10 6	78 498	6 116,0 _	1,084	130,0 _	12.740
10 7	664 579	44 158 , .0	1,071	339,0 _	15.047
10 8	5 761 455	332 774 , .0	1,061	754,0 _	17.357
10 9	50 847 534	2 592 592 .0	1,054	1 701 , .0	19,667
10 10	455 052 511	20 758 029 .0	1,048	3 104,0 _	21,975
10 11	4 118 054 813	169 923 159 .0	1,043	11 588 ,0	24,283
10 12	37 607 912 018	1 416 705 193 , .0	1,039	38 263 , .0	26.590
10 13	346 065 536 839	11 992 858 452 .0	1,034	108 971 , .0	28,896
10 14	3 204 941 750 802	102 838 308 636 .0	1,033	314 890 , .0	31,202
10 15	29 844 570 422 669	891 604 962 452 .0	1,031	1 052 619 .0	33,507
10 16	279 238 341 033 925	7 804 289 844 393 .0	1,029	3 214 632 .0	35,812
10 17	2 623 557 157 654 233	68 883 734 693 281 .0	1,027	7 956 589 .0	38,116
10 18	24 739 954 287 740 860	612 483 070 893 536 .0	1,025	21 949 555 , .0	40,420
10 19	234 057 667 276 344 607	5 481 624 169 369 960 .0	1,024	99 877 775 .0	42,725
10 20	2 220 819 602 560 918 840	49 347 193 044 659 701 .0	1,023	222 744 644 .0	45,028
10 21	21 127 269 486 018 731 928	446 579 871 578 168 707 .0	1,022	597 394 254 .0	47,332
10 22	201 467 286 689 315 906 290	4 060 704 006 019 620 994 .0	1,021	1 932 355 208 .0	49,636
10 23	1 925 320 391 606 803 968 923	37 083 513 766 578 631 309 .0	1,020	7 250 186 216 .0	51,939
10 24	18 435 599 767 349 200 867 866	339 996 354 713 708 049 069 .0	1,019	17 146 907 278 .0	54,243
10 25	176 846 309 399 143 769 411 680	3 128 516 637 843 038 351 228 .0	1,018	55 160 980 939 .0	56,546
OEIS	A006880	A057835		A057752

Värdet för π (10 ²⁴ ) beräknades ursprungligen under antagande av Riemann-hypotesen ; det har sedan dess verifierats ovillkorligt.

Analog för irreducerbara polynom över ett ändligt fält

Det finns en analog till primtalssatsen som beskriver "fördelningen" av irreducible polynom över ett ändligt fält ; formen den tar är slående lik fallet med den klassiska primtalssatsen.

För att ange det exakt, låt F = GF( q ) vara det finita fältet med q element, för vissa fixerade q , och låt N _n vara antalet moniska irreducerbara polynom över F vars grad är lika med n . Det vill säga, vi tittar på polynom med koefficienter valda från F , som inte kan skrivas som produkter av polynom av mindre grad. I den här inställningen spelar dessa polynom rollen som primtal, eftersom alla andra moniska polynom är uppbyggda av produkter av dem. Då kan man bevisa det

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

Om vi ​​gör substitutionen x = q ⁿ , så är den högra sidan bara

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

vilket gör analogin tydligare. Eftersom det finns exakt q ⁿ moniska polynom av grad n (inklusive de reducerbara), kan detta omformuleras på följande sätt: om ett moniskt polynom av grad n väljs slumpmässigt, så är sannolikheten att det är irreducerbart ungefär 1 / n .

Man kan till och med bevisa en analog till Riemann-hypotesen, nämligen den

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

Bevisen för dessa påståenden är mycket enklare än i det klassiska fallet. Det involverar ett kort, kombinatoriskt argument, sammanfattat enligt följande: varje element i graden n förlängning av F är en rot av något irreducerbart polynom vars grad d delar n ; genom att räkna dessa rötter på två olika sätt slår man fast det

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

där summan är över alla divisorer d av n . Möbius inversion ger då efter

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

där μ ( k ) är Möbius-funktionen . (Denna formel var känd för Gauss.) Huvudtermen förekommer för d = n , och det är inte svårt att binda de återstående termerna. "Riemann-hypotesen"-påståendet beror på det faktum att den största egentliga delaren av n inte kan vara större än n / 2 .

Se även

• Abstrakt analytisk talteori för information om generaliseringar av satsen.
• Landau primidealsats för en generalisering till primideal i algebraiska talfält.
• Riemanns hypotes

Citat

•   Granville, Andrew (1995). "Harald Cramér och fördelningen av primtal" (PDF) . Scandinavian Actuarial Journal . 1 :12–28. CiteSeerX 10.1.1.129.6847 . doi : 10.1080/03461238.1995.10413946 .
•   Hardy, GH ; Littlewood, JE (1916). "Bidrag till teorin om Riemanns zeta-funktion och teorin om fördelningen av primtal" . Acta Mathematica . 41 : 119-196. doi : 10.1007/BF02422942 . S2CID 53405990 .
•   Hardy, GH ; Wright, EM (2008) [första uppl. 1938], An Introduction to the Theory of Numbers , reviderad av DR Heath-Brown och JH Silverman , med ett förord ​​av Andrew Wiles (6:e upplagan), Oxford: Oxford University Press, ISBN 978-0-19-921985-8
•    Narkiewicz, Władysław (2000), The Development of Prime Number Theory: From Euclid to Hardy and Littlewood , Springer Monographs in Mathematics, Springer-Verlag, doi : 10.1007/978-3-662-13157-2 , ISBN 5478-3 -66289-1 , ISSN 1439-7382

externa länkar

• "Distribution of prime numbers" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Table of Primes av Anton Felkel .
• Kort video som visualiserar primtalssatsen.
• Primformler och primtalssats på MathWorld .
• Hur många primtal finns det? Arkiverad 2012-10-15 på Wayback Machine och The Gaps between Primes av Chris Caldwell, University of Tennessee på Martin .
• Tabeller över primtalsfunktioner av Tomás Oliveira e Silva
• Eberl, Manuel och Paulson, LC The Prime Number Theorem (Formell bevisutveckling i Isabelle/HOL, Archive of Formal Proofs)
• Primtalssatsen: det "elementära" beviset − En presentation av det elementära beviset för Atle Selbergs och Paul Erdős elementära bevis för primtalssatsen på www.dimostriamogoldbach.it/en/