Background: We define $$\theta(x) := \sum_{p\le x} \log p$$
where the sum is taken over primes $\le x$.
Chebycheff’s Theorem: There exist positive constants $A$ and $B$ such that $$Ax < \theta(x) < Bx$$
The book by Cojocaru and Murty presents a proof due to Ramanujan, which is paraphrased below with inline questions.
Observe that if $\{a_n\}$ is a decreasing sequence of real numbers with $a_n \to 0$, then $$a_0 – a_1 \le \sum_{n=0}^\infty (-1)^n a_n \le a_0 – a_1 + a_2$$
(The book uses absolute convergence of the series to prove this assertion, but later uses this assertion for a series with only finitely many terms, so we should not bother ourselves with this aspect.)
Following Chebycheff, we define
$$\psi(x) := \sum_{p^a \le x} \log p$$
where the summation is over all prime powers $p^a \le x$. We let $$T(x) := \sum_{n\le x} \psi\left(\frac x n\right)$$
and notice that $$\sum_{n\le x} \log n = {{\sum_{n\le x} \left(\sum_{p^a \mid n} \log p\right) = \sum_{m\le x} \psi\left(\frac x m \right)}} = T(x)$$
- Where does the second equality above come from?
By an earlier observation (that $\sum_{n\le x} \log n = x\log x – x + O(\log x))$ we have
$$T(x) = x\log x – x + O(\log x)$$
so that
$$T(x) – 2T\left(\frac x 2\right) = x \log 2 + O(\log x)$$
On the other hand,
$$T(x) – 2T\left(\frac x 2\right) = \sum_{n\le x} (-1)^{n-1} \psi\left(\frac x n \right)$$
and we can apply our initial observation to deduce
$$\psi(x) – \psi\left(\frac x 2\right) + \psi\left(\frac x 3\right) \ge x\log 2 + O(\log x) \tag{1}$$
and
$$\psi(x) – \psi\left(\frac x 2\right) \le x\log 2 + O(\log x) \tag{2}$$
because $a_n = \psi(x/n)$ is a decreasing sequence of real numbers tending to
zero (in fact, equal to zero for $n > x$). By successively replacing $x$ with $x/2^k$ in the above inequality $(2)$, we obtain
$$\psi(x) \le 2x\log 2 + O(\log^2 x) \tag{3}$$
This completes Ramanujan’s proof of Chebycheff's theorem.
-
I've worked out the last step, and I want to confirm the correctness of my work. From equation $(3)$, we have $\psi(x) \le 2x\log 2 + c_1 \log ^2 x$ for some $c_1 > 0$. We can find $\beta > 0$ such that $\psi(x) < \beta x$ for sufficiently large $x$, say for $x > k$ for some $k \in \mathbb N$. For $1\le x\le k$, $\psi(x) \le 2k\log 2 + c_1 \log^2 k$, i.e., $\psi(x)$ is bounded. We can choose $B = \max\{\beta, 2k\log 2 + c_1 \log^2 k + 1\}$ to get $\psi(x) < Bx$ for all $x$. Lastly, we get the required upper bound using $\theta(x) \le \psi(x)$.
-
The proof in the book doesn't seem to address the lower bound at all. I suspect we must use equation $(1)$, i.e., $\psi(x) – \psi\left(\frac x 2\right) + \psi\left(\frac x 3\right) \ge x\log 2 + O(\log x)$ to derive it. An added problem in the case of the lower bound is that $\theta(x) \le \psi(x)$, and not the other way round. To find $A > 0$ such that $\theta(x) > Ax$ for all $x$, we may have to find another way to compare $\theta(x)$ and $\psi(x)$ too, i.e., consider the growth of $|\theta(x) – \psi(x)|$ with $x$. Could someone help me fill in the details for the lower bound?
Thank you!
Reference: An Introduction to Sieve Methods and Their Applications by
Alina Carmen Cojocaru and M. Ram Murty.
Best Answer
This may explain the answer to the first question: $$\sum_{n\leq x}\sum_{p^\alpha|n}=\sum_{n\leq x}\sum_{p^\alpha\cdot m=n}=\sum_{p^\alpha m\leq x}=\sum_{m\leq x}\sum_{p^\alpha\leq\frac{x}{m}}.$$ And for the third question, let's firstly observe: $$T(x)-2T\left(\frac{x}{2}\right)\leq\psi(x),$$ and then recall the estimate value of the left-hand side to get that $\psi(x)$ is bounded from below by $cx$ for some $c$. Finally, you want to discuss the growth of $\theta(x)-\psi(x)$ indeed. For that use $$\psi(x)=\sum_{n=1}^\infty\theta\left(x^\frac{1}{n}\right)=\theta(x)+\sum_{n=2}^{\log_2x}\theta\left(x^\frac{1}{n}\right)\leq$$ $$\leq\theta(x)+\sum_{n=2}^{\log_2x}\theta\left(\sqrt{x}\right)=\theta(x)+\mathcal{O}(\ln x\cdot\theta(\sqrt{x}))=$$ $$=\theta(x)+\mathcal{O}(\sqrt{x}\cdot\ln x),$$ where we used that $\theta(x)=0$ for $x<2$ and that $\theta(x)=\mathcal{O}(x)$ which we already know. Recall once again that $\theta(x)=\mathcal{O}(x)$ to get: $$\psi(x)=\theta(x)+\mathcal{O}(\sqrt{x}\cdot\ln x)=$$ $$=\mathcal{O}(x)+\mathcal{O}(\sqrt{x}\cdot\ln x)=\mathcal{O}(x).$$ To show that $\theta(x)$ is bounded from below by a linear function we use the difference with $\psi(x)$ which we got earlier to find: $$\theta(x)=\psi(x)-\mathcal{O}(\sqrt{x}\cdot\ln x)=\Omega(x)+\mathcal{O}(\sqrt{x}\cdot\ln x)=\Omega(x).$$ For detailed description of used notations, see this. It should be clear how each step was deduced.