Is there any guarantee of maximum distance to next prime?

When watching the Numberphile video about Highly Composite Number, I spotted something that aroused some of my doubts. One of properties suggested by Ramanujan was that the highly composite number's powers of prime factors are in order of decreasing order, with the highest prime factor almost always (with exactly 2 exceptions: 4 and 36.) appearing with power of 1.

It seems to me this assertion hinges upon the next prime after the last being lower than the square of the previous one. While π(N) shows the average distance between the consecutive primes would be significantly lower than between the prime and it's square, as I understand it's more of a probabilistic thing, and while very unlikely, it's not guaranteed next prime will be found within pretty much any finite distance of the prior one. So is this property of highly composite numbers just a conjecture based on dwindling probability of such a gap between primes ever appearing, or is there some solid proof to it?

• en.m.wikipedia.org/wiki/Bertrand%27s_postulate Aug 30, 2020 at 0:03
• On the opposite end of the spectrum, there are very small prime gaps. According to en.wikipedia.org/wiki/Prime_gap#Upper_bounds there are infinitely many prime gaps with a gap less than 247. Aug 30, 2020 at 0:32
• @Houston: It is suspected there's an infinite number of twin primes, so with a gap of 2.
– SF.
Aug 30, 2020 at 0:51

2 Answers

We can do even better than finding a prime smaller than the square of the previous: Bertrand's postulate, or the Bertrand-Chebyshev theorem, tells us that there is always a prime between $$n$$ and $$2n$$.

As a side note, the distribution of the primes is not at all "a probabilistic thing". Every statement about prime numbers, in specific ranges, or based on variables, etc. is either true or false, though it may be very difficult or impossible to prove or disprove some such statements. The prime number theorem and many similar results tell us some things which are always true as patterns in the limit when we take averages of large ranges. Since this is similar to some patterns in random variables which are almost always true when we take averages of many samples, some of the same techniques for dealing with random variables can be applied in much the same ways to properties of the prime numbers. But these arguments can only tell us about average properties for large numbers, and don't always help attempting to show something always or never happens, or applies in any way to small numbers.

• You can do even better. It follows from the prime number theorem that for every $\epsilon$ there is a prime between $n$ and $(1 + \epsilon)n$ for all sufficiently large $n$. Aug 30, 2020 at 14:46
• Could you elaborate on or make more formal your sentence "Every statement about prime numbers, in specific ranges, or based on variables, etc. is either true or false, though it may be very difficult or impossible to prove or disprove some such statements."? I guess I know what you want to express, but provability/independence is already a non-trivial topic on its own that it's best to express terms thereof clearly. Aug 30, 2020 at 15:02
• @EthanBolker I don't think that helps with the question here, of the distance from a particular $n$ to the next prime. Aug 31, 2020 at 23:27
• @aschepler Maybe not. But it may be worth pointing out that for large $n$ you can do a lot better than Bertrand. Aug 31, 2020 at 23:31
• @ComFreek Maybe that was a bit bold. The "or impossible" is a reference to Gödel's theorems and related results, yes. But "is either true or false" gets into a murky mix of theory modeling and philosophy. It assumes the Peano axioms describe something specific, just incompletely. But maybe that's from a misleading intuition, that I think I understand natural numbers and their common operations as obvious enough that there's exactly one thing (model) they really are about. Aug 31, 2020 at 23:36

If I understand your question, you are asking if there is a bound on the gaps between primes or if at some point in the primes there could be a huge gap that is way out of the ordinary.

Well, there is a bound from this wikipedia page that gives the following bounds on the nth prime number (for n > 6):

$$\ln(n) + \ln(\ln(n)) - 1 < \frac{p_n}{n} < \ln(n) + \ln(\ln(n))$$

Now let's assume we have $$p_n$$ and $$p_{n+1}$$ where $$p_n$$ is the smallest possible and $$p_{n+1}$$ is the largest possible. Then the difference would be:

$$g_n < (n+1)(\ln(\ln(n+1)) + \ln(n+1)) - n(\ln(\ln(n)) + \ln(n) - 1)$$

$$g_n$$ is the gap between the nth and the n+1 th prime. If you are willing to be a little less exact you can assume that $$\ln(n+1)=\ln(n)$$ because as $$n \to \infty$$, $$\ln(n+1)\to\ln(n)$$, you get this result:

$$g_n ≲ \ln(\ln(n)) + \ln(n) + n$$

So it seems that it would be impossible for $$p_n > p_{n-1}^2$$. There is also something I heard on numberphile which is that there is always a prime between $$x$$ and $$2x$$ for any $$x$$.