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 defined as the number of positive primes $\leq x$.

The Prime Number Theorem states

$$\lim_{n \to \infty} \frac{\pi(n)}{n / \ln(n)} = 1.$$

I'm not sure how to go about doing this. I don't get how the $\frac{1}{2}$ would come into play. Can someone help me please?

  • $\begingroup$ Inceptio's point is that $p_{k+1}-p_k\geq 1 > \frac{1}{2}$ always. $\endgroup$ – Thomas Andrews May 24 '13 at 15:33
  • $\begingroup$ Kaish, is it your own problem? I'm sure you didn't mean $p_{k+1}-p_k > \dfrac{1}{2}.$ $\endgroup$ – Inceptio May 24 '13 at 15:51
  • 1
    $\begingroup$ @Inceptio Sorry, I completley missed out a bit. It is supposed to have $\ln(n)$ on the end, like I have edited in. $\endgroup$ – Kaish May 24 '13 at 18:58

So let's apply the hint given. By the definition, $m=\pi(n).$ If each gap $p_{k+1}-p_k\le \frac{1}{2}\ln n$ then the sum $p_m-p_1=\sum_{k=1}^{m-1}(p_{k+1}-p_k)\le m\cdot \frac{1}{2}\ln n=\frac{1}{2}\pi(n)\cdot \ln n.$ Hence, $p_m\le 2+\frac{1}{2}\pi(n)\cdot \ln n.$ Now, by the prime number theorem, starting from $n=n_0$ the quantity $\frac{\pi(n)\cdot \ln n}{n}<(1+\varepsilon),$ or $\pi(n)\cdot \ln n\le (1+\varepsilon)n.$ This can be used to estimate $p_m$ for $n\ge n_0:$ $p_m\le 2+\frac{1}{2}(1+\varepsilon)n.$ This means, that between $2+\frac{1}{2}(1+\varepsilon)n$ and $n$ there is no primes This contradicts some stronger version of Bertand's postulate.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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