## Tuesday, September 29, 2015

### A quite short proof of Bertrand's postulate

In the Wikipedia article about Bertrand's postulate, three proofs are mentioned: Chebyshev's proof, Ramanujan's proof and Erdős's proof. In this post, I give a simplified version of Chebyshev's proof.
In his Mémoire Chebyshev analyzes the expression \begin{equation*} T(x) - T\left( \frac{x}{2} \right)- T\left( \frac{x}{3} \right)- T\left( \frac{x}{5} \right)+ T\left( \frac{x}{30} \right) \end{equation*} where $T(x) = \sum_{ 1 \le n \le x} \log n\$. If one only wants to prove Bertrand's postulate, it is sufficient to analyze instead the simpler expression $$\label{20150927.1} V(x) = T(x) - T\left( \frac{x}{2} \right)-2 T\left( \frac{x}{3} \right)+ T\left( \frac{x}{6} \right)$$ If $\psi(x) = \sum_{n \le x } \Lambda(n)$ with $\Lambda$ the von Mangoldt function, then \begin{equation*} T(x) = \sum_{n=1}^{\infty} \psi\left(\frac{x}{n} \right) \end{equation*} and thus \begin{equation*} V(x) = \psi(x) -\psi\left( \frac{x}{3} \right)+ \psi\left( \frac{x}{5} \right)- \psi\left( \frac{x}{6} \right) + \cdots \end{equation*} The coefficients of $\psi\left( \frac{x}{n} \right)$ in this expression have period 6 and are alternating. This leads immediately to the inequalities $$\label{20150927.3} V(x) \le \psi(x)$$ and $$\label{20150927.4} \psi(x) -\psi\left( \frac{x}{3} \right) \le V(x)$$ To bound $V(x)$ I use that for all real $x \ge 1$ $$\label{20150927.5} x \log x - x - \log x +1 \le T(x) \le x \log x - x + \log x +1$$ From \eqref{20150927.1} and \eqref{20150927.5} one immediately deduces that for all real $x \ge 6$ $$\label{20150927.6} V(x) \le B x + 5 \log x - 1- \log 108$$ and $$\label{20150927.7} B x - 5 \log x - 1 + \log 108 \le V(x)$$ with $B = \frac{1}{6}\log 108$. We thus immediately have from \eqref{20150927.3} and \eqref{20150927.7} that for all $x \ge 6$ \begin{equation*} B x - 5 \log x - 1 + \log 108 \le \psi(x) \end{equation*} I simplify the inequality a little bit to $$\label{20150927.8} B x - 5 \log x\le \psi(x)$$ One can also check that \eqref{20150927.8} is valid for the wider range $x \ge 2$. Combining \eqref{20150927.4} and \eqref{20150927.6} and using $- 1 - \log 108 < 0$, one has for all real $x \ge 6$ that \begin{equation*} \psi(x) - \psi\left(\frac{x}{3} \right)\le B x + 5 \log x \end{equation*} On can easily check that his inequality is more widely valid for all real $x \ge 1$. To prove the upper bound, take $m \in \mathbb{N}$ such that $1 \le \frac{x}{3^m} < 3$. Applying \eqref{20150927.8} several times gives \begin{align*} \psi\left(\frac{x}{3} \right)- \psi\left(\frac{x}{3^2} \right) &\le B \frac{x}{3} + 5 \log \frac{x}{3}\\ \psi\left(\frac{x}{3^2} \right)- \psi\left(\frac{x}{3^3} \right) &\le B \frac{x}{3^2} + 5 \log \frac{x}{3^2}\\ \cdots\\ \psi\left(\frac{x}{3^m} \right)- \psi\left(\frac{x}{3^{m+1}} \right) &\le B \frac{x}{3^m} + 5 \log \frac{x}{3^m}\\ \end{align*} Because $\frac{x}{3^{m+1}} < 1$, it follows that $\psi\left(\frac{x}{3^{m+1}} \right) = 0$. Adding the inequalities thus gives \begin{equation*} \psi(x) \le \frac{3}{2} B x + 5 (m+1) \log x \end{equation*} The inequality $3^m \le x$ gives $m \le \frac{\log x }{\log3 }$. Thus \begin{equation*} \psi(x) \le \frac{3}{2} B x + 5 \left( \frac{\log x }{\log3 } + 1\right) \log x \end{equation*} I have thus shown that for all $x \ge 1$ \begin{equation*} \psi_1(x ) \le \psi(x) \le \psi_2(x) \end{equation*} with \begin{equation*} \psi_1(x ) = B x - 5 \log x \end{equation*} and \begin{equation*} \psi_2(x ) = \frac{3}{2} B x + 5 \left( \frac{\log x }{\log3 } + 1\right) \log x \end{equation*} Using further elementary manipulations, one can deduce from this that \begin{equation*} \theta(x) - \theta\left(\frac{x}{2} \right) \ge \psi_1(x) - 2 \psi_2\left( x^{1/2} \right) - \psi_2\left( \frac{x}{2} \right) \end{equation*} Because the expression on the right hand side is larger than $1$ for $x \ge 3400$, the follows that for $x \ge 3400$ there is prime $p$ with \begin{equation*} \frac{x}{2} < p \le x \end{equation*} Smaller values of $x$ can be quickly checked by hand or with Mathematica.