Sunday, August 23, 2015

How not to prove Bertrand's postulate

This is a first post motivated by Chebyshev's paper "Mémoire sur les nombres premiers" from 1852. In this paper Chebyshev proves Bertrand's postulate that there is always a prime between $a$ and $2a$ for all $a \ge 2$. Chebyshev bases his proof on inequalities for the function $$\label{HNTPeq:1} 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)$$ with \begin{equation*} T(x) = \sum_{ 1 \le n \le x} \log n \end{equation*} Chebyshev's paper is quite easy to read and can be found at this link. In this post I will follow Chebyshev's reasoning on an easier version of \eqref{HNTPeq:1}.
A good motivation why Chebyshev uses \eqref{HNTPeq:1} can be found in this master thesis. Namely, if one defines $\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*} \psi(x) = \sum_{n=1}^{\infty} \mu(n)\ T\left(\frac{x}{n} \right) \end{equation*} See Murty's book for example for these formulas. Because $T(x) \approx x \log x - x$, $\psi(x)$ can be approximated as \begin{equation*} \psi(x) \approx \sum_{n\le x} \mu(n)\left( \frac{x}{n} \log\frac{x}{n} - \frac{x}{n}\right) \approx \sum_{n\le x} \frac{\mu(n)}{n} \left(x \log x - x \right) - \left( \sum_{n\le x} \frac{\mu(n)}{n} \log n \right)x \end{equation*} The prime number theorem, which was not proved yet at the time of Chebyshev, states that $\psi(x) \sim x$. It thus seems natural to use some kind of approximation to the Möbius function $\tilde\mu \approx \mu$ so that $\tilde\mu(n) = 0$ for large $n$ and $\sum \frac{\tilde\mu(n)}{n} = 0$ in order to remove the term $x \log x$. Chebyshev took $\tilde\mu(1) = 1,\ \tilde\mu(2) = -1,\ \tilde\mu(3) = -1,\ \tilde\mu(5) = -1,\ \tilde\mu(30) = 1,$ and other $\tilde\mu(n) = 0$. For this choice, it follows indeed that \begin{equation*} 1 - \frac{1}{2} - \frac{1}{3}- \frac{1}{5}+\frac{1}{30} = 0 \end{equation*} To get close to the prime number theorem, one also would like that $- \sum\frac{\tilde\mu(n)}{n} \log n \approx 1$. Chebyshev's choice gives $- \sum\frac{\tilde\mu(n)}{n} \log n \approx 0.92$ which is quite close to 1. In the following, I will take instead $\tilde\mu(1) = 1,\ \tilde\mu(2) = -2$, and other $\tilde\mu(n) = 0$. For this simpler choice, \begin{equation*} \sum\frac{\tilde\mu(n)}{n} = 1 - \frac{2}{2} = 0 \end{equation*} and \begin{equation*} \sum\frac{\tilde\mu(n)}{n} \log n \approx 0.69 \end{equation*} Because 0.69 is farther from 1 than Chebyshev's value 0.92, one thus expects this simpler choice for $\tilde\mu$ to give weaker results than Chebyshev's results. I now follow Chebyshev's reasoning from his paper but on this simpler choice of $\tilde \mu$. Additionally, I use Landau's large $O$ notation whereas Chebyshev's uses explicit inequalities. I thus study the function \begin{equation*} T(x) - 2\ T\left( \frac{x}{2} \right) \end{equation*} Because $T(x) = \sum_{n=1}^{\infty} \psi\left(\frac{x}{n} \right)$, one has \begin{equation*} T(x) - 2\ T\left( \frac{x}{2} \right) = \psi(x) - \psi\left(\frac{x}{2} \right)+\psi\left(\frac{x}{3} \right)-\psi\left(\frac{x}{4} \right)+\cdots \end{equation*} This series is alternating and decreasing, thus $$\label{eq:2} \psi(x) - \psi\left(\frac{x}{2} \right)\le T(x) - 2\ T\left( \frac{x}{2} \right) \le \psi(x)$$ Because $T(x) = x \log x - x + O(\log x )$, it follows that \begin{align*} T(x) - 2\ T\left( \frac{x}{2} \right) &= x \log x - x + O(\log x ) -2 \left( \frac{x}{2} \log\frac{x}{2} - \frac{x}{2} + O\left( \log \frac{x}{2} \right) \right)\\ & = - x + x \cdot \log 2 + x + O(\log x ) \\ &= \log 2 \cdot x + O(\log x ) \end{align*} The terms involving $x \log x$ have cancelled. This is not a coincidence, but a consequence of the choice of $\tilde \mu$. The function $\psi(x)$ has thus the following lower bound $$\label{eq:3} \log 2 \cdot x + O(\log x ) \le \psi(x)$$ To obtain an upper bound , one can proceed as follows (Chebyshev uses a different argument) \begin{align*} \psi(x) - \psi\left(\frac{x}{2} \right) & \le \log 2 \cdot x + O(\log x )\\ \psi\left(\frac{x}{2} \right)- \psi\left(\frac{x}{4} \right) & \le \log 2 \cdot \frac{x}{2} + O(\log x )\\ \psi\left(\frac{x}{4} \right)- \psi\left(\frac{x}{8} \right) & \le \log 2 \cdot \frac{x}{4} + O(\log x )\\ \cdots \end{align*} Because $\psi\left(\frac{x}{2^m} \right) = 0$ if $m > \frac{\log x}{\log 2}$, adding the above inequalities gives the upper bound $$\label{eq:4} \psi(x) \le 2 \cdot \log 2 \cdot x + O(\log^2 x )\\$$
3. In the next post, I will repeat the argument using explicit inequalities instead of using the big $O$ notation.