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.

  • 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} \)

  • 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

No comments:

Post a Comment