Generalisation of Bertrand’s postulate: not just one but two primes

number theoryprime numbers

Just a sunday's question. Bertrand's postulate states that for every $n>1$, there is always at least one prime $p$ such that $n \lt p \lt 2n$.

Playing around with some small numbers suggests the question if there is possibly not just one but there are at least two primes in that interval.

From the following numerical example we can see that the answer seems to be affirmative for $n\ge6$

\begin{array}{ccc}
n&\{n-1,2n-1\}&\text{list of primes }p\\
1 & \{0,1\} & \{\} \\
2 & \{1,3\} & \{3\} \\
3 & \{2,5\} & \{5\} \\
4 & \{3,7\} & \{5,7\} \\
5 & \{4,9\} & \{7\} \\
6 & \{5,11\} & \{7,11\} \\
7 & \{6,13\} & \{11,13\} \\
8 & \{7,15\} & \{11,13\} \\
9 & \{8,17\} & \{11,13,17\} \\
10 & \{9,19\} & \{11,13,17,19\} \\
\end{array}

Question

I would greatly appreciate some references for this most probably well known result.

EDIT

Here I add some plots which show the number of primes between $n+1$ and $2n-1$ over different ranges of $n$.

I have fitted the curves with the function

$$b(n) = \frac{A n }{\log(1+B n)}$$

The parameters are shown in the plots.

enter image description here

enter image description here

enter image description here

Discussion

  1. These graphs illustrate the proof of Erdös: "for any $k$ and sufficiently large $n$ there are always at least $k$ primes between $n$ and $2n$", as was pointed out in a comment of @lulu and in the solution of @Thomas Preu

  2. The number $b(n)$ is not monotonous on a small scale.

  3. The shape of the fitted functions is just what was to be expected from the prime counting function $\pi(n)$. Indeed we have exactly just $b(n) = \pi(2n) – \pi(n)$.

Best Answer

According to wikipedia on prime gaps there is a prime in every interval of the form $[x,x+x^{0.525}]$ for large enough $x\geq x_0$.

This implies immediately that $[n,2n]$ contains at least two primes for large enough $n\geq n_0$.

But this result seems to be nonexplicit about the bounds $x_0$ respectively $n_0$.

In a paper of Dusart you can find the explicit result (Proposition 6.8): there is a prime in every interval $\left(x,x\left(1+\frac{1}{25(\ln(x))^2}\right)\right]$ for $x\geq x_0=396738$.

The proof given there establishes this result only for $x\geq x_0'=3.8\cdot 10^6$. I guess the comparatively small gap between $x_0$ and $x_0'$ got checked numerically and the author doesn't even bother to mention it.

Since $1+\frac{1}{25(\ln(x))^2}$ is monotonically decreasing and $1+\frac{1}{25(\ln(x_0))^2}<1.00602<\sqrt{2}$ this implies your result for all $n\geq x_0$.

The $n<x_0$ can quickly be checked numerically. And it turns out to be true for $x_0>n\geq n_0=6$.

Remarks: As lulu pointed out in the comments, Dusart's result can be used to find for every $\epsilon>0$ and $k\geq 1$ an $x_{0,\epsilon,k}$ such that for all $x\geq x_{0,\epsilon,k}$ we have at least $k$ primes in $\left(x,\left(1+\epsilon\right)x\right]$.

Solving $1+\frac{1}{25(\ln(x))^2}=(1+\epsilon)^{1/k}$ we get $x_{0,\epsilon,k}=\max\left\{e^{\left((1+\epsilon)^{1/k}-1\right)^{-1/2}/5},x_0\right\}$.

This bound is actually fairly practical: It seems that only for $\epsilon$ and $k$ with $\frac{k}{\epsilon}\geq 10^4$ the bound $x_{0,\epsilon,k}$ starts to "explode".

These bounds are exponentially worse than what is expected to be true about prime gaps in conjectures (e.g. Cramér's conjecture) that mathematicians seriously persue and that have been checked numerically at least up to $10^{19}$ (cf. this paper).

Related Question