History Of Higher-Dimensional Partitions

The generalisation of ordinary (or one-dimensional) partitions to higher-dimensional partitions is due to Major Percy MacMahon in the early part of the twentieth century. MacMahon computed the numbers of partitions in low-dimensions and conjectured formulae for their generating functions. It took him 20+ years to prove his conjecture for the generating function of plane partitions. The other conjectured generating functions turned out to be incorrect[1]. It is possible that MacMahon also knew that they could be incorrect but there appears to be no published result due to him.

After MacMahon, the first serious computation of higher dimensional partitions, due to Atkin, Bratley, MacDonald and McKay, appeared in 1967[1]. Here is a report by Birch on this paper in his memoir on Atkin[2]:

I cannot resist mention [1967d], on $m$-dimensional partitions. At the time the authors complained that no one seemed to know anything about them except in the first two cases (ordinary partitions corresponding to the case $m=2$, and the case $m=3$ more often known as plane partitions); and very little seems to have been discovered since; there is a note on the subject in [1971d]. In the words of the third author, the paper landed like a lead balloon; but they look genuinely interesting.

The analogy with a lead balloon couldn't have been more appropriate — nothing happened for another 45 years. Their computations were aided by a computer program implementing an algorithm due to Bratley and McKay[8]. In 1970, Knuth realised that he could relate this counting problem to another counting problem, the enumeration of topological sequences of a partially ordered set, that appears in computer science[3]. He provided an algorithm to enumerate topological sequences and hence by implication, numbers of higher-dimensional partitions. He also computed the first 28 numbers of solid partitions.

Stanley in his 1971 doctoral thesis[4] has this to say about higher-dimensional partitions. (Below $r$ denotes the dimension with $r=3$ for solid partitions.)

The case $r=2$ has a well-developed theory — here 2-dimensional partitions are known as plane partitions. See $\S$ 21 and the survey article by Stanley[34] for results on plane partitions. For $r\geq3$, almost nothing is known and Proposition 11.1 casts only a faint glimmer of light on a vast darkness.

The extract also alludes to the enormous progress in enumerating plane partitions, both restricted and unrestricted. In 1986, Stanley organized the counting by symmetry[5]. By introducing a new symmetry operation called complementarity (these arose in the work on Mills-Robbins-Rumsey) in addition to the obvious $S_3$ action, plane partitions that fit into a box can be organized into ten classes. Stanley provided formulae, some conjectural, for generating functions for the numbers of plane partitions in each class. The story of how these formulae and their proofs came about is discussed in a popular science book by David Bressoud[6].

… more to come

1. A.O.L. Atkin, P. Bratley, I.G. Macdonald, and J.K.S. McKay, Some computations for $m$-dimensional partitions, Proc. Cambridge Philos. Soc. 63 (1967) 1097—1100.
2. Birch, B. "Atkin and the Atlas Lab," in Buell, D. A. and Teitelbaum, J. T. Computational perspectives on number theory. American Mathematical Society, 1998. pp. 13-20.
3. D. Knuth, A note on solid partitions, Math. Comp. 24 (1970), 955-961.
4. R. P. Stanley, Ordered structures and partitions, Ph. D. thesis (Harvard University, 1971), Memoirs of the Amer. Math. Soc., no. 119 (1972).
5. R. P. Stanley, Symmetries of plane partitions, J. Combinatorial Theory (A) 43 (1986), 103-113. Erratum, 44 (1987), 310.
6. D. Bressoud, Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, Cambridge University Press (1999)
7. S. Govindarajan, Notes on higher-dimensional partitions arXiv:1203.4419.
8. P. Bratley and J. K. S. McKay, Algorithm 313: Multi-dimensional partition generator, Commun. ACM 10 (1967) 666

This page is maintained by Suresh Govindarajan

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License