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.

This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s