06 October 2007

Some partition identities due to Euler

I wrote a couple weeks ago about my love of the identity

\prod_{i=0}^\infty \left( 1 + z^{2^i} \right) = \sum_{i=0}^\infty z^i

which is an analytic version of the fact that every integer is uniquely a sum of distinct powers of 2. What I didn't realize at the time, but learned from George Andrews article Euler's "De Partitio Numerorum", in the current issue (Vol. 44, No. 4) of the Bulletin of the American Mathematical Society, is that this is due to Euler. This is hardly surprising, though, as Euler was as far as I know the first person to apply generating functions to partitions. (The result was known before that; it's the generating-function statement that's due to Euler.)

But here's one I didn't know:

\prod_{i=0}^\infty \left( z^{-3^i} + 1 + z^{3^i} \right) = \sum_{i=-\infty}^\infty z^i

This is an analytic version of the fact that every integer is uniquely a sum of distinct powers of 3 and their negatives, and is Theorem 4 of the Andrews paper. For example, 1 = 1, 2 = 3-1, 3 = 3, 4 = 3+1, 5 = 9-3+1, 6 = 9-3, 7 = 9-3+1, and so on.

To see this fact combinatorially, note that we can make 3k sums out of the numbers 30, 31, ..., 3k-1; for each of these we include the number, its negative, or neither. If we can show that these are the distinct integers from -l to l, where l = (3k-1)/2, then that's enough. (For example, when k = 2, we have l = 4, and the nine possible sums of 1, 3, and their negatives are
-3-1, -3, -3+1, -1, 0, 1, 3-1, 3, 3+1
where "0" denotes the empty sum. These are just the integers from -4 to 4.)

But this can be shown by induction on k. Clearly it's true for k = 0. Then, for the induction, consider the 3k sums of the powers of three up to 3k-1 and their negatives; by the inductive hypothesis these are just the integers in the interval $\left[ {1-3^k \over 2},  {3^k-1 \over 2} \right]$. Now consider the 3k+1 sums of the powers of three up to 3k and their negatives. There are 3k of these which are just the ones which don't include 3k. Those that include +3k add up to $\left[ {1-3^k \over 2}+3^k,  {3^k-1 \over 2}+3^k \right]$, and those which include -3k add up to $\left[ {1-3^k \over 2}-3^k,  {3^k-1 \over 2}-3^k \right]$. These three intervals put together are $\left[ {1-3^{k+1} \over 2},  {3^{k+1}-1 \over 2} \right]$, as desired. (For example, when k=2, these three intervals are [-4, 4], [5, 13], and [-13, -5], which together make up [-13, 13].) By induction, we can make each integer in $\left[ {1-3^k \over 2},  {3^k-1 \over 2} \right]$ uniquely as a sum of distinct powers of 3 which are less than 3k and their negatives, which is essentially the desired result.

The last section of the article talks about partitions with some negative parts, or "signed partitions". For example, 9+8-6-5 is a signed partition of 6. These are a bit more awkward to work with in terms of generating functions -- the generating function above about the powers of 3 doesn't converge, ever! So it's basically a curiosity, but one can actually prove things about these signed partitions using generating functions; see the article for examples.

No comments: