In our previous post, we learned about the partitioning problem, and here we will look at the contributions that Ramanujan made together with Hardy.
Ramanujan’s work
One of the topics that Hardy and Ramanujan worked on together when Ramanujan arrived at Cambridge in 1914 was the calculation of the number of partitions; that is, how many different ways we can write each \(n\) as a sum of positive integers, a number we call \(p(n)\).
Ramanujan believed he could find a formula that would give \(p(n)\). At least approximately. With Euler’s recursive formula it was possible to find \(p(n)\) systematically, but at the cost of a lot of work. The mathematician Percy MacMahon (the “greater MacMahon”, as Hardy and Ramanujan refer to him), Hardy’s colleague at Cambridge, had calculated up to \(p(200)\). Thus, for example:
\begin{align*}
p(1) &= 1, &
p(5) &= 7, &
p(10) &= 42, \\
p(15) &= 176, &
p(20) &= 627, &
p(25) &= 1\,958, \\
p(30) &= 5\,604, &
p(30) &= 37\,338, &
p(50) &= 204\,226, \\
p(100) &= 190\,569\,292, &
p(150) &= 40\,853\,235\,313, &
p(200) &= 3\,972\,999\,029\,388.
\end{align*}
MacMahon did not believe that Ramanujan could find a method for calculating \(p(n)\), or for estimating it with a small error. Ramanujan, on the contrary, was convinced that he had one, and, in fact, there were already formulae for it in the famous letter he wrote to Hardy in 1913, as a result of which Hardy took him to Cambridge. But he was faced with the challenge – a tremendous one for him – of being able not only to state it, but to prove it. This, of course, was where Hardy and his efforts to ensure that Ramanujan’s intuitions could be correctly stated and rigorously demonstrated came into play.
First asymptotic formulae
Their joint efforts were fruitful, and in 1917 they published a first paper [5] on the subject, a precursor of the main work (Ramanujan’s papers can also be found in the Collected papers [4]; moreover, all his papers, as well as his notebooks, are available at https://ramanujan.sirinudi.org). In that first paper they show several types of approximations for \(p(n)\), with varying accuracy.
In particular, approximating
\[
p(n) \sim P(n) := \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{2n/3}}
\]
they get
\[
\begin{array}{ccccc}
\hline
n & 10 & 20 & 50 & 80 \\
\hline
p(n) & 42 & 627 & 204\,226 & 15\,796\,476 \\
P(n) & 48 & 692 & 217\,590 & 16\,606\,781 \\
P(n)/p(n) & 1.145 & 1.104 & 1.065 & 1.051 \\
\hline
\end{array}
\]
They also propose
\[
p(n) = \frac{1}{2 \pi \sqrt{2}} \frac{d}{dn}
\frac{e^{\pi \sqrt{\frac{2}{3} \left(n-\frac{1}{24}\right)}}}{\sqrt{n-\frac{1}{24}}}
+ O\big(e^{k \sqrt{n}}\big)
=: Q(n) + O\big(e^{k \sqrt{n}}\big)
\]
with \(k\) any number greater than \(\pi/\sqrt{6}\). As can be seen, the approximation obtained with this formula is already very good:
\[
\begin{array}{cccc}
\hline
n & 61 & 62 & 63 \\
\hline
p(n) & 1\,121\,505 & 1\,300\,156 & 1\,505\,499 \\
Q(n) & 1\,121\,539 & 1\,300\,121 & 1\,505\,536 \\
\hline
\end{array}
\]
(sometimes by excess, sometimes by shortfall).
They also show the approach
\begin{align*}
p(n) &= \frac{1}{2 \pi \sqrt{2}} \frac{d}{dn}
\frac{e^{\pi \sqrt{\frac{2}{3} \left(n-\frac{1}{24}\right)}}}{\sqrt{n-\frac{1}{24}}}
+ \frac{(-1)^n}{2 \pi} \frac{d}{dn}
\frac{e^{\frac{1}{2} \pi \sqrt{\frac{2}{3} \left(n-\frac{1}{24}\right)}}}{\sqrt{n-\frac{1}{24}}}
\\
&\qquad + \frac{\sqrt{3}}{\pi\sqrt{2}} \cos\Big( \frac{2n\pi}{3}-\frac{\pi}{18} \Big)
\frac{d}{dn}
\frac{e^{\frac{1}{3} \pi \sqrt{\frac{2}{3} \left(n-\frac{1}{24}\right)}}}{\sqrt{n-\frac{1}{24}}}
+ O\big(e^{k \sqrt{n}}\big).
\end{align*}
with \(k\) any number greater than \(\pi/\sqrt{24}\).
Complete asymptotic formula
In 1918 the main paper [6] was published, which contains more complete asymptotic expressions as well as proofs of the results presented.
This full asymptotic development is
\[
p(n) = \frac{1}{2\pi\sqrt{2}} \sum_{k \le \alpha\sqrt{n}} A_{k}(n) \sqrt{k} \,
\frac{d}{dn} \Bigg\{\frac{\exp\Big(\frac{\pi}{k} \sqrt{\frac{2}{3}(n-1/24)}\,\Big)}{\sqrt{n-1/24}}\Bigg\}
+ O\big(n^{-1/4}\big)
\]
with \(\alpha\) an arbitrary positive constant, and being
\[
A_{k}(n) = \sum_{\begin{smallmatrix}0 \le h < k\\ \operatorname{mcd}(h,k)=1\end{smallmatrix}}
\omega_{h,k} \exp\bigg({-2\pi} i\frac{h}{k} n\bigg),
\]
where
\[
\omega_{h,k} = \exp\bigg( \pi i \sum_{\mu=1}^{k-1} \frac{\mu}{k}
\Big( \frac{h\mu}{k} – \Big[ \frac{h\mu}{k} \Big] – \frac{1}{2} \Big) \bigg)
\]
(\([\,\cdot\,]\) is used to denote the integer part). To be precise, we should clarify that the Hardy-Ramanujan description for \(\omega_{h,k}\) was more complicated; this formulation for the \(\omega_{h,k}\), which is equivalent to the original one, was provided by Rademacher in 1932. In their paper, Hardy and Ramanujan compare \(p(100)\) and \(p(200)\) (calculated by MacMahon) with what their formula provides:
\[
\begin{array}{ccccc}
\hline
n & p(n) \text{ (exact)} & \text{sumands} & \text{approximate value} & \text{error} \\
\hline
100 & 190\,569\,292 & 6 & 190\,569\,291.996 & 0.004 \\
200 & 3\,972\,999\,029\,388 & 8 & 3\,972\,999\,029\,388.004 & 0.004 \\
\hline
\end{array}
\]
According to what they had managed to prove, the formula represents \(p(n)\) with an error \(O(n^{-1/4})\). Since \(p(n)\) is an integer, this suffices to obtain the exact value for \(n\) sufficiently large. Moreover, it is easy to see that the error observed in the table appears to be much smaller than that \(O(n^{-1/4})\). In fact, Hardy himself confessed that the approximation was much better than expected, and that he could have come up with a more accurate result (as we shall see a little later, he was right).
It is worth emphasising that the Hardy-Ramanujan formula is an asymptotic expression; that is, if we make \(\sum_{k=1}^{\infty}\), it is not a convergent series. If you haven’t seen that before, it may sound a bit strange, but it’s actually commonplace. For example, it’s the same thing that happens to Stirling’s formula for the factorial:
\[
\log(n!) \sim n \log(n) – n + \frac{1}{2} \ln(2\pi n)
+ \sum_{k=1}^{N} \frac{B_{2k}}{2k(2k-1) n^{2k-1}}
\]
(the \(B_k\) are the Bernoulli numbers), or to Euler-Maclaurin sums.
¿Cómo es la demostración?
The proof of the Hardy-Ramanujan asymptotic expression is not simple; in addition to Euler’s formula, Cauchy’s theorem with complex variable integrals, elliptic functions and Tauberian theorems are used. This is not the right place to give it, but it is probably not out of place to see how it begins.
Let us recall Euler’s partition generating formula:
\[
G(x) := \prod_{m=1}^{\infty} \frac{1}{1-x^{m}} = \sum_{n=0}^{\infty} p(n) x^n,
\qquad |x| < 1.
\]
In particular,
\[
p(n) = n! \,\frac{d^n}{dx^n} G(x)\Big|_{x=0}.
\]
Additionally, applying Cauchy’s theorem to \(G(x)\) (as a function of a complex variable), we have
\[
G^{(n)}(0) = \frac{n!}{2\pi i} \oint_{\gamma} \frac{G(x)}{x^{n+1}}\,dx,
\]
with \(\gamma\) a circle centred at the origin and radius less than \(1\).
Then,
\[
p(n) = \frac{1}{2\pi i} \oint_{\gamma} \frac{G(x)}{x^{n+1}}\,dx.
\]
This has made it possible to relate the function \(p(n)\) to a complex integral to which all the machinery of complex analysis can be applied.
The Rademacher formula
Slightly modifying the Hardy-Ramanujan method, in 1937, Hans Rademacher [7] gave a representation of \(p(n)\) by means of a convergent series:
\[
p(n) = \frac{1}{\pi\sqrt{2}} \sum_{k=1}^{\infty} A_{k}(n) \sqrt{k} \,
\frac{d}{dn} \Bigg\{\frac{\operatorname{senh}\Big(\frac{\pi}{k}
\sqrt{\frac{2}{3}(n-1/24)}\,\Big)}{\sqrt{n-1/24}}\Bigg\}
\]
with the same \(A_{k}(n)\) as before.
The Hardy-Ramanujan asymptotic formula is an “immediate corollary” of this one. In fact, if one recalls that \(\operatorname{senh}(x) = (e^x – e^{-x})/2\), it is easy to realise that, at least apparently, the two expressions are not very different.
The fact is that the method now known as the Hardy-Ramanujan-Rademacher method (also called the “circle method”, because of the circle of radius smaller than \(1\) used in the demonstration by means of integrals of complex variable), and which is embodied in the formula we have just shown, solves in a complete and very satisfactory way an important classical problem posed by Leibniz and Euler.
At about the same time as Rademacher, Atle Selberg (Fields medalist in 1950), who was then 20 years old, obtained the same result as Rademacher, although with a different formula for the coefficients \(A_k(n)\). However, when Selberg learned that Rademacher had already found the convergent series, he decided not to publish his result, and it only became known quite a few years later.
Perhaps it is not superfluous to conclude this review by mentioning that Selberg was very critical of Hardy because, in his opinion, Hardy’s overzealousness in the rigour he demanded of Ramanujan had prevented the latter from finding the exact formula. Who can tell?
Referencias
[1] T. M. Apostol, Introducción a la Teoría Analítica de Números, Reverté, Barcelona, 1980.
[2] L. Euler, Introductio in analysin infinitorum (1748), cap. 16, «De partitione numerorum», Opera omnia, ser.1, 8; «De partition enumerorum» (1753), Opera omnia, ser. 1, 2, p. 280.
[3] L. Euler, Introductio in analysin infinitorum} (Introduction to the analysis of infinite), edited by A. J. Durán y F. J. Pérez, 2 vols. (facsimile and critical edition), SAEM Thales and Real Sociedad Matemática Española, Sevilla, 2000.
[4] G. H. Hardy, P. V. Seshu Aiyar y B. M. Wilson (editors), Collected papers of Srinavasa Ramanujan, Cambridge University Press, 1927.
[5] G. H. Hardy y S. Ramanujan, Une formule asymptotique pour le nombre des partitions de \(n\), Comptes Rendus, 2 Jan. 1917.
[6] G. H. Hardy y S. Ramanujan, Asymptotic formules in combinatory analysis, Proc. Lond. Math. Soc. (2) 17 (1918), 75–115.
[7] H. Rademacher, A convergent series for the partition function \(p(n)\), Proc. Nat. Acad. Sci. 23 (1937), 78–84.
Leave a Reply