Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have an assignment question that asks me to show that the sequence of prime gaps is never strictly monotonic. I'm also allowed to assume the Prime Number Theorem.

I've managed to show that it cannot be strictly decreasing by considering the numbers $N!+2, N!+3,...,N!+N$ which gets arbitrarily large as $N\rightarrow\infty$.

However, I seem to not be able to show the strictly increasing bit. I have an idea but I'm not sure if it works and whether it is a suitable usage of the Prime Number Theorem.

Here is my idea: Suppose $\pi(n_0)=k$ and $d(n)$ is strictly increasing $\forall n\geq n_0$. Then we consider the "worst case scenario" (call it $\pi_1$) of finding primes at gaps $2,4,6,...$ after $n_0$, meaning that $n_0+2,n_0+2+4,n_0+2+4+6,...$ are the primes.

Then what I'm saying is $\pi_1(n_0+q(q-1))=k+q-1$ because of the arithmetic progression. I don't know if we can give any comparisons between $\pi(n)$ and $\pi_1(n)$ but I also don't see if this actually leads to anything. If I'm totally off track, I'll be glad if somebody can point me in the right direction.

I can't seem to find any literature regarding this either!

share|cite|improve this question
You have $\pi(n) \leqslant \pi_1(n)$ for $n > n_0$. Can you derive an asymptotic behaviour of $\pi_1$ that contradicts the Prime Number Theorem? – Daniel Fischer Oct 17 '13 at 22:04
That's the thing. I'm not sure if we can safely say that $\pi(n)\leq\pi_1(n)$ or even any meaningful comparison though? What if the actual prime gap was something like 2,2,2,... for a long sequence and then shot up to some huge number to overturn the inequality after that? – Haikal Yeo Oct 17 '13 at 22:08
Under the assumption that the prime gaps are strictly increasing after $n_0$ you have $\pi(n) \leqslant \pi_1(n)$ for $n > n_0$. Because under that assumption, you have $\pi_{m+1} - \pi_m \geqslant 2(m-k+1)$ for $m \geqslant k = \pi(n_0)$. So if $r_j = n_0 + 2 + 4 + \dotsb 2j$, then $p_{k+j} \geqslant r_j$. – Daniel Fischer Oct 17 '13 at 22:14
Zhang proved that there are infinitely many prime pairs with a difference not exceeding $7\times 10^7$. This shows that an INFINITE strictly increasing difference sequence is impossible. – Peter Aug 28 '15 at 9:17
up vote 4 down vote accepted

As per your ides, there cannot be essentially more than $q$ primes below $q^2$ (give or take low order stuff like your constants $k$ and $n_0$), i.e. $\pi(q^2 )<q$. As $\pi(q^2)\approx \frac{q^2}{\ln q^2}=\frac q2\cdot \frac q{\ln q}\approx \frac q2\pi(q)$, this leads to $\pi(q)<2$, which is absurd. (Check that dropping low order terms was indeed allowed!)

share|cite|improve this answer
Could you elaborate a little on how you obtained the inequality $\pi(q)<2$ from the previous statement? – Haikal Yeo Oct 17 '13 at 22:33

It looks as if you're on a good track.

Suppose that after $p_n$, the gaps $d_n := p_{n+1} - p_n$ are strictly increasing, so that surely $d_{n+k} \geq k$. We can estimate $p_{n+k}$: $$p_{n+k} > d_{n+k-1} + \dots + d_{n} \geq (k-1) + (k-2) + \dots + 1 = \frac{k(k-1)}{2} \gg k^2.$$

But this is a problem, because $\pi(p_{n+k}) = n +k \ll k $ on one hand, and on the other $$\pi(p_{n+k}) \gg p_{n+k} / \log p_{n+k} \gg k^2/\log k.$$ It remains to convince yourself that these estimates are not compatible.

Above $f(k) \ll g(k)$ stands for "there are constants $C$ and $k_0$ with $f(k) \leq C g(k)$ for $k \geq k_0$.

Note that the function $x/\log x$ is increasing, which is used above.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.