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

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?

share|cite|improve this question
up vote 2 down vote accepted

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.$

share|cite|improve this answer
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$.

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.