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 http://arxiv.org/abs/1002.0442 .

  • $\begingroup$ I think this is the topic of the Polymath4 project. $\endgroup$ – Péter Komjáth Nov 1 '10 at 18:17
  • $\begingroup$ 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. $\endgroup$ – Charles Nov 1 '10 at 19:52
  • 1
    $\begingroup$ 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$. projecteuclid.org/euclid.rmjm/1268655519 $\endgroup$ – Junkie Aug 24 '11 at 6:27
  • 2
    $\begingroup$ Cheng's result unfortunately contains an arithmetic error, but Dudek recovered the result for $e^{e^{33.217}}$ and above: arxiv.org/abs/1401.4233 $\endgroup$ – Terry Tao Jun 8 '14 at 21:21

Your Answer

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

Browse other questions tagged or ask your own question.