# Bounds on prime number spacing

Suppose n is an integer. What kind of bounds do we know for how close the closest prime p > n will be?

I'd especially appreciate an answer that pushes me in the right direction of proving a good bound for this without showing the proof fully.

Context: I ran into this while coming up to a solution for http://stackoverflow.com/questions/4058172/tricky-algorithm-interview-question. Depending on the bound, the algorithm I come up with may or may not be deterministic.

-
Bertrand's postulate gives the bound $n-2$. The prime number theorem can be used to show that for all $\epsilon>0$, the bound $\epsilon n$ will work for sufficiently large $n$. I'm not an expert and don't know how helpful this is, hence just a comment. Here's a reference: en.wikipedia.org/wiki/Bertrand%27s_postulate. Other results: $n/5$ works if $n\gt 24$, $n/16597$ works if $n\gt 2010760$, $n/(25\ln^2n)$ works if $n\gt 396738$. – Jonas Meyer Oct 31 '10 at 8:07
I've posted a related question at MathOverflow: mathoverflow.net/questions/44466 – Charles Nov 1 '10 at 21:22

The keyword you want is prime gap. The best unconditional result I can see on that page appears to be $O(n^{3/4 + \epsilon})$ for any $\epsilon > 0$. With the Riemann hypothesis you get $O(\sqrt{n} \log n)$, but a famous conjecture asserts that you should be able to do considerably better, something like $O((\log n)^2)$.

-
Baker-Harman-Pintz achieve O(n^(21/40)) which is almost as good as Cramer's conditional result you mention (but of course not as good as his conjecture). – Charles Nov 1 '10 at 16:32
@Charles: nice. Do you want to update the Wikipedia article with that information? – Qiaochu Yuan Nov 1 '10 at 17:12

There are many things that are known about this. Most of which I believe come from something called the Prime Number Theorem, which you can read about on wikipedia.

Something that might be helpful with regards to your question are the formulas in this section:

http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

The proofs for most of these theorems are really tricky and require a lot of knowledge of analysis though, so be warned!

-