7

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

Community
  • 1
Lavender Lullaby
  • 1,230
  • 3
    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). – Saeed Aug 23 '13 at 14:18
  • The answer you reference doesn't seem to state that there is a prime between $n^3$ and $(n+1)^3$ for all n. – user84413 Aug 23 '13 at 22:54
  • 1
    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). – Mike Bennett Aug 24 '13 at 16:06

1 Answers1

8

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

Peter Košinár
  • 10,810