0
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ 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.) $\endgroup$
    – KConrad
    Jan 20, 2021 at 3:49
  • 2
    $\begingroup$ 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. $\endgroup$
    – KConrad
    Jan 20, 2021 at 3:49
  • 2
    $\begingroup$ 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$). $\endgroup$
    – KConrad
    Jan 20, 2021 at 3:55
  • $\begingroup$ @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. $\endgroup$
    – Turbo
    Jan 20, 2021 at 4:30
  • 2
    $\begingroup$ @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)$. $\endgroup$
    – KConrad
    Jan 20, 2021 at 12:08

1 Answer 1

Reset to default
2
$\begingroup$

I think a short answer is we don't have a supply of alternative models for prime numbers lying around that make very different predictions for gaps.

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

In particular, for gaps so large that they imply a failure of RH, the first approach tried would surely be to look at the zeroes of zeta off the critical line and how they might be distributed, and use those to get an estimate for the density of primes in a certain region.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Turbo
    Jan 21, 2021 at 18:49
  • $\begingroup$ I didn't jmply a failure of rh and implied the scenario where the gap hypothesis supported by rh is indeed the truth. $\endgroup$
    – Turbo
    Jan 21, 2021 at 18:52
  • $\begingroup$ @1.. We can't just prove something is np hard out of nothing - the proof would rely on some new property or structure of prime gaps that relates them to previous known np hard problems, and that property or structure would be used to construct a random model. It's possible that the property or structure could be concealed by an indirect argument, as in the recent resolution of Tsirelson's problem, and then it might take quite some time to find a good random model. $\endgroup$
    – Will Sawin
    Jan 21, 2021 at 19:10
  • 2
    $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Jan 21, 2021 at 19:12
  • 2
    $\begingroup$ @1.. I mean you choose the primes so that this algorithm runs for longer than some fixed polynomial while searching for primes. This is a standard approach to constructing oracles in theoretical computer science. I'm not sure if it can be made to work here, but one could investigate. However, you should first precisely formulate that question - it seems like a different question than what would number theorists predict. $\endgroup$
    – Will Sawin
    Jan 21, 2021 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.