MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


What is the best known effective upper bound on the prime gap following x?


Suppose you needed to show a good bound for the gap between a fixed large constant, say $G=10^{10^{100}}$, and the following prime. Bertrand's postulate gives $G$, but we know unconditionally that the prime gap is $O(G^\theta)$ for $\theta$ near 1/2, so $G^\theta$ seems more reasonable. But it seems that the best that can be proved at present is much larger: $G/k\log^2G$.


Bounds on large prime gaps seem to fall into three categories. We expect that the maximal prime gap below x is polylogarithmic: Cramér conjectured that it is $O(\log^2 x)$. (Maier suggests that the constant should be about $2e^{-\gamma}$.)

With the Riemann hypothesis, the gap falls to $O(\sqrt x\log x)$ thanks to Cramér. The unconditional result, due to Baker, Harman, & Pintz (extending Ingham's method), is nearly as good: $O(n^{21/40})$.

Schoenfeld's result allows an effective version of Cramér's conditional result with a constant near $1/4\pi$. But for an unconditional effective result, I know of nothing better than Dusart's $x/25\log^2x$.

That is, the results fall into three categories: those with exponent near 0 (Cramér's conjecture, Maier's theorem, etc.); those with exponent near 1/2 (Baker-Harman-Pintz, Cramér); and those with exponent near 1 (Rosser & Schoenfeld, Dusart, Chebyshev).


If, as I suppose, there are no further results known, I raise this "soft" question:

Why is "the best we can (effectively) prove" in the same neighborhood as Bertrand's postulate, even though we can show much more (and expect quite a bit more)? It might be too much to expect an effective version for $\theta=0.525$, but we lack such a result for Chudakov's $\theta=3/4+\varepsilon$ and even Hoheisel's $\theta=32999/33000$.


On request. Most of the papers I gave are well-known: Maier 1985, Baker-Harman-Pintz 2001, Schoenfeld 1976, etc. The Dusart preprint is at .

share|cite|improve this question
I think this is the topic of the Polymath4 project. – Péter Komjáth Nov 1 '10 at 18:17
They're trying to find a weak result in the first category (working in polynomial time); I'm trying to find an improvement from the third to the second (from exponential to exponential). They don't need to prove that gaps are small, though that would suffice. So there's a relationship, but it's not that strong. A polynomial-time algorithm for the last bit of pi(x) would solve polymath4 but not my problem, unless it could be shown that it flips in short intervals. – Charles Nov 1 '10 at 19:52
There are effective versions of $x^{1-\theta}$ for various $\theta>0$, but the interest in them seems rather low. One explicit example is Cheng's result, which says that $e^{e^{15}}$ suffices to have a prime between $x^3$ and $(x+1)^3$. – Junkie Aug 24 '11 at 6:27
Cheng's result unfortunately contains an arithmetic error, but Dudek recovered the result for $e^{e^{33.217}}$ and above: – Terry Tao Jun 8 '14 at 21:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.