Supriya Ghosh (Editor)

Solid partition

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In mathematics, solid partitions are natural generalizations of partitions and plane partitions defined by Percy Alexander MacMahon. A solid partition of n is a three-dimensional array, n i , j , k , of non-negative integers (the indices i ,   j ,   k 1 ) such that

Contents

i , j , k n i , j , k = n

and

n i + 1 , j , k n i , j , k , n i , j + 1 , k n i , j , k and n i , j , k + 1 n i , j , k ,   i ,   j  and  k   .

Let p 3 ( n ) denote the number of solid partitions of n . As the definition of solid partitions involves three-dimensional arrays of numbers, they are also called three-dimensional partitions in notation where plane partitions are two-dimensional partitions and partitions are one-dimensional partitions. Solid partitions and their higher-dimensional generalizations are discussed in the book by Andrews.

Ferrers diagrams for solid partitions

Another representation for solid partitions is in the form of Ferrers diagrams. The Ferrers diagram of a solid partition of n is a collection of n points or nodes, λ = ( y 1 , y 2 , , y n ) , with y i Z 0 4 satisfying the condition:

Condition FD: If the node a = ( a 1 , a 2 , a 3 , a 4 ) λ , then so do all the nodes y = ( y 1 , y 2 , y 3 , y 4 ) with 0 y i a i for all i = 1 , 2 , 3 , 4 .

For instance, the Ferrers diagram

( 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 )   ,

where each column is a node, represents a solid partition of 5 . There is a natural action of the permutation group S 4 on a Ferrers diagram – this corresponds to permuting the four coordinates of all nodes. This generalises the operation denoted by conjugation on usual partitions.

Equivalence of the two representations

Given a Ferrers diagram, one constructs the solid partition (as in the main definition) as follows.

Let n i , j , k be the number of nodes in the Ferrers diagram with coordinates of the form ( i 1 , j 1 , k 1 , ) where denotes an arbitrary value. The collection n i , j , k form a solid partition. One can verify that condition FD implies that the conditions for a solid partition are satisfied.

Given a set of n i , j , k that form a solid partition, one obtains the corresponding Ferrers diagram as follows.

Start with the Ferrers diagram with no nodes. For every non-zero n i , j , k , add n i , j , k nodes ( i 1 , j 1 , k 1 , y 4 ) for 0 y 4 < n i , j , k to the Ferrers diagram. By construction, it is easy to see that condition FD is satisfied.

For example, the Ferrers diagram with 5 nodes given above corresponds to the solid partition with

n 1 , 1 , 1 = n 2 , 1 , 1 = n 1 , 2 , 1 = n 1 , 1 , 2 = n 2 , 2 , 1 = 1

with all other n i , j , k vanishing.

Generating function

Let p 3 ( 0 ) 1 . Define the generating function of solid partitions, P 3 ( q ) , by

P 3 ( q ) := n = 0 p 3 ( n )   q n = 1 + q + 4   q 2 + 10   q 3 + 26   q 4 + 59   q 5 + 140   q 6 +

The generating functions of partitions and plane partitions have simple formulae due to Euler and MacMahon respectively. However, a guess of MacMahon fails to correctly reproduce the solid partitions of 6 as shown by Atkin et al. It appears that there is no simple formula for the generating function of solid partitions. Somewhat confusingly, Atkin et al. refer to solid partitions as four-dimensional partitions as that is the dimension of the Ferrers diagram.

Exact enumeration using computers

Given the lack of an explicitly known generating function, the enumerations of the numbers of solid partitions for larger integers have been carried out numerically. There are two algorithms that are used to enumerate solid partitions and their higher-dimensional generalizations. The work of Atkin. et al. used an algorithm due to Bratley and McKay. In 1970, Knuth proposed a different algorithm to enumerate topological sequences that he used to evaluate numbers of solid partitions of all integers n 28 . Mustonen and Rajesh extended the enumeration for all integers n 50 . In 2010, S. Balakrishnan proposed a parallel version of Knuth's algorithm that has been used to extend the enumeration to all integers n 72 . One finds

p 3 ( 72 ) = 3464274974065172792   ,

which is a 19 digit number illustrating the difficulty in carrying out such exact enumerations.

Asymptotic behavior

It is known that from the work of Bhatia et al. that

lim n n 3 / 4 ln p 3 ( n ) a constant .

The value of this constant was estimated using Monte-Carlo simulations by Mustonen and Rajesh to be 1.79 ± 0.01 .

References

Solid partition Wikipedia


Similar Topics
Heaven on Earth: The Rise and Fall of Socialism
Paola Pérez
James Sinegal
Topics
 
B
i
Link
H2
L