Decidir si un intervalo contiene un número primo

¿Cuál es la complejidad de decidir si un intervalo de los números naturales contiene un primo? Una variante de la criba de Eratóstenes da una algoritmo, donde L es la longitud del intervalo y ~ cueros factores poli-logarítmicas en el punto de partida del intervalo; ¿Podemos hacerlo mejor (solo en términos de L )?$\tilde O(L)$$L$$\sim$$L$

Descargo de responsabilidad : no soy un experto en teoría de números.

Respuesta corta : si está dispuesto a asumir "conjeturas de teoría de números razonables", entonces podemos decir si hay un primo en el intervalo en el tiempo p o l y l o g ( n ) . Si no estás dispuesto a hacer tal suposición, entonces hay una hermosa algoritmo debido a que logra Odlyzko n 1 / 2 + O ( 1 $[n, n+\Delta]$$\mathrm{polylog}(n)$$n^{1/2 + o(1)}$ , y creo que este es el más conocido.

Enlace muy útil con mucha información excelente sobre un problema estrechamente relacionado : el proyecto PolyMath sobre algoritmos deterministas para encontrar números primos .

Respuesta larga :

Este es un problema difícil, un área activa de investigación, y parece estar íntimamente relacionado con la difícil cuestión de cerrar las brechas entre los números primos. Su problema es moralmente muy similar al problema de encontrar un primo entre y $n$ determinista, que recientemente fue objeto de unproyecto PolyMath$2n$ . (Si realmente quiere profundizar en estas preguntas, ese enlace es un excelente lugar para comenzar). En particular, nuestros mejores algoritmos para ambos problemas son esencialmente los mismos.

En ambos casos, el mejor algoritmo depende en gran medida del tamaño de los espacios entre los primos. En particular, si es tal que siempre hay un primo entre n y n + f ( n ) (y f ( n ) se puede calcular de manera eficiente), entonces siempre podemos encontrar un primo en el tiempo p o l y l o g ( n ) ⋅ f ( n ) de la siguiente manera. Para determinar si hay un primo entre , primero verifique si Δ $f(n)$$n$$n + f(n)$$f(n)$$\mathrm{polylog}(n) \cdot f(n)$ y n $n$$n + \Delta$ . Si es así, salida sí. De lo contrario, solo recorra los enteros entre n y n + Δ y pruebe cada uno de ellos para la primalidad y responda sí si encuentra un primo y no de lo contrario. (Esto se puede hacer de manera determinista, razón por la cual determinísticamente encontrar un primo entre n y 2 $\Delta \geq f(n)$$n$$n + \Delta$$n$$2n$ está tan estrechamente relacionado con la determinación de si hay un primo en cierto intervalo).

Si los números primos se comportan como creemos que lo hacen, entonces este es el final de la historia (hasta factores de ). En particular, esperamos poder tomar f ( n ) = O ( log 2 n ) . Esto se conoce como conjetura de Cramér independientemente al azar con probabilidad 1 /$\mathrm{polylog}(n)$$f(n) = O(\log^2 n)$ después de Harald Cramér, y demuestra que parece estar muy lejos de su alcance en este momento. Pero, que yo sepa, se cree ampliamente. (Se llega a esta conjetura, por ejemplo, a partir de la heurística de que los números primos se comportan como el conjunto aleatorio de enteros obtenido al incluir cada entero $n \geq 3$$1/\log n$ .)

Hay muchas conjeturas que implican el límite mucho más débil $f(n) \leq O(\sqrt{n})$$f(n) \leq O(\sqrt{n} \log n)$$n^{o(1)}$ ) con un algoritmo mucho más simple.

$\widetilde{O}(n^{0.525})$debido a Baker, Harman y Pintz . Entonces, si no asume nada, entonces el algoritmo de Odlyzko supera al algoritmo obvio en un factor aproximado de$n^{0.025}$.