Cam's Blog

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:A partition of 26
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:A Durfee square
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!

Advertisements

2 Comments »

  1. 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


RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: