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


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

  • $\begingroup$ 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) $\endgroup$ – Pietro Majer Feb 27 '14 at 8:53
  • $\begingroup$ 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? $\endgroup$ – barak manos Feb 27 '14 at 8:55
  • $\begingroup$ 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. $\endgroup$ – Pietro Majer Feb 27 '14 at 9:00
  • $\begingroup$ @Pietro Majer: Oh, I understand now, you mean $f(n)=P_{n}$ and $g(n)=P_{n+1}$? $\endgroup$ – barak manos Feb 27 '14 at 9:04
  • 1
    $\begingroup$ It is easy to define $P_n$ with a few symbols: $P_n$ is the $n$-th prime number. $\endgroup$ – 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$.

| cite | improve this answer | |
  • 1
    $\begingroup$ 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. $\endgroup$ – user9072 Feb 27 '14 at 8:47
  • 1
    $\begingroup$ @quid: Thanks for the feedback and your response as well! $\endgroup$ – GH from MO Feb 27 '14 at 8:50
  • 1
    $\begingroup$ @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/… $\endgroup$ – user9072 Feb 27 '14 at 8:55
  • 1
    $\begingroup$ @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. $\endgroup$ – GH from MO Feb 27 '14 at 14:54
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.

| cite | improve this answer | |

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.