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?

  • $\begingroup$ I assume you work with "maybe partitions" (i. e., elements of the set $\left\{\text{partitions}\right\}\cup\left\{0\right\}$), and $0$ is not the empty partition $\emptyset$ ? $\endgroup$ Feb 20, 2013 at 4:13
  • $\begingroup$ Sorry, I should have mentioned that. I will edit the question. Thanks $\endgroup$ Feb 20, 2013 at 4:17
  • $\begingroup$ The way the question is written, it seems that for every word $w$ there are some partitions that become $0$, and thus no two words would be equivalent. Can you clarify further what happens with $d_i$ when there is no part of length $i$? $\endgroup$ Feb 20, 2013 at 5:38
  • $\begingroup$ If you check the relations that I gave, then they already list some words that are equivalent. For example, $d_1d_3$ and $d_3d_1$ are equivalent words because either both act on a partition to give $0$ or the same partition. Hope this clarifies. $\endgroup$ Feb 20, 2013 at 5:45

2 Answers 2


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.

  • 1
    $\begingroup$ Thanks for the answer and the link to Garsia's paper. But I do believe there is a lot more going on here than the case you mention, and I disagree that these are the Coxeter-Knuth relations. I checked a paper of Fomin's that defines the adjoint of the operators that I am considering, calling them Schur operators (or box adding operators if you will). He further goes on to say that the complete list of relations between the Schur operators is not known. $\endgroup$ Feb 20, 2013 at 23:07
  • $\begingroup$ Here is the reference of Fomin-Greene that I am talking about (example 2.6 specifically) math.lsa.umich.edu/~fomin/Papers/ncschur.ps $\endgroup$ Feb 20, 2013 at 23:08

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.

  • $\begingroup$ Thank you for the answer. Let me see if I can push the idea here in the general case. $\endgroup$ Feb 21, 2013 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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