Unimodalilty Of Higher Dimensional Partitions

## Introduction

Definition: A sequence $\{a_0, a_1,\ldots , a_d\}$ (of real numbers) is called log-concave if $a^2_i \geq a_{i−1}a_{i+1}$ for $i = 1,\ldots,d−1$. It is said to be unimodal if there exists an index $0\leq j\leq d$ such that $a_i \leq a_{i+1}$ for $i=0,\ldots, j−1$ and $a_i\geq a_{i+1}$ for $i=j,\ldots,d−1$.

Consider partitions whose Ferrers diagram fit into a square box of area $L^2$. Let $p^{(L)}_1(n)$ denote the number of partitions of $n$ that fit into the square box with side $L$. We have chosen all sides to be equal for simplicity and there is the obvious generalisation to unequal sides. Clearly, $0\leq n \leq L^2$. For L=2, one obtain the following sequence for $p^{(2)}_1(n)$:

(1)
$$1,1,2,1,1.$$

Notice that the numbers increase and then decrease clearly showing unmodality. Further, one has $p^{(L)}_1(n) = p^{(L)}_1(L^2-n)$ — the bijection is between the filled boxes and the unfilled boxes.

Proposition: The sequences $p^{(L)}_1(n)$ for are unimodal for all $L$.

Proof: See ref. [1] below for an elementary proof by Proctor. See also the combinatorial proof of Kathy O'Hara[5].

## Generalisations

Let $p^{(L)}_d(n)$ denote the number of $d$-dimensional partitions whose $(d+1)$-dimensional Ferrers diagrams fit into a hypercube of volume $L^{d+1}$.

The following holds:

(2)
\begin{align} p^{(L)}_d(n)= p^{(L)}_d(L^{d+1}-n)\ . \end{align}

The proof follows from the bijection implied by the map between a partition and its complement in the box.

Conjecture: The sequences $p^{(L)}_d(n)$ for are unimodal for all $L$ and $d$.

Remarks

1. This question of the unimodaiity of higher-dimensional partitions was posed to me by Pritam Majumder, a graduate student of Mathematics at TIFR, Mumbai during March 2016. I am stating as a conjecture as I always thought this to be true.
2. The conjecture is known to hold for $d=1,2$ i.e., for ordinary and plane partitions.
3. The proof for plane partitions is quite complicated. See reference [2] below.
4. For plane partitions ($d=2$) and $L=2$, one obtains the following unimodal sequence(3)
$$1, 1, 3, 3, 4, 3, 3, 1, 1.$$

The sum of the above numbers is the Dedekind number $M[3]=20$. The Dedekind numbers appear as sequence A000372 in the OEIS. Only the first 8 numbers are known. An estimate due to Korshunov (1981) gives $M[9]\sim 7.61352\times 10^{40}$ which appears to be a very difficult number to enumerate. The first eight numbers are

 $d$ $M[d]$ 0 1 2 3 4 5 6 7 8 2 3 6 20 168 7581 7828354 2414682040998 56130437228687557907788
5. For solid partitions ($d=3$) and $L=2$, one obtains the following unimodal sequence:(4)
$$1, 1, 4, 6, 10, 13, 18, 19, 24, 19, 18, 13, 10, 6, 4, 1, 1.$$
6. Let $T(d,k)=p_{d-1}^{(2)}(k)$. This appears as sequence A269699 in the OEIS! I have checked that it holds for $d\leq 6$. There $T(d,k)$ is the number of $k$-element proper ideals of the $d$-dimensional Boolean lattice, with $0 < k < 2^d$ while our interpretation is the number of $(d-1)$-dimensional partitions that fit in a hypercube of size $2^d$. There is an alternate interpretation of $T(d,k)$ in terms of monotone boolean functions from $\{0,1\}^{d} \rightarrow \{0,1\}$. There is indeed a very simple bijection mapping monotone boolean functions and $(d-1)$-dimensional partitions. The connection that I have obtained appears to be new! The bijection is a follows. Recall that a partition $\lambda$ is a collection of points in $\{0,1\}^{d}$. Consider the boolean function $f_\lambda(x)$ given by(5)
\begin{align} f_\lambda(x) = \begin{cases} 0 & \text{if}\quad x\in \lambda \\ 1 & \text{otherwise.} \end{cases} \end{align}

It is easy to verify that $f_\lambda(x)$ is monotone and that the map is indeed a bijection. Complementation in partitions gets mapped to the operation $f_\lambda(x) \rightarrow f_{\lambda^c}(x):=\overline{f_\lambda(\bar{x})}$. We have extended the sequence by adding the data for $d=7$ and hope to add the data for $d=8$.

Here is a nice table from the chapter on Boolean Functions in Volume 4 of Knuth's famous series of books.

7. The various methods used to prove unimodality as well as log-concavity of sequences is discussed in refs. [3] and [4] below.

### Ongoing Projects

1. Refining the Wiedemann computation of $M[8]$ by computing $T(8,k)$ for $k=0,\ldots,256$. Vidyasagar is working on this project with me. We have working code that computed $T(7,*)$ and reproduced the results in A269699 obtained by me using the Bratley-McKay algorithm.
2. Trying to look for methods to prove the unimodality conjecture mentioned above. This is something I (S.G.) have been working on passively with no bright ideas.

### References

1. R. A. Proctor, Solution of Two Difficult Combinatorial Problems with Linear Algebra, The American Mathematical Monthly Vol 89, No. 10 (1982) 721-734
2. R. A. Proctor. Bruhat Lattices, Plane Partition Generating Functions, and Minuscule Representations, Europ. J. Combinatorics, 5 (1984) 331-350
3. R. Stanley, Log-concave and Unimodal sequences in Algebra, Combinatorics, and Geometry, Annals NY Academy of Sciences, 576 (1989) 500-535.
4. F. Brenti, Log-concave and Unimodal sequences in Algebra, Combinatorics, and Geometry: an update, Contemporary Math., 178 (1994), 71-89.
5. K. O' Hara, Unimodality of Gaussian coefficients: a constructive proof, J. of Comb. Theory, Ser. A, 53 (1990) 29-52.

This page is maintained by Suresh Govindarajan