MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know that in 1952 Jitsuro Nagura was able to show that there is always a prime between $k$ and $\frac{6k}{5}$ for $k > 24$.

At what point would an improvement on Nagura's result be interesting? If an approach could show for example that for any $k$, there is a specific value $X$ which could be calculated such that for all $x \ge X$, there is a prime between $kx$ and $(k+1)x$, would this be interesting?

Or, does the Prime Number Theorem provide us enough insight that short of a proof of Legendre's Conjecture, elementary results are not very interesting at this time?

share|cite|improve this question
From the Erdos-Selberg argument, it is not too difficult to see (basically by iterating the Selberg symmetry formula) that if one can get $\gg_k x/\log x$ primes between $kx$ and $(k+1)x$ for all $k$ and all sufficiently large $x$, then the prime number theorem follows from elementary means (of course, this is a somewhat vacuous statement since the entire Erdos-Selberg proof of PNT is already considered elementary, but the derivation here is simpler than that of full Erdos-Selberg). – Terry Tao Apr 11 '13 at 22:22
From the explicit formula linking primes and zeroes, the above assertion for a given $k$ is morally equivalent to the absence of a zero on the line $\{ Re(s)=1 \}$ of imaginary part $O(k)$. I vaguely recall reading some discussion in which this equivalence could be made more precise, in that such a zero-free region could be converted to an elementary Ramanujan-style result (somewhat analogously to how the non-vanishing of $L(1,\chi)$ for all $\chi$ of period $q$ can be converted to an elementary proof of Dirichlet's theorem mod $q$) but I don't remember the details. – Terry Tao Apr 11 '13 at 22:25
Ah, I found the reference now, in this survey of Diamond:… . In section 9 he discusses how, for each k, there is an elementary proof of Chebyshev type of a prime between $kx$ and $(k+1)x$ for large enough x. Unfortunately, the proof that the elementary proof exists (!) itself depends on the PNT! – Terry Tao Apr 11 '13 at 22:56
Thanks very much for the reference! I look forward to checking it out. – Larry Freeman Apr 12 '13 at 10:38
I found in my lecture notes a reference to a paper by N.Costa Pereira that proves $|\psi(x)/x - 1| < 1/2976$ for $x > 10^{11}$: "Elementary estimates for the Chebyshev function psi(x) and the Möbius function M(x)", Acta Arithmetica 52 (1989), 307-337. – Noam D. Elkies Aug 30 '13 at 23:23
up vote 18 down vote accepted

Current results are able to yield such results. Depending on how generous one is regarding what $X$ is. If it is just the optimal value can be calculated exactly this will work for many more $k$ and if one is happy with an explicit bound for all $k$.

For example Dusart showed that $$ \frac{x}{\log x - 1} \le \pi(x) \le \frac{x}{\log x - 1.1} $$ for $x\ge 60184$. Now for some $k$, write $y=kx$. Then, if the upper bound for $kx=y$ is smaller than the lower bound for $(k+1)x = (1+1/k)y$, that is $$ \frac{y}{\log y - 1.1} \lt \frac{y(1+ 1/k)}{\log( y (1+1/k) )- 1} $$ one has a prime between $kx$ and $(k+1)x$, since then $\pi(kx) \lt \pi((k+1)x)$.

One can check that this inequality holds for (up to potential error in my calculation) $$ y \ge 10 e^{0.1 k}. $$

So, for $x \ge \max \lbrace 10 e^{0.1 k}/k , 60184/k \rbrace $ one always has a prime between $kx$ and $(k+1)x$.

While this grows exponential in $k$, the growth is such that it is well feasible to check 'everything' up to the bound to get an optimal $X$ for not too large $k$. And, one always has an explict value.

This proof is of course not elementary (the non-elementariness being hidden in Dusart's result) and is an application of the PNT in some sense. But what this is meant to show is that for a result around this to be interesting it seems necessary either to be better (and one could still optimize this here) than this or the proof would have to be interesting (or both). [What an interesting proof is is of course a bit subjective.]

share|cite|improve this answer
Just to be clear regarding the 'up to error': this will work with some explict value, it just could be a different one if I made an error. – user9072 Apr 11 '13 at 16:05
@quid: I edited the first inequality, since the left-hand side was larger than the right-hand side. -- Please check! – Stefan Kohl Apr 11 '13 at 17:05
@Stefan Kohl: Thank you! Yes this was written in the wrong order. Also, the second is wrong (as I first copied and then modified). I will chanhe the later one now. – user9072 Apr 11 '13 at 17:23
As a check on your equations I set k=100 x=2478 and should therefore expect one prime between 2478 and 2478 + 2478/100 = 2502.78. (for k=100, x must be greater than 2202.65 as detailed by your equations - this condition is met for x=2478). But there are no primes between 2478 and 2502.78. (Though 2503 is prime) Is the domain of x for your answer the positive integers? Then everything checks out. Or as you warned 'up to error'? Appreciate your answer and went through this numerical check to see when a 1% addition to any x>2203 guarantees a prime in what seems to me to be a very short interval. – marh_g Mar 26 at 19:06
Thank you for the interest in my answer. Note the prime is between $kx$ and $(k+1)x$. So in this case $247800$ and $247800 + 2478$, and $247800+ 11$ is prime. – user9072 Mar 26 at 19:35

I think that it would be interesting if it has an effective (and not too huge) value of $X$.

share|cite|improve this answer
Thanks very much. That helps. I am reviewing Ramanujan's proof of Bertrand's Postulate and I'm wondering if his approach can be applied to an arbitrary value of $k$. I'm still getting up to speed so my thoughts are very preliminary. – Larry Freeman Apr 11 '13 at 15:33

Once again, being new here I tried to comment your answer, but obviously don't have 50 points yet.

Here is the original text of my comment with my mistake on value of x

"As a check on your equations I set k=100 x=2478 and should therefore expect one prime between 2478 and 2478 + 2478/100 = 2502.78.(for k=100, x must be greater than 2202.65 as detailed by your equations - this condition is met for x=2478).But there are no primes between 2478 and 2502.78. (Though 2503 is prime) Is the domain of x for your answer the positive integers? Then everything checks out okay. Or as you warned 'up to error'?"

Assigning x=24.78 is the correct value.

@quid: Note the prime is between kx and (k+1)x, so with my corrected value of x there should be a prime between 2478 < (some prime) < 2502.78, but the next prime is 2503.

@stefan kohl: understood and my calculation and answer/comment also gave x > 2202.65. My mistake was not putting the correct value for x

share|cite|improve this answer
This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review – Stefan Kohl Apr 8 at 13:43
Dear fellow MO users: the author of this post doesn't have the rep to make comments in response to comments under someone else's post, but would like to do so. I propose that we keep this "answer" for a while and then convert the kit and caboodle over to comments once a bit of rep has accrued. I expect this user can make further useful comments and contributions, but his/her hands are tied at the moment. – Todd Trimble Apr 8 at 17:01
@ToddTrimble At least marh_g followed the advice given in this meta answer. And imho, this "answer" is interesting enough not to be deleted immediately. – Sebastian Goette Apr 8 at 17:41
@Todd, can't you, as a mod, convert an answer to comments, regardless of how many points the person has? – Gerry Myerson Apr 9 at 3:21
@GerryMyerson Ordinarily I do just that, and in fact I did that before with a very similar post (which OP appreciated); see below the accepted answer. But then when people began making comments on his comment and OP was unable to respond, he/she flagged to explain so. In view of this and Sebastian's comment, I'm going to keep this answer, at least temporarily. – Todd Trimble Apr 9 at 11:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.