Let $R(n)$ be the $n$th record gap between primes; $R(n)=\mbox{A005250}(n)$ in OEIS.

The paper arXiv:1709.05508 conjectures, among other things, that $$ R(n) = O(n^2) \tag{1} $$ and, more specifically, $$ R(n) \le n^2. \tag{2} $$

(The heuristic reasoning in arXiv:1709.05508 is based on (a) Cramer's conjecture and (b) a conjecture that record prime gaps occur more often than records in an i.i.d. random sequence of comparable length.) From computations, we know that the first 77 record (maximal) prime gaps (between primes below $10^{19}$) do satisfy $(2)$.

Can we reasonably say that $(1)$ and $(2)$ are true by accident (and therefore not amenable to proof)?

Edit: Many thanks @Gerhard and @reuns for your insights! Based on more thinking, I am now sure that in Cramer's probabilistic model of primes we can prove: with probability 1, the true order of magnitude of the $n$th record prime gap is $O(n^2)$ (I haven't found a reference yet, though). So, Gerhard's assessment below would mean that the true order of $n$th record gap between ordinary primes is less than that for Cramer's probabilistic primes.


1 Answer 1


I don't think it is true by accident in the sense of the linked post. I think the statements are a weak approximation of the truth, and that we have too little data to come up with a better approximation that appeals to intuition.

I am currently researching some functions which exhibit a mildly surprising behaviour. For the first few hundred values of n, they exceed sqrt(n). However, they are provably O(sqrt(n/\log n)), and I am still working hard to understand why. The proof is easy to understand, but I am still reconciling my intuition with what is provable. Further, these functions are likely to be O(n^\alpha) for some real \alpha less than 1/2, and I am struggling to explain why to myself. If it weren't for the additional knowledge I have, I might consider these functions as being greater than sqrt(n) "by accident".

For prime gaps (and objects based on Jacobsthal's function), the data we have suggests the true bounds are far from what we have proven. I think n^2 can be replaced by n(log n)^2 in (1), but I could not give a coherent rationale to back up that suggestion. I think maximal prime gaps grow at a slower than quadratic rate, that (2) is a convenient upper bound but asymptotically weak, and until a miracle happens we probably won't see even a decent heuristic for either (1) or (2) for a while. (I may change my mind after reading the referenced ArXiv print.)

Gerhard "Is Working On A Miracle" Paseman, 2018.01.04.

  • $\begingroup$ Thank you Gerhard. I do agree, we may just know too little, and statements (1) and (2) may be weak approximations to the truth. However, if Cramer's conjecture is true and if another conjecture in arXiv:1709.05508 is also true, namely, if the number of record gaps observed between primes below $x$ is $O(\log x)$, then $O(n^2)$ in (1) might well be the true order of $R(n)$. $\endgroup$
    – Alex
    Jan 5, 2018 at 6:13
  • $\begingroup$ I compared the truth with the random model for the primes ($X_n = 1_{n \text{ is prime}}$ are independent random variables with $P[X_n = 1] = \frac{1}{\log n}$) and the difference doesn't look too high. @Alex $\endgroup$
    – reuns
    Jan 5, 2018 at 13:34

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.