Primzahlsatz - Prime number theorem

In der Zahlentheorie beschreibt der Primzahlensatz ( PNT ) die asymptotische Verteilung der Primzahlen unter den positiven ganzen Zahlen. Es formalisiert die intuitive Vorstellung, dass Primzahlen mit zunehmender Größe seltener werden, indem die Geschwindigkeit, mit der dies geschieht, genau quantifiziert wird. Der Satz wurde 1896 unabhängig von Jacques Hadamard und Charles Jean de la Vallée Poussin unter Verwendung von Ideen von Bernhard Riemann (insbesondere der Riemann-Zeta-Funktion ) bewiesen .

Die erste gefundene solche Verteilung ist π ( N ) ~ n/log( N ), wobei π ( N ) die Primzahlzählfunktion (die Anzahl der Primzahlen kleiner oder gleich N ) und log( N ) der natürliche Logarithmus von N ist . Dies bedeutet, dass für N , die groß genug sind , die Wahrscheinlichkeit, dass eine zufällige ganze Zahl, die nicht größer als N ist, eine Primzahl ist, sehr nahe bei 1/log( N ) liegt . Folglich ist eine zufällige ganze Zahl mit höchstens 2 n Stellen (für groß genug n ) ungefähr halb so wahrscheinlich, dass sie eine Primzahl ist wie eine zufällige ganze Zahl mit höchstens n Stellen. Beispielsweise ist unter den positiven ganzen Zahlen mit höchstens 1000 Stellen etwa eine von 2300 eine Primzahl ( log(10 ¹⁰⁰⁰ ) ≈ 2302,6 ), während unter positiven ganzen Zahlen mit höchstens 2000 Stellen etwa eine von 4600 eine Primzahl ist ( log(10 ²⁰⁰⁰ ) 4605.2 ). Mit anderen Worten, die durchschnittliche Lücke zwischen aufeinanderfolgenden Primzahlen unter den ersten N ganzen Zahlen beträgt ungefähr log( N ) .

Stellungnahme

Graph, der das Verhältnis der Primzahlzählfunktion π ( x ) zu zwei ihrer Näherungen, x /log x und Li( x ) zeigt . Mit zunehmendem x (beachte, dass die x- Achse logarithmisch ist) tendieren beide Verhältnisse gegen 1. Das Verhältnis für x / log x konvergiert von oben sehr langsam, während das Verhältnis für Li( x ) von unten schneller konvergiert.

Log-Log-Plot, der den absoluten Fehler von x / log x und Li( x ) zeigt , zwei Näherungen der Primzahlzählfunktion π ( x ) . Im Gegensatz zum Verhältnis nimmt die Differenz zwischen π ( x ) und x / log x mit steigendem x unbegrenzt zu. Andererseits wechselt Li( x ) − π ( x ) unendlich oft das Vorzeichen.

Sei π ( x ) die Primzahlzählfunktion , die die Anzahl der Primzahlen kleiner oder gleich x für jede reelle Zahl  x angibt . Zum Beispiel π (10) = 4, weil es vier Primzahlen (2, 3, 5 und 7) kleiner oder gleich 10 gibt. Der Primzahlensatz besagt dann, dass x / log x eine gute Annäherung an π ( x ) (wobei hier log den natürlichen Logarithmus bedeutet), in dem Sinne , dass der Grenzwert des Quotienten der beiden Funktionen π ( x ) und x / log x als x erhöht , ohne gebunden ist 1:

${\displaystyle \lim_{x\to \infty }{\frac {\;\pi(x)\;}{\;\left[{\frac {x}{\log(x)}}\right] \;}}=1,}$

bekannt als das asymptotische Verteilungsgesetz der Primzahlen . Unter Verwendung der asymptotischen Notation kann dieses Ergebnis neu formuliert werden als

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

Diese Notation (und der Satz ) nicht nicht sagen nichts über die Grenze der Differenz der beiden Funktionen wie x unbeschränkt wächst. Stattdessen das Theorem besagt , dass x / log x annähert π ( x ) in dem Sinne , dass die relativen Fehler dieser Näherung als 0 nähern x erhöht , ohne gebunden.

Der Primzahlensatz ist äquivalent zu der Aussage, dass die n- te Primzahl p _n erfüllt

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

die asymptotische Notation bedeutet wiederum, dass sich der relative Fehler dieser Näherung 0 nähert, wenn n unbegrenzt zunimmt. Zum Beispiel die2 × 10 ^17. Primzahl ist8 512 677 386 048 191 063 , und (2 × 10 ¹⁷ )log(2 × 10 ¹⁷ ) rundet auf7 967 418 752 291 744 388 , ein relativer Fehler von etwa 6,4 %.

Wie unten beschrieben , ist der Primzahlensatz auch äquivalent zu

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

wobei θ und ψ sind die erste und die zweite Chebyshev - Funktionen sind.

Geschichte des Beweises des asymptotischen Primzahlgesetzes

Basierend auf den Tischen von Anton Felkel und Jurij Vega , Adrien-Marie Legendre gemutmaßt im Jahre 1797 oder 1798 , dass π ( a ) durch die Funktion approximiert wird ein / ( A log a + B ) , wobei A und B nicht spezifiziert Konstanten sind. In der zweiten Auflage seines Buches zur Zahlentheorie (1808) machte er dann eine genauere Vermutung mit A = 1 und B = −1.08366 . Carl Friedrich Gauß beschäftigte sich im Alter von 15 oder 16 Jahren "im Jahr 1792 oder 1793" nach eigener Erinnerung 1849 mit derselben Frage. 1838 entwickelte Peter Gustav Lejeune Dirichlet seine eigene Näherungsfunktion, das logarithmische Integral li( x ) (unter der etwas anderen Form einer Reihe, die er Gauß mitteilte). Sowohl die Formeln von Legendre als auch von Dirichlet implizieren die gleiche mutmaßliche asymptotische Äquivalenz von π ( x ) und x / log( x ) , obwohl sich herausstellte, dass die Näherung von Dirichlet erheblich besser ist, wenn man die Differenzen anstelle von Quotienten betrachtet.

In zwei Arbeiten aus den Jahren 1848 und 1850 versuchte der russische Mathematiker Pafnuty Chebyshev , das asymptotische Verteilungsgesetz der Primzahlen zu beweisen. Seine Arbeit ist bemerkenswert für die Verwendung der Zeta-Funktion ζ ( s ) , für reale Werte des Arguments „ s “, wie in Werken von Leonhard Euler , bereits 1737 beim Beweis einer etwas schwächeren Form des asymptotischen Gesetzes, nämlich dass, wenn der Grenzwert von x gegen unendlich geht, von π ( x ) / ( x / log( x )) überhaupt existiert, dann ist er notwendigerweise gleich eins. Er konnte bedingungslos beweisen, dass dieses Verhältnis nach oben und unten durch zwei explizit gegebene Konstanten nahe 1 für alle hinreichend großen x beschränkt ist . Obwohl Chebyshevs Arbeit den Primzahlensatz nicht bewies, waren seine Schätzungen für π ( x ) stark genug, um Bertrands Postulat zu beweisen , dass es für jede ganze Zahl n 2 eine Primzahl zwischen n und 2 n gibt .

Ein wichtiges Papier über die Verteilung von Primzahlen war Riemanns Memoiren von 1859 " Über die Anzahl der Primzahlen kleiner als eine gegebene Größe ", die einzige Arbeit, die er jemals zu diesem Thema verfasste. Riemann führte neue Ideen in das Thema ein, hauptsächlich, dass die Verteilung von Primzahlen eng mit den Nullstellen der analytisch erweiterten Riemannschen Zetafunktion einer komplexen Variablen verbunden ist. Insbesondere in dieser Arbeit entstand die Idee, Methoden der komplexen Analysis auf das Studium der reellen Funktion π ( x ) anzuwenden . In Erweiterung von Riemanns Ideen wurden zwei Beweise für das asymptotische Gesetz der Verteilung von Primzahlen unabhängig von Jacques Hadamard und Charles Jean de la Vallée Poussin gefunden und erschienen im selben Jahr (1896). Beide Beweise verwendeten Methoden der komplexen Analysis, wobei als Hauptschritt des Beweises festgestellt wurde, dass die Riemannsche Zetafunktion ζ ( s ) für alle komplexen Werte der Variablen s , die die Form s = 1 + it mit t > 0 haben, von Null verschieden ist .

Im 20. Jahrhundert wurde der Satz von Hadamard und de la Vallée Poussin auch als Primzahlensatz bekannt. Es wurden mehrere verschiedene Beweise dafür gefunden, einschließlich der "elementaren" Beweise von Atle Selberg und Paul Erdős (1949). Die Originalabzüge von Hadamard und de la Vallée Poussin sind lang und aufwendig; spätere Beweise führten verschiedene Vereinfachungen durch die Verwendung von Tauber-Theoremen ein , blieben aber schwer verdaulich. Ein kurzer Beweis wurde 1980 von dem amerikanischen Mathematiker Donald J. Newman entdeckt . Der Beweis von Newman ist wohl der einfachste bekannte Beweis des Satzes, obwohl er insofern nicht elementar ist, als er den Integralsatz von Cauchy aus der komplexen Analysis verwendet.

Beweisskizze

Hier ist eine Skizze des Beweises, auf den in einem Vortrag von Terence Tao Bezug genommen wurde . Wie die meisten Beweise der PNT beginnt sie mit einer Neuformulierung des Problems in Form einer weniger intuitiven, aber besser verhaltenen Primzahlzählfunktion. Die Idee besteht darin, die Primzahlen (oder eine verwandte Menge wie die Menge der Primzahlenpotenzen) mit Gewichten zu zählen, um eine Funktion mit einem glatteren asymptotischen Verhalten zu erhalten. Die gebräuchlichste solche verallgemeinerte Zählfunktion ist die Chebyshev-Funktion ψ ( x ) , definiert durch

${\displaystyle \psi(x)=\!\!\!\!\sum _{\stackrel {p^{k}\leq x,}{p{\text{ ist eine Primzahl}}}}\!\! \!\!\log p.}$

Dies wird manchmal geschrieben als

${\displaystyle \psi(x)=\sum_{n\leq x}\Lambda(n),}$

wobei Λ ( n ) die von Mangoldt-Funktion ist , nämlich

${\displaystyle \Lambda(n)={\begin{cases}\log p&{\text{if}}n=p^{k}{\text{ für eine Primzahl }}p{\text{ und integer }} k\geq 1,\\0&{\text{sonst.}}\end{Fälle}}}$

Es ist jetzt relativ einfach zu überprüfen, ob die PNT der Behauptung äquivalent ist, dass

${\displaystyle \lim_{x\to\infty }{\frac {\psi(x)}{x}}=1.}$

Dies folgt in der Tat aus den einfachen Abschätzungen

${\displaystyle \psi(x)=\sum _{p\leq x}\log p\left\lfloor {\frac {\log x}{\log p}}\right\rfloor \leq \sum _{p \leq x}\log x=\pi(x)\log x}$

und (unter Verwendung der großen O- Notation ) für jedes ε > 0 ,

${\displaystyle \psi(x)\geq\!\!\!\!\sum _{x^{1-\varepsilon}\leq p\leq x}\!\!\!\!\log p\geq \!\!\!\!\sum _{x^{1-\varepsilon}\leq p\leq x}\!\!\!\!(1-\varepsilon)\log x=(1-\varepsilon )\left(\pi(x)+O\left(x^{1-\varepsilon}\right)\right)\log x.}$

Der nächste Schritt besteht darin, eine nützliche Darstellung für ψ ( x ) zu finden . Sei ζ ( s ) die Riemannsche Zetafunktion. Es kann gezeigt werden , dass ζ ( s ) wird im Zusammenhang mit der von Mangoldt Funktion Λ ( n ) , und somit zu ψ ( x ) , über die Relation

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

Eine heikle Analyse dieser Gleichung und verwandter Eigenschaften der Zeta-Funktion unter Verwendung der Mellin-Transformation und der Perron-Formel zeigt, dass für nicht ganzzahlige x die Gleichung

${\displaystyle \psi(x)=x-\sum _{\rho }{\frac {x^{\rho}}{\rho}}-\log(2\pi)}$

gilt, wobei die Summe über alle Nullstellen (trivial und nicht trivial) der Zetafunktion ist. Diese auffallende Formel ist eine der sogenannten expliziten Formeln der Zahlentheorie und deutet bereits auf das Ergebnis hin, das wir beweisen wollen, da rechts der Term x (angeblich die korrekte asymptotische Ordnung von ψ ( x ) ) erscheint -hand-Seite, gefolgt von (vermutlich) asymptotischen Termen niedrigerer Ordnung.

Der nächste Schritt des Beweises beinhaltet eine Untersuchung der Nullstellen der Zetafunktion. Die trivialen Nullstellen −2, −4, −6, −8, ... können separat behandelt werden:

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

die für ein großes x verschwindet . Die nichttrivialen Nullstellen, nämlich die auf dem kritischen Streifen 0 ≤ Re( s ) 1 , können potentiell von asymptotischer Ordnung vergleichbar mit dem Hauptterm x sein, falls Re( ρ ) = 1 , also müssen wir zeigen, dass alle Nullstellen reelle Teil streng weniger als 1.

Nicht verschwindend auf Re( s ) = 1

Um dies zu tun, nehmen wir für selbstverständlich , dass ζ ( s ) ist meromorphic in der Halbebene Re ( s )> 0 und analytisch ist es für einen einfachen Pol bei ausnehmen s = 1 , und dass es eine Produktformel

${\displaystyle \zeta(s)=\prod_{p}{\frac {1}{1-p^{-s}}}}$

für Re( s ) > 1 . Diese Produktformel folgt aus der Existenz einer eindeutigen Primfaktorzerlegung ganzer Zahlen und zeigt, dass ζ ( s ) in diesem Bereich niemals Null ist, sodass sein Logarithmus dort definiert ist und

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

Schreiben Sie s = x + iy ; dann

${\displaystyle {\big |}\zeta (x+iy){\big |}=\exp \left(\sum _{n,p}{\frac {\cos ny\log p}{np^{nx }}}\rechts).}$

Beobachte nun die Identität

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

so dass

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

für alle x > 1 . Nehmen Sie nun an, dass ζ (1 + iy ) = 0 ist . Sicher ist y nicht Null, da ζ ( s ) bei s = 1 einen einfachen Pol hat . Angenommen, x > 1 und x strebt von oben gegen 1 an. Da bei s = 1 einen einfachen Pol hat und ζ ( x + 2 iy ) analytisch bleibt, geht die linke Seite in der vorherigen Ungleichung gegen 0, ein Widerspruch. ${\displaystyle\zeta(s)}$

Schließlich können wir schlussfolgern, dass die PNT heuristisch wahr ist. Um den Beweis rigoros zu vervollständigen, sind noch gravierende Formalitäten zu überwinden, da die Summation über Zeta-Nullen in der expliziten Formel für ψ ( x ) nicht absolut, sondern nur bedingt und im Sinne eines "Hauptwertes" konvergiert. Es gibt mehrere Möglichkeiten, dieses Problem zu umgehen, aber viele von ihnen erfordern ziemlich heikle komplex-analytische Schätzungen. Edwards Buch liefert die Details. Eine andere Methode besteht darin, den Taubersatz von Ikehara zu verwenden , obwohl dieser Satz selbst ziemlich schwer zu beweisen ist. DJ Newman beobachtete, dass für den Primzahlensatz nicht die volle Stärke des Ikehara-Theorems benötigt wird, und man kann mit einem Spezialfall davonkommen, der viel einfacher zu beweisen ist.

Newmans Beweis des Primzahlsatzes

DJ Newman gibt einen schnellen Beweis des Primzahlensatzes (PNT). Der Beweis ist "nicht elementar", da er sich auf die komplexe Analysis stützt, aber die kritische Schätzung verwendet nur elementare Techniken aus einem ersten Kurs in diesem Fach: Cauchys Integralformel , Cauchys Integralsatz und Schätzungen komplexer Integrale. Hier ist eine kurze Skizze dieses Beweises:

Die erste und zweite Chebyshev-Funktion sind jeweils

${\displaystyle \psi (x)=\sum _{k\geq 1}\sum _{p^{k}\leq x}\log p\quad {\text{ und }}\quad \vartheta (x) =\sum _{p\leq x}\log p.}$

Die zweite Reihe erhält man durch Weglassen der Terme mit aus der ersten. PNT entspricht entweder oder . ${\displaystyle k\geq 2}$${\displaystyle \lim_{x\to\infty}\psi(x)/x=1}$${\displaystyle \lim_{x\to\infty}\vartheta(x)/x=1}$

Die Summen für und sind Teilsummen der Koeffizienten der Dirichlet-Reihe${\displaystyle \psi}$${\displaystyle\vartheta}$

${\displaystyle -{\frac {\zeta '(s)}{\zeta(s)}}=\sum _{k\geq 1}\sum _{p^{k}\leq x}\log p\ ,\,p^{-ks}\quad {\text{ und }}\quad\quad\Phi(s)=\sum _{p\leq x}\log p\,\,p^{-s} ,}$

wo ist die Riemannsche Zetafunktion . Wie bei den Teilsummen erhält man die zweite Reihe durch Weglassen der Terme mit aus der ersten. Die Dirichlet-Reihe, die durch Terme mit gebildet wird, wird von der Dirichlet-Reihe für für jedes Positiv dominiert , so dass sich die logarithmische Ableitung von und durch eine holomorphe Funktion in unterscheidet und daher die gleichen Singularitäten auf der Geraden aufweisen . ${\displaystyle\zeta}$${\displaystyle k\geq 2}$${\displaystyle k\geq 2}$${\displaystyle \zeta (2s+\varepsilon)}$${\displaystyle\varepsilon}$${\displaystyle\zeta}$${\displaystyle \Phi (s)}$${\displaystyle \Re s>{\frac {1}{2}}}$${\displaystyle \Re s=1}$

Teilweise Integration ergibt für , ${\displaystyle \Re s>1}$

${\displaystyle \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.}$

Alle analytischen Beweise des Primzahlensatzes verwenden die Tatsache, dass keine Nullen auf der Geraden sind . Eine weitere Information, die in Newmans Beweis benötigt wird, ist, dass sie beschränkt ist. Dies lässt sich mit elementaren Methoden leicht nachweisen. ${\displaystyle\zeta}$${\displaystyle \Re s=1}$${\displaystyle\vartheta(x)/x}$

Newmans Methode beweist PNT, indem sie das Integral zeigt

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

konvergiert, und daher geht der Integrand gegen Null als . Im Allgemeinen bedeutet die Konvergenz des uneigentlichen Integrals nicht, dass der Integrand gegen Null geht, da er oszillieren kann, aber da er zunimmt, ist dies in diesem Fall leicht zu zeigen. ${\displaystyle t\to\infty}$${\displaystyle\vartheta}$

Für lass ${\displaystyle \Re z>0}$

${\displaystyle g_{T}(z)=\int _{0}^{T}\left({\frac {\vartheta (e^{t})}{e^{t}}}-1\right )e^{-zt}\,dt\quad\quad}$

dann

${\displaystyle \lim_{T\to\infty}g_{T}(z)=g(z)={\frac {\Phi(s)}{s}}-{\frac {1}{s- 1}}\quad \quad {\text{wo}}\quad z=s-1}$

die auf der Linie holomorph ist . Die Konvergenz des Integrals wird dadurch bewiesen, dass . Dies beinhaltet eine Änderung der Reihenfolge der Grenzen, da sie geschrieben werden kann ${\displaystyle \Re z=0}$${\displaystyle I}$${\displaystyle \lim_{T\to\infty}g_{T}(0)=g(0)}$

${\displaystyle \lim_{T\to\infty}\lim_{s\to 0}g_{T}(z)=\lim_{s\to 0}\lim_{T\to\infty}g_ {T}(z)}$

und wird daher als Taubersatz klassifiziert .

Die Differenz wird unter Verwendung der Integralformel von Cauchy ausgedrückt und dann werden Schätzungen auf das Integral angewendet. Fix und solche, die in der Region holomorph sind, wo und sei ihre Grenze. Da 0 im Inneren liegt, ergibt die Integralformel von Cauchy${\displaystyle g(0)-g_{T}(0)}$${\displaystyle R>0}$${\displaystyle \delta >0}$${\displaystyle g(z)}$${\displaystyle |z|\leq R{\text{ und }}\Re z\geq -\delta }$${\displaystyle C}$

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

Um eine grobe Schätzung des Integranden zu erhalten, sei eine obere Schranke für , dann für${\displaystyle B}$${\displaystyle \vartheta(e^{t})/{e^{t}}-1}$${\displaystyle \Re z>0}$

${\displaystyle |g(z)-g_{T}(z)|\leq B\int _{T}^{\infty}e^{-\Re(z)t}\,dt={\frac { Sei^{-\Re (z)T}}{\Re z}}.}$

Diese Schranke ist nicht gut genug, um das Ergebnis zu beweisen, aber Newman führt den Faktor ein

${\displaystyle F(z)=e^{zT}\left(1+{\frac {z^{2}}{R^{2}}}\right)}$

in den Integrand für . Da der Newman - Faktor ist ganz und bleibt die linke Seite unverändert. Nun die obige Schätzung für und die Schätzungen für kombinieren, um zu geben ${\displaystyle g(0)-g_{T}(0)}$${\displaystyle F}$${\displaystyle F(0)=1}$${\displaystyle |g(z)-g_{T}(z)|}$${\displaystyle F}$

${\displaystyle \left|{\frac {1}{2\pi i}}\int _{C_{+}}\left(g(z)-g_{T}(z)\right)F(z) {\frac {dz}{z}}\right|\leq {\frac {B}{R}}.}$

wo ist der halbkreis . ${\displaystyle C_{+}}$${\displaystyle C\cap \left\{z\,\vert \,\Re z>0\right\}}$

Sei die Kontur . Die Funktion ist vollständig , so dass nach dem Integralsatz von Cauchy die Kontur in der linken Halbebene in einen Halbkreis mit Radius geändert werden kann, ohne das Integral von zu ändern , und das gleiche Argument gibt den Absolutwert dieses Integrals als an . Letztlich geht das Integral von über die Kontur zu Null, da es auf der Kontur zu Null geht. Kombinieren Sie die drei Schätzungen, erhalten Sie ${\displaystyle C_{-}}$${\displaystyle C\cap \left\{\Re z\leq 0\right\}}$${\displaystyle g_{T}}$${\displaystyle C_{-}}$${\displaystyle R}$${\displaystyle g_{T}(z)F(z)/2\pi iz}$${\displaystyle \leq B/R}$${\displaystyle T\to\infty}$${\displaystyle g(z)F(z)/z}$${\displaystyle C_{\delta}}$${\displaystyle F}$

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

Dies gilt für alle so , und PNT folgt. ${\displaystyle R}$${\displaystyle \lim_{T\to\infty}g_{T}(0)=g(0)}$

Primzahlzählfunktion im Sinne des logarithmischen Integrals

In einer handschriftlichen Notiz auf einem Nachdruck seines 1838 erschienenen Papiers " Sur l'usage des séries infinies dans la théorie des nombres ", das er an Gauss schickte, vermutete Dirichlet (in einer etwas anderen Form, die eher eine Reihe als ein Integral anspricht), dass eine noch bessere Annäherung an π ( x ) wird durch die gegebene Offset - logarithmischen Integralfunktion Li ( x ) , definiert durch

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

Tatsächlich weist dieses Integral stark auf die Vorstellung hin, dass die "Dichte" der Primzahlen um t herum 1 / log t betragen sollte . Diese Funktion steht in Beziehung zum Logarithmus durch die asymptotische Entwicklung

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

Der Primzahlensatz kann also auch als π ( x ) ~ Li( x ) geschrieben werden . Tatsächlich bewies de la Vallée Poussin in einer anderen Arbeit im Jahr 1899, dass

${\displaystyle \pi (x)=\operatorname {Li} (x)+O\left(xe^{-a{\sqrt {\log x}}}\right)\quad {\text{as }}x \zu \infty}$

für eine positive Konstante a , wobei O (...) die große O- Notation ist . Dies wurde verbessert zu

${\displaystyle \pi (x)=\operatorname {li} (x)+O\left(x\exp \left(-{\frac {A(\log x)^{\frac {3}{5}} }{(\log\log x)^{\frac {1}{5}}}}\right)\right)}$wo .${\displaystyle A=0,2098}$

Im Jahr 2016 hat Trudgian eine explizite Obergrenze für die Differenz zwischen und nachgewiesen : ${\displaystyle \pi(x)}$${\displaystyle \operatorname {li} (x)}$

${\displaystyle {\big |}\pi (x)-\operatorname {li} (x){\big |}\leq 0.2795{\frac {x}{(\log x)^{3/4}}} \exp \left(-{\sqrt {\frac {\log x}{6.455}}}\right)}$

für . ${\displaystyle x\geq 229}$

Der Zusammenhang zwischen der Riemannschen Zetafunktion und π ( x ) ist ein Grund dafür, dass die Riemannsche Hypothese in der Zahlentheorie von erheblicher Bedeutung ist: Wenn sie aufgestellt würde, würde sie den Fehler des Primzahlsatzes viel besser abschätzen als heute verfügbar ist. Genauer gesagt zeigte Helge von Koch 1901, dass, wenn die Riemann-Hypothese wahr ist, der Fehlerterm in der obigen Beziehung verbessert werden kann zu

${\displaystyle \pi (x)=\operatorname {Li} (x)+O\left({\sqrt {x}}\log x\right)}$

(diese letzte Schätzung entspricht tatsächlich der Riemann-Hypothese). Die an der großen O- Notation beteiligte Konstante wurde 1976 von Lowell Schoenfeld geschätzt : unter Annahme der Riemann-Hypothese

${\displaystyle {\big |}\pi (x)-\operatorname {li} (x){\big |}<{\frac {{\sqrt {x}}\log x}{8\pi }}}$

für alle x ≥ 2657 . Er leitete auch eine ähnliche Schranke für die Chebyshev-Primzahlzählfunktion ψ ab :

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

für alle x ≥ 73,2 . Es wurde gezeigt, dass diese letztere Schranke eine Varianz zum mittleren Potenzgesetz ausdrückt (wenn sie als Zufallsfunktion über die ganzen Zahlen betrachtet wird) und1/F- Rauschen und entsprechen auch der Tweedie-Compound-Poisson-Verteilung . (Die Tweedie-Verteilungen stellen eine Familie von skaleninvarianten Verteilungen dar, die als Konvergenzschwerpunkte für eine Verallgemeinerung des zentralen Grenzwertsatzes dienen .)

Das logarithmische Integral li( x ) ist für "kleine" Werte von x größer als π ( x ) . Dies liegt daran, dass (in gewissem Sinne) keine Primzahlen, sondern Primzahlen gezählt werden, wobei eine Potenz p ⁿ einer Primzahl p gezählt wird als1/neiner Primzahl. Dies deutet darauf hin , dass li ( x ) sollte in der Regel größer als π ( x ) um etwa li ( √ x ) / 2 , und insbesondere sollte immer größer sein als π ( x ) . 1914 bewies JE Littlewood jedoch , dass sich das Vorzeichen unendlich oft ändert. Der erste Wert von x in dem π ( x ) übersteigt , Li ( x ) ist wahrscheinlich um x = 10 ³¹⁶ ; Weitere Informationen finden Sie im Artikel über die Nummer von Skewes . (Andererseits ist das versetzte logarithmische Integral Li( x ) bereits für x = 2 kleiner als π ( x ) ; tatsächlich ist Li(2) = 0 , während π (2) = 1 .) ${\displaystyle \pi (x)-\operatorname {li} (x)}$

Elementare Beweise

In der ersten Hälfte des zwanzigsten Jahrhunderts glaubten einige Mathematiker (insbesondere GH Hardy ), dass es in der Mathematik eine Hierarchie von Beweismethoden gibt , die davon abhängt , welche Arten von Zahlen ( ganze Zahlen , reelle Zahlen , komplexe Zahlen ) ein Beweis erfordert, und dass der Primzahlsatz (PNT) ist ein "tiefes" Theorem, da es eine komplexe Analyse erfordert . Dieser Glaube wurde durch einen Beweis der PNT auf der Grundlage von Wieners tauberischem Theorem etwas erschüttert , obwohl dies beiseite gelegt werden könnte, wenn man davon ausgeht , dass Wieners Theorem eine "Tiefe" hat, die der von komplexen Variablenmethoden entspricht.

Im März 1948 stellte Atle Selberg mit "elementaren" Mitteln die asymptotische Formel auf

${\displaystyle \vartheta(x)\log(x)+\sum\limits_{p\leq x}{\log(p)}\\vartheta\left({\frac {x}{p}}\right )=2x\log(x)+O(x)}$

wo

${\displaystyle\vartheta(x)=\sum\limits_{p\leq x}{\log(p)}}$

für Primzahlen p . Bis Juli dieses Jahres hatten Selberg und Paul Erdős jeweils elementare Beweise der PNT erhalten, wobei beide Selbergs asymptotische Formel als Ausgangspunkt verwendeten. Diese Beweise haben die Vorstellung, dass die PNT in diesem Sinne "tief" war, effektiv zunichte gemacht und zeigten, dass technisch "elementare" Methoden leistungsfähiger waren, als angenommen wurde. Zur Geschichte der elementaren Beweise der PNT, einschließlich des Prioritätsstreits Erdős-Selberg , siehe einen Artikel von Dorian Goldfeld .

Es gibt einige Debatten über die Bedeutung des Ergebnisses von Erdős und Selberg. Es gibt keine strenge und allgemein akzeptierte Definition des Begriffs des elementaren Beweises in der Zahlentheorie, daher ist nicht genau klar, in welchem ​​Sinne ihr Beweis "elementar" ist. Obwohl es keine komplexe Analyse verwendet, ist es in der Tat viel technischer als der Standardnachweis von PNT. Eine mögliche Definition eines "elementaren" Beweises ist "einer, der in Peano-Arithmetik erster Ordnung durchgeführt werden kann ". Es gibt zahlentheoretische Aussagen (zum Beispiel das Paris-Harrington-Theorem ), die mit Methoden zweiter Ordnung, aber nicht mit Methoden erster Ordnung beweisbar sind, aber solche Sätze sind bis heute selten. Der Beweis von Erdős und Selberg kann sicherlich in der Peano-Arithmetik formalisiert werden, und 1994 bewiesen Charalambos Cornaros und Costas Dimitracopoulos, dass ihr Beweis in einem sehr schwachen Fragment von PA formalisiert werden kann, nämlich I Δ ₀ + exp . Dies beantwortet jedoch nicht die Frage, ob der Standardnachweis von PNT in PA formalisiert werden kann oder nicht.

Computerüberprüfungen

Im Jahr 2005 haben Avigad et al. verwendeten den Isabelle-Theorembeweiser , um eine computerverifizierte Variante des Erdős-Selberg-Beweises der PNT zu entwickeln. Dies war der erste maschinell verifizierte Nachweis des PNT. Avigad entschied sich, den Erdős-Selberg-Beweis eher zu formalisieren als einen analytischen, da Isabelles Bibliothek zu dieser Zeit zwar die Begriffe Grenze, Ableitung und transzendentale Funktion implementieren konnte , aber fast keine Integrationstheorie hatte.

Im Jahr 2009, John Harrison beschäftigte HOL Licht einen Beweis Einsatz zu formalisieren komplexe Analyse . Durch die Entwicklung der notwendigen analytischen Maschinerie, einschließlich der Cauchy-Integralformel , konnte Harrison "einen direkten, modernen und eleganten Beweis anstelle des komplizierteren 'elementaren' Erdős-Selberg-Arguments" formalisieren.

Primzahlsatz für arithmetische Folgen

Sei π _{d , a} ( x ) die Anzahl der Primzahlen in der arithmetischen Folge a , a + d , a + 2 d , a + 3 d , ... die kleiner als x sind . Dirichlet und Legendre gemutmaßt, und de la Vallée Poussin bewiesen, dass, wenn ein und d sind coprime , dann

${\displaystyle \pi_{d,a}(x)\sim {\frac {1}{\varphi(d)}}\operatorname {Li} (x),}$

wo φ ist Eulersche Phi-Funktion . Mit anderen Worten sind die Primzahlen gleichmäßig auf den Restklassen verteilt [ a ] Modulo d mit ggT ( a , d ) = 1. Dies ist stärker als Theorem Dirichlet auf arithmetische Progressionen ( in dem es heißt nur , dass es unendlich viele Primzahlen in jeweils Klasse) und kann mit ähnlichen Methoden bewiesen werden, die Newman für seinen Beweis des Primzahlensatzes verwendet hat.

Der Satz von Siegel-Walfisz gibt eine gute Abschätzung für die Verteilung von Primzahlen in Restklassen.

Bennett et al. bewiesen die folgende Abschätzung mit expliziten Konstanten A und B (Satz 1.3): Sei d eine ganze Zahl und sei a eine ganze Zahl, die zu d teilerfremd ist . Dann gibt es positive Konstanten A und B mit ${\displaystyle \geq 3}$

${\displaystyle \left|\pi_{d,a}(x)-{\frac {\operatorname {Li} (x)}{\varphi (d)}}\right|<A{\frac {x} {(\logx)^{2}}}}$für alle ,${\displaystyle x\geq B}$

wo

${\displaystyle A={\frac {1}{840}}}$wenn und wenn ,${\displaystyle 3\leq d\leq 10^{4}}$${\displaystyle A={\frac {1}{160}}}$${\displaystyle d>10^{4}}$

und

${\displaystyle B=8\cdot 10^{9}}$wenn und wenn .${\displaystyle 3\leq d\leq 10^{5}}$${\displaystyle B=\exp(0.03{\sqrt {d}}(\log {d})^{3})}$${\displaystyle d>10^{5}}$

Primzahlrennen

Obwohl wir insbesondere

${\displaystyle \pi_{4,1}(x)\sim\pi_{4,3}(x),}$

empirisch sind die zu 3 kongruenten Primzahlen zahlreicher und liegen in diesem "Primzahlenrennen" fast immer vorne; die erste Umkehrung erfolgt bei x = 26861 . Littlewood zeigte jedoch 1914, dass es unendlich viele Vorzeichenwechsel für die Funktion gibt

${\displaystyle \pi_{4,1}(x)-\pi_{4,3}(x),}$

so wechselt die Führung im Rennen unendlich oft hin und her. Das Phänomen, dass π _4,3 ( x ) die meiste Zeit voraus ist, wird als Tschebyschew-Bias bezeichnet . Die Rasse der Primzahlen lässt sich auf andere Moduli verallgemeinern und ist Gegenstand vieler Forschungen; Pál Turán gefragt , ob es immer der Fall ist, dass π ( x ; a , c ) und π ( x ; b , c ) die Plätze wechseln , wenn ein und b sind coprime bis c . Granville und Martin geben eine gründliche Darstellung und Übersicht.

Nicht asymptotische Schranken der Primzahlzählfunktion

Der Primzahlsatz ist ein asymptotisches Ergebnis. Sie liefert eine ineffektive Schranke auf π ( x ) als direkte Folge der Definition des Grenzwerts: für alle ε > 0 gibt es ein S mit für alle x > S ,

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

Es sind jedoch bessere Schranken für π ( x ) bekannt, zum Beispiel Pierre Dusart s

${\displaystyle {\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).}$

Die erste Ungleichung gilt für alle x 599 und die zweite für x ≥ 355991 .

Eine schwächere, aber manchmal nützliche Schranke für x ≥ 55 ist

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

In Pierre Dusarts These gibt es stärkere Versionen dieser Art von Ungleichung, die für größere x gültig sind . Später im Jahr 2010 bewies Dusart:

${\displaystyle {\begin{aligned}{\frac {x}{\log x-1}}&<\pi (x)&&{\text{for }}x\geq 5393,{\text{ and}} \\\pi (x)&<{\frac {x}{\log x-1.1}}&&{\text{for }}x\geq 60184.\end{aligned}}}$

Der Beweis von de la Vallée Poussin impliziert Folgendes. Für jedes ε > 0 gibt es ein S, so dass für alle x > S gilt

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

Approximationen für die n- te Primzahl

Als Folge des Primzahlensatzes erhält man einen asymptotischen Ausdruck für die n- te Primzahl, bezeichnet mit p _n :

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

Eine bessere Näherung ist

${\displaystyle {\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}}}\rechts).}$

Nochmals unter Berücksichtigung der 2 × 10 ^17. Primzahl8 512 677 386 048 191 063 , dies ergibt eine Schätzung von8 512 681 315 554 715 386 ; die ersten 5 Stellen stimmen überein und der relative Fehler beträgt ca. 0,0005 %.

Der Satz von Rosser besagt, dass

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

Dies kann durch das folgende Paar von Grenzen verbessert werden:

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

Tabelle von π ( x ) , x / log x und li ( x )

Die Tabelle vergleicht genaue Werte von π ( x ) mit den beiden Näherungen x /log x und li( x ) . Die letzte Spalte x / π ( x ) ist die durchschnittliche Primzahllücke unterhalb von  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 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

Der Wert für π (10 ²⁴ ) wurde ursprünglich unter Annahme der Riemannschen Hypothese berechnet ; es wurde seitdem bedingungslos verifiziert.

Analog für irreduzible Polynome über einem endlichen Körper

Es gibt ein Analogon des Primzahlensatzes, das die "Verteilung" irreduzibler Polynome über einen endlichen Körper beschreibt ; die Form, die es annimmt, ist dem Fall des klassischen Primzahlsatzes auffallend ähnlich.

Um es genau auszudrücken, sei F = GF( q ) der endliche Körper mit q Elementen für ein festes q und sei N _n die Anzahl der monischen irreduziblen Polynome über F, deren Grad gleich n ist . Das heißt, wir betrachten Polynome mit aus F ausgewählten Koeffizienten , die nicht als Produkte von Polynomen kleineren Grades geschrieben werden können. In dieser Einstellung spielen diese Polynome die Rolle der Primzahlen, da alle anderen monischen Polynome aus Produkten von ihnen aufgebaut sind. Das kann man dann beweisen

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

Wenn wir die Substitution x = q ^{n machen} , dann ist die rechte Seite gerade

${\displaystyle {\frac {x}{\log_{q}x}},}$

was die Analogie deutlicher macht. Da es genau q ⁿ monische Polynome vom Grad n (einschließlich der reduzierbaren) gibt, kann dies wie folgt umformuliert werden: Wenn ein monisches Polynom vom Grad n zufällig ausgewählt wird, dann ist die Wahrscheinlichkeit, dass es irreduzibel ist, ungefähr 1/n.

Man kann sogar ein Analogon der Riemannschen Hypothese beweisen, nämlich dass

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

Die Beweise dieser Aussagen sind viel einfacher als im klassischen Fall. Es beinhaltet ein kurzes, kombinatorisches Argument, das wie folgt zusammengefasst wird: Jedes Element der Erweiterung von F vom Grad n ist eine Wurzel eines irreduziblen Polynoms, dessen Grad d n teilt ; indem man diese Wurzeln auf zwei verschiedene Arten zählt, stellt man fest, dass

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

wobei die Summe über alle Teiler d von n ist . Möbius-Inversion liefert dann

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

wobei μ ( k ) die Möbius-Funktion ist . (Diese Formel war Gauss bekannt.) Der Hauptterm tritt für d = n auf , und es ist nicht schwierig, die restlichen Terme zu begrenzen. Die Aussage der "Riemann-Hypothese" hängt davon ab, dass der größte echte Teiler von n nicht größer sein kann alsn/2.

Siehe auch

• Abstrakte analytische Zahlentheorie für Informationen über Verallgemeinerungen des Satzes.
• Landauer Primidealsatz zur Verallgemeinerung auf Primideale in algebraischen Zahlenkörpern.
• Riemann-Hypothese

Anmerkungen

Verweise

• Hardy, GH; Littlewood, JE (1916). "Beiträge zur Theorie der Riemannschen Zeta-Funktion und zur Theorie der Primzahlenverteilung" . Acta Mathematica . 41 : 119-196. doi : 10.1007/BF02422942 . S2CID  53405990 .
• Granville, Andrew (1995). "Harald Cramér und die Verteilung der Primzahlen" (PDF) . Skandinavisches Aktuar-Journal . 1 : 12–28. CiteSeerX  10.1.1.129.6847 . doi : 10.1080/03461238.1995.10413946 .

Externe Links

• "Verteilung der Primzahlen" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Primzahlentabelle von Anton Felkel .
• Kurzes Video zur Visualisierung des Primzahlsatzes.
• Primformeln und Primzahlensatz bei MathWorld .
• Wie viele Primzahlen gibt es? und The Gaps between Primes von Chris Caldwell, University of Tennessee at Martin .
• Tabellen der Primzahlzählfunktionen von Tomás Oliveira e Silva