Friday, September 25, 2015

A proof of Bertrand's postulate by Sylvester

In his paper "On Tchebycheff's Theory of the Totality of the Prime Numbers Comprised within Given Limits" from 1881, Sylvester gives an outline of a proof of Bertrand's postulate. Namely, he writes "the formulae above indicated would suffice to prove M. Bertrand's postulate, and would lead to an equation somewhat simpler in form than that led to by M. Tchebycheff's process". In this post, I provide more detail on this proof.
The proof is based on inequalities for the function $$\label{20150923.1} V(x) = T(x) - T\left( \frac{x}{2} \right)- T\left( \frac{x}{3} \right)- T\left( \frac{x}{6} \right)$$ where \begin{equation*} T(x) = \sum_{ 1 \le n \le x} \log n \end{equation*} 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 $$\label{20150923.2} V(x) = \psi(x) +\psi\left( \frac{x}{5} \right)- 2 \psi\left( \frac{x}{6} \right)+ \psi\left( \frac{x}{7} \right) +\psi\left( \frac{x}{11} \right)- 2 \psi\left( \frac{x}{12} \right) + \cdots$$ The coefficients of $\psi\left( \frac{x}{n} \right)$ in this expression have period 6. In contrast to a similar equation in Chebyshev's Mémoire, the signs in \eqref{20150923.2} are not alternating, this makes it less straightforward to use \eqref{20150923.2} to obtain bounds on $\psi(x)$.

For all real $x \ge 1$, one has $$\label{20150923.3} x \log x - x - \log x +1 \le T(x) \le x \log x - x + \log x +1$$ From \eqref{20150923.1} and \eqref{20150923.3} one immediately deduces that for all real $x \ge 6$ $$\label{20150923.4} V(x) \le B x +4 \log x - 2 -2 \log 6$$ and $$\label{20150923.5} B x - 4 \log x - 2 + 2 \log 6 \le V(x)$$ where $B = \frac{1}{2} \log 2 + \frac{1}{3} \log 3 + \frac{1}{3} \log 3$.

Calculation of upper bound on $\psi(x)$
Because $n \to \psi\left( \frac{x}{n} \right)$ is decreasing, it follows that \begin{equation*} \psi\left( \frac{x}{7} \right)+\psi\left( \frac{x}{11} \right)- 2 \psi\left( \frac{x}{12} \right) \ge 0 \end{equation*} and \begin{equation*} \psi\left( \frac{x}{13} \right)+\psi\left( \frac{x}{17} \right)- 2 \psi\left( \frac{x}{18} \right) \ge 0 \end{equation*} and so on. Therefore from \eqref{20150923.2} one obtains \begin{equation*} V(x) \ge \psi(x) +\psi\left( \frac{x}{5} \right)- 2 \psi\left( \frac{x}{6} \right) \end{equation*} Because $\psi\left( \frac{x}{5} \right)- \psi\left( \frac{x}{6} \right) \ge 0$, it follows also that $$\label{20150923.6} V(x) \ge \psi(x) - \psi\left( \frac{x}{6} \right)$$ One can obtain an upper bound on $\psi(x)$ with a standard calculation: combining \eqref{20150923.4} and \eqref{20150923.6} and using $-2 - 2 \log 6 < -5$, one has for all real $x \ge 6$ that $$\label{20150923.7} \psi(x) - \psi\left(\frac{x}{6} \right)\le B x + 4 \log x - 5$$ Take $m \in \mathbb{N}$ such that $6 \le \frac{x}{6^m} < 6^2$. Applying \eqref{20150923.7} several times gives \begin{align*} \psi\left(\frac{x}{6} \right) - \psi\left(\frac{x}{6^2} \right) & \le B \frac{x}{6} + 4 \log \frac{x}{6} - 5\\ \psi\left(\frac{x}{6^2} \right) - \psi\left(\frac{x}{6^3} \right) & \le B \frac{x}{6^2} + 4 \log \frac{x}{6^2} - 5\\ \cdots\\ \psi\left(\frac{x}{6^m} \right) - \psi\left(\frac{x}{6^{m+1}} \right) & \le B \frac{x}{6^m} + 4 \log \frac{x}{6^m} - 5 \end{align*} Adding the inequalities gives \begin{equation*} \psi(x) \le \psi\left(\frac{x}{6^{m+1}} \right) + \frac{6}{5} B + 4 (m+1) \log x - (m+1) 5 \end{equation*} The inequality $6^{m+1} \le x$ gives $m + 1 \le \frac{\log x }{\log 6 }$. Also, $1 \le \frac{x}{6^{m+1}} < 6$, thus $\psi\left(\frac{x}{6^{m+1}} \right) \le 3$. Therefore, for all $x \ge 6$ one has $$\label{20150923.8} \psi(x)\le \frac{6}{5} B x + 4 \frac{\log^2 x}{\log 6}$$ One can verify in Mathematica that this inequality is also valid for $x \ge 1$

Calculation of lower bound on $\psi(x)$
One has \begin{equation*} -2 \psi\left( \frac{x}{6} \right)+\psi\left( \frac{x}{7} \right)+\psi\left( \frac{x}{11} \right) \le 0 \end{equation*} and \begin{equation*} -2 \psi\left( \frac{x}{12} \right)+\psi\left( \frac{x}{13} \right)+\psi\left( \frac{x}{17} \right) \le 0 \end{equation*} and so on. Therefore from \eqref{20150923.2} one obtains \begin{equation*} V(x) \le \psi(x) + \psi\left( \frac{x}{5} \right)\end{equation*} Combining this inequality with \eqref{20150923.5} and \eqref{20150923.8} then gives for $x \ge 5$ \begin{equation*} B x - 4 \log x -2 + 2 \log 6 - \frac{6}{5} B \frac{x}{5} - 4 \frac{\log^2 x/5}{\log 6} \le \psi(x) \end{equation*} I simplify this expression slightly by using $-2 + 2 \log 6 > 0$, then $$\label{20150923.9} \frac{19}{25} B x - 4 \log x - 4 \frac{\log^2 x/5}{\log 6} \le \psi(x)$$

Proof of Bertrand's postulate
Because $\displaystyle\frac{6/5 B}{19/25 B} < 2$, the upper and lower bound are sufficiently close and one can now deduce Bertrand's postulate in a standard way. I do not do so here, because the post is already quite long. Details can for example be found in Murty's book.