7
$\begingroup$

How do we show that For $x,y \ge 0$ real numbers, there exists a constant C suchthat: $$\pi(x+y)-\pi(y) \le \frac{1}{3}x+C$$ Where $\pi(.)$ denotes thes prime counting function, is true?

the hint is to sieve n with $y< n \le x+y $:

$$\pi (x+y) \le 1+ \sum _{n \le x+y} 1+1-1 - \sum_{2|n}1 - \sum_{3|n}1 + \sum_{6|n}1 + \sum_{n\le x+y} 1 = $$ $$1+ \sum _{n \le x+y} 1+1-1 - \sum_{2|n}1 - \sum_{3|n}1 + \sum_{6|n}1 + [x+y]$$

because: $1\le n = dm \le x+y \Leftrightarrow \frac{1}{d}\le m \le \frac{x+y}{y} $

so: $$\sum_{n\le x+y , d|n}1 = [\frac{x+y}{d}]$$

then that gives: $$\pi (x+y) < 1+ [x+y] - [\frac{x+y}{2}] - [\frac{x+y}{3}] + [\frac{x+y}{6}]$$

so that will give: $\pi (x+y) < \frac{x+y}{3} + 3$ but also we get : $\pi(y) < \frac{y}{3} + 3$ so for any constant $C\ge 0$ it will surely hold that:

$$\pi(x+y) - \pi(y) < \frac{x}{3} \le \frac{x}{3} + C$$

Is this correct?

  • 1
    There is $ \leq 1/3 \pi(x)$ in the title, but $\leq 1/3 x$ in the post.2012-03-14
  • 0
    Thanks for the correction dtldarek.2012-03-14
  • 0
    Hint: Which numbers modulo $6$ can be prime?2012-03-14
  • 0
    Is there an assumption that $y > x$? Otherwise, the formula is not symmetric in $x,y.$2012-03-14
  • 0
    @J.D.: Intuitively you could read $x = \Delta y$ so that the equation becomes $\pi(y + \Delta y) - \pi(y) \leq \frac{1}{3} \Delta y + C$2012-03-14
  • 0
    @TMM That's exactly what I'm thinking about! $x$ is a delta offset after $y$.2012-03-14
  • 0
    @J.D. But it should not be. It means: in any range, on average, less than 1/3 of numbers is prime.2012-03-14
  • 1
    What if you forget about the $C$ for a moment and bring $\Delta y$ to the LHS. With $\Delta y \to 0$ you get: $$ \lim_{\Delta y\to 0} \frac{\pi(y+\Delta y)-\pi(y)}{\Delta y}=\pi(y)'\le 1/3. $$ Now use $\pi(y)\approx \frac{y}{\log y}$ and therefore $\pi(y)'\approx \frac{\log y-1}{(\log y)^2}=\frac{1}{\log y}-\frac{1}{(\log y)^2}$ which has a global maximum of $1/4$ at $y=e^2$. See [here](http://tinyurl.com/7545v3r).2012-03-15
  • 1
    Thank you. The prime number theorem wasnt proven yet, so the only thing that comes in question is the sieve of eratosthenes (as TMM suggests, sieving n numbers in the interval of $y but it looks like I did it wrong (I believe).2012-03-15

2 Answers 2