# Proving prime gaps not monotonic

I want to prove (or see a proof) that the prime gap function is not monotonic. (but not using extremely difficult theory like Zhangs proof please)

The idea for proof is to first suppose it is monotonic and find the slowest possible asymptotic growth it could have.

The get a contradiction by showing that even this is still "too fast" compared to say the chebychev bound $x/\log(x)$.

Lemma: A sequence of primes with gap $d$ can't be longer than $d+2$.

So we suppose the prime gap function $g(n)$ grows as slow as possible, like this:

1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 6, ...

Then I found that we would have $\pi(\sum g(n)) = n$, so $\pi(\sum_{d=2k} (d+2)^2) = \sum_{d=2k} d+2$. The first sum being $O(n^3)$ and the second $O(n^2)$. Inserting $n = x^{1/3}$ gives $\pi(x) = O(n^{2/3})$.

This gives us $x/x^{1/3}$ which sadly doesn't beat $x/\log(x)$.

Is this proof strategy doomed then? Or is there a way to repair it? Alternatively does anyone have an accessable reference which has this proof?

• You cannot have successive gaps like $4,4,4$ or $8,8,8$ or $10,10,10$ as they will lead to multiples of $3$ Feb 21 '16 at 17:41
• @Henry, I don't understand what you mean! Feb 21 '16 at 17:53
• One of $x,x+4,x+8$ is a multiple of $3$ for any integer $x$. More generally, one of $x,x+y,x+2y$ is a multiple of $3$ if $y$ is not a multiple of $3$. So your bound is looser than it needs to be. Feb 21 '16 at 18:04
• ok bounds are generally not exact. Feb 21 '16 at 18:05
• The 54th,55th,56th,57th primes each have a gap of 6. Feb 21 '16 at 18:54

This gives us $$x/x^{1/3}$$ which sadly doesn't beat $$x/\log(x)$$.

Is this proof strategy doomed then? Or is there a way to repair it?

There is no problem as the inequality holds the other way round. One should combine a hypothetical upper bound of order $$x/x^{1/3}$$ on the prime counting function, obtained under the assumption of monotone gaps, with a lower bound on the prime counting function to get a contradiction.

The point is if the gaps would grow monotonically they would be large so it is natural there would be too few primes then.

• $x/x^{1/3}$ is a lower bound though, we got it by assuming $g(n)$ grew as slowly as possible. since $x/\log(x)$ grows faster than this we haven't got a contradiction. To get an upper bound I would need to assume $g$ grows as fast as possible and put some limit on that, I don't see any way to do that. Feb 21 '16 at 17:55
• No it is not a lower bound on the number of primes. When I tell you it takes me at least $10$ minutes to write an answer post. Then assuming the minimal possible gap of ten minutes between two answers, after two hours of my work is $12$ answers an upper or lower bound on the number of answers I wrote?
– quid
Feb 21 '16 at 17:58
• It just hit me! I get it now, thank you so much. A lower bound on the gaps translates into an upper bound on the number of primes. Feb 21 '16 at 18:02
• That's great! I can see how the switch of orders can be confusing at first.
– quid
Feb 21 '16 at 18:03

Henry's observation solves the problem relatively simply.

A gap of length $d$ cannot repeat more than $p$ times where $p$ is the smallest prime not dividing $d$.

Let $f(d)$ be any increasing upper bound function for maximum number of consecutive gaps of length $d$. By the previous paragraph, $f$ can be taken to be $O((\log d)^c)$. For a logarithmic choice of $f$ let $g$ be its sum, the function with $g(n+1) - g(n) = f(n)$. Then asymptotically $g(n) \sim nf(n)$.

An increasing integer sequence $P_n$ whose gap lengths are bounded by $f$ has a subsequence $P_{g(n)}$ with strictly increasing differences and thus bounded below by a quadratic function $\frac{n(n+1)}{2}$. Composing this with $g^{-1}(n) \sim \frac{n}{f(n)}$ we get a nearly-quadratic lower bound on $P_n$ which is far larger than the $n$-th prime for large $n$.

• we can have 3 primes in a row with the same gap though. doesn't that mean we can't apply this argument? Feb 21 '16 at 18:53
• The 54th,55th,56th,57th primes each have a gap of 6. Feb 21 '16 at 18:53
• That's right, so I mis-stated the observation by Henry. There is no constant upper bound on the gap repetition, but a logarithmic function of the gap size $d$ equal to the smallest prime not dividing $d$. This would imply a lower bound of $O(n^2 / \log(n)^k)$ for some $k$ by the same argument.
– zyx
Feb 21 '16 at 19:05
• That's really interesting and I'd like to understand it more! Would you say this approach gives a shorter proof or just an alternative way of looking at the problem? Feb 21 '16 at 19:08
• (I guess this has to do with the primorial function needing to be a divisor of a long AP of primes) Feb 21 '16 at 19:08