Empirically it seems

$$\lim_{k\to \infty} \frac{1}{k}\sum_{n=1}^k \frac{g(n)}{\log p(n)} = 1\tag{1} $$ in which p(n) is the nth prime and g(n) is the prime gap $p(n+1)-p(n).$

Cramer conjectured that

$$g(n) = O\left(\log^2 p(n)\right). $$

My somewhat open-ended question is:

Formally how does (1) relate to Cramer's estimate (if at all)...and can we prove (1)?

For instance, we might have infinitely many values $\frac{g(n)}{\log p(n)}$ close to $0$ for prime gaps of $2$.

So clearly $(1) \nrightarrow g(n) \sim \log p(n).$ But can we say for general $f(n), g(n)$ for example that

$$\lim_{k \to \infty} \frac{1}{k}\sum \frac{f(n)}{g(n)} = 1 \rightarrow f(n) = O(g(n))? $$

I would prefer the question be construed broadly in case I have missed something about how these two ideas relate. Thank you for any insights.

  • $\begingroup$ What is $f(n)$ here? $\endgroup$
    – Kunnysan
    Commented Jul 11, 2013 at 16:19
  • $\begingroup$ Do you know Zhang recently (April, 2013) proved that there exist infinitely many primes $p,q$ such that $|p-q|<C$, so eventually $\liminf_{n\to \infty} g(n)=0$ $\endgroup$
    – Kunnysan
    Commented Jul 11, 2013 at 16:53
  • $\begingroup$ No, I meant what you claimed was Twin prime $conjecture$. Even it was unknown before Zhang's paper whether or not $\liminf_{n\to \infty} g(n)=C$. SO your example is true. It may not happen that $f(n)=O(g(n))$ $\endgroup$
    – Kunnysan
    Commented Jul 11, 2013 at 17:05
  • $\begingroup$ @Kunnysan: Yes. I am aware of Zhang's result. So I could substitute that in my argument. The question is already broad so I wanted to just mention the issue and leave it at that for simplicity's sake. My questions tend to be too involved so I am trying to keep them simple. $\endgroup$
    – daniel
    Commented Jul 11, 2013 at 17:07
  • $\begingroup$ Pardon me for my ignorance. $\lim_{k \to \infty} \frac{1}{k}\sum \frac{f(n)}{g(n)} = 1 \implies f(n) = O(g(n))?$ : Is this your question? $\endgroup$
    – Kunnysan
    Commented Jul 11, 2013 at 17:11

2 Answers 2


This is true, but it does not use any properties of prime gaps deeper than the prime number theorem.

Claim Let $2=p_1$, $p_2$, $p_3$, ... be an increasing sequence of positive integers with $p_{n+1} < 2 p_n$. Then $$\lim_{k \to \infty} \frac{\sum_{n=1}^k \frac{p_{n+1}-p_n}{\log p_n}}{\int_{t=2}^{p_{k+1}} \frac{dt}{\log t}} = 1.$$

For primes, the condition $p(n+1) < 2 p(n)$ is Bertrand's postulate. So this implies that your limit is $$\lim_{k \to \infty} \frac{1}{k} \int_{t=2}^{p(k+1)} \frac{dt}{\log t} = \lim_{p \to \infty} \frac{1}{\pi(p)-1} \int_{t=2}^{p} \frac{dt}{\log t}.$$ By the prime number theorem, this limit is $1$.

So, let's prove the claim. The function $1/\log t$ is decreasing. So the integral $\int_{t=2}^{p_{k+1}} \frac{dt}{\log t}$ is bounded above and below by its left and right Riemann sums. We choose a Riemann sum whose division points are $p_1$, $p_2$, ..., $p_{k+1}$: $$\sum_{n=1}^k \frac{p_{n+1}-p_n}{\log p_n} \ > \ \int_{t=2}^{p_{k+1}} \frac{dt}{\log t} \ > \ \sum_{n=1}^k \frac{p_{n+1}-p_n}{\log p_{n+1}} > \ \sum_{n=1}^k \frac{p_{n+1}-p_n}{\log p_{n} + \log 2}$$ where the last inequality is by the Bertrand like condition.

For any $\epsilon>0$, there will be some $m$ such that $\log 2/\log p_n < \epsilon$ for $n > m$. So the last term is $$> \sum_{n=1}^m \frac{p_{n+1}-p_n}{\log p_{n} + \log 2} + \frac{1}{1+\epsilon} \sum_{n=m+1}^k \frac{p_{n+1}-p_n}{\log p_n} = -C_{\epsilon} + \frac{1}{1+\epsilon} \sum_{n=1}^m \frac{p_{n+1}-p_n}{\log p_{n}}$$ for a constant $C_{\epsilon}$. So the limit in the claim is bounded between $1$ and $1/(1+\epsilon)$ for any $\epsilon>0$.

  • 2
    $\begingroup$ Splendid result--I would like to accept both answers and for very different reasons. I cannot gauge the importance of the gesture and don't want to offend anyone. One answer gives me the context I sought and the other the an instructive answer to a question I thought very difficult. Suggestions? $\endgroup$
    – daniel
    Commented Jul 13, 2013 at 5:53
  • 2
    $\begingroup$ @daniel: I have no problem if you accept David's answer since it probably took him more time to actually prove this result! $\endgroup$
    – blabler
    Commented Jul 13, 2013 at 18:48

It is conjectured that the proportion of $n < k$ for which $$ \frac{g(n)}{\log p(n)} \in (\alpha, \beta) $$ tends to $$ \int_{\alpha}^{\beta} e^{-t} dt $$ This is far from proven but we have some partial results, see http://arxiv.org/abs/1103.5886. But certainly, assuming the conjecture on the distribution of $g(n)$ it follows that your limit should tend to $$ \int_{0}^{\infty} t e^{-t} dt = 1 $$ as you've empirically noticed. The limit relation certainly does not imply that $f(n) = O(g(n))$ since it is known for prime gaps that for any constant $K > 0$ and for infinitely many $n$, we have $g(n) > K \log p(n)$. The relation of $(1)$ to Cramer's conjecture is in that both are related to the distribution of $g(n)$. The limit relation $(1)$ is the first moment of the distribution. While Cramer conjecture corresponds to the extreme case of the distribution of $g(n)$. Otherwise asking for a relation amounts to asking as to whether there is a relation between the mean and the tails of a distribution. The answer is not really unless you have some additional information.

Finally some remarks. Notice that if the conjecture on the distribution of the gaps failed then the limit could be $\neq 1$. Therefore to prove that the limit is one you will need some amount of control on the average distribution of the gaps. Essentially you are asking about the first moment of the distribution of gaps between primes. Since the first moment is easier than the full distribution there might be some hope of proving $(1)$. As far as the information contained in the first moment, it is not very much, unless you can add some other moments, such as the second one (the variance).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .