DOUBLE CRYSTAL GRAPHS

Alain Lascoux CNRS, Institut Gaspard Monge, Université de Marne-la-Vallée 77454 Marne-la-Vallée Cedex, France Alain.Lascoux@univ-mlv.fr

Abstract

We show how to expand a non-symmetric Cauchy kernel ∏_{i+j≤n}(1 − x_{i}y_{j})^{−1} in the basis of Demazure characters for type A_{n}. The construction involves using the left and right structure of crystal graphs on words, and mostly reduces to properties of the jeu de taquin. We give, without proof, the expansion of a similar kernel in the

nilplactic algebra, and define characters in two sets of variables.

1 Kernels

The best characterization of Schur functions, as symmetric functions, relies on the diagonalization of the Cauchy kernel ∏_{i} ∏_{j}(1 − x_{i}y_{j})^{−1}.

Indeed, this kernel expands as a sum over all partitions λ :

∏_{i} ∏_{j}(1 − x_{i}y_{j})^{−1} = ∑_{λ} S_{λ}(X) S_{λ}(Y) ,  (1)

defining the Schur functions S_{λ} uniquely (choosing them to be positive).

One could as well have started from the resultant ∏_{i} ∏_{j}(x_{i} − y_{j}) of the two polynomials in z, ∏_{i}(z − x_{i}) and ∏_{j}(z − y_{j}).

Relaxing symmetry, one still wants to “separate variables” in ∏_{i+j≤n}(x_{i} − y_{j}) and ∏_{i+j≤n}(1 − x_{i}y_{j})^{−1}, or more generally, in products corresponding to the diagram of a partition.

The first function ∏_{i+j≤n}(x_{i} − y_{j}) expands as a sum of products of Schubert polynomials in X and Y separately [19]. For the second one, given a partition λ, let

F_{λ} := ∏_{(i,j)∈λ}(1 − x_{i}y_{j})^{−1} ,

product over all the boxes of the diagram of λ, noting (i, j) the coordinates of a box. We shall see that the cases λ = ρ := [n, …, 1], n ∈ ℕ, allows to recover all the F_{λ}, and therefore we shall mostly comment the case

F_{ρ} = ∏_{i+j≤n+1}(1 − x_{i}y_{j})^{−1} ,

the explicit expansion given in Theorem 6 being our main new result. A representation explanation of the decomposition of F_{ρ}, as we have for ∏_{i} ∏_{j}(1 − x_{i}y_{j})^{−1}, seems highly desirable.

One way to understand the Cauchy kernel is to have recourse to Schur functors instead of Schur functions, and to use representations of linear groups as Schur did in his thesis [36].

One can equivalently consider spaces of sections of ample line bundles over the flag manifold F(ℂ^{n}). The non-symmetric case involves using sections over Schubert varieties, and this leads to Demazure characters [3]. However, the geometrical study of line bundles over Schubert varieties is more complicated than the study of characters only. Instead of representations, we shall rather use spaces of words (which can be thought as “canonical bases”).

In that framework, Cauchy formula (1) is interpreted as a bijection, due mostly to Schensted, between the terms in the expansion of the left side of (1) (words in commutative biletters (x_{i}, y_{j})), and pairs of tableaux of the same shape.

Thanks to this bijection, generating functions of monomials in commutative biletters are transformed into expressions in the free algebra, or transformed into multisets of pairs of tableaux. In particular, since F_{ρ} expands into a subfamily of monomials of the expansion of ∏_{i} ∏_{j}(1 − x_{i}y_{j})^{−1}, we already know that F_{ρ} can be interpreted as a family of pairs of tableaux.

To characterize this family, we need some combinatorial tools associated to the natural two-sided structure of crystal graph on words. In fact, we do not need to prove new properties of crystal graphs to explicit F_{ρ}, but have mostly to gather in Theorem 4 results stated in different languages. We shall use words and tableaux as the simplest concepts in the type A_{n} case.

We mention, in the last two sections, the possibility of defining “Demazure characters” in two sets of variables, or inside the nilplactic algebra.

The three figures at the end provide three different realizations of the basis of a Demazure module.

2 Combinatorial Tools

Let X = {x_{1}, x_{2}, …} be a totally ordered alphabet (of non commuting letters).

A row is a weakly increasing word, a column is a strictly decreasing one. A pair of rows a_{1} ⋯ a_{ℓ}, b_{1} ⋯ b_{k} , a_{i}, b_{j} ∈ X, is a

• 2-rows tableau iff ℓ ≤ k & a_{i} > b_{i}, i = 1, …, ℓ

• 2-rows contretableau iff ℓ ≥ k & a_{i+ℓ−k} > b_{i}, i = 1, …, k

A sequence of rows is a tableau (resp. a contretableau) if every pair of consecutive rows is so. Both can be planarly represented, stacking rows on top of each other, and left justifying in the case of tableaux, right justifying them in the case of contretableaux. We shall identify planar objects with their row reading, and with the sequence of rows composing them.

The plactic relations (due to Knuth[11]) are the congruences

cab ≡ acb (a ≤ b < c) ,  (2)
bac ≡ bca (a < b ≤ c) .  (3)

that can be planarly written

c ; a b ≡ a c ; b  (a ≤ b < c)  (4)
b ; a c ≡ b c ; a  (a < b ≤ c)  (5)

The set of words congruent modulo the plactic relations to a given word w is called the plactic class of w.

The following theorem is an algebraic reinterpretation [37] [22] of a construction due to Schensted [35].

Theorem 1 In the plactic class Pℓ(w) of a word w, there exists a tableau and only one tableau, denoted P (w).

A right string is the ordered string of the two-rows words in the plactic class of a 2-rows tableau (with the tableau as its origin, and the contretableau as its end, the words being ordered according to the length of their top row; edges are denoted f) :

_{1 2 4 5 7}^{3 6} ⟶^{f} _{2 4 5 7}^{1 3 6} ⟶^{f} _{2 5 7}^{1 3 4 6} ⟶^{f} _{2 5}^{1 3 4 6 7}  (6)

Left strings are described in terms of words on an alphabet of two letters, and it is convenient to take the two parentheses ( , ) as letters. Given a word w in such an alphabet, pair successive parentheses iteratively. Call the subword of paired parentheses its paired subword (caution: one needs to record positions). The original word w is the shuffle of it and of a subword of the type ) ⋯) (⋯ ( (i.e. closing parentheses come first).

A left string is a maximal sequence of words of the same degree which coincide on their paired subwords. Here is a left string, indicating below each word the positions of letters, and underlining the paired subword :

)_{7} (_{\underline{6}} )_{\underline{5}} )_{4} (_{\underline{3}} )_{\underline{2}} )_{1} ⟶^{f} )_{7} (_{\underline{6}} )_{\underline{5}} )_{4} (_{\underline{3}} )_{\underline{2}} (_{1} ⟶^{f} )_{7} (_{\underline{6}} )_{\underline{5}} (_{4} (_{\underline{3}} )_{\underline{2}} (_{1} ⟶^{f} (_{7} (_{\underline{6}} )_{\underline{5}} (_{4} (_{\underline{3}} )_{\underline{2}} (_{1} .  (7)

One exchanges the two notions of strings by just reading the positions of the (’s as the entries of the top rows of the elements of (6), and the )’s as the entries of the bottom rows, as can be seen on the preceding two strings. We shall later give a better interpretation in terms of Schensted bijection.

Given two totally ordered alphabets X = {x_{1}, x_{2}, …}, Y = {y_{1}, y_{2}, …}, a monomial w in the commutative variables \binom{y}{x}, x ∈ X, y ∈ Y, is called a biword.

Ordering lexicographically w, with priority to Y, one writes

w = \binom{y_{1}}{a_{1}} ⋯ \binom{y_{1}}{b_{1}}\binom{y_{2}}{a_{2}} ⋯ \binom{y_{2}}{b_{2}}\binom{y_{3}}{a_{3}} ⋯ \binom{y_{3}}{b_{3}} ⋯  (8)

where a_{1} ⋯ b_{1}, a_{2} ⋯ b_{2}, … are rows in the monoid X^{∗}, and a_{i}, b_{j} belong to X.

One can erase the y_{j}’s and interpret w as a sequence of rows :

w ↦ w^{x} := [a_{1} ⋯ b_{1}, a_{2} ⋯ b_{2}, a_{3} ⋯ b_{3}, …]  (9)

We shall write a_{1} ⋯ b_{1} = row_{1}(w), a_{2} ⋯ b_{2} = row_{2}(w), …

Ordering lexicographically w with priority to X, one obtains similarly a sequence w^{y} of rows in Y^{∗}.

Schensted’s bijection, as reinterpreted by Knuth [11], is described by the following theorem.

Theorem 2 The map w ↦ (P (w) := P (w^{x}) , Q(w) := P (w^{y})) is a bijection between biwords and pairs of tableaux of the same shape.

The algebraic interpretation of Theorem 2 is the following combinatorial version of Cauchy formula [1] :

∏_{x∈X} ∏_{y∈Y}(1 − \binom{y}{x})^{−1} = ∑ (t, t′) ,  (10)

sum over all pairs of tableaux t ∈ X^{∗}, t′ ∈ Y^{∗} of the same shape (we have written an equality instead of a bijection; the left hand side is a commutative function, and the right hand side a set of pairs of words in non commutative letters).

Strings can now be defined at the level of biwords. Given an integer i, a right i-string is a sequence of biwords w_{1}, …, w_{ℓ} such that

[row_{i}(w_{1}), row_{i+1}(w_{1})], [row_{i}(w_{2}), row_{i+1}(w_{2})], …, [row_{i}(w_{ℓ}), row_{i+1}(w_{ℓ})]

is a right string, and such that row_{j}(w_{1}) = ⋯ = row_{j}(w_{ℓ}), ∀j ≠ i, i+1.

Similarly, a left i-string is a sequence of biwords w_{1}, …, w_{ℓ} such that w_{1}, …, w_{ℓ} coincide under the specialization x_{i} = x_{i+1}, and such that w_{1}^{x}, …, w_{ℓ}^{x} becomes a string when one specializes x_{i+1} to ‘(‘, x_{i} to ‘)‘, erasing the other letters.

We could have used the symmetry in X and Y to exchange left and right strings.

Crystal bases B(λ) have been introduced by Kashiwara [9]. In the type A case, B(λ) can be identified with the set T ab(λ) of tableaux of shape λ [10]. The space B(λ) ⊗ B(λ)^{∨} admits a natural structure of double crystal graph. Since the set ∪_{λ}(T ab(λ) ⊗ T ab(λ)) is, according to Theorem 2, in bijection with a set of biwords, we can describe double crystal graphs in terms of biwords. A double crystal graph for 𝔖_{n} is a graph, with biwords as vertices, left and right colored oriented edges labeled f_{1}, …, f_{n−1} called crystal operators, such that if it contains a biword w, then it contains the full left and right i-strings, i = 1, …, n−1, passing through w.

Crystal operators can be thought as (left or right) linear operators on sums of biwords: if w ⟶^{f_{i}} w′, then one puts f_{i}(w) = w′, and one puts f_{i}(w) = 0 if w is the end of the i-string passing through it.

The symmetric group 𝔖_{n} acts by permuting the vertices of a double crystal graph [22] . The left (resp. right) action of a simple transposition s_{i} restricts, on a left (resp. right) i-string, to the symmetry with respect to the middle of the string [21, 27, 9]. We shall note w ↦ s_{i}(w) the left action.

Instead of taking symmetry with respect to middle of strings, one can define operators π_{i} and π̂_{i}, i = 1, …, n − 1, on the free algebra in X as follows [25, 8]:

• if v ∈ X^{∗} is the first part (or is the middle) of the left i-string containing it, then π_{i}(v) is the sum of all words between v and s_{i}(v), and π̂_{i}(v) is the same sum minus v.

• the action is extended to all words by requiring that π_{i}(v + s_{i}(v)) = v + s_{i}(v) and π̂_{i}(v + s_{i}(v)) = 0 (either v or s_{i}(v) is in the first part of the string, when not in the middle).

For example, using x_{1}, x_{2} instead of parentheses, and writing in small characters the paired letters, one gets from string (7) :

π_{1}(x_{1}x_{2}x_{1}x_{1}x_{2}x_{1}x_{1}) = x_{1}x_{2}x_{1}x_{1}x_{2}x_{1}x_{1}+x_{1}x_{2}x_{1}x_{1}x_{2}x_{1}x_{2}+x_{1}x_{2}x_{1}x_{2}x_{2}x_{1}x_{2}+x_{2}x_{2}x_{1}x_{2}x_{2}x_{1}x_{2},

π_{1}(x_{1}x_{2}x_{1}x_{1}x_{2}x_{1}x_{2}) = x_{1}x_{2}x_{1}x_{1}x_{2}x_{1}x_{2} + x_{1}x_{2}x_{1}x_{2}x_{2}x_{1}x_{2}

and, by symmetry for the two other words,

π_{1}(x_{1}x_{2}x_{1}x_{2}x_{2}x_{1}x_{2}) = 0 , π_{1}(x_{2}x_{2}x_{1}x_{2}x_{2}x_{1}x_{2}) = −x_{1}x_{2}x_{1}x_{1}x_{2}x_{1}x_{2}−x_{1}x_{2}x_{1}x_{2}x_{2}x_{1}x_{2} .

The operators π_{i} do not satisfy the braid relations. They induce (isobaric) divided differences on polynomials (in commutative indeterminates x_{i}), that we shall denote π_{i}^{x}:

f ⟶^{π_{i}^{x}} \frac{x_{i}f − x_{i+1}f^{s_{i}}}{x_{i} − x_{i+1}} with s_{i} = transposition of x_{i}, x_{i+1} .  (11)

The operators π_{i}^{x}, due to Demazure [3], satisfy braid relations, and therefore, for any permutation σ, there exists a well defined divided difference π_{σ}^{x} (which can be obtained by taking a product of π_{i}^{x} corresponding to a reduced decomposition of σ).

To relate biwords to permutations, I used with M.P. Schützenberger the following two notions which are in fact equivalent.

The first one consists in singling out some element V ice(w) in each plactic class Pℓ(w) of a word w ∈ X^{∗}, called vice-tableau.

V ice(w) can be recursively defined as follows. It is the unique word a_{1} ⋯ a_{ℓ} in a plactic class Pℓ(w) such that

• a_{ℓ} is the suffix (i.e. the rightmost letter) of the contretableau in Pℓ(w)

• The shape of P (a_{1} ⋯ a_{ℓ−1}) is maximum (with respect to the natural order on partitions) among the words in Pℓ(w) having suffix a_{ℓ}.

• a_{1} ⋯ a_{ℓ−1} is a vice-tableau.

Recall that the inverse operation of “inserting a letter” into a tableau t (Inverse-Schensted algorithm) consists in choosing a box at the periphery of t, and finding a pair (t′, x) such that t′ is a tableau of shape obtained by erasing this box from the shape of t′, and t′x ≡ t. Thus, the recursive definition of a vice-tableau implies the following algorithm, consisting of a distinguished sequence of Inverse-Schensted operations : at each step, the box which is erased is the highest which factors out on the right the suffix of the contretableau.

For example

1 3 3 4 5 1 2 4 1 2 ≡ \begin{aligned}1 & 3 & 3 & 4 & 5 \\ & & 1 & 2 & 4 \\ & & & ■ & 1 \end{aligned} · 2 ≡ \begin{aligned}1 & 3 & 3 & 4 & 5 \\ & & ■ & 2 & 4 \\ & & & 1 & 1 \end{aligned} · 2 ≡ \begin{aligned}■ & 1 & 3 & 3 & 5 \\ & & 1 & 2 & 4 \\ & & & 1 & 2 \end{aligned} · 4  (12)

shows that

V ice(13345 124 12) = V ice(13345 24 11) · 2

(iterating, one finds V ice(13345 124 12 = [35 12344 112]).

Factoring V ice(w) as a product of maximal rows, on can consider it as a biword v, with row_{1}(v) row_{2}(v) ⋯ = V ice(w). One can show that the sequence of lengths ℓ(row_{1}(v)), ℓ(row_{2}(v)), … is a permutation of the shape λ of the tableau P (w).

Sorting the rows of V ice(w) by decreasing order of length, and recording their suffixes, one gets a permutation σ(w) :

[35, 12344, 112, ∅, ∅] → [12344, 112, 35, ∅, ∅] → σ(w) = [4, 2, 5, 1, 3]

(in case some rows are of equal length, or when there are missing suffixes, i.e. empty rows, one takes the permutation of minimum length).

Using the right action of the symmetric group on a contretableau t with k rows, one generates k! words v = t^{ν} : ν ∈ 𝔖_{k}. One can show by induction on the degree the following extremality property of the vice-tableau.

Lemma 3 Given a contretableau t, then there exists a permutation ν such that V ice(t) is equal to some t^{ν}. One can take for ν the permutation of maximal length among those such that the sequences of suffixes of row_{1}(t^{ν}), row_{2}(t^{ν}), … is the same as for t.

For example the action of 𝔖_{3} on the contretableau [13345 124 12], writing s and s′ for the two generators of 𝔖_{3}, produces 6 words (s′ acts by jeu de taquin on the two top rows, s on the bottom two) :

1 3 3 4 5 1 2 4 1 2 →^{s} 1 3 3 4 5 2 4 1 1 2 →^{s′} 3 5 1 2 3 4 4 1 1 2 →^{s} 3 5 2 3 4 1 1 1 2 4 →^{s′} 3 3 5 2 4 1 1 1 2 4 →^{s} 3 3 5 1 1 2 4 4 1 2 (13)

and the vice-tableau is the third element 35 12344 122, having suffixes 5, 4, 2 and being given by a permutation of length 2.

Instead of using the action on rows of a tableau, one can similarly act on columns, still with the jeu de taquin. Given a tableau t with columns of respective lengths ℓ_{1}, …, ℓ_{k}, and a permutation σ ∈ 𝔖_{k}, there exists, in the plactic class of t, a unique word t^{col,σ} which is a product of columns of lengths ℓ_{σ_{1}}, …, ℓ_{σ_{k}}. The tableau of the same shape as t such that its columns appears as a right column of some t^{col,σ} is called the key of t [25, 5] . By construction, the set of columns of Cℓ(t) (columns interpreted as sets) is a flag of sets (with respect to inclusion). Writing the letters in the order they appear in the successive columns (ordering them increasingly when they appear several at a time, and adding a complete column [n, …, 1]), one obtains a permutation which is equal to σ(t), i.e. to the permutation determined by the vice-tableau. Continuing with the same example, reading the objects columnwise,

1 3 3 4 5 1 2 4 1 2 ≡ 1 3 3 5 2 4 4 1 1 2 ≡ 1 3 5 2 4 4 1 1 2 4 ⇒ Cℓ(t) = 5 5 4 4 4 2 2 2 4 4 .  (14)

The right columns are [4], [42], [542] and therefore σ(t) = [4 2 5 13].

3 Crystals

We restrict now our study to some distinguished subsets of tableaux and crystal graphs corresponding to Demazure modules. Given a dominant weight λ = [λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} ≥ 0], and a permutation σ ∈ 𝔖_{n}, there exists a crystal B(λ, σ), which is a collection of tableaux which can be described in many ways. It is in fact more convenient to index bases by weights, i.e. to write B(λ^{σ}) rather than B(λ, σ), to take into account the stabilizer of λ in 𝔖_{n}.

Define the top component of a crystal to be :

B̂(λ^{σ}) = B(λ^{σ}) \ ∪_{ν<σ:λ^{ν}≠λ^{σ}}B(λ^{ν}) .  (15)

Moreover, instead of using tableaux only, one can choose a tableau Q of shape λ, and call crystal B(λ^{σ}, Q) the collection of biwords

w : Q(w) = Q, P (w) ∈ B(λ^{σ}) .

Figure 1 gives B([2431], Q) for Q = 4 3 4 2 3 3 1 1 1 3 , the arrows being left crystal

operations (increasing some i into i + 1, i = 1, 2, 3); we have written w^{x} instead of w, separating the factors by a dot and replacing x_{i} by i.

There are several equivalent descriptions of a crystal, or of a basis of a Demazure module, using different combinatorial objects. The following theorem summarizes, in terms of tableaux, these different descriptions for what concerns the type A_{n}.

Statement 1) is given by Lakshmibai and Seshadri [13], Th.9.6, Lakshmibai [12], Th.4.1, by me and M.P. Schützenberger [25], Th.4.3.

Formula 16 is given by Littelmann [27], Th.5.2, Kashiwara [8], Prop.3.2.3, [12], Th.4.1. Using simultaneously the operators π_{i} and π̂_{i} to get the two formulas (16) and (17) is done in [25], Th.4.3.

The first part of statement 3) is Proposition 5.6 of [25]; using Lemma 3, one can refine it to get the second part describing Ŵ(μ).

Theorem 4 Let n be an integer, λ ∈ ℕ^{n} be a dominant weight, σ ∈ 𝔖_{n} be minimum in its class modulo the stabilizer of λ, and let μ = λ^{σ}.

Then the crystal B(μ) (resp. B̂(μ)) can be characterized by any of the following properties :

1) It is the set of all tableaux t of shape λ, with σ(t) ≤ σ (resp. σ(t) = σ), the order being the Ehresmann-Bruhat order on permutations.

2) Given any reduced decomposition s_{i} ⋯ s_{j} = σ, then

B(μ) = π_{i} ⋯ π_{j}(⋯ x_{2}^{λ_{2}}x_{1}^{λ_{1}}) ,  (16)
B̂(μ) = π̂_{i} ⋯ π̂_{j}(⋯ x_{2}^{λ_{2}}x_{1}^{λ_{1}}) .  (17)

3) Let W (μ) (resp. Ŵ(μ)) be the set of all biwords (resp. biwords such that row_{1}(w) row_{2}(w) ⋯ is a vice-tableau) such that ℓ(row_{1}(w)) = μ_{1}, ℓ(row_{2}(w)) = μ_{2}, … and such that ∀i, ∀x ∈ row_{i}(w), then x ≤ x_{n+i−1}.

Let moreover Q = P (⋯ y_{2}^{μ_{2}} y_{1}^{μ_{1}}). Then

W (μ) = B(μ, Q) and Ŵ(μ) = B̂(μ, Q)  (18)

The elements of a crystal are connected by left crystal operations. If a biword w belongs to a crystal B(μ, Q), and i is such that w is not the origin of the left i-string passing through it, then the full i-string is contained in B(μ, Q). Thus, for any i, B(μ, Q) is composed of full i-strings and of origins of i-strings [8].

Demazure characters K(μ, X) and K̂(μ, X) are the images of respectively B(μ, Q) and B̂(μ, Q) (considered as sums) in the ring of polynomials in commutative variables x_{1}, …, x_{n}. They depend only on μ and not on Q.

Crystals admit a dual description, using right crystal operations. We shall need only one characterization.

Given λ, σ, μ = λ^{σ}, and any tableau P of shape λ, call cocrystal CB(μ, P) the set of biwords w: P (w) = P, Q(w) ∈ B(μ).

Theorem 5 Let n be an integer, λ ∈ ℕ^{n} be a dominant weight, σ ∈ 𝔖_{n}, μ = λ^{σ}. Let P be a tableau in B̂(μ). Then CB(μ, P) is the set of biwords w

P (w) = P & ∀i, ∀x ∈ row_{i}(w) then x ≤ x_{n+1−i} .  (19)

Figure 1 and Figure 2 have the same underlying colored graph. In Figure 2, we are using w^{x} instead of a biword w, writing consecutive rows on top of each other (and using i for x_{i}). Crystal operations are the jeu de taquin on two consecutive rows. Vertices are all the 4-rows words in the plactic class

of 4 3 4 2 3 3 1 1 1 3 which satisfy the flag conditions

row_{1}(w) ∈ {1, 2, 3, 4}^{∗}, row_{2}(w) ∈ {1, 2, 3}^{∗}, row_{3}(w) ∈ {1, 2}^{∗}, row_{4}(w) ∈ {1}^{∗} .

One cannot add to Figure 2 any word by the jeu de taquin, without breaking the flag conditions. For example, the second lowering operator has the effect, on the two minimum elements to push a 3 on the third row :

3 4 4 1 3 3 3 2 1 1 ⟶^{f_{2}} 3 4 4 1 3 3 2 3 1 1 , 4 4 3 3 3 3 2 1 1 1 ⟶^{f_{2}} 4 4 3 3 3 2 3 1 1 1 .

4 Non symmetric Cauchy kernels

The function ∏_{i+j≤n+1}(1 − x_{i}y_{j})^{−1}, rewritten F_{ρ} = ∏_{i+j≤n+1}(1 − \binom{y_{j}}{x_{i}})^{−1}, is

the sum of all biwords in the commutative variables \binom{y_{j}}{x_{i}}, such that i + j ≤ n + 1.

However, from Theorems 4, 5, one knows that for a biword w, if P (w) = P, P of shape λ, σ(P) = σ, μ = λ^{σ}, then Q(w) ∈ CB(μ, P). Therefore, the conditions i + j ≤ n + 1 are equivalent to the following expansion of F_{ρ}, writing μ^{ω} = [μ_{n}, …, μ_{1}] when μ = [μ_{1}, …, μ_{n}].

Theorem 6 Let n be a positive integer. Then, under Schensted’s bijection, F_{ρ} can be written

∏_{i+j≤n+1}(1 − \binom{y_{j}}{x_{i}})^{−1} = ∑ (t, t′) ,

sum over all weights μ ∈ ℕ^{n}, all t ∈ B̂(μ, X), t′ ∈ B(μ^{ω}, Y). The commutative image of the preceding identity is

F_{ρ} = ∑_{μ∈ℕ^{n}} K̂(μ, X) K(μ^{ω}, Y) .

Let us see how expansions for staircases imply expansions for all partitions (the characterization of pairs of tableaux will be less explicit than in Theorem 6, because it probably depends on not yet known properties of the monoid generated by the π_{i}’s and π̂_{j}’s. However, the image of K(μ, Y) under some π_{i}^{y} is some K(μ′, Y), and the image of K̂(μ, X) under π̂_{i}^{x} = π_{i}^{x} − 1 is ±K̂(μ′, X); passing from Theorem 6 to Theorem 7 mostly reduces to reordering indices).

Given a partition λ, let ρ(λ) = [k, k − 1, …, 1] be the biggest staircase, the diagram of which is contained in the one of λ.

Take any box in the staircase [k + 1, …, 1] which does not belong to λ. The diagonal passing through this box cuts the diagram of λ/ρ(λ) into two pieces that we call respectively the North-West part and the South-East part of λ/ρ. Fill now each box of row r, r = 2, … of the North-West part with the number r − 1. Similarly, fill each box of column c of the South-East part with the number c − 1.

Reading the North-West part by columns, from right to left, and interpreting r as the simple transposition s_{r}, gives a reduced decomposition of a certain permutation σ(λ, NW); similarly, reading rows, from right to left, and from top to bottom, of the South-East part, gives a permutation σ(λ, SE) (these two permutations depend on the choice of the box cutting the diagram λ/ρ, there can be several ways to get F_{λ} from F_{ρ}).

Theorem 7 Let λ be a partition, ρ(λ) = [k, …, 1] the maximal staircase contained in the diagram of λ, σ(λ, NW), σ(λ, SE) be the two permutations obtained by cutting the diagram of λ/ρ as explained above. Then

F_{λ}(X, Y) = ∏_{(i,j)∈λ}(1−x_{i}y_{j})^{−1} = ∑_{μ∈ℕ^{k}} π_{σ(λ,NW)}^{x}(K̂(μ, X)) π_{σ(λ,SE)}^{y}(K(μ^{ω}, Y)) ,

sum over all weights μ ∈ ℕ^{k}.

Proof. Divided differences allow to increase the number of poles in a rational function. Indeed, if F is symmetrical in x_{k}, x_{k+1}, then the divided difference π_{k}^{x} (acting on x_{k}, x_{k+1}) has the effect

(1 − x_{k}y)^{−1} F ⟶^{π_{k}^{x}} (1 − x_{k}y)^{−1}(1 − x_{k+1}y)^{−1} F

because π_{k}^{x}(x_{k+1}) = 0 and π_{k}^{x} commutes with multiplication by F. Now, a function F_{λ} is symmetrical in x_{k}, x_{k+1} if rows k and k + 1 of the diagram of λ have equal length; it is symmetrical in y_{j} and y_{j+1} if columns j and j + 1 have equal length. Therefore, when the difference of lengths of row k and k + 1 is 1, the image of F_{λ} under π_{k}^{x} is F_{λ^{+}}, where λ^{+} is obtained by adding a box to row k + 1 of the diagram of λ.

It is easy to see that the chosen sequence of π_{k}^{x} or π_{j}^{y} has the effect of producing a sequence F_{ρ}, F_{ν^{1}}, …, F_{νℓ}, F_{λ}, with partitions differing by one box at a time. QED

For example, when λ = [7, 5, 2, 2, 2, 2], one has ρ = [4, 3, 2, 1],

\begin{matrix}5 & 5 \\ 4 & 4 \\ ■ & 3 \\ ■ & ■ \\ ■ & ■ & ■ & 3 & 4 \\ ■ & ■ & ■ & ■ & 4 & 5 & 6 \end{matrix} ⟹ σ(λ, NW) = s_{5}s_{4}s_{3} s_{5}s_{4} & σ(λ, SE) = s_{4}s_{3} s_{6}s_{5}s_{4}

Representing F_{λ} by the diagram of λ (filled with ■, except for the box just added), writing below it the lengths of rows i, i + 1 (when using π_{i}^{x}), or columns j, j + 1 (when using π_{j}^{y}), Theorem 7 provides the following sequence to pass from F_{4321} to F_{752222} :

\begin{matrix}■ \\ ■ & ■ \\ ■ & ■ & ■ \\ ■ & ■ & ■ & ■ \end{matrix} ; r_{4}=1,r_{5}=0 ⟶^{π_{4}^{x}} \begin{matrix}4 \\ ■ \\ ■ & ■ \\ ■ & ■ & ■ \\ ■ & ■ & ■ & ■ \end{matrix} ; r_{5}=1,r_{6}=0 ⟶^{π_{5}^{x}} \begin{matrix}5 \\ ■ \\ ■ \\ ■ & ■ \\ ■ & ■ & ■ \\ ■ & ■ & ■ & ■ \end{matrix} ; r_{3}=2,r_{4}=1⟶^{π_{3}^{x}} \begin{matrix}■ \\ ■ \\ ■ & 3 \\ ■ & ■ \\ ■ & ■ & ■ \\ ■ & ■ & ■ & ■ \end{matrix} ; r_{4}=2,r_{5}=1⟶^{π_{4}^{x}} \begin{matrix}■ \\ ■ & 4 \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ & ■ \\ ■ & ■ & ■ & ■ \end{matrix} ; r_{5}=2,r_{6}=1⟶^{π_{5}^{x}} \begin{matrix}■ & 5 \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ & ■ \\ ■ & ■ & ■ & ■ \end{matrix} ; c_{4}=1,c_{5}=0

⟶^{π_{4}^{y}} \begin{matrix}■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ & ■ \\ ■ & ■ & ■ & ■ & 4 \end{matrix} ; c_{5}=1,c_{6}=0⟶^{π_{5}^{y}} \begin{matrix}■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ & ■ \\ ■ & ■ & ■ & ■ & ■ & 5 \end{matrix} ; c_{6}=1,c_{7}=0 ⟶^{π_{6}^{y}} \begin{matrix}■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ & ■ \\ ■ & ■ & ■ & ■ & ■ & ■ & 6 \end{matrix} ; c_{3}=2,c_{4}=1 ⟶^{π_{3}^{y}} \begin{matrix}■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ & ■ & 3 \\ ■ & ■ & ■ & ■ & ■ & ■ & ■ \end{matrix} ; c_{4}=2,c_{5}=1 ⟶^{π_{4}^{y}} ^{\begin{matrix}■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ \\ ■ & ■ & ■ & ■ & 4 \\ ■ & ■ & ■ & ■ & ■ & ■ & ■ \end{matrix}}

5 Nilplactic kernel

The two sets of indeterminates X and Y played a symmetrical role in the preceding sections. We present now an example where it is not the case and where tableaux are given another interpretation.

The x_{i}’s are commutative variables, and commute with the y_{j}’s. The y_{j}’s obey the nilplactic relations [24], [4] :

y_{i}^{2} = 0 , y_{i}y_{i+1}y_{i} = y_{i+1}y_{i}y_{i+1}  (20)
y_{j}y_{i}y_{k} = y_{j}y_{k}y_{i} , y_{i}y_{k}y_{j} = y_{k}y_{i}y_{j} (i < j < k)  (21)

One says that a word in the y_{i}’s is reduced if its image under y_{i} → s_{i}, s_{i} simple transposition, is reduced. Two reduced words equivalent under the nilplactic relations project onto the same permutation. The nilplactic algebra is the algebra generated by the y_{j}’s, modulo the ideal generated by non reduced words.

Schensted’s construction can be adapted to the nilplactic case. The basic objects are now sequences of columns w = [u_{1}, …, u_{ℓ}], and one has the following theorem ([24], [4]):

Theorem 8 There exists a bijection between ℓ-uples of columns (=strictly decreasing words) w = [u_{1}, …, u_{ℓ}], such that u_{1} ⋯ u_{ℓ} is reduced, and pairs of tableaux t = P^{nil}(w), t′ = Q^{nil}(w) ∈ {x_{1}, …, x_{ℓ}}^{∗} of conjugate shape, t being reduced.

The tableau P^{nil}(w) is the unique tableau in the nilplactic class of u_{1} ⋯ u_{ℓ}. Multiplying P^{nil}(u_{1} ⋯ u_{ℓ−1}) by the column u_{ℓ} increase the shape by a vertical strip (as for the multiplication of a Schur function by an elementary symmetric function, cf. [32]), which is recorded as the set of boxes occupied by the letter x_{ℓ} in the tableau Q^{nil}(w).

For example, the product 5 1 · 6 5 2 1 · 4 3 2 produces the following sequence of

tableaux and transposed shapes differing by a strip

\begin{matrix}tableau \\ transposed shape \end{matrix} 5 1 1 1 ⟶ 6 5 2 6 1 2 2 2 1 1 2 2 ⟶ 3 2 2 3 1 1 2 2 3 = Q^{nil}^{6 5 4 6 2 3 1 2 3} .

As before, instead of taking all possible reduced words, one wants to characterize the possible pairs of tableaux which correspond to the expansion of some kernel.

Instead of taking a general partition, we restrict to ρ = [n, …, 1] for simplicity, and define the NilCauchy kernel to be

NilC(n) = ((1 + x_{1}y_{n}) ⋯ (1 + x_{1}y_{1}))

((1 + x_{2}y_{n}) ⋯ (1 + x_{2}y_{2})) · · · · · · ((1 + x_{n}y_{n})) . (22)

One notices that each block expands into a sum of columns :

(1 + xy_{n}) ⋯ (1 + xy_{k}) = ∑_{u} x^{ℓ(u)}u ,  (23)

sum over all possible columns u in the letters y_{n}, …, y_{k}.

Thus, NilC(n) can be studied using Theorem 8. All the tools presented in the first sections involving right actions can be adapted to the nilplactic case. For example, there are two symmetric groups acting on a tableau, permuting either rows, or columns. One can choose to record the columns appearing on the left, the columns appearing on the right, the rows appearing upwards or the rows appearing downwards. One has indeed four possible keys in the nilplactic case. To describe NilC(n), one needs the bottom key, which is illustrated on the following example, which will be used in Figure 3 (read now objects as sequences of rows in the y_{i} (noted y_{i} = i). Transformations are now given by the nil-jeu de taquin exchanging a two-rows tableau with the two-rows contretableau in its nilplactic class.

5 4 6 2 3 5 1 2 3 4 ↦ 5 4 6 1 2 3 5 1 2 4 ↦ 5 1 2 4 6 3 5 1 2 4 ↦ 5 1 2 4 6 1 3 5 2 4 ↦ 1 2 5 6 4 1 3 5 2 4 ↦ 1 2 5 6 1 4 5 3 2 4 ↦ 1 2 5 6 1 4 5 3 4 2

In that case, the bottom key is the set of bottom rows (with the same multiplicities as the lengths of rows of the tableau)

{ [2], [2, 4], [1, 2, 4], [1, 2, 3, 4] } ,  (24)

with weight μ = [2, 4, 1, 3] (number of occurrences of 1, 2, 3, 4 respectively).

We shall just state, but not prove, the following property which shows another use of tableaux and the jeu de taquin.

Property 9 The NilCauchy kernel expands, in the nilplactic algebra, as

NilC(n) ≡^{Nil} ∑_{t} K(μ(t), X) t ,  (25)

sum over all tableaux (read by columns, and which are reduced words) that appear as subwords of

(y_{n} ⋯ y_{1}) (y_{n} ⋯ y_{2}) ⋯ (y_{n}) ,

μ(t) being the weight of the bottom key of t.

For example,

NilC(2) ≡^{Nil} x_{1}^{2}x_{2} y_{2} ; ^{y_{1} y_{2}} + x_{1}^{2} y_{2} ; y_{1} + x_{1}x_{2} y_{1} y_{2} + x_{1} y_{1} + (x_{1}+x_{2}) y_{2} + 1

(the term y_{2}y_{2} has disappeared, because it is not a reduced word).

Figure 3 shows all the terms in NilC(6) belonging to the nilplactic class

of t = \begin{matrix}5 \\ 4 & 6 \\ 2 & 3 & 5 \\ 1 & 2 & 3 & 4 \end{matrix} (writing i instead of y_{i}). They constitute a crystal, the crystal

operations being the nil-jeu de taquin on two consecutive columns. Each vertex must be read as a product of four columns in the y_{i}, of lengths ℓ_{1}, …, ℓ_{4}, appearing as a subword of

((1+x_{1}y_{6}) ⋯ (1+x_{1}y_{1}))((1+x_{2}y_{6}) ⋯ (1+x_{2}y_{2}))((1+x_{3}y_{6}) ⋯ (1+x_{3}y_{3}))

((1+x_{4}y_{6})(1+x_{4}y_{5})(1+x_{4}y_{4}))( )( )( ) ,

its factor being x_{1}^{ℓ_{1}}x_{2}^{ℓ_{2}}x_{3}^{ℓ_{3}}x_{4}^{ℓ_{4}}.

For example, 2 5 1 4 6 3 5 2 3 4 stands for

(x_{1}y_{2}x_{1}y_{1})(x_{2}y_{5}x_{2}y_{4}x_{2}y_{3}x_{2}y_{2})(x_{3}y_{6}x_{3}y_{5}x_{3}y_{3})(x_{4}y_{4}) = x_{1}^{2}x_{2}^{4}x_{3}^{3}x_{4}^{1} y_{2}y_{1} y_{5}y_{4}y_{3}y_{2} y_{6}y_{5}y_{3} y_{4}.

Because the weight of the bottom key is μ = [2, 4, 1, 3], then, according to Property 9, the sum of all factors x_{1}^{ℓ_{1}}x_{2}^{ℓ_{2}}x_{3}^{ℓ_{3}}x_{4}^{ℓ_{4}} is the Demazure character K([2413]) = x_{1}^{4}x_{2}^{3}x_{3}^{2}x_{4}^{1} + ⋯ + x_{1}^{2}x_{2}^{4}x_{3}^{1}x_{4}^{3}.

Thus the study of NilC(n) essentially reduces to recognize that the intersection of a nilplactic class with the set of reduced words appearing in the expansion of NilC(n) is isomorphic to some crystal.

Property 9 implies the expansion of Schubert polynomials in terms of Demazure characters given in [26].

Projecting expression (25) on the NilCoxeter algebra with generators y_{i} satisfying :

y_{i}^{2} =^{Cox} 0 , y_{i}y_{i+1}y_{i} =^{Cox} y_{i+1}y_{i}y_{i+1} , y_{i}y_{k} =^{Cox} y_{k}y_{i} , |k − i| ≠ 1 (26)

one gets Fomin-Kirillov expansion [7] of the nilCoxeter kernel involving Schubert polynomials (see also [20], [6])

NilC(n) =^{Cox} ∑_{σ∈𝔖(n+1)}Schub_{σ}(X) σ .  (27)

For example

NilC(2) =^{Cox} x_{1}^{2}x_{2} s_{2}s_{1}s_{2} + x_{1}^{2} s_{2}s_{1} + x_{1}x_{2} s_{1}s_{2} + x_{1}s_{1} + (x_{1} + x_{2}) s_{2} + 1 .

6 Double characters

Having a combinatorial interpretation of characters in terms of tableaux and crystal graphs, it is easy to modify their definition to handle functions in two sets of indeterminates. Let w be a word in non commuting letters \binom{j}{i}, and let w_{x} be the word obtained by sending \binom{j}{i} to x_{i}, ∀j. We have seen that a left crystal operator f_{i} sends a word w_{x} to 0, or change in it a single precise occurrence of the letter x_{i} into a x_{i+1}.

Define accordingly the action of f_{i} on w to be

\{ \begin{matrix}f_{i}(w_{x}) = 0 & ⇒ & f_{i}(w) = 0 \\ f_{i}(w′_{x} x_{i} w′′_{x}) = w′_{x} x_{i+1} w′′_{x} & ⇒ & f_{i}(w′ \binom{j}{i} w′′) = w′ \binom{j+1}{i+1} w′′ \end{matrix}  (28)

One extends similarly the action of π_{i} from words in the x_{j}’s to words in the \binom{j}{i}’s.

Let λ ∈ ℕ be a dominant weight, σ ∈ 𝔖_{n}, and μ = λ^{σ}. Let now

w^{λ} := \begin{matrix}\binom{1}{n} & … & \binom{λ_{n}}{n} \\ \binom{1}{n−1} & … & … & \binom{λ_{n−1}}{n−1} \\ ⋮ & & & ⋮ \\ \binom{1}{1} & … & … & … & \binom{λ_{1}}{1} \end{matrix} (read by rows)

Let s_{i} ⋯ s_{j} = σ be a reduced decomposition of σ (σ can be supposed to be minimum in its class modulo the stabilizer of λ).

Then one defines the crystal BB(μ) to be

BB(μ) = π_{i} ⋯ π_{j} (w^{λ})  (29)

This sum of words does not depend on the choice of the reduced decomposition of σ, as shows the characterization given in the next theorem.

Given a tableau t ∈ X^{∗}, let φ(t) be the tableau in the \binom{j}{i}’s obtained by changing an entry x_{i} in row r, column c, into the letter \binom{i+c−r}{i}, and extends φ by linearity to sums of tableaux. Considering B(μ, X) to be a sum of tableaux rather than a set, one has :

Theorem 10 Let λ ∈ ℕ be a dominant weight, μ be a permutation of λ. then

φ(B(μ, X)) = BB(μ)  (30)

The proof consists just in noticing that the action of any f_{i} preserves the differences between subscripts and superscripts: \binom{j}{i} ↦ \binom{j+1}{i+1}. Thus, recording the initial superscripts in w^{λ}, one can as well erase them and operate on tableaux in the x_{i}’s, reintroducing the superscripts at the last step.

Now the entries of the initial tableau w^{λ} are of the type \binom{i+c−r}{i}, for a letter in column c, row r. QED

For example,

B([1, 0, 2], X) = x_{2} ; ^{x_{1} x_{1}} + x_{2} ; ^{x_{1} x_{2}} + x_{3} ; ^{x_{1} x_{1}} + x_{2} ; ^{x_{1} x_{3}} + x_{3} ; ^{x_{1} x_{3}} implies

BB([1, 0, 2]) = \binom{1}{2} ; ^{\binom{1}{1} \binom{2}{1}} + \binom{1}{2} ; ^{\binom{1}{1} \binom{3}{2}} + \binom{2}{3} ; ^{\binom{1}{1} \binom{2}{1}} + \binom{1}{2} ; ^{\binom{1}{1} \binom{4}{3}} + \binom{2}{3} ; ^{\binom{1}{1} \binom{4}{3}}

The characters K(μ, X) are obtained by taking the sum of the commutative images of the tableaux in B(μ, X). Similarly, one defines a double character 𝕂(μ, X, Y) in two sets of commutative indeterminates by taking the image of a word under the morphism

\binom{j}{i} ↦ (x_{i} − y_{j}) .

By construction, one recovers K(μ, X) by specializing the y_{j}’s to 0 :

K(μ, X) = 𝕂(μ, X, 0) .

But now, the polynomials 𝕂(μ, X, Y) have some specific properties (e.g. vanishing properties) that make them easier to characterize than the polynomials K(μ, X).

For example, if μ is the code of a vexillary permutation σ (cf. [30]), then one can show (but we shall not) that 𝕂(μ, X, Y) coincides with the Schubert polynomial indexed by σ.

A special case, when μ is of the type

μ = [μ_{1} ≤ μ_{2} ≤ ⋯ ≤ μ_{r}, 0, 0, …]

is known since long. Indeed, specializing y_{1} = 0, y_{2} = 1, y_{3} = 2, …, one recognizes that 𝕂(μ, X, {0, 1, 2, …}) is a factorial Schur function, which was defined by Biedenharn and Louck [2] through the enumeration of the same tableaux as in Theorem 10. The more general case were the y_{j}’s are not specialized has been obtained by several authors ( [31], [33], [34]), but was already used, following Giambelli, in [15] to describe Schubert cycles for relative Grassmann varieties.

Some historical comments. I shall end this text evoking why Schur’s work was personally important for me, even before I was aware of it, restricting to my work in 1974.

In [14] I considered symmetric functions as operators on isobaric determinants, Schur functions (not named) being operators transforming Vandermonde determinants by increasing exponents. Shortly after [15], multi-Schur functions appeared as Schubert cycles. In [16] Schur functions were “Schur-Littlewood” functions, sums of all the tableaux of a given shape [29]. In [17], Schur functions became elements of the plactic algebra, this interpretation being needed to explain their products. Finally Schur functors are used in my thesis [18]. I could add that much of my further work with M.P. Schützenberger can be interpreted as reflections about what remains of Schur functions when allowing non-symmetry [23] and non-commutativity [26].

References

[1] Bender and D. Knuth. Enumerations of plane partitions, J. Comb. A 13 (1972) 40–54.

[2] L. C. Biedenharn and J. D. Louck. A new class of symmetric polynomials defined in terms of tableaux Advances in Appl. Math. 10 (1989) 396–438.

[3] M. Demazure. Une formule des caractères , Bull. Sc. Math., 98 (1974) 163–172.

[4] P. Edelman and C. Greene. Balanced tableaux, Advances in Maths 63 (1987) 42–99.

[5] W. Fulton. Young tableaux, Cambridge Univ. Press (1997).

[6] S. Fomin and C. Greene. Noncommutative Schur functions and their applications, Discrete Math. 193 (1998), 179–200.

[7] S. Fomin and A. Kirillov. The Yang-Baxter equation, symmetric functions and Schubert polynomials, Discrete Math., 153 (1996) 123–143.

[8] M. Kashiwara. Crystal base and Littelmann refined Demazure character formula, Duke Math. 71 (1993) 839–858.

[9] M. Kashiwara. On crystal bases, Canadian M. Soc. Conf. Proc., 16(1995) 155–197.

[10] M. Kashiwara, T. Nakashima. Crystal graphs for representations of the q-analogue of classical Lie algebras, J. Algebra 165(1994) 295–345.

[11] D. Knuth. Permutations, matrices, and generalized Young tableaux, Pacific J.M. 34 (1970) 709–727.

[12] V. Lakshmibai. Bases for Demazure modules for symmetrizable Kac-Moody algebras, Contemp. Math., 153 (1993) 59–78.

[13] V. Lakshmibai, C.S. Seshadri. Geometry of G/P V, J. Algebra, 100(1986) 462–557.

[14] A. Lascoux. Coefficients d’intersection de cycles de Schubert, Comptes Rendus 279(1974) 201–203.

[15] A. Lascoux. Puissances extérieures, déterminants et cycles de Schubert, Bull. Soc. Math. Fr. 102(1974) 161–179.

[16] A. Lascoux. Tableaux de Young et fonctions de Schur-Littlewood, Séminaire Pisot 74/75, n^{0}4 (1974).

[17] A. Lascoux. Tableaux de Young gauches, Séminaire de Théorie des Nombres, exp. n^{o}4, Bordeaux (1974).

[18] A. Lascoux. Polynômes symétriques, Foncteurs de Schur et Grassmanniennes. Thèse, Université Paris 7 (1977).

[19] A. Lascoux. Classes de Chern des variétés de drapeaux, Comptes Rendus 295 (1982) 393–398.

[20] A. Lascoux, B. Leclerc and J.Y. Thibon. Flag Varieties and the Yang-Baxter Equation, Letters in Math. Phys., 40 (1997) 75–90.

[21] A. Lascoux, B. Leclerc and J.Y. Thibon. The plactic monoid, in Combinatorics on words II, Lothaire ed., Cambridge Univ. Press, to appear.

[22] A. Lascoux & M.P. Schützenberger. Le monoïde plaxique, Noncommutative structures in algebra and geometric combinatorics, Napoli 1978, Quaderni de “La Ricerca Scientifica”, 109, C.N.R., Roma (1981) 129–156.

[23] A. Lascoux & M.P. Schützenberger. Polynômes de Schubert, Comptes Rendus 294 (1982) 447.

[24] A. Lascoux & M.P. Schützenberger. Structure de Hopf, Comptes Rendus 295 629–633.

[25] A. Lascoux & M.P. Schützenberger. Keys and standard bases, Invariant Theory and Tableaux, IMA volumes in Math. and its Applications, 19, Springer (1988) 125–144.

[26] A. Lascoux & M.P. Schützenberger. Tableaux and non commutative Schubert Polynomials, Funk.Anal 23(1989) 63–64.

[27] P. Littelmann. A Littlewood-Richardson rule for symmetrizable Kac-Moody algebras, Invent. Math. 116 (1994) 329–346.

[28] P. Littelmann. A plactic algebra for semisimple Lie algebras, Adv. in Math. 124 (1996) 312–331.

[29] D.E. Littlewood. The theory of group characters, Oxford University Press (1950).

[30] I. G. Macdonald. Notes on Schubert polynomials LACIM, Publi. Université Montréal, (1991).

[31] I. G. Macdonald. Schur functions: theme and variations, 28^{e} Séminaire Lotharingien (1992) 5–39.

[32] I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford University Press, Oxford, 2nd edition (1995).

[33] A. Molev. Factorial supersymmetric Schur functions and super Capelli identities, in Kirillov’s Seminar on Representation Theory, ed G. Olshanski, A.M.S. Translations (2), Vol. 181 (1997) 109–137.

[34] A. Okounkov and G. Olshanski. Shifted Schur functions, St. Petersburg Math. J. 9 (1998) 239–300.

[35] C. Schensted. Longest increasing and decreasing subsequences, Canad. J. Math., 13 (1961) 179–191.

[36] I. Schur. Gesammelte Abhandlungen, Springer (1973).

[37] M.P. Schützenberger. La correspondance de Robinson, Combinatoire et représentation du groupe symétrique, Strasbourg 1975, Springer Lect. Notes in Math. 579(1977) 59–113.

[figure: 234.3.1122.11; 234.3.1222.11; 334.3.1122.11; 244.3.1122.11; 334.3.1222.11; 244.3.1222.11; 344.3.1122.11; 334.3.2222.11; 344.3.1222.11; 444.3.1222.11; 344.3.2222.11; 444.3.1222.11; 444.3.2222.11]

Figure 1

Crystal B([2413], Q) with Q = 4 3 4 2 3 3 1 1 1 3 [figure: 3 3 4 4 1 3 3 1 2 1; 3 4 4 1 3 3 3 1 2 1; 3 3 4 4 3 3 1 1 2 1; 3 3 4 4 1 3 3 2 1 1; 3 4 4 3 3 3 1 1 2 1; 3 4 4 1 3 3 3 2 1 1; 3 3 4 4 3 3 1 2 1 1; 4 4 3 3 3 3 1 1 2 1; 3 4 4 3 3 3 1 2 1 1; 3 3 4 4 3 3 2 1 1 1; 4 4 3 3 3 3 1 2 1 1; 3 4 4 3 3 3 2 1 1 1; 4 4 3 3 3 3 2 1 1 1] Vertices must be read as products of four rows, crystal operations are the jeu de taquin on consecutive rows

Figure 2: Cocrystal CB([2413])

[figure: 5 4 6 2 3 5 1 2 3 4; 5 6 2 4 1 3 5 2 3 4; 5 4 2 3 6 1 2 5 3 4; 5 4 6 2 3 1 2 3 5 4; 5 2 4 6 1 3 5 2 3 4; 5 6 2 4 1 3 2 3 5 4; 5 4 2 3 6 1 2 3 5 4; 2 5 1 4 6 3 5 2 3 4; 5 2 4 1 3 6 2 3 5 4; 5 4 2 3 1 2 3 6 5 4; 2 5 1 4 3 6 2 3 5 4; 5 2 4 1 3 2 3 6 5 4; 2 5 1 4 3 2 3 6 5 4]

Figure 3

A copy of the crystal B([2, 4, 1, 3]), with reduced words as vertices. Read each vertex as a sequence of four columns, interpreting it as a reduced subword of (6 ⋯ 1)(6 ⋯ 2)(6 ⋯ 3)(6 ⋯ 4). Edges are given by the (nil) jeu de taquin on pairs of consecutive columns