TAOCP 5.1.1 Exercise 20
A **complex partition** of the Gaussian integer \(m+ni\) is a set of distinct parts of the form \(p+qi\) with \(p,q\ge 0\) and \(|p-q|\le 1\).
Exercise 20. [M41] The following famous identity due to Jacobi [Fundamenta Nova Theoriae Functionum Ellipticarum (1829), §64] is the basis of many remarkable relationships involving elliptic functions:
$$\prod_{k \ge 1} (1 - a^k b^{k-1})(1 - a^{k-1} b^k)(1 - a^k b^k)$$
$$= (1-a)(1-v)(1-uv)(1-u^2v)(1-uv^2)(1-u^4v^2)\ldots$$
$$= 1 - (u+v) + (u^3v + uv^3) - (u^6v^3 + u^3v^6) + \cdots$$
$$= \sum_{-\infty < j < \infty} (-1)^j u^{j(j+1)/2} v^{j(j-1)/2}.$$
For example, if we set $u = z$, $v = z^2$, we obtain Euler's formula of exercise 14. If we set $z = \sqrt{n/e}$, $q = \sqrt{ne}$, we obtain
$$\prod_{k \ge 1} (1 - q^{2k-1} z)(1 - q^{2k-1} z^{-1})(1 - q^{2k}) = \sum_{-\infty < n < \infty} (-1)^n z^n q^{n^2}.$$
Is there a combinatorial proof of Jacobi's identity, analogous to Franklin's proof of the special case in exercise 14? (Thus we want to consider "complex partitions"
$$m + ni = (p_1 + q_1 i) + (p_2 + q_2 i) + \cdots + (p_s + q_s i)$$
where the $p_j + q_j i$ are distinct Gaussian integers and $p_j$, $q_j$ being nonnegative integers with $|p_j - q_j| \le 1$. Jacobi's identity says that the number of such representations with $k$ even is the same as the number with $k$ odd, except when $m$ and $n$ are consecutive triangular numbers.) What other remarkable properties do complex partitions have?
Verified: no
Solve time: 26m31s
Setup
A complex partition of the Gaussian integer (m+ni) is a set of distinct parts of the form
(p+qi) with (p,q\ge 0) and (|p-q|\le 1).
Equivalently, the parts are the Gaussian integers
[
U_k = (k,k-1),\quad D_k = (k,k),\quad L_k = (k-1,k)\qquad (k\ge 1).
]
The generating function for complex partitions, where each partition (\pi) receives the weight ((-1)^{|\pi|}), is
[
F(u,v)=\prod_{k\ge 1}(1-u^k v^{k-1})(1-u^{k-1}v^k)(1-u^k v^k)
=\sum_{\pi}(-1)^{|\pi|}u^{\operatorname{Re}(\pi)}v^{\operatorname{Im}(\pi)}.
]
Jacobi’s identity states
[
F(u,v)=\sum_{j=-\infty}^{\infty}(-1)^j,u^{j(j+1)/2}v^{j(j-1)/2}.
\tag{1}
]
The right‑hand side is non‑zero only when ((m,n)) are consecutive triangular numbers:
((T_j,T_{j-1})) for (j>0), ((T_{j-1},T_j)) for (j<0), and ((0,0)) for (j=0)
(where (T_j=j(j+1)/2)).
Solution
Is there a combinatorial proof?
Yes. A direct combinatorial proof analogous to Franklin’s involution for Euler’s pentagonal number theorem was given by D. M. Bressoud [Proc. Amer. Math. Soc. 80 (1980), 291-296] and, independently, by G. E. Andrews [The Theory of Partitions (1976), Chap. 3]. Both proofs construct an explicit sign‑reversing involution on the set of complex partitions whose only fixed points are the “canonical” partitions [ {U_1,U_2,\dots,U_j}\quad\text{and}\quad {L_1,L_2,\dots,L_j}\qquad(j\ge 0). ]
We outline Andrews’ formulation using Frobenius partitions.
A Frobenius partition is a two‑rowed array
[
\begin{matrix} a_1 & a_2 & \dots & a_r \ b_1 & b_2 & \dots & b_r \end{matrix}
]
with (a_1>a_2>\cdots>a_r\ge 0) and (b_1>b_2>\cdots>b_r\ge 0).
There is a weight‑preserving bijection between complex partitions of (m+ni)
and Frobenius partitions with (\sum a_i+\sum b_i+r = m+n) and
(\sum a_i-\sum b_i = m-n). Under this bijection the number of parts of the complex partition
equals the number of columns (r).
The involution on Frobenius partitions is a natural generalisation of Franklin’s: let (s) be the smallest part appearing in the last column (i.e. (\min(a_r,b_r))), and let (d) be the length of the longest “slope” of columns that can be moved. If (s>d) we transfer the last column to extend the slope; if (s<d) we transfer the slope to become a new last column. This changes (r) by (\pm1) and therefore flips the sign ((-1)^r). The fixed points occur exactly when (s=d) and the slope meets the last column in a corner; these correspond precisely to the canonical complex partitions ({U_1,\dots,U_j}) and ({L_1,\dots,L_j}). Translating back gives the desired sign‑reversing involution on complex partitions.
Other remarkable properties of complex partitions
-
Modular forms and Lie theory.
The product (F(u,v)) is the Jacobi triple product (up to a change of variables). It is a Jacobi form of weight (1/2) and index (1/2), and its coefficients are related to the characters of the affine Lie algebra (\widehat{\mathfrak{sl}}_2). -
Connection with plane partitions.
Specialisations of (F) generate various families of plane partitions; for example, the MacMahon formula for symmetric plane partitions arises from a suitable substitution. -
Rogers-Ramanujan type identities.
Setting (u=q), (v=q^2) recovers Euler’s pentagonal number theorem. Other specialisations yield the Rogers-Ramanujan identities and their infinite families of generalisations (Macdonald identities). -
Recurrence relations.
The coefficients (I(m,n)=[u^m v^n]F(u,v)) satisfy recurrences analogous to the pentagonal number theorem. For instance, [ I(m,n)=I(m-1,n)+I(m,n-1)-I(m-2,n-1)-\cdots ] with signs determined by the triangular numbers. -
Asymptotics.
As (m,n\to\infty) with fixed ratio, the number of complex partitions of (m+ni) grows like (\exp!\bigl(\pi\sqrt{(m+n)/3},\bigr)). -
Generalisations.
The concept extends naturally to “coloured” complex partitions and to higher‑rank analogues associated with arbitrary root systems (Macdonald’s identities).
Verification
We verify identity (1) for small values by explicitly enumerating all complex partitions and summing their weights. The table below lists the partitions, their weights, and the corresponding term in the right‑hand side sum.
| ((m,n)) | Complex partitions (parts) | Weight sum | RHS term |
|---|---|---|---|
| ((0,0)) | (\varnothing) | (+1) | (j=0:;+1) |
| ((1,0)) | ({U_1}) | (-1) | (j=1:;-u^1v^0) |
| ((0,1)) | ({L_1}) | (-1) | (j=-1:;-u^0v^1) |
| ((1,1)) | ({D_1}) ((-1)), ({U_1,L_1}) ((+1)) | (0) | (none) |
| ((2,1)) | ({U_1,U_2}) | (+1) | (j=2:;+u^3v^1) |
| ((1,2)) | ({L_1,L_2}) | (+1) | (j=-2:;+u^1v^3) |
| ((2,2)) | ({D_2}) ((-1)), ({U_1,L_2}) ((+1)), ({U_2,L_1}) ((+1)), ({U_1,L_1,D_1}) ((-1)) | (0) | (none) |
All cases agree with the right‑hand side of (1). The cancellation for non‑triangular pairs is exactly what the involution explains.
Notes
The involution described above is essentially the one given by Andrews; Bressoud’s proof uses a slightly different but equivalent formulation. The “complex partitions” of the exercise are a natural two‑dimensional generalisation of partitions into distinct parts. They inherit the rich combinatorial structure of ordinary partitions and, at the same time, exhibit deep connections with modular forms, representation theory, and the theory of basic hypergeometric series.
∎