# Proving equivalences between prime counting functions.

If we have that: $$\theta(x)=\sum_{p\leq x}\log p,$$ and $$\psi(x)=\sum_{n\leq x}\Lambda(n)$$ Where $\Lambda(n)=\log p$ if $n=p^m$ and $\Lambda(n)=0$ in another case.

How can I prove that :

1) $\theta(x)=\psi(x)+O(\sqrt{x})$

2) $\pi(x)=\frac{\psi(x)}{\log x}+O(\frac{x}{\log^2x})$

Being $\pi(x)=\sum_{p\leq x}1$ the function that counts the number of primes less than $x$

-
The traditional notation used for these functions is a lower case $\theta$, and $\psi$ for Chebyshev's functions, with a lower case $\pi$ for the prime counting function, the capital $\Pi$ is typically used when referring to Reimann's prime counting function. – Ethan Jun 4 '13 at 6:58

$$\binom{2n}{n}=\frac{(2n)!}{n!^2}, \text{ is always an integer}$$ $$\text{no integer between } 1 \text{ and } n \text{ is divisible by a prime between n} \text{ and } 2n$$

$$\implies\frac{(2n)!}{n!^2}=\binom{2n}{n} \text{ is divisible by all the primes between n and 2n}$$

$$\implies\binom{2n}{n}\ge\prod_{n<p\leq 2n}p$$ $$\prod_{n<p\leq 2n}p\leq\binom{2n}{n}\leq 4^n$$ Sense $$4^n=(1+1)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}\ge\binom{2n}{n}$$ So that, $$\prod_{n<p\leq 2n}p\leq 4^n$$ $$\implies \prod_{\frac{n}{2}<p\leq n}p\leq 2^n$$ Taking logarithms gives

$$\theta(n)-\theta(\frac{n}{2})\leq \ln(2)n$$ $$\implies \theta(n)=(\theta(n)-\theta(\frac{n}{2}))+( \theta(\frac{n}{2})-\theta(\frac{n}{4}) )...\leq (1+\frac{1}{2}+\frac{1}{4}...)\ln(2)n$$ $$\implies \theta(n)\leq 2\ln(2)n=n\ln(4)$$ So that we have, $$\theta(x)\leq x\ln(4)$$ Which means $$\theta(x)=O(x)$$ Also note that $$\psi(x)=\sum_{p\leq x}\ln(p)+\sum_{p^2\leq x}\ln(p)+\sum_{p^3\leq x}\ln(p)...$$

$$=\theta(x)+\theta(x^\frac{1}{2})+\theta(x^\frac{1}{3})+...$$ $$=\theta(x)+O(\theta(x^{1/2}))=\theta(x)+O(x^{1/2})$$

So that we get $$\psi(x)=\theta(x)+O(\sqrt{x})$$

And sense $$\pi(x)+O(\sqrt{x})=\sum_{1<n\leq x}\frac{\Lambda(n)}{\ln(n)}=\frac{\psi(x)}{\ln(x)}+\int_{2}^x\frac{\psi(t)}{t\ln(t)^2} dt=\frac{\psi(x)}{\ln(x)}+O(\frac{x}{\ln(x)^2})$$

We have,

$$\pi(x)=\frac{\psi(x)}{\ln(x)}+O(\frac{x}{\ln(x)^2})$$

-
Why do you have $\pi(x)+O(\sqrt{x})=\sum_{1<n\leq x}\frac{\Lambda(n)}{\log n}$? – Elmo goya Jun 4 '13 at 19:01
@Elmogoya Because $$\sum_{1<n\leq x}\frac{\Lambda(n)}{\ln(n)}=\pi(x)+\frac{\pi(x^{1/2})}{2}+\frac{\pi(x^{1/3})}{3}‌​...=\pi(x)+O(\sqrt{x})$$ – Ethan Jun 4 '13 at 21:18
And... Why do you have that $$\int_{2}^{x}\frac{\psi(t)}{t\log(t)^2}dt=O\left(\frac{x}{\log(x)^2}\right)$$ – Elmo goya Jun 4 '13 at 21:41
@Elmogoya Because $$\frac{\psi(t)}{t}=O(1)$$ and $$\int_{2}^x\frac{1}{\ln(t)^2} dt =O(\frac{x}{\ln(x)^2})$$ – Ethan Jun 4 '13 at 21:50