## Wednesday, August 26, 2015

### Lower and upper bound for Chebyshev's psi function

In this post, I prove the inequalities $$\label{eq:1} \log 2 \cdot x - 3 \log x \le \psi(x) \le 2 \log 2 \cdot x + \frac{3}{\log 2} \log^2 x$$ for all real $x \ge 2$. Hereby is $\psi(x) = \sum_{n \le x } \Lambda(n)$ with $\Lambda$ the von Mangoldt function. This is a second post motivated by Chebyshev's paper "Mémoire sur les nombres premiers" from 1852. In this paper, Chebyshev uses a more complex variant of the calculation below to obtain stronger inequalities. Similar inequalities can also be found on page 50 in Murty's book.
I showed in a previous post that if $T(x) = \sum_{ 1 \le n \le x} \log n\$ then $$\label{eq:2} \psi(x) - \psi\left(\frac{x}{2} \right)\le T(x) - 2\ T\left( \frac{x}{2} \right) \le \psi(x)$$ For all real $x \ge 1$, one has $$\label{eq:3} x \log x - x - \log x +1 \le T(x) \le x \log x - x + \log x +1$$ These inequalities are easily proved by comparing the sum in the expression $T(x) = \sum_{ 1 \le n \le x} \log n$ with the corresponding integral. From \eqref{eq:3} one immediately deduces that for all real $x \ge 2$ $$\label{eq:4} \log 2 \cdot x - 3 \log x + 2 \log 2 -1 \le T(x) - 2\ T\left( \frac{x}{2} \right)$$ and $$\label{eq:5} T(x) - 2\ T\left( \frac{x}{2} \right) \le \log 2 \cdot x + 3 \log x - 2 \log 2 -1$$ Combining \eqref{eq:2} and \eqref{eq:4} and using $2 \log 2 -1 > 0\$ gives $$\label{eq:6} \log 2 \cdot x - 3 \log x \le \psi(x)$$ The lower bound of \eqref{eq:1} is thus proved. Combining \eqref{eq:2} and \eqref{eq:5} and using $- 2 \log 2 -1 < 0$, one has for all real $x \ge 2$ that $$\label{eq:7} \psi(x) - \psi\left(\frac{x}{2} \right)\le \log 2 \cdot x + 3 \log x$$ To prove the upper bound, take $m \in \mathbb{N}$ such that $2 \le \frac{x}{2^m} < 4$. Applying \eqref{eq:7} several times gives \begin{align*} \psi(x) - \psi\left(\frac{x}{2} \right) &\le \log 2 \cdot x + 3 \log x\\ \psi\left(\frac{x}{2} \right)- \psi\left(\frac{x}{4} \right) &\le \log 2 \cdot \frac{x}{2} + 3 \log \frac{x}{2}\\ \psi\left(\frac{x}{4} \right)- \psi\left(\frac{x}{8} \right) &\le \log 2 \cdot \frac{x}{4} + 3 \log \frac{x}{4}\\ \cdots\\ \psi\left(\frac{x}{2^m} \right)- \psi\left(\frac{x}{2^{m+1}} \right) &\le \log 2 \cdot \frac{x}{2^m} + 3 \log \frac{x}{2^m} \end{align*} Because $1 \le \frac{x}{2^{m+1}} < 2$, it follows that $\psi\left(\frac{x}{2^{m+1}} \right) = 0$. Adding the inequalities thus gives \begin{equation*} \psi(x) \le 2 \log 2 \cdot x + 3 (m+1) \log x \end{equation*} The inequality $2^{m+1} \le x$ gives $m + 1 \le \frac{\log x }{\log2 }$. The upper bound of \eqref{eq:1} is thus also proved.

Here is a graph that illustrates the inequality \eqref{eq:1}.
 The red line is the upper bound, the black line is $\psi(x)$, the green line is the lower bound.