# At what point would an elementary generalization of Bertrand's Postulate be interesting?

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?

-
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: projecteuclid.org/… . 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

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

-
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. –  quid 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. –  quid Apr 11 '13 at 17:23

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

-
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