Festlegen, ob ein Intervall eine Primzahl enthält

Wie komplex ist die Entscheidung, ob ein Intervall der natürlichen Zahlen eine Primzahl enthält? Eine Variante des Sieve von Eratosthenes gibt einen Algorithmus, wobei L die Länge des Intervalls ist und ~ Häute poly-logarithmische Faktoren in dem Ausgangspunkt des Intervalls; können wir es besser machen (in Bezug auf L allein)?$\tilde O(L)$$L$$\sim$$L$

Haftungsausschluss : Ich bin kein Experte für Zahlentheorie.

Kurze Antwort : Wenn Sie bereit sind, "vernünftige zahlentheoretische Vermutungen" anzunehmen, können wir feststellen, ob im Intervall in der Zeit p o l y l o g ( n ) eine Primzahl vorhanden ist . Wenn Sie nicht bereit sind , eine solche Annahme zu machen, dann gibt es einen schönen Algorithmus aufgrund Odlyzko erreicht , dass n 1 / 2 + o ( 1 ) , und ich glaube , dass dies die bekannteste ist.$[n, n+\Delta]$$\mathrm{polylog}(n)$$n^{1/2 + o(1)}$

Sehr hilfreicher Link mit vielen tollen Informationen zu einem eng verwandten Problem : PolyMath-Projekt über deterministische Algorithmen zum Auffinden von Primzahlen .

Lange Antwort :

Dies ist ein schwieriges Problem, ein aktives Forschungsgebiet, das eng mit der schwierigen Frage verbunden zu sein scheint, wie Lücken zwischen den Primzahlen geschlossen werden können. Ihr Problem ähnelt moralisch sehr dem Problem, deterministisch eine Primzahl zwischen und 2 n zu finden , das kürzlich Gegenstand eines PolyMath-Projekts war . (Wenn Sie sich wirklich mit diesen Fragen befassen möchten, ist dieser Link ein guter Ausgangspunkt.) Insbesondere sind unsere besten Algorithmen für beide Probleme im Wesentlichen gleich.$n$$2n$

In beiden Fällen hängt der beste Algorithmus stark von der Größe der Lücken zwischen den Primzahlen ab. Insbesondere dann , wenn ist so , dass es immer eine Primzahl ist zwischen n und n + f ( n ) (und f ( n ) effizient berechnet werden), dann können wir immer ein erstklassige in der Zeit finden p o l y l o g ( n ) ≤ f ( n ) wie folgt. Um festzustellen, ob es eine Primzahl zwischen n und n $f(n)$$n$$n + f(n)$$f(n)$$\mathrm{polylog}(n) \cdot f(n)$$n$ , zuerstob Δ ≥ f ( n ) . Wenn ja, geben Sie yes aus. Andernfalls iterieren Sie einfach durch die ganzen Zahlen zwischen n und n + Δ und testen Sie jede auf Primalität und antworten Sie mit Ja, wenn Sie eine Primzahl finden, und mit Nein. (Dies kann deterministisch erfolgen, weshalb das deterministische Finden einer Primzahl zwischen n und 2 n so eng mit der Bestimmung zusammenhängt, ob es in einem bestimmten Intervall eine Primzahl gibt.)$n + \Delta$$\Delta \geq f(n)$$n$$n + \Delta$$n$$2n$

Wenn die Primzahlen verhalten sich wie wir denken , dass sie es tun, dann ist dies das Ende der Geschichte (bis zu Faktoren). Insbesondere erwarten wir, dass wir f ( n ) = O ( log 2 n ) nehmen können . Dies ist nach Harald Cramér als Cramérs Vermutung bekannt und beweist, dass es im Moment sehr weit außerhalb der Reichweite zu sein scheint. Aber soweit ich weiß, wird weithin davon ausgegangen. (Zu dieser Vermutung gelangt man beispielsweise aus der Heuristik, dass sich die Primzahlen wie die zufällige Menge von ganzen Zahlen verhalten, die durch Einbeziehung jeder ganzen Zahl n ≥ $\mathrm{polylog}(n)$$f(n) = O(\log^2 n)$$n \geq 3$unabhängig zufällig mit Wahrscheinlichkeit .)$1/\log n$

Es gibt viele Vermutungen, die implizieren, dass die viel schwächere Grenze , wiedie Vermutung von Legendre. (Ich kenne keine Vermutungen, von denen bekannt ist, dass sie eine Zwischengrenze implizieren, obwohl ich mir vorstelle, dass sie existieren.) Und die Riemann-Hypothese impliziert bekanntermaßen die ähnliche Grenzef(n)≤O($f(n) \leq O(\sqrt{n})$. Also, wenn Sie diese Vermutungen annehmen, passen SieWesentlichen Odlyzko-Algorithmus (bis einen Faktor vonn o ( 1 ) ) mit einem viel einfacheren Algorithmus.$f(n) \leq O(\sqrt{n} \log n)$$n^{o(1)}$

Ich glaube, dass die derzeit beste bedingungslose Bindung was Baker, Harman und Pintz zu verdanken ist . Wenn Sie also nichts annehmen, schlägt der Odlyzko-Algorithmus den offensichtlichen Algorithmus um ungefähr einen Faktor von n 0,025 .$\widetilde{O}(n^{0.525})$$n^{0.025}$