What asymptotic lower bounds are known on the number of primes between $n$ and $2n$, call it $\Pi(n) = \pi(2n)-\pi(n)$? Obviously Bertrand's Theorem is the statement that $\Pi(n) \geq 1$ for all $n$, and the PNT says that $\Pi(n) \approx \frac{n}{\log n}$ but doesn't provide a lower bound.

It seems like Hoheisel's result on prime gaps that there exists a $\theta \lt 1$ such that $\pi(x+x^\theta)-\pi(x) \approx \frac{x^\theta}{\log x}$ (as seen at http://en.wikipedia.org/wiki/Guido_Hoheisel ) should give a lower bound of the form $\Pi(n) \geq k\frac{n}{\log n}$ for some $k$ by stacking up $O(x^{1-\theta})$ such intervals; more precisely, if we take $c=2^{\theta}$ and $f(x) = x+x^\theta$, then since $x^\theta \leq cn^\theta$ for $x\leq 2n$, we have $f^{\circ t}(n) = f^{\circ(t-1)}(n) + \left(f^{\circ(t-1)}(n)\right)^\theta\leq f^{\circ(t-1)}(n) +cn^\theta\leq n+ctn^\theta$ as long as $ctn^\theta \lt n$ - or in other words, as long as $t\lt t_0 = c^{-1}n^{1-\theta}$, and therefore $$\begin{align*} \Pi(n) &= \pi(2n)-\pi(n) \\ &\geq \sum_{i=0}^{t_0-1} \left(\pi(f^{\circ (i+1)}(n))-\pi(f^{\circ i}(n))\right) \\ &\geq \sum_{i=0}^{t_0-1}\frac{(f^{\circ i}(n))^\theta}{\log f^{\circ i}(n)} \\ &\geq \sum_{i=0}^{t_0-1}\frac{n^\theta}{\log n} \\ &= t_0 \frac{n^\theta}{\log n} \\ &= c^{-1}\frac{n}{\log n} \end{align*}$$

Is this reasoning correct? It makes sense to me, but I'm surprised I've never seen such an explicit lower bound given before. While I'm more interested in the asymptotics, I'm also curious about the precise constants; if this is a known lower bound, is anything known about explicit $k$ such that $\Pi(n) \geq k\frac{n}{\log n}$ for all $n$ (or even all $n\gt n_0$)?

  • 3
    $\begingroup$ There are versions of the prime number theorem with bounds. Take a lower bound for $\pi(2n)$ and an upper bound on $\pi(n)$. $\endgroup$ – Hurkyl May 24 '12 at 18:09
  • $\begingroup$ @Hurkyl D'oh - of course, that's much easier than the path I went down and gives the same result. Feel free to give that as an answer! $\endgroup$ – Steven Stadnicki May 24 '12 at 18:31

Quick and dirty bounds on the prime counting function are, for $n > 55$:

$$ \frac{n}{\log n + 2} < \pi(n) < \frac{n}{\log n - 4}, $$

and so you get the bounds

$$ \frac{2n}{\log(2n) + 2} - \frac{n}{\log n - 4} < \pi(2n) - \pi(n) < \frac{2n}{\log(2n) - 4} - \frac{n}{\log(n) + 2}. $$

Better bounds are available, but I find these simple enough that I prefer them when they are good enough for my purposes. From here, you should be able to massage them into whatever form you want (assuming you aren't looking for stronger approximations, of course).

  • $\begingroup$ I understand how you've arrived at this answer, but when I graph $\frac{2n}{log(2n)+2} - \frac{n}{logn - 4}$ I get an output of about 52 for n = 56. I know for a fact that there are not that many primes between 56 and 112. $\endgroup$ – Linus Rastegar Dec 26 '16 at 20:25
  • 1
    $\begingroup$ @Linus: Natural logarithm, not log base 10. $\endgroup$ – Hurkyl Dec 26 '16 at 20:28
  • $\begingroup$ Thanks for this clarification, but the graph now shows a negative value for 56. $\endgroup$ – Linus Rastegar Dec 26 '16 at 20:34
  • $\begingroup$ @Linus: And the number of primes in the interval $[56,112]$ does, indeed, exceed $-2192$. The relative error of the estimate will decrease as $n$ grows. $\endgroup$ – Hurkyl Dec 26 '16 at 20:40

PNT says that $$\pi(2n) = 2n/\log(2n) + o(2n/\log 2n) = 2n/(\log n + \log 2) + o(2n/(\log n+\log 2)) = 2 (n/\log n) + o(n/\log n)$$ and that $\pi(n) = n/\log n + o(n/\log n).$ Putting these together gives $$\pi(2n) - \pi(n) = n/\log n + o(n/\log n ),$$ or equivalently, $$\pi(2n) - \pi(n) \sim n/\log n.$$

If you put in an actual bound for the error term in the prime number theorem, you can get an actual bound here as well. In any case, it shows that you can take $k$ as close to $1$ as you like, if $n$ is large enough.


This problem is very closely related to Ramanujan primes, $R_n$:

$$\pi(x) - \pi(x/2) \ge n\text{ for all }x \ge R_n.$$

Clearly, by letting $x=2y$ we see that there are $n$ primes between $y$ and $2y$.

See https://en.wikipedia.org/wiki/Ramanujan_prime. And see the OEIS sequence A104272.


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.