Decidindo se um intervalo contém um número primo

Qual é a complexidade de decidir se um intervalo dos números naturais contém um primo? Uma variante da Peneira de Eratóstenes fornece um algoritmo , onde é a duração do intervalo e oculta fatores polialogarítmicos no ponto inicial do intervalo; podemos fazer melhor (apenas em termos de )?$\tilde O(L)$$L$$\sim$$L$

Disclaimer : Eu não sou um especialista em teoria dos números.

Resposta curta : se você estiver disposto a assumir "conjecturas teóricas razoáveis", podemos dizer se existe um primo no intervalo no tempo p o l y l o g ( n ) . Se você não está disposto a fazer tal suposição, então há uma bela algoritmo devido a Odlyzko que atinge n 1 / 2 + o ( 1 ) , e eu acredito que este é o mais conhecido.$[n, n+\Delta]$$\mathrm{polylog}(n)$$n^{1/2 + o(1)}$

Link muito útil com muitas informações excelentes sobre um problema intimamente relacionado : Projeto PolyMath sobre algoritmos determinísticos para localização de números primos .

Resposta longa :

Esse é um problema difícil, uma área ativa de pesquisa, e parece estar intimamente ligado à difícil questão de estabelecer lacunas entre os primos. Seu problema é moralmente muito semelhante ao de encontrar um primo entre e 2 n deterministicamente, que foi recentemente o assunto de um projeto PolyMath . (Se você realmente quiser se aprofundar nessas questões, esse link é um ótimo ponto de partida.) Em particular, nossos melhores algoritmos para os dois problemas são essencialmente os mesmos.$n$$2n$

Nos dois casos, o melhor algoritmo depende muito do tamanho das lacunas entre os primos. Em particular, se é tal que sempre existe um primo entre n e n + f ( n ) ( ef ( n ) pode ser computado com eficiência), então sempre podemos encontrar um primo no tempo p o l y l O g ( n ) ⋅ f ( n ) como se segue. Para determinar se existe um primo entre n e n $f(n)$$n$$n + f(n)$$f(n)$$\mathrm{polylog}(n) \cdot f(n)$$n$ , verifique primeiro se Δ ≥ f ( n ) . Se sim, emita sim. Caso contrário, basta percorrer os números inteiros entre n e n + Δ e testar cada um quanto à primalidade e responder sim se você encontrar um primo e não o contrário. (Isso pode ser feito deterministicamente, e é por isso que encontrar determinamente um primo entre n e 2 n está tão intimamente relacionado à determinação de se existe um primo em um determinado intervalo.)$n + \Delta$$\Delta \geq f(n)$$n$$n + \Delta$$n$$2n$

Se os números primos se comportar como nós pensamos que eles fazem, então este é o fim da história (até fatores). Em particular, esperamos poder tomar f ( n ) = O ( log 2 n ) . Isso é conhecido como conjectura de Cramér depois de Harald Cramér, e provando que parece muito distante do alcance no momento. Mas, tanto quanto eu sei, é amplamente aceito. (Chega-se a essa conjectura, por exemplo, a partir da heurística de que os primos se comportam como o conjunto aleatório de números inteiros obtido pela inclusão de cada número inteiro n ≥ $\mathrm{polylog}(n)$$f(n) = O(\log^2 n)$$n \geq 3$independentemente aleatoriamente com probabilidade .)$1/\log n$

Existem muitas conjecturas que implicam o limite muito mais fraco , comoa conjectura de Legendre. (Não conheço nenhuma conjectura que implique um limite intermediário, embora eu imagine que exista.) E, sabe-se que a hipótese de Riemann implica o limite similarf(n)≤O($f(n) \leq O(\sqrt{n})$. Portanto, se você assume essas conjecturas, combina essencialmente o algoritmo de Odlyzko (um fator den o ( 1 ) ) com um algoritmo muito mais simples.$f(n) \leq O(\sqrt{n} \log n)$$n^{o(1)}$

Acredito que o melhor limite incondicional no momento é devido a Baker, Harman e Pintz . Portanto, se você não assume nada, o algoritmo de Odlyzko vence o óbvio por aproximadamente um fator de n 0,025 .$\widetilde{O}(n^{0.525})$$n^{0.025}$