# Counting higher-dimensional partitions with symmetric function theory

My coauthors and I are writing a (mostly expository) paper in which we construct the Specht module. Our proof that the Specht module is irreducible in characteristic zero implies the following stronger fact:

The number of monomial ideals of $\mathbb{Q}[x_1, \ldots, x_k]$ of codimension $n$ is equal to the number of $k$-tuples of partitions, $(\lambda^1, \ldots, \lambda^k)$, $\lambda^i \vdash n$ , for which $\langle h_{\lambda^1} \ast \cdots \ast h_{\lambda^k} \;,\; e_n \rangle = 1$.

Here, $\ast$ denotes Kronecker product, $h$ denotes the homogeneous symmetric function, $e$ denotes the elementary symmetric function, and $\langle \;\;, \;\; \rangle$ denotes the Hall inner product.

It seems likely that this fact is known. However, the literature on planar partitions (and higher-dimensional partitions) focuses on finding a generating function, which is a different, much harder question. Does anyone know a reference for the easier fact above?

To use Sage to compute these numbers, start with the following lines:

h = SymmetricFunctions(QQ).homogeneous()
e = SymmetricFunctions(QQ).elementary()


Now, the number of monomial ideals in three variables up to codimension 7 may be computed using

for n in range(7):
print sum([1 if h[a].itensor(h[b].itensor(h[c])).scalar(e[n]) == 1 else 0\
for a in Partitions(n)\
for b in Partitions(n)\
for c in Partitions(n)])


which lists the numbers $1, 1, 3, 6, 13, 24, 48,$ an initial segment of OEIS A000219. Similarly, monomial ideals in four variables may be counted

for n in range(5):
print sum([1 if h[a].itensor(h[b].itensor(h[c].itensor(h[d])))\
.scalar(e[n]) == 1 else 0\
for a in Partitions(n)\
for b in Partitions(n)\
for c in Partitions(n)\
for d in Partitions(n)])


The resulting sequence, $1, 1, 4, 10, 26$, is an initial segment of OEIS A000293. It is a famous open problem in combinatorics to find a generating function for this sequence.

EDIT for the curious, the paper has been posted: https://arxiv.org/abs/1701.05277

• +1 for writing an expository paper on Specht modules. Where can I +1 the question? :) – darij grinberg Oct 15 '16 at 23:19
• (I think your $\vdash$ is the wrong way round...) – darij grinberg Oct 15 '16 at 23:20
• @darijgrinberg Thanks! (I can't ever remember which way) – John Wiltshire-Gordon Oct 16 '16 at 1:19
• maybe this arxiv.org/pdf/1203.4419.pdf could be of use? – Wouter M. Oct 16 '16 at 10:13
• @WouterM. Yes, thank you for the reference! I have learned a lot from reading it, and it does indeed give a nice perspective. – John Wiltshire-Gordon Oct 16 '16 at 17:07

This conjecture is false. It has to be, because it is asymtotically wrong: The number of plane partitions of size $n$ grows like $\exp(n^{2/3- \epsilon})$ and the number of triples of partitions of $n$ (with no condition on them) grows like only $\exp(n^{1/2+\epsilon})$. (citation)

As I'll explain below, there is a relationship between the two sides. Using that relationship, I can predict that the result will fail for $n=13$, $k=3$. I don't know if this is the first failure.

Details: Let's consider the condition that $\langle h_{\lambda_1} \ast \cdots \ast h_{\lambda_k}, e_n \rangle = 1$. As is well known, $h_{\lambda_1} \ast \cdots \ast h_{\lambda_k}$ expands positively in the $h$'s, and the coefficient of $h_{\mu}$ is the number of $k$-dimensional tables of nonnegative integers where summing up the $k-1$ dimensional slices gives the partitions $\lambda_1$, ..., $\lambda_k$ and just listing all the entries in sorted order gives $\mu$. (We pad partitions with infinitely many zeroes at the end.) Also, $\langle h_{\mu}, e_{n} \rangle$ is $0$ unless $\mu = 1^n$, in which case it is $1$. So you are counting $k$-tuples of partitions $(\lambda_1, \ldots, \lambda_k)$ such that there is a unique way to fill a $k$-dimensional table with $0$'s and $1$'s so that the $(k-1)$-dimensional slices total $(\lambda_1, \ldots, \lambda_k)$.

Let $T$ be a $k \times k$ array of $0$'s and $1$'s, and let $\sigma(T) = (\sigma_1(T), \ldots, \sigma_k(T))$ be its sums along slices. I'll call $T$ "ordered" if each of the $\sigma_j(T)$ is a partition. I'll call $T$ an "ideal" if the set of $1$'s of $T$ is an order ideal. And I'll call $T$ "singleton" if no other $T'$ has $\sigma(T) = \sigma(T')$. It is clear that, if $T$ is an ideal, then $T$ is ordered.

Your conjecture is that the number of $(k,n)$ ideals is equal to the number of $(k,n)$ ordered singletons. Here are the true statements:

Claim 1 Every ordered singleton is an ideal.

Proof Suppose that $T$ is ordered, but not an ideal. Then there must be some $(i_1, \ldots, i_k)$ and some index $j$ for which $T(i_1, \ldots, i_k)=1$ but $T(i_1, \ldots, i_j-1, \ldots, i_k)=0$. Since $\sigma_j(T)_{i_j} \leq \sigma_j(T)_{i_j-1}$, there must be some other $(i'_1, \ldots, i'_k)$ with $i_j=i'_j$, $T(i'_1, \ldots, i'_k)=0$ but $T(i'_1, \ldots, i'_j-1, \ldots, i'_k)=1$. But then define $T'$ by switching the values of $T$ in these $4$ places, and $\sigma(T) = \sigma(T')$, a contradiction. $\square$

Claim 2 There are ideals of type $(3,13)$ which are not singleton.

Proof Let $I$ be the order ideal which contains the $10$ triples $(i_1, i_2, i_3)$ with $i_1+i_2+i_3 \leq 2$ and also $\{ (2,1,0), (1,0,2), (0,2,1) \}$. Let $I'$ be the same with $\{ (0,1,2), (1,2,0), (2,0,1) \}$. Let $T$ and $T'$ be the corresponding indicator functions. Then $\sigma(T) = \sigma(T') = (7,4,2)^3$. $\square$