Sunday, May 10, 2015

Ramanujan's proof of Bertrand's postulate, 1919

I read Ramanujan's proof of Bertrand's postulate. I liked the paper because with only 2 pages it is very short. Secondly, the paper contains explicit upper and lower bounds on some arithmetical functions; such bounds can be tested in Mathematica, whereas the more common statements involving the big-O notation cannot. Murty refers to Ramanujan's proof on page 38 in his book, but Murty rephrases Ramanujan's proof with the big-O notation. I find it refreshing to read the original version of the proof instead. This post contains thoughts on the structure of Ramanujan's proof.

Define $\theta(x) = \sum_{p \le x} \log p$. To prove Bertrand's postulate it is sufficient to prove that  $\theta(2 x ) - \theta(x) > 0$ for sufficiently large $x$ and check smaller values of  $x$ by hand.

Remarks:
• One could calculate the asymptotic expansion of  $\theta(x)$ and then verify that  $\theta(2 x ) - \theta(x) > 0$. However, I think this is more difficult because knowing the asymptotic expansion is already closely related to the prime number theorem.
• I use the terminology "derivative" of  $f(x)$ for expressions like $f(x) - f(\frac{x}{2} )$
It turns out that it is easier to treat the Möbius transform $\psi(x) = \sum_{n=1}^\infty \theta(x^{1/n})$. From bounds on "derivatives" of $\psi(x)$ Ramanujan deduces bounds on the "derivatives" of $\theta(x)$ . I call this the Tauber step.

To obtain bounds on "derivatives" of $\psi (x)$, Ramanujan uses the Möbius transform $\log \lfloor x \rfloor ! = \sum_{n=1}^\infty \psi(\frac{x}{n} )$ and uses bounds on "derivatives" of  $\log \lfloor x \rfloor !$, and another Tauber step. Finally, bounds on $\log \lfloor x \rfloor !$ are easy because one has Stirling's approximation.

Hence, the structure of the proof is
$\begin{array}{ccccc} \text{bounds on} & & \text{bounds on} & & \text{bounds on}\\ \text{(derivatives of)} & \xrightarrow{T} & \text{(derivatives of)} & \xrightarrow{T}& \text{(derivatives of)}\\ \log \lfloor x \rfloor ! && \psi(x) && \theta(x) \end{array}$

Remarks:
• Here $\xrightarrow{T}$ means the Tauber step.
• What I call the Tauber step is a simple version of the Landau-Ingham Tauberian theorem, see notes from Michael Müger for details on this theorem.
• In the next post I will follow Ramanujan's manipulations to calculate bounds in a simpler situation.
Other posts about Bertrand's postulate