How can we show that $\pi (x+y) - \pi(y) \le \frac{1}{3} x + C$ using the sieve of eratosthenes?

Question

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?

Answer 1

Hint: Which numbers modulo $6$ can be prime? (Certainly not those divisible by $2$ or $3\ldots$)

So on an interval of width $x$ from $y$ to $y + x$, how many primes ($\pi(y+x) - \pi(y)$) do we expect at most on this interval?

Answer 2

You are asking us to show that your inequality holds for any $x, y \ge 0$ and for any constant $C$, which is obviously false. Perhaps this is what you mean:

Show that there exists a constant $C$ such that for any real numbers $x, y \ge 0$, $\pi(x+y)-\pi(y) \le \frac{1}{3}x+C$.

Answer 3

Let me elaborate on my earlier hint. The idea is that you look at numbers modulo $6 = 2 \cdot 3$ and see which of them can be prime. For example, if $n \geq 5$, then:

• If $n \equiv 0 \bmod 6$ then $n = 6k = 2 \cdot 3 \cdot k$ is never prime.
• If $n \equiv 2 \bmod 6$ then $n = 6k + 2 = 2 \cdot (3k + 1)$ is never prime.
• If $n \equiv 3 \bmod 6$ then $n = 6k + 3 = 3 \cdot (2k + 1)$ is never prime.
• If $n \equiv 4 \bmod 6$ then $n = 6k + 4 = 2 \cdot (3k + 2)$ is never prime.

So if $n \geq 5$, then the only possible cases for which $n$ can be prime are $n \equiv 1,5 \bmod 6$. Since those are two of the six congruence classes, only $2/6 = 1/3$ of all numbers on some interval $[y, y + x]$ belong to either of these classes and could potentially be prime. The constant $C$ is just there for those annoying cases like $y = 1$ and $x = 6$, but $C = 2$ should do.

Note that the fraction $2/6$ is actually $\phi(6)/6$ in disguise (where $\phi$ is Euler's totient function, counting the numbers less than $n$ that are coprime to $n$), and by looking at congruence classes modulo any fixed $n$ you can prove that for all $x,y$,

$$\pi(y + x) - \pi(y) \leq \frac{\phi(n)}{n} x + C,$$

where $C \leq n$ is constant when $n$ is fixed and $x,y$ are variable. Since

$$\inf_{n \in \mathbb{N}} \ \frac{\phi(n)}{n} = 0,$$

the primes become sparser and sparser as $x$ increases, and $\pi(y + x) - \pi(y) = o(x)$ grows slower than any linear function in $x$. In other words, if you replace the $\frac{1}{3}$ in the problem by any other positive fraction, the statement is still true.