Box removing operators on partitions

Question

Consider the box removing operators $d_i$ for $i\geq 1$ defined as follows.

Let $\lambda$ be a partitions. Then $d_i(\lambda)$ is the partition obtained by removing a box from a part of length $i$ in $\lambda$ so as to obtain another partition. (Here removing a box is an operation performed on the Ferrers diagram of $\lambda$.) If there is no part of length $i$ in $\lambda$, then $d_i(\lambda)=0$. (As pointed out by Darij in the comments below, $0$ is not to be confused with the empty partition $\varnothing$.)

It is easy to see that the following equalities are satisfied. $$ d_id_j=d_jd_i \text{ if } \lvert i-j \rvert\geq 2$$ $$d_id_{i+1}d_i=d_id_id_{i+1}$$ $$d_id_{i+1}d_{i+1}=d_{i+1}d_id_{i+1}$$

Now consider words in the $d_i$. Two words $w_1$ and $w_2$ are called equivalent if $w_1(\lambda)=w_2(\lambda)$ for all partitions $\lambda$.

Is it true that if $w_1, w_2$ are equivalent then one can be obtained from the other by using the 3 relations mentioned above?

Answer 1

These are the Coxeter relations, and I believe equivalence comes from a general theorem: Tit's Theorem. For example, if you are willing to accept the Edelemann-Greene correspondence between Young Tableau and reduced words of permutations, then it would be equivalent to show that one can move freely between two reduced words using the above relations (now correspondingly, $d_i$ act on permutations via adjacent transpositions: $d_i(i,i+1)=(i+1,i)$. You can find a proof of reduced word equivalence here, page 4, Theorem 1.1.2. Essentially, the proof for tableaux should be of the same flavor: show that you can pass from any word to a carefully chosen canonical word.

Answer 2

Here is an ad-hoc proof in the special case where only the operators $d_1$ and $d_2$ appear. (My apologies for the multiple edits and a bad mistake in the definition of the normal form in the first version.)

I found it easier to work with conjugate partitions. If $\lambda$ is a partition with conjugate partition $\lambda'$ then $\lambda_i' > {\lambda'}_{i+1}$ if and only if $\lambda$ has a part of size $i$. So when $d_i$ is applied to $\lambda$ it reduces (when possible) $\lambda_i'$ by $1$. Hence if we define $e_i$ to be the operator which removes a box from the $i$th part of a partition, then $e_i$ is $d_i$ conjugated by tranposition, and the $e_i$ obey the relations in the question.

Write $1$ for $e_1$ and $2$ for $e_2$ and let $w$, $w'$ be words of length $n$ in the symbols $1$ and $2$. Say that $w$ is related to $w'$ if there is a sequence of applications of the identities $121 = 112$ and $122 = 212$ which transforms $w$ to $w'$. For $j \in \lbrace 1,\ldots,n\rbrace$ define

$$c_j(w) = \bigl| \lbrace i : j \le i \le n, w_i = 1 \rbrace \bigr| - \bigl| \lbrace i : j \le i \le n, w_i = 2 \rbrace \bigr| $$

and let $\ell(w)$ be the maximum value of $c_j(w)$ for $j \in \lbrace 1,\ldots,n,n+1\rbrace$, where we take $c_{n+1}(w) = 0$. (Operators compose from right to left, so we must read $w$ from right to left.)

Consider what happens when we apply $w$ to the two row partition $(n+m,n)$. At some point we will have removed $\ell(w)$ more boxes from row $1$ than from row $2$. Moreover, this is the maximum difference in boxes removed. So we get $0$ if and only if $m < \ell(w)$. This shows that if $w$ and $w'$ are equivalent then $\ell(w) = \ell(w')$.

It is obvious that related words are equivalent. So to complete a circle of implications it suffices to prove that if $\ell(w) = \ell(w')$ then $w$ and $w'$ are related. For this, it is sufficient to prove that $w$ is related to a word in the normal form

$$u 1\ldots 1 $$

where the final block of $1$ has length $\ell(w)$, and $u$ is of the form $1\ldots 12\ldots 2$ with at least as many $2$s as $1$s.

We work by induction on $\ell(w)$. First suppose that $\ell(w) = 0$. If $w = 1\ldots 12\ldots 2$ we are done. Otherwise let $w = u 212 v$, where $v$ is a (possibly empty) word consisting only of $2$s. Replace $212$ with $122$ to get the related word $u 122 v$, in which the number of final $2$s has increased by one. After finitely many steps we reach the normal form.

Now suppose that $\ell(w) > 0$. Let $j$ be maximal such that $c_j(w) = 1$. So we have $$w = z 1 v$$ where $v$ has length $n-j$ and $\ell(v) = 0$. Suppose that $j=n$, so $v$ is empty. Since $\ell(z) = \ell(w) - 1$, by induction, $z$ is related to a word in normal form $$u 1\ldots 1 $$ where the final block has length $\ell(w)-1$. Applying the corresponding sequence of identities to positions $1$, $\ldots$, $n-1$ of $w$ puts $w$ in normal form.

Finally suppose that $j < n$. Then since $\ell(v) = 0$, by the inductive assumption, $v$ is related to $1212 \ldots 12$. Hence $1v$ is related to $11212 \ldots 12$. Repeatedly replacing $112$ with $121$, working from left to right in $1v$, we see that $1v$ is related to $1212 \ldots 121$. So $w$ is related to a word ending with $1$; this reduces to the case $j = n$ already solved.