# How differently would we model the distribution of primes if prime gap is larger?

Cramer's conjecture based on his random model provides prime gaps are bound by $$O(\log^2p_n)$$ where the gap is between $$(n+1)$$th and $$n$$th prime.

1. How differently would primes be modeled if gaps of $$O(2^{\mathsf{poly}(\log\log p_n)})$$ were indeed accurate?

2. $$RH$$ supports a gap hypothesis of $$O(\sqrt{p_n}\log p_n)$$ and so if this much larger gap were true will we be much off from 1. and would any 'random' model have any relevance?

• An estimate $O(g(x))$ need not be as large as $g(x)$, but is just upper-bounded by a constant multiple of $g(x)$, e.g., $\sin x = O(x^{55})$ as $x \to \infty$. So when you say RH predicts a gap of $O(\sqrt{p_n}(\log p_n)^2)$, that does not mean it predicts a gap on the order of $\sqrt{p_n}(\log p_n)^2$. Such a $O$-estimate is simply the sharpest people have been able to prove; we are dealing here with a lack of suitable technique to push the upper bound down to what is expected to be the true order of magnitude. (contd.) Jan 20 '21 at 3:49
• For comparison, Bach showed GRH implies that for composite $m \geq 3$, the least witness for the Miller-Rabin test on $m$ is $O((\log m)^2)$, but numerical data suggest the the least witness is $O(\log m)$. Only being able to prove $O((\log m)^2)$ from GRH does not mean the true order of magnitude can't be smaller than what that bound suggests. Jan 20 '21 at 3:49
• RH implies $\pi(x) = {\sf Li}(x) + O(\sqrt{x}(\log x)^2)$, but that $(\log x)^2$ is an artifact of what can be proved, not an indication that it is in some way a reflection of the true order of magnitude of the error term. There is no claim that the error term can't be $O(\sqrt{x}\log x)$ or even $O(\sqrt{x})$; it's just that nobody has ever shown something like that. In contrast, the exponent $1/2$ in the $\sqrt{x}$ piece of the error term is known to be optimal, since shrinking that would lead to a known false result (because there are nontrivial zeros with real part $1/2$). Jan 20 '21 at 3:55
• @KConrad yes I agree $O(\cdot)$ is not $\Omega(\cdot)$ but the problem is not about these issues. I mention 'So if this much larger gap were true..' and so the point is what if the truth is way off. Jan 20 '21 at 4:30
• @EmilJeřábek yes, I was careless there. Monach and Montgomery conjectured that $\pi(x) - {\rm Li}(x)$ is $O(\sqrt{x})$, with $|\pi(x) - {\rm Li}(x)|/\sqrt{x}$ being $O((\log\log\log x)^2/\log x)$ and $\Omega((\log\log\log x)^2/\log x)$. Jan 20 '21 at 12:08

If a proof was found of larger prime gaps than predicted, or any other property of primes counter current predictions, I think analytic number theorists would look to the method of proof for clues about a revised random model of the primes. For instance if the proof relied crucially on a newfound correlation between the primes and some arithmetic function $$f(n)$$, a random model might begin by modeling $$f$$ and then viewing the primes as random variables depending on $$f$$.
• Say a proof p is not np is true and a problem related to primegaps is shown np hard and so necessitates $\omega(poly(\log n))$ worst case gap for primes? This has nothing to do with zeta functions. Jan 21 '21 at 18:49
• @1.. One model that I think is RH-compatible and gives big gaps is to flip a coin for each $n$ and if it comes up heads, the primes between $n^2$ and $(n+1)^2$ are distributed a la Cramer but with twice the density, and if it comes up tails, there are no primes between $n^2$ and $(n+1)^2$. (This may not be compatible with everything we know about primes and zeta, though.) But we have no motivation for this model, so we can't say it's what we would choose if really large gaps are found. Jan 21 '21 at 19:12