# prime number theorem and prime counting function

$\pi(x)$ is the prime counting function (no. of prime within x)

For the interval $(x, x + \delta x]$, $\delta > 0$, what is the smallest integer $x_{0}$ such that for any $x >= x_{0}$, $\pi(x + \delta x) - \pi(x) > 0$ is always true?

For example, Bertrand's Postulate tells us that when $\delta = 1$, the smallest integer to make the above statement true is $x_{0} = 2$.

The following result might help: one paper by Rosser and Schoenfeld gives out two inequalities about $\pi(x)$:

$\frac{x}{\log{x}}(1 + \frac{1}{2\log{x}}) < \pi(x)$, for $x>= 59$,

and $\pi(x) < \frac{x}{\log{x}}(1+ \frac{3}{2\log{x}})$, for $x>1$

-
If you haven't already, you might want to look at en.wikipedia.org/wiki/Prime_gap, especially the section "Further results". –  joriki Sep 30 '12 at 19:47
What is the requirement on $\delta$? –  Ankur Sep 30 '12 at 20:14
@Ankur, there is no requirement for $\delta$. I'm curious if we can find the smallest integer for any $\delta$. –  Lindsay Duran Sep 30 '12 at 23:13

From Proposition 6.8 on pdf page 8 of DUSART, you may take $$x_0 = \max \left( 396738, \; e^{\left( \frac{1}{5 \sqrt \delta} \right)} \right).$$ This is not the optimal value of your $x_0 = x_0(\delta)$ but it works.

Note: Dusart's adviser was Guy Robin, whose adviser was Jean-Louis Nicolas. It all fits.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

-
This is great. Maybe it would be worth including the x < p < x(...) statement from the paper in your answer? –  daniel Oct 1 '12 at 2:06
@daniel, I have a scanner at home, I made a jpeg of the appropriate page. My experience is that pdf's are not good enough for this website, not enough pixels or suchlike. –  Will Jagy Oct 1 '12 at 2:48
Looks good to me. I found it very interesting. Hopefully others (including the OP) will too. –  daniel Oct 1 '12 at 2:57
@WillJagy, Thank you! This is indeed very helpful! –  Lindsay Duran Oct 1 '12 at 21:51

I don't think that the answer above is correct. In fact, such an $x_{0}$ does exist. It is a consequence of the Prime Number Theorem. One may refer to the Wikipedia article on Bertrand's Postulate: http://en.wikipedia.org/wiki/Bertrand%27s_Postulate. As for the original question, I'm not sure if bounds have been established for the size of $x_{0}$, except in certain cases. Examples are also given in the Wikipedia article mentioned above. One of the references listed there, an article by Lowell Schoenfeld, gives the following result: For any $n \geq 2010760$, there exists a prime between $n$ and $\left( 1 + \frac{1}{16597} \right) n$. I believe that $2010760$ is the smallest $n_{0} \in \mathbb{N}$ corresponding to $\delta = \frac{1}{16597}$. However, I haven't read the article yet, so please go ahead and read it to help me verify what I've written here.

-
I had misread the question; I read $\delta x$ as an additive constant. You're right that it's probably meant to be $\delta$ times $x$. I've deleted my answer. Note that "the answer above" isn't meaningful on this site, since answers are ordered according to criteria that can a) be selected differently by different voters (active/oldest/votes) and b) change over time. –  joriki Sep 30 '12 at 19:41
@daniel, is it possible to find $x_{0}$ for any $\delta$? –  Lindsay Duran Sep 30 '12 at 23:17
@LindsayDuran: Sorry, the result in the answer about Schoenfeld is not conditional. There are conditional results in the paper but I think this result is from studying the zeros of the zeta function very carefully. It's really a three-paper series. –  daniel Oct 1 '12 at 1:14