5
$\begingroup$

As an amateur, I honestly do not know what exactly to think about this question of mine. I know that there are arbitrarily large gaps between primes but do not know will they ever overlap with intervals of this kind, so that fact somehow goes in favor of that it could be that some intervals of this kind will not have primes inside (endpoints also count).

But as I also expect Polignac's conjecture to be true it could be that there will always be at least one prime in $[2^n,2^n+n^2]$.

I do not know do these intervals grow too slow but I think they (in a certain sense) do, so somehow a counterexample seems to probably exist, if you ask me, but, again, I am not sure.

Feel free to close if I made a mistake again and asked a question not appropriate for MO.

Improve this question
$\endgroup$
7
  • 6
    $\begingroup$ For $n$ large enough, your conjecture follows from the Cramér's conjecture (see for example "Harald Cramér and the distribution of prime numbers" by A.Granville). Both conjectures (yours and Cramér's) seem to be extremely hard to prove. $\endgroup$
    – Alexander Kalmynin
    Commented Dec 22, 2017 at 6:58
  • 7
    $\begingroup$ Just to give you some idea of the difficulty of the problem, even proving the existence of primes in intervals $[2^n, 2^n + \sqrt{2^n}]$ is unsolved and considered to be extremely difficult. $\endgroup$
    – Kurisuto Asutora
    Commented Dec 22, 2017 at 8:25
  • 2
    $\begingroup$ The usual heuristic (suggested by the prime number theorem) is that the "probability" of a large number $N$ to be prime is about $1/\log N$. Accordingly, one can expect about $n/\log 2$ primes in the interval $[2^n,2^n+n^2]$. However, proving rigorously anything of this sort is completely out of reach, see the previous comment. $\endgroup$
    – Seva
    Commented Dec 22, 2017 at 10:23
  • $\begingroup$ If you change the statement to almost every $n\in \mathbb N^*, [n,n+clog n]$, This morally could be look as a corollary of the result establish in "multiplication function and short interval" by Matomaki and Raziwill. But if you wish to consider a sparse set, I think this is out of the understanding. $\endgroup$
    – Hu xiyu
    Commented Dec 23, 2017 at 1:50
  • 1
    $\begingroup$ Here's some recent computational data on record gaps between primes: arxiv.org/pdf/1309.4053.pdf $\endgroup$
    – Noam D. Elkies
    Commented Dec 25, 2017 at 4:23

1 Answer 1

Reset to default
14
$\begingroup$

As mentioned, this follows from an effective form of Cramér's conjecture, so we won't be able to disprove it.

But we won't be able to prove it either, because it implies the existence of an algorithm to find an $n$-bit prime in polynomial time, another open problem. The algorithm searches for a prime using the AKS primality test by starting at $2^n+1$ and counting up until it finds one, requiring total time $n^{8+o(1)}$ if your conjecture is true. But the state of the art in finding an $n$-bit prime is an algorithm requiring $2^{0.525 \cdot n + o(n)}$ time — in fact, it's the same algorithm, it's just not known to run any faster than that.

Improve this answer
$\endgroup$

You must log in to answer this question.