# What is the minimal range $[f(n),g(n)]$ that contains a prime number for every integer $n>0$?

I know the following:

• Proven: There is a prime number between $n$ and $2n$ for every integer $n>0$.

• Conjectured: There is a prime number between $n^2$ and $(n+1)^2$ for every integer $n>0$.

My questions are:

1. Is the above correct?

2. Has this been conjectured or refuted:

There is a prime number between $n^2$ and $n(n+1)$ for every integer $n>0$ ?

3. What is the minimal range $[f(n),g(n)]$ proven to contain a prime number for every $n>0$?

UPDATE:

The term 'minimal' is somewhat confusing in this case, since obviously, the difference between $n$ and $2n$ is in fact smaller than the difference between $n^2$ and $(n+1)^2$.

So to refine my question - 'minimal range' refers to the ratio between $f(n)$ and $g(n)$, and not to the difference between them. In other words $Min[g(n)/f(n)]$ instead of $Min[g(n)-f(n)]$.

-
I think it is more clear if you fix $f$ to be the identity, $f(n)=n$ (besides, taking $f(n)=g(n)=p_n$ would somehow trivialize the question) –  Pietro Majer Feb 27 '14 at 8:53
It will not describe my question properly if I do so. Please note that I'm asking if there is a prime number between $n^2$ and $(n+1)^2$. How can $f(n)$ be $n$ in this case? –  barak manos Feb 27 '14 at 8:55
Then maybe your problem is : the function $f$ being ${\it given}$, ${\it find}$ the smallest function $g\ge f$ such that there is a prime in the interval? I was just saying that if we can choose both $f$ and $g$ there is the trivial answer above. –  Pietro Majer Feb 27 '14 at 9:00
@Pietro Majer: Oh, I understand now, you mean $f(n)=P_{n}$ and $g(n)=P_{n+1}$? –  barak manos Feb 27 '14 at 9:04
It is easy to define $P_n$ with a few symbols: $P_n$ is the $n$-th prime number. –  GH from MO Feb 27 '14 at 10:46

Baker-Harman-Pintz (2000) proved that for every sufficiently large $n$ the interval $[n-n^{0.525},n]$ contains a prime number. Schoenfeld (1976) proved that if the Riemann Hypothesis is true, then the term $n^{0.525}$ in the previous statement can be replaced by $\sqrt{n}\log^2 n$. For a very recent strengthening of this result, see this preprint. This is still probably far from the truth, e.g. Cramér (1937) made the conjecture based on a probabilistic model, that the term $n^{0.525}$ above can be replaced by a certain constant times $\log^2 n$.

-
Strangely I only got notified of your answer when it was already almost 15 mins old; so mine was almost done and I thus posted it and leave it, also as the symmetric difference is nonempty. And, thanks for bringing that preprint to my attention. –  quid Feb 27 '14 at 8:47
@quid: Thanks for the feedback and your response as well! –  GH from MO Feb 27 '14 at 8:50
@barakmanos yes in my opinion this conjecture is almost purely relevant for historical reasons (Legendre was a pioneer in that field an the conjecture dates from around 1800 where these questions were much less understood), see my comments on mathoverflow.net/questions/114399/… –  quid Feb 27 '14 at 8:55
@barak: Legendre's conjecture implies a slightly weaker variant of $L(1/2)$: there is a prime in $[n-5\sqrt{n},n]$. On the other hand, $L(1/2)$ implies Legendre's conjecture. It is subjective what is interesting and for what reasons. quid tried to say, and I agree with him, that the specific intervals $[n^2,(n+1)^2]$ are not too interesting in this problem. We don't really distinguish between the following intervals: $[n-\sqrt{n},n]$, $[n-100\sqrt{n},n]$, $[n-\sqrt{n}\log^{29} n,n]$, $[n-n^{1/2+o(1)},n]$. They are much the same, and they are on the edge what the Riemann Hypothesis can handle. –  GH from MO Feb 27 '14 at 14:54
Probably the probabilistic model does not give the correct answer when dealing with primes in short intervals. Maier's matrix method shows that on a scale up to a power of $\log x$ the distribution of primes is much more irregular than what probability would predict. –  Jan-Christoph Schlage-Puchta Mar 3 '14 at 7:46

Yes what you say is correct.

For the minimal range known, it is know by results of Baker, Harman, Pintz that $[x, x + x^{0.525}]$ contains a prime for all sufficiently large $x$, as a consequence of this, but in fact already of earlier results, it is known that there is a prime between $n^3$ and $(n+1)^3$ for all sufficiently large $n$. If one could replace $0.525$ by $0.5$ this would essentially yield the conjecture you mentioned, known as Legendre's conjecture.

This also immediately yields, but really for this the Prime Number Theorem suffices, that the ratio of your $g(n)/f(n)$ can be taken to tend to $1$ as $n \to \infty$. And, the difference, in a suitable sense, is rather the better notion to consider here.

It is conjetured that $[x, x + f(x)]$ contains a prime for each $x$ where $f$ is some $O( (\log x)^2)$; the key-word here is Cramér's conjecture, which is still slightly more precise but it is not quite clear what exactly should be conjectured. But the $O( (\log x)^2)$ is likely about alright.

In the converse direction it is known (due to Rankin) that there are infinitely many $n$ such that the gap between $n$ and $n+1$ prime is of size

$$c \frac{(\log n) (\log \log n)(\log \log \log \log n)}{ (\log \log \log n)^2}$$ for a positive $c$.

-