Let $g(n)$ be the distance between the $n$th prime and the next.

By elementary means we can see that $g(n)$ is not eventually constant and that $g(n)$ is not strictly monotonic.

Further we know that it isn't eventually monotonic (meaning $g(k) \le g(k+1) \le g(k+2) \le \cdots$) by extremely advanced theorems like Zhangs result that some finite gap occurs infinitely often.

It was hinted to me that there is an easier proof though, that doesn't depend extremely advanced results. Could anyone point me to one please?

  • 2
    $\begingroup$ Presumably, you mean "not eventually monotonic." Because it can clearly be demonstrated to not be monotonic. Such as $13-11<11-7$. $\endgroup$ Feb 10, 2016 at 15:26
  • $\begingroup$ How about that $[p#, p#+p]$ are all composite. Then all you need is that some gap is less than $p$ $\endgroup$ Dec 24, 2018 at 23:38

1 Answer 1


In brief: You can tweak the linked to argument. All you need in addition is a reasonable bound on the number of consecutive primes that have the same difference. It is not hard to show a bound linear in the difference.

Then proceed as in the linked question, that is show that this leads to an upper bound on the number of primes below a certain threshold that contradicts well-known results.

There it is that the number of primes below $N^2$ is at most linear in $N$. Here it will be that the number of primes below $N^2$ is at most quadratic in $N$. Both are absurd.

In detail:

Let us first show that the number of consecutive primes with difference $d$ is at most $2d$.

A difference $d$ is fixed. Let $p$ be a an auxiliary prime that does not divide $d$, for example the next prime after $d$ (which by Bertrand's postulate is $<2d$).

We show that there can be at most $p+2$ consecutive primes with difference $d$. Let us consider $p_0, p_0 + d , p_0 + 2d , \dots, p_0 + p d, p_0 + (p+1)d$. modulo $p$. We show at least one of these numbers is not prime.

Since $p \nmid d$, we get that $p_0, p_0 + d , p_0 + 2d , \dots,p_0 + (p-1)d$ covers all congruence classes modulo $p$. Thus in particular one of these is $0$ modulo $p$. This means it is not a prime unless it is equal to $p$ itself. However this is only possible for $p_0$ or $p_0 + d$, as $p < 2d$. In this case, $p_0 + pd$ or $p_0 + (p+1)d$, respectively, is divisible by $p$ too and thus not prime.

Thus we have shown that the difference $d$ can occur at most $p+1$ times successively, and thus if the sequence of differences is not decreasing it can occur at most $p+1$ times in total. Recall that $p+1 \le 2d$. So, the difference $d$ occurs at most $2d$ times.

This implies that the size of the $1+ \sum_{d=1}^D 2d$-th prime is at least $2+ \sum_{d=1}^D (2d)d$.

Now the former sum is $1 + D(D+1)$ and the latter sum is $2 + \frac{D(D+1)(2D+1)}{3}$. This later expression is at least of size $D^3/2$ (leaving very small $D$ aside).

Yet by the prime number theorem we know that there are about $D^3/2/\log (D^3/2)$ primes below $D^3/2$. For sufficiently large $D$ this is much larger than $1 + D(D+1)$, and thus yields a contradiction to the $1 + D(D+1)$-th prime being greater than $D^3/2$.

  • $\begingroup$ I'm sorry but I don't see this, can anyone provide a reference please? $\endgroup$ Feb 11, 2016 at 22:56
  • $\begingroup$ What don't you see? Do you understand the argument linked? $\endgroup$
    – quid
    Feb 12, 2016 at 0:09
  • $\begingroup$ I am a bit puzzled why you place a bounty rather than just answering my question. Anyway I'll write some details soon. $\endgroup$
    – quid
    Feb 14, 2016 at 16:26
  • $\begingroup$ There are more details now. Let me know what if anything is not clear. $\endgroup$
    – quid
    Feb 14, 2016 at 22:06
  • 1
    $\begingroup$ Sorry for the delay in responding. Yes the basic reasoning is as you say. On the specific numbers, I fumbled that a bit. But as there are $p+2$ primes there are $p+1$ differences between them, and this is already impossible, so in fact we could get down to $p$. But you are right it is better to argue this with $d+1$. Anything coprime to $d$ will do. $\endgroup$
    – quid
    Feb 15, 2016 at 18:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .