Counting solutions to equations involving partitions

99 Views Asked by At

This is a problem that has come up in my research and seems to be true from numerical tests via Mathematica. It should be provable in general, but I have been unable to show it so far. It would be greatly appreciated if someone could help with a proof or a method in order to solve such problems.

Given integer partitions $\rho$ and $\mu$ and a non-zero natural number $H$ such that $\ell(\mu)\leqslant H$ and $\ell(\rho)<H$, I am interested in two statistics:

  1. For how many $x \in \{1,\dots,\ell(\mu)\}$ is it the case that $\rho^\vee (\mu(x))=x$?

  2. For how many $x \in \{1,\dots,H\}$ is it the case that $\mu^\vee(\rho(x)+1)=x-1$?

My claim is that when $\ell(\mu)=H$ the first statistic is equal to the second statistic, while when $\ell(\mu)<H$ the second statistic is one greater than the first.

To be clear on notation

$\mu(n)$ is the $n^{\text{th}}$ part of $\mu$ and is defined to be zero if $n\neq 1,\dots,\ell(\mu)$.

$\mu^\vee$ is the dual of the partition $\mu$ defined by $\mu^\vee(x):=|\{y|\mu(y)\geqslant x\}|$.

$\ell(\mu)$ is the length of $\mu$ and obeys $\ell(\mu)=\mu^\vee(1)$.

1

There are 1 best solutions below

5
On BEST ANSWER

$\rho^\vee (a)=x$ means $|\{y\mid\rho(y)\geqslant a\}| = x$, which given that the parts are in descending order means that $\rho(x+1) < a \leqslant \rho(x)$.

So statistic 1 is $\chi_{\rho, \mu} =|\{ x \mid \rho(x+1) < \mu(x) \leqslant \rho(x) \}|$ and statistic 2 is $\psi_{\rho, \mu} = |\{ x \mid \mu(x) < \rho(x)+1 \leqslant \mu(x-1) \}|$, which since we're dealing with integers is equivalent to $\psi_{\rho, \mu} = |\{ x \mid \mu(x) \leqslant \rho(x) < \mu(x-1) \}|$

In fact, since we're dealing with integers we can carefully add some small offsets and write $$ \chi_{\rho, \mu} =\left|\left\{ x \mid \rho(x+1) + \tfrac12 < \mu(x) < \rho(x) + \tfrac12 \right\}\right| \\ \psi_{\rho, \mu} = \left|\left\{ x \mid \mu(x) < \rho(x) + \tfrac12 < \mu(x-1) \right\}\right| $$

Merge the parts $\mu(i)$ and the offset parts $\rho(j)+\tfrac12$ into a single list $\nu(k)$ in descending order, and define an asymmetry statistic $\sigma(k)$ such that $\sigma(-1) = 0$, $\sigma(k) = \sigma(k-1) - 1$ when $\nu(k)$ comes from $\mu$, and $\sigma(k) = \sigma(k-1) + 1$ when $\nu(k)$ comes from $\rho$. Then $\chi_{\rho, \mu}$ is the number of $k$ for which $\nu(k)$ comes from $\mu$ and $\sigma(k) = 0$ (i.e the number of steps from $1$ to $0$); and $\psi_{\rho, \mu}$ is the number of $k$ for which $\nu(k)$ comes from $\rho$ and $\sigma(k) = 1$ (i.e. the number of steps from $0$ to $1$).

Now it all becomes clear: since we start at $0$ and always step up or down by $1$, the number of steps from $1$ to $0$ in the first $k$ steps is either equal to the number of steps from $0$ to $1$ or one less, and the latter is only possible when we've taken more parts from $\rho$ than from $\mu$. When $\ell(\mu) = H > \ell(\rho)$, we end up with a negative $\sigma$ and so the two statistics must be equal.

It's slightly more interesting when $\ell(\mu) < H$. Why must we end up with positive $\sigma$, even if $\ell(\mu) = \ell(\rho)$? Essentially: by making $x$ run up to $H$ we effectively pad both partitions, but because of the offset of $\tfrac12$ we're padding $\rho$ with positive values and $\mu$ with zeroes.

I don't claim that this is a rigorous proof, but I think it explains the core intuition sufficiently to be convincing.