14
$\begingroup$

What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the interval and $\sim$ hides poly-logarithmic factors in the starting point of the interval; can we do better (in terms of $L$ alone)?

$\endgroup$
  • 1
    $\begingroup$ Nitpick: The Sieve of Eratosthenes doesn't give you merely poly-logarithmic factors in the starting point, even for an interval of length 1. It is indeed possible to check that a number is prime is time which is polylogarithmic in the number (= polynomial in the size of the representation) but this requires an algorithm much more sophisticated than the Sieve of Eratosthenes. $\endgroup$ – Squark Jul 29 '18 at 9:44
  • 1
    $\begingroup$ @Squark True, should have specified "pseudoprime relative to a given factor base". Though as the starting point of the interval gets large, the expected cost of primality testing goes to zero... $\endgroup$ – Elliot Gorokhovsky Jul 29 '18 at 15:34
27
$\begingroup$

Disclaimer: I'm not an expert in number theory.

Short answer: If you're willing to assume "reasonable number-theoretic conjectures", then we can tell whether there is a prime in the interval $[n, n+\Delta]$ in time $\mathrm{polylog}(n)$. If you're not willing to make such an assumption, then there is a beautiful algorithm due to Odlyzko that achieves $n^{1/2 + o(1)}$, and I believe that this is the best known.

Very helpful link with lots of great information about a closely related problem: PolyMath project on deterministic algorithms for finding primes.

Long answer:

This is a difficult problem, an active area of research, and seems to be intimately connected to the difficult question of bounding gaps between the primes. Your problem is morally very similar to the problem of finding a prime between $n$ and $2n$ deterministically, which was recently the subject of a PolyMath project. (If you want to really dive into these questions, that link is a great place to start.) In particular, our best algorithms for both problems are essentially the same.

In both cases, the best algorithm depends heavily on the size of gaps between the prime. In particular, if $f(n)$ is such that there is always a prime between $n$ and $n + f(n)$ (and $f(n)$ can be computed efficiently), then we can always find a prime in time $\mathrm{polylog}(n) \cdot f(n)$ as follows. To determine whether there is a prime between $n$ and $n + \Delta$, first check if $\Delta \geq f(n)$. If so, output yes. Otherwise, just iterate through the integers between $n$ and $n + \Delta$ and test each for primality and answer yes if you find a prime and no otherwise. (This can be done deterministically, which is why deterministically finding a prime between $n$ and $2n$ is so closely related to determining whether there is a prime in a certain interval.)

If the primes behave like we think they do, then this is the end of the story (up to $\mathrm{polylog}(n)$ factors). In particular, we expect to be able to take $f(n) = O(\log^2 n)$. This is known as Cramér's conjecture after Harald Cramér, and proving it seems very far out of reach at the moment. But, as far as I know, it is widely believed. (One arrives at this conjecture, e.g., from the heuristic that the primes behave like the random set of integers obtained by including each integer $n \geq 3$ independently at random with probability $1/\log n$.)

There are many conjectures that imply the much much weaker bound $f(n) \leq O(\sqrt{n})$, such as Legendre's conjecture. (I'm not aware of any conjectures that are known to imply an intermediate bound, though I imagine that they exist.) And, the Riemann hypothesis is known to imply the similar bound $f(n) \leq O(\sqrt{n} \log n)$. So, if you assume these conjectures, you essentially match Odlyzko's algorithm (up a factor of $n^{o(1)}$) with a much simpler algorithm.

I believe that the best unconditional bound right now is $\widetilde{O}(n^{0.525})$ due to Baker, Harman, and Pintz. So, if you assume nothing, then Odlyzko's algorithm beats the obvious algorithm by roughly a factor of $n^{0.025}$.

$\endgroup$
  • 3
    $\begingroup$ This answer is awesome!! Can these approaches be adapted to decide if there are $k$ primes in the interval where $k$ is a given number? And, what's the complexity in this case? $\endgroup$ – Michael Wehar Jul 31 '18 at 6:38
  • 3
    $\begingroup$ @MichaelWehar Nice question. Odlyzko's algorithm definitely can, since his algorithm actually computes the prime counting function $\pi(x) := \text{\# primes below $\leq x$}$. For the approach using gaps between the primes, I'm not the right guy to ask. Obviously, this requires bounds on $p_{n+k}-p_n$, as opposed to just $p_{n+1}-p_n$, and I simply don't know much about this. Maybe someone else knows? $\endgroup$ – Noah Stephens-Davidowitz Jul 31 '18 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.