# Is there always at least one prime in the closed interval $[2^n,2^n+n^2]$?

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.

• 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. – Asymptotiac K Dec 22 '17 at 6:58
• 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. – Kurisuto Asutora Dec 22 '17 at 8:25
• 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. – Seva Dec 22 '17 at 10:23
• 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. – Hu xiyu Dec 23 '17 at 1:50
• Here's some recent computational data on record gaps between primes: arxiv.org/pdf/1309.4053.pdf – Noam D. Elkies Dec 25 '17 at 4:23

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.