Consequence of Bertrand's Postulate

I read that the following can be proved using Bertrand's postulate (there's always a prime between $n$ and $2n$): $\forall N\in\mathbb N$, there exists an even integer $k>0$ for which there are at least $N$ prime pairs $p$, $p+k$.

But I have no idea how to prove it. Any help would be much appreciated.

Many thanks.

• I believe I answered the wrong question. I thought you were asking to show there was a $k$ such that there were $N$ primes between $p$ and $p+k$. I have deleted my answer, and will think about the originally intended question. Dec 15 '11 at 16:45
• By the way, where did you read this claim? Dec 15 '11 at 16:48
• I read it here, on the very last page: math.dartmouth.edu/~thompson/Bertrand%27s%20Postulate.pdf Dec 15 '11 at 16:58
• @user19012, nice slides!
– lhf
Dec 15 '11 at 17:43

You don' need Bertrand's Postulate to prove it, it is enough with Euler's theorem on the divergence of $\sum \frac{1}{p}$. The argument is as follows:

For some integer $n$, consider the $n-2$ differences $p_{i+1}-p_i$ for $i=2,3,\dots, n-1$, if they take at most $$T_n = \left\lfloor\frac{n-2}{N}\right\rfloor$$ different values then there is at least one taken $N$ times and we are done.

Suppose otherwise that for every $n$ there are more than $T_n$ different values in the set $\{ p_{i+1}-p_i\,\,; i=2,3,\dots,n\}$ then $$p_n - p_2 = \sum_{i=2}^{n-1} p_{i+1}-p_i \ge 2+4+6+\dots+2T_n+2(T_n+1) = (T_n+1)(T_n+2)$$ but $$(T_n+1)(T_n+2) \ge \frac{(n-2)^2}{N^2}$$ So $$\frac{1}{p_n} \le \frac{N^2}{(n-2)^2 + 3N^2}$$ if we fix $N$ and sum for $n=N,N+1,\dots,M$ we get $$\sum_{i\le M} \frac{1}{p_i} \le -\sum_{i\le N} \frac{1}{p_i} + N^2 \sum_{N\le n \le N} \frac{1}{(n-2)^2 + 3N^2}$$ But the right hand side is bounded and by Euler's theorem the right hand isn't so for $n$ large enough we get a contradiction.

Note that this proves something stronger: for every $N$ there is an integer $k$ such that there are more than $N$ consecutive primes with difference $k$.

I read this argument in some old issue of the American Math Monthly (in 1985 or earlier), I'm sorry I can't give a reference.

• user19012: It was my fault there was a flaw in the argument. I have corrected it. Dec 19 '11 at 16:07
• Thanks, I get it now. But surely it doesn't prove that the primes are consecutive, right? Dec 20 '11 at 1:40
• It proves that for every $N$ there exist a $k$ such that there are $N$ (or more) pairs of consecutive primes with common difference $k$. The problem if there are $N$ consecutive primes with common difference $k$ is AFAIK open, though is related to Green-Tao theorem. Dec 20 '11 at 9:06
• Sorry, I was being stupid, I thought you were implying the gaps were consecutive. I get it now, thanks a lot for your help. Dec 24 '11 at 1:27

It's not a direct consequence of the postulate. Indeed, consider the set $P = \{ 2^k : k \geq 0\}$. This set also satisfies Bertrand's postulate, but the differences $2^a - 2^b$ are unique.

• Actually this set doesn't satisfy the Bertrand postulate. There is no element of $P$ strictly between $n$ and $2n$ when $n \in P$. Dec 19 '11 at 16:09