2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Partitions of what? $\endgroup$ – Paul Sinclair Apr 9 '18 at 23:47
  • $\begingroup$ The two partitions are completely arbitrary except for the condition on their lengths. They need not even be partitions of the same number. $\endgroup$ – Alec B-G Apr 10 '18 at 7:18
  • $\begingroup$ The claim needs to hold for all partitions. A single counterexample would be an answer. I am counting the number of possible solutions to $\rho^\vee(\mu(x))=x$ for $x$ in the domain $\{1,\dots,\ell(\mu)\}$, but I am not saying that the equation holds for every $x$. It may only hold for $x=2$ for example. However if this is the case then given $\ell(\mu)=H$ there is only one solution to equation 2. $\endgroup$ – Alec B-G Apr 10 '18 at 10:09
  • $\begingroup$ For example if $\mu=(2,1)$ and $\rho=(2,1)$ and $H>2$ then we have solutions to 1 $\rho^\vee(\mu(1))=1$ and $\rho^\vee(\mu(2))=2$. Solutions to 2 are $\mu^\vee(\rho(1)+1)=0$, $\mu^\vee(\rho(2)+1)=1$ and $\mu^\vee(\rho(3)+1)=2$. $\endgroup$ – Alec B-G Apr 10 '18 at 10:13
1
$\begingroup$

$\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.

$\endgroup$
  • $\begingroup$ Thank you for your answer, I'm reading through it now. I'm struggling to understand your definition of $\sigma$. When you say $\sigma(k)=\sigma(k)-1$, do you mean $\sigma(k)=\sigma(k-1)$? Also when you say asymmetry statistic does that mean $\sigma$ is valued in $\mathbb Z_2$? $\endgroup$ – Alec B-G Apr 11 '18 at 10:00
  • $\begingroup$ @AlecB-G, no (although I did have a typo, now corrected) and no. $\sigma$ counts how many more parts from $\rho$ we've seen vs $\mu$, so it goes up or down one with each part processed. $\endgroup$ – Peter Taylor Apr 11 '18 at 10:11
  • $\begingroup$ Do you mean $\sigma(0)=0$ for the definition of $\sigma$ or are you counting your list of $\nu$ from 0? $\endgroup$ – Alec B-G Apr 11 '18 at 11:17
  • $\begingroup$ Assuming $\sigma(0)=0$ I now understand your proof. It's very nice, thank you for the help. $\endgroup$ – Alec B-G Apr 11 '18 at 11:28
  • $\begingroup$ @AlecB-G, I was counting from 0. It's a fair point that in the context of partitions it's preferable to count from 1. $\endgroup$ – Peter Taylor Apr 11 '18 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.