9
$\begingroup$

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$)?

  • 0
    @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!2012-05-24

3 Answers 3

7

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

  • 0
    @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.2016-12-26
5

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.

1

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.