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)
\begin{equation} 1,1,2,1,1. \end{equation}

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)
    \begin{equation} 1, 1, 3, 3, 4, 3, 3, 1, 1. \end{equation}

    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$ 0 1 2 3 4 5 6 7 8
    $M[d]$ 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)
    \begin{equation} 1, 1, 4, 6, 10, 13, 18, 19, 24, 19, 18, 13, 10, 6, 4, 1, 1. \end{equation}
  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.

    FromKnuthChap4.jpg
  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

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