3
$\begingroup$

Question

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

Motivation

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$.

Background

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).

Further

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$.

References

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 .

$\endgroup$
4
  • $\begingroup$ I think this is the topic of the Polymath4 project. $\endgroup$ Nov 1, 2010 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, 2010 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, 2011 at 6:27
  • 4
    $\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, 2014 at 21:21

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.