# Lower bound for Prime Counting Function

Is it true for large N that

$$\frac{1}{log(N)} \ge \prod_{\frac{N}{2}>p>2}{\frac{p-1}{p}} + \frac{\pi{(\frac{N}{2})}}{N}$$

?

It is not true, let me try to explain why.

The idea is as follows:

We can count $\pi(n)$ by first counting all primes less than or equal to $n/2$ and then adding the rest. However, the other primes are exactly the ones that are relatively prime to $p_1p_2\dots p_k$ (where these are the primes smaller not exceeding $\frac{n}{2}$)

So if $\lambda$ is the fraction of numbers relatively prime to $p_1p_2\dots p_n$ in the range $\{1,2,\dots,p_k\}$ then we obtain: $\pi(n)=\pi(n/2)+n\lambda$. Basically, your bound hinges on the fact that $\lambda > \frac{\varphi(p_1p_2\dots p_k)}{p_1p_2\dots p_k}$. Which is not always the case.

Note that the same idea also works with $\sqrt{n}$.

• Thank you very much! Then, are you saying that $\lambda > \frac{\varphi(p_1p_2\dots p_k)}{p_1p_2\dots p_k}$ is not always true? – user3141592 Dec 25 '16 at 20:10
• yeah, although I'm trying to figure out if it holds for large values of $n$. Maybe its one of those cases where all the counterexamples are small. – Jorge Fernández Hidalgo Dec 25 '16 at 20:12
• I really think so. The multiples of 3 would be $\frac{n}{2}\frac{1}{3} +E(n)$ where $-1/3 \le E(n) \le 1/3$. The same for number 5. $\frac{n}{2}\frac{1}{5} +E(n)$ where $-2/5 \le E(n) \le 2/5$. The we have that the number of not multiples of 3 or 5 is $\frac{n}{2} \frac{2}{3} \frac{4}{5} + E(n)$. But you have to take into account that for each prime, the maximun error term will always be lower than 0.5, and that when "sieving" the multiples of 5 you are also sieving some multiples of 3 that had already been sieved, so that this can clearly compensate E(n) for sufficiently large n. – user3141592 Dec 25 '16 at 20:18
• you should change it to $p\leq n/2$, I haven't found a counterexample for that yet. – Jorge Fernández Hidalgo Dec 25 '16 at 20:46
• Yes, so sorry. It's true – user3141592 Dec 25 '16 at 21:30

No, it is already false for $N=10$. We have $\pi(10)=4$, $\pi(5)=3$, so that $$4\ge 10\left(\frac{2}{3}\right)+3\sim 9.666$$ is wrong.

• And for large values of N? – user3141592 Dec 25 '16 at 22:11