Polynomials and Representations XVI

Here is the main problem we are trying to solve today.

Word Problem

Given a word $w = (w_1, w_2, \ldots, w_m),$ let us consider $k$ disjoint subwords of $w$ which are weakly increasing. For example if $w = (1, 1, 5, 4, 2, 5, 4, 6, 7)$ , then we can pick two or three disjoint subwords as follows:

subwords_examples

For each $k\ge 1$ , we wish to compute $L(w, k)$ , the maximum length sums of disjoint weakly increasing subwords. In our example, $L(w, 3) = 9.$ However, $L(w, 2) \ge 8$ since we can add the second ‘5’ to the circles, thus using up 8 numbers in the word. It turns out we do have $L(w,2) = 8$ although this is not obvious at the moment.

There is at least one case where computing $L(w, k)$ is trivial.

Proposition 1. If $w = w(T)$ for some SSYT $T$ of shape $\lambda$ , then for each $k$ we have:

$L(w, k) = \lambda_1 + \lambda_2 + \ldots + \lambda_k.$

Proof

Indeed if $T$ has rows $w_1, w_2, \ldots, w_l$ , then $w(T) = w_l * w_{l-1} * \ldots * w_1$ and the words $w_1, \ldots, w_k$ are disjoint weakly increasing words of the required length sum. Hence $L(w, k) \ge \lambda_1 + \ldots + \lambda_k.$

Conversely, if $w_1', \ldots, w_k'$ are disjoint weakly increasing subwords of $w(T)$ , the numbers in each $w_i'$ are from different columns of $T$ . So in each column of $T,$ at most $k$ entries are used among the $w_i'$ and the length sum of $w_1', \ldots, w_k'$ is at most $\lambda_1 + \ldots + \lambda_k.$ ♦

blue-lin

General Solution

The good news is, every case can be reduced to the SSYT case. Indeed, given any word $w,$ we can write $w = w(T)$ for some skew SSYT $T.$ Now we perform sliding operations to turn $T$ into an SSYT $T'.$ By the next result, $L(w, k) = L(w(T), k) = L(w(T'), k)$ for all k, so we can revert to the above special case.

Proposition 2. If $w, w'$ are Knuth-equivalent words, then $L(w, k) = L(w', k).$

Proof

We may assume $w'$ is obtained from $w$ by rule R1 or R2. Let us consider each case.

R1: in $w$ we have a consecutive triplet $(a, b, c)$ with $c < a \le b$ ; we swap $b$ and $c$ to get $w'.$ In most instances, disjoint weakly increasing subwords of $w$ will remain so in $w'$ and vice versa. The only problem is when a subword of $w'$ contains $c,b$ , say $w_1 = \ldots, c, b,\ldots.$ If no subword contains $a,$ we can replace $c,b$ with $a,b$ and the resulting word is still weakly increasing. If not, we swap the heads:

$\displaystyle\left.\begin{aligned}w_1 = \text{(seq 1)}, &c, b, \ldots\\ w_2 = \text{(seq 2)}, &a, \ldots \end{aligned}\right\} \text{subwords of } w' \implies\left.\begin{aligned}w_1 = \text{(seq 2)}, &a, b, \ldots\\w_2 = \text{(seq 1)}, &c, \ldots \end{aligned}\right\} \text{subwords of } w$

which are still weakly increasing.

R2: similarly, in $w$ we have a consecutive triplet $(a, b, c)$ with $a\le c <b$ ; swap $a$ and $b$ to get $w'.$ The critical case is now as follows:

$\displaystyle\left.\begin{aligned} w_1 = \ldots, a, b, &\text{(seq 1)}\\w_2 = \ldots, c, &\text{(seq 2)} \end{aligned}\right\} \text{subwords of } w \implies \left. \begin{aligned} w_1 = \ldots, a, c, &\text{(seq 2)}\\w_2 = \ldots, b, &\text{(seq 1)}\end{aligned}\right\} \text{subwords of } w'$

This completes the proof. ♦

Summary

Thus we have:

Algorithm. To compute $L(w, k)$ , write $w = w(T)$ for a skew SSYT $T$ , perform the sliding algorithm to turn $T$ into an SSYT $T'$ of shape $\lambda.$ Now we have:

$L(w, k) = \lambda_1 + \lambda_2 + \ldots + \lambda_k$ for all $k\ge 1.$

E.g. in our initial example of (1, 1, 5, 4, 2, 5, 4, 6, 7), first write it as a word of some skew SSYT, then perform sliding to turn it into an SSYT.

word_problem_solution

It follows that $L(w, 1) = 6$ , $L(w, 2) = 8$ and $L(w, 3) = 9$ .

Question to Ponder

Besides computing $L(w, k)$ , what is an efficient way to compute explicit disjoint subwords with the desired length sum?

blue-lin

Uniqueness of SSYT for Word

We need the following lemma for our theorem later.

Lemma. If $w \equiv w'$ and $w_0$ (resp. $w_0'$ ) is obtained from $w$ (resp. $w'$ ) by removing the largest element, then $w_0 \equiv w_0'.$ The same holds for the smallest element.

Here, if the maximal element $k$ of $w$ occurs more than once, the rightmost occurrence is taken to be the largest. Similarly, the leftmost occurrence of the minimal element is the smallest.

Proof

We may assume $w'$ is obtained from $w$ by R1 or R2, i.e. by replacing a consecutive triplet:

$\displaystyle (a, b, c) \mapsto \begin{cases}(a, c, b), \quad &\text{ if } c < a \le b, \\(b, a, c), \quad &\text{ if } a \le c < b. \end{cases}$

If none of $a,b,c$ is maximal, we are done. Otherwise, in both cases, $b$ is maximal; after removing it, we get $(a,c)$ in $w_0$ and $w_0'.$

In the case the smallest element is removed, in the first case we remove $c$ and obtain $(a,b)$ in both $w_0$ and $w_0'.$ In the second case, we remove $a$ and obtain $(b,c)$ in both $w_0$ and $w_0'.$ ♦

Now we have enough tools to prove the following result we claimed earlier.

Theorem. For any word $w,$ there is a unique SSYT $T$ such that $w \equiv w(T).$

We call this $T$ the rectification of the word $w.$ For a skew SSYT $T',$ the rectification of $w(T')$ is also called the rectification of $T'.$

Proof

Existence of $T$ was proven earlier; we now prove uniqueness, i.e. for any SSYT $T, T',$

$w(T) \equiv w(T') \implies T = T'.$

By proposition 2, the shape $\lambda$ of $T$ satisfies

$\lambda_1 +\lambda_2 + \ldots + \lambda_k = L(w(T),k) = L(w(T'), k)$

so $T$ and $T'$ have the same shape. Now we proceed by induction on $|\lambda|$ ; when $|\lambda| \le 1$ we clearly have $T = T'.$

Suppose $|\lambda| \ge 2$ and $m$ is the largest element in $w(T)$ and $w(T');$ if this occurs more than once, we take the rightmost occurrence. Note that $m$ must lie in a corner square of $T$ and $T'.$ Removing it thus gives us SSYT $T_0$ and $T_0'.$ By the above lemma, we have

$w(T) \equiv w(T') \implies w(T_0) \equiv w(T_0').$

Since $T_0$ has one less square than $T$ , by induction hypothesis $T_0 = T_0'.$ And since $T$ and $T'$ have the same shape, we have $T = T'.$ ♦

blue-lin

Summary

There is a bijection:

summary_equivalence_words_and_ssyt

The bijection is preserved when we drop the maximum or minimum element in either case. Clearly concatenation preserves Knuth-equivalence:

$w_1 \equiv w_1',\ w_2 \equiv w_2' \implies w_1 * w_2 \equiv w_1' * w_2'$

since any sequence of R1’s and R2’s performed on $w_1 \mapsto w_1'$ can be done on $w_1 * w_2 \mapsto w_1' * w_2.$ Thus this gives an associative product operation on the set of SSYT: given $T, T',$ let $T*T'$ be the rectification of $w(T) * w(T').$ This motivates the product operation we defined earlier.