Explanation of prime gap result

Question

In a video here the author (t. tao) says that following is easy consequence of: prime number theorem (PNT) and pigeonhole principle. He talks about this result:

P[n+1]-P[n]>=log P[n]

Can someone break it down, why this is the case? How come above follows from PNT and pigeonhole principle?

Answer 1

Let's first forget about primes. Instead let $\alpha \in (0,1)$, $m \geq 1$ and $2\leq p_1<p_2<\ldots$ be any increasing sequence such that $p_{k+1}-p_k < \alpha \log(p_k)$ for all $k\geq m$. Then for any $n >m$ $$ p_n-p_m = \sum_{k=m}^{n-1}(p_{k+1}-p_k) < \alpha \sum_{k=m}^{n-1} \log(p_k) < \alpha (n-m) \log(p_n)$$ or $$\frac{p_n}{\log(p_n)} < \alpha(n-m) + \frac{p_m}{\log(p_n)}.$$ By the PNT this precludes the sequence of prime numbers for any choice of $\alpha$ and $m$. In other words, for the sequence of prime numbers and any $\alpha\in (0,1)$, $m\geq 1$ there is an index $n>m$ such that $p_{n+1}-p_n \geq \alpha \log(p_n)$.

Answer 2

The least fancy way to express this: Not all the prime gaps can be shorter than average (otherwise the average would be smaller). The PNT tells you the average gap size and that the gaps are not all the same from some point on (the average gap size slowly increases). The pigeonhole principle here uses two bins: $p_{n+1}-p_n \geq \ln p_n$ and $p_{n+1}-p_n < \ln p_n$. If, for some $N$, all the $n>N$ have gap sizes in the second bin, then the average gap size is smaller than the PNT says it is.${}^1$ Consequently, you never run out of gap sizes in the first bin; that is, there are infinitely many prime gaps $p_{n+1}-p_n \geq \ln p_n$.

WimC's answer expresses this for any sequence $(s_1, s_2, \dots)$ having average gap size $\alpha \ln s_n$ for some constant $\alpha \in (0,1)$. He's showing that this application of the pigeonhole principal applies to any sequence with the density given by the PNT, not just to the primes. So the argument Dr. Tao is referencing doesn't depend on (extra) features of the primes, just on the average gap size given by the ("easy") PNT. WinC is also showing that the "$1+o(1)$" isn't essential either -- if you have any constant there, no matter how close to zero, you never run out of gaps bigger than the average.

${}^1$: This depends on the fact that there are infinitely many primes. If we split the sequence of gaps into a finite initial segment and the infinite sequence after that, the average gap size is the average of the infinite part -- the contribution from the finite segment is overwhelmed by the contribution from the infinite part. As simple model of this: for the sequence $(1, 0, 0, 0, \dots, 0, \dots)$, find the average of the first $k$ terms. It's $1/k$. As you let $k$ go to $\infty$, the average shrinks to zero. That is, the contribution from the finite initial segment is gradually overwhelmed by the average of infinitely many zeroes.