In this answer, it is mentioned that for $q=3$, we are guaranteed the existence of a prime between $n^q$ and $(n+1)^q$, and that it is conjectured that this is true for $q=2$. I am wondering though, how close to $2$ have we gotten? In other words, as of today, what is the smallest $q$ such that there is always a prime $p$ satisfying

$$n^q <p<(n+1)^q\;\;\text{for all}\; n\,?$$

If possible, I would be delighted to see a link towards a proof of the answer to this question (or a reference, which I can look up).

  • 3
    $\begingroup$ Prime distances is $O(\log n)$, so if you edit the $\forall n$ and change it to $\forall n > f(\epsilon)$, then you have to get the result for $q=1+\epsilon$(I guess). $\endgroup$
    – Saeed
    Aug 23 '13 at 14:18
  • $\begingroup$ The answer you reference doesn't seem to state that there is a prime between $n^3$ and $(n+1)^3$ for all n. $\endgroup$
    – user84413
    Aug 23 '13 at 22:54
  • 1
    $\begingroup$ What do you mean by ``prime distance is $O(\log n)$''? The best known result on largest prime gaps would give the desired result for a given $q > 40/19$, for suitably large $n$ (Baker, Harman and Pintz). $\endgroup$ Aug 24 '13 at 16:06

The Wikipedia entry on Prime gaps can serve as a good starting point for this problem.

The best known unconditional bound on the size of the prime gaps is due to Baker, Harman, Pintz who proved that there is always a prime between $x$ and $x+x^{21/40}$ for sufficiently large $x$. Applying this result to the interval $(n^q, (n+1)^q)$ by using the estimate $(n+1)^q \geq n^q + qn^{q-1}$ tells us that taking $q\geq 40/19$ will work for sufficiently large $n$.

Some of the well-known conjectures could get it further down:

  • Riemann Hypothesis and also the weaker Lindelöf hypothesis imply that $q$ can be taken to be equal to $2+\varepsilon$ for any $\varepsilon>0$. They're both just short of getting us to $q=2$, though.
  • While it is not true that prime gaps are $O(\log n)$ as one comment suggested, Cramér's conjecture claims they are $O(\log^2 n)$, which would allow us to take $q=1+\varepsilon$ for any $\varepsilon>0$.

All the bounds above hold for $n$ large enough. If we really insist on the bound being valid for any positive integer $n$, it's possible to show that $q>\log_{95}(1151)$. This can be done by looking for closed intervals $I_{n,k}$ such that for any $q\in I_{n,k}$, we have $p_k \leq n^q \wedge (n+1)^q \leq p_{k+1}$ (where $p_k$ denotes $k$-th prime). In other words, if the interval is non-empty, it can be expressed as $$I_{n,k}=\left[\log_{n}(p_k),\log_{(n+1)}(p_{k+1})\right]=\left[\frac{\log p_k}{\log n},\frac{\log p_{k+1}}{\log (n+1)}\right]$$ Since our desired $q$ has to work for all $n$, it cannot be member of any such interval. Thus, in order to show the bound mentioned above, it suffices to exhibit a set of intervals whose union covers $[1,\log_{95}(1151)]$. One such set is listed below (just the indices $(n,k)$ of $I_{n,k}$): $(3,2)$, $(6,4)$, $(5,4)$, $(7,6)$, $(10,9)$, $(4,4)$, $(24,30)$, $(119,217)$, $(35,47)$, $(8,9)$, $(22,30)$, $(32,47)$, $(105,217)$, $(94,189)$. Of course, this bound might not be final; it's based only on computer-aided calculation over small values of $n$ and $k$.

In the unproven land, Legendre's conjecture states that exponent $q=2$ should work for all $n$. Also, there is an explicit bound available for the $q=3$ case; so we know that it is true (at least) for $n\geq e^{e^{15}}$ and thus can have at most finitely many "failures".


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.