# Need help understanding proof to their being a prime gap $G(p_k, p_{k+1})$ with $p_k \leq n$ and $p_{k+1} - p_k > \frac{1}{2}\ln(n)$

Let $p_k ( k \geq 1)$ be an enumeration of all the positive primes with $p_1 = 2$ and $p_k < p_{k+1}$ for all $k \geq 1$. Prove that if $n$ is sufficiently large, then there is a prime gap $G(p_k, p_{k+1})$ with $p_k \leq n$ and $p_{k+1} - p_k > \frac{1}{2}\ln(n)$.

HINT: Let $m$ be the largest integer with $p_m \leq n$. Consider $\sum_{k=1}^m (p_{k+1} - p_k)$ and apply the Prime Number Theorem to $\pi(x)$.

$\pi(x)$ is the prime counting function.

I didn't have a clue how to do this so I looked in the answers and this is what it says:

If $n$ is sufficently large given $n$, we have $\pi(n) \leq \frac{5n}{4 \ln(n)}$. If $m$ is the largest integer with $p_m \leq n$, then $\pi(n) = m$. If $p_{k+1} - p_k \leq \frac{1}{2} \ln(n)$ for all $k \leq m$ then

$$n \leq p_{m+1} - 1 \leq 1 + \sum_{i = 1}^m(p_{k+1} - p_k) \leq 1 + \frac{1}{2} \ln(n) \cdot m \leq 1 + \frac{1}{2} \cdot \ln(n) \cdot \frac{5}{4} \cdot \frac{n}{\ln(n)} = 1 + \frac{5n}{8}.$$

This gives a contradiction if $\frac{3n}{8} > 1$, in paarticular, for $n \geq 3$.

Now, I kind of understand most of everything that's going on, but one this that's making it very hard is the very first line. Where does the $\frac{5}{4}$ come from? I know they've re-aranged the prime number theorem to get it in this form, but I don't get where that number comes from?

Can someone tell me?

-

If you substitute $\alpha$ for your $5/4$ and run your proof you will end up with the inequality $n\le1+\frac{\alpha}{2}n.$ Now to get a contradiction, you may take anything to satisfy $\alpha/2<1.$ So there is nothing special about $5/4$ here, except that it is $> 1$ (to satisfy the convergence in the Prime number theorem) and $\frac{5}{4}\cdot\frac{1}{2}<1.$

-
When you gave your version of this, I didn't get why (and in here) $p_m - p_1 < \frac{1}{2}m \ln(n)$. Why does the $m$ come into play? – Kaish May 26 '13 at 20:42
you have the sum that has $m$ elements of the form $p_{k+1}-p_k.$ Each of them, by our assumption does not exceed $1/2\ln n$ which gives the RHS. As to the left hand side, when you add $(p_2-p_1)+(p_3-p_2)+(p_4-p_3)+...(p_m-p_{m-1})$ the middle terms cancel out and you are left with $p_m-p_1.$ Hope it helps. – leshik May 26 '13 at 20:51
Oh ok, that bit makes sense now, thanks. I still don't get one more bit in this proof, where does the + 1 come from right at the begining? You don't seem to have that in your version? – Kaish May 26 '13 at 21:09
Not that in the present solution, the sum is being taken up to $p_{m+1}$ and is equal to $p_{m+1}-p_{1}=p_{m+1}-2.$ So the $+1$ makes this to be equal to $p_{m+1}-1$ which is greater than $n.$ In my solution, the summation goes up to $m$ and it forces us to use something more advance (Generalized Bertrand's Postulate). – leshik May 27 '13 at 3:10

Recall that by the Prime Number Theorem, we have $$\lim_{n\to\infty} \frac{\pi(n)}{\frac{n}{\log n}}=1.$$ Thus by the definition of limit, we have that for any $\epsilon\gt 1$, there is an $N$ such that if $n\gt N$ ("if $n$ is large enough") then $$\frac{\pi(n)}{\frac{n}{\log n}}\lt 1+\epsilon.$$ The prover picked $\epsilon=\frac{1}{4}$, because that is plenty good enough to push the proof through, as explained by leshik.

Remark: We do not really need the Prime Number Theorem to prove the result. A half century before the first proofs of PNT, Chebyshev had shown by "elementary" means that for large enough $n$, the ratio $\pi(n)/(n/\log n)$ is less than $1.12$.

-