An identity of Ramanujan

November 24, 2009

An identity of Ramanujan

Filed under: Math — cfranc @ 8:14 pm

Here at McGill, Darmon’s graduate students participate in a weekly student seminar. Today Luca Candelori was the victim, and he spoke about his masters research. To start he motivated things with a discussion of the partition function and its connection with modular forms. He gave a really nice combinatorial proof of an identity for the generating function of the partition function, which was first written down by Ramanujan. I thought it was such a nice proof that it deserved to be singled out in its own blog post. Everything I say here I learned from Luca today, and he learned of it from papers of Ken Ono. In particular, everything I say below (and much, much more) can be found in Ono’s paper “Unearthing the visions of a master: harmonic Maass forms and number theory“.

To start we should recall the definition of a partition of a positive integer. Here positive means strictly larger than $0$ . A partition of a positive integer $n$ is just a nonincreasing sequence of positive integers which sums to $n$ . This is best illustrated by example. One usually writes such a partition as a sum of terms decreasing in size as one moves to the right. Here are all of the distinct partitions of 5:

$5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1$ .

The number of distinct partitions of a positive integer is finite. We let $p(n)$ denote the number of partitions of $n$ . It is easy to see that for each $n$ one has $p(n) \leq n^n + 1$ , but this is just about the most naive bound that one can come up with. I don’t know about the asymptotic behaviour of $p(n)$ , but it has been well-studied. In any case, when we extend $p(n)$ by defining $p(0) = 1$ , then the resulting function $p(n)$ is called the partition function.

In this post we are concerned with the generating function of $p(n)$ , which is the formal series

$\sum_{n = 0}^\infty p(n)q^n$ .

We will prove the formal identity

$\prod_{n = 1}^\infty \left(\frac{1}{1-q^n}\right) = 1 + \sum_{n = 1}^\infty \frac{q^{n^2}}{(1 - q)^2(1 - q^2)^2\cdots(1 - q^n)^2}$ .

by showing that both sides equal the generating function of $p(n)$ . One of these equalities is an old theorem of Euler, and the other was first written down by Ramanujan. It was not clear to anybody at our student seminar whether Ramanujan had a proof of this fact, though.

We’ll begin by establishing the identity of Euler. For this first consider the geometric series identity

$\frac{1}{1-q} = 1 + q + q^2 + q^3 + \cdots$

I want to write this in a stupid way that will be helpful later. Let’s write $p_m(n)$ for the number of partitions of $n$ using only terms of size at most $m$ . Then of course $p_1(n) = 1$ for all positive integers $n$ , as there is only one way to write each positive integer as a sum of ones. So, if we again define $p_m(0) = 1$ , then the identity above just says that the generating function of $p_1(n)$ is equal to $(1 - q)^{-1}$ . So far so good. What happens if we consider the product $(1 -q)^{-1}(1 - q^2)^{-1}$ instead? In this case we can again use the geometric series formula to obtain

$\frac{1}{(1 - q)(1 - q^2)} = \left(1 + q + q^2 + q^3 + \cdots \right)\left(1 + q^2 + q^4 + q^6 + \cdots\right)$ .

Expanding this product gives a formal series $\sum_{n \geq 0} a_nq^n$ where $a_n$ is just the number of even numbers between $0$ and $n$ . But if $2d$ is an even integer satisfying $0 \leq 2d \leq n$ , then associating it to the partition of $n$ consisting of $d$ twos and $n - 2d$ ones shows that $a_n = p_2(n)$ for all $n$ . Thus

$\frac{1}{(1 - q)(1 - q^2)} = p_2(0) + p_2(1)q + p_2(2)q^2 + p_2(3)q^3 + \cdots$

In general one has the identity

$\frac{1}{(1 - q)(1 - q^2)\cdots(1 - q^m)} = p_m(0) + p_m(1)q + p_m(2)q^2 + p_m(3)q^3 + \cdots$ .

This can be proved by induction, for instance. As $p_m(n) = p(n)$ for all $n \leq m$ , this formula shows that the partial products above converge to the generating function of $p(n)$ in the $q$ -adic topology as $m$ tends to infinity. This establishes Euler’s identity:

$\sum_{n \geq 0} p(n)q^n = \prod_{n = 1}^\infty \left(\frac{1}{1-q^n}\right)$ .

Proving Ramanujan’s identity requires a little more work. The trick is to count partitions of numbers in a different way, according to a Durfee square. To explain, note that partitions may be represented in diagramatic form via a sequence of lines of dots. For instance, the partition $5 = 2 + 2 + 1$ can be written as two lines of two dots each, followed by a third line of a single dot. A larger example appears below:
The Durfee square of a partition drawn like this is the largest square of dots in the partition starting in the top left corner. Thus, in the example above the Durfee square has size $4^2$ and is drawn in green below:
Notice that there are two other partitions involving terms of size at most $4$ associated to this Durfee square,
In this way one sees that partitions of $n$ containing a Durfee square of side length $m$ correspond one to one with pairs of partitions of integers $a$ and $b$ , such that the partitions have terms of size at most $m$ and $a + b + m^2 = n$ .

Let’s write $d_m(n)$ for the number of partitions of $n$ which contain a Durfee square of side length $m$ . Then of course $p(n) = d_1(n) + d_2(n) + \cdots$ , where this sum is in fact finite; we have $d_m(n) = 0$ whenever $m^2 > n$ . With this notation we compute

$\sum_{n = 0}^\infty p(n)q^n = \sum_{n = 0}^\infty \sum_{m^2 \leq n} d_m(n)q^n = \sum_{m \geq 0} \left(\sum_{n \geq m^2} d_m(n)q^{n - m^2}\right)q^{m^2}$ .

Now let’s focus on the inner sum. A change of index gives

$\sum_{n \geq m^2} d_m(n)q^{n - m^2} = \sum_{k \geq 0} d_m(k + m^2)q^k$ .

Recall that for each $m \geq 0$ one has

$\frac{1}{(1 - q)(1 - q^2)\cdots(1 - q^m)} = p_m(0) + p_m(1)q + p_m(2)q^2 + p_m(3)q^3 + \cdots$ .

Squaring this gives the sequence $\sum_{k = 0}^\infty a_kq^k$ where

$a_k = \sum_{r = 0}^n p_m(r)p_m(k - r)$ .

This is just the number of pairs of partitions of integers $a$ and $b$ which contain terms of size at most $m$ , and such that $a + b = k$ ! But such pairs correspond one to one with partitions of $k + m^2$ containing a Durfee square of side length $m$ , which shows that $a_k = d_m(k + m^2)$ . Substituting this back up into our computation of the generating function for $p(n)$ above gives Ramanujan’s identity:

$\sum_{n = 0}^\infty p(n)q^n = 1 + \sum_{n = 1}^\infty \frac{q^{n^2}}{(1 - q)^2(1 - q^2)^2\cdots(1 - q^n)^2}$ .

Wow!

Like this:

Be the first to like this post.

Comments (2)

2 Comments »

I liked the proof and use of durfee square. Please let me know its publication details

Comment by Shivani Bedi — March 26, 2010 @ 3:19 am

Reply
- You can read a copy of a paper of Ken Ono containing this and much, much more at the link:
  http://www.math.wisc.edu/~ono/reprints/114.pdf
  It’s a nice read with lots of biographical info and background on Ramanujan. The stuff on Durfee squares begins at page 8.
  
  Comment by cfranc — March 28, 2010 @ 2:06 pm
  
  Reply

RSS feed for comments on this post.

Cam's Blog

November 24, 2009