An explicit construction of type A Demazure atoms

(1)

DOI 10.1007/s10801-008-0133-4

An explicit construction of type A Demazure atoms

S. Mason

Received: 28 July 2007 / Accepted: 12 March 2008 / Published online: 29 March 2008

Abstract Demazure characters of type A, which are equivalent to key polynomi- als, have been decomposed by Lascoux and Schützenberger into standard bases. We prove that the resulting polynomials, which we call Demazure atoms, can be obtained from a certain specialization of nonsymmetric Macdonald polynomials. This combinatorial interpretation for Demazure atoms accelerates the computation of the right key associated to a semi-standard Young tableau. Utilizing a related construction, we provide a new combinatorial description of the key polynomials.

Keywords Symmetric functions·Young tableaux·Demazure characters

1 Introduction

The Demazure character formula generalizes the Weyl character formula to highest- weight modules over symmetrizable Kac-Moody Lie algebras. In particular, ifV (λ) is a highest weight module of weightλ, then the extremal weight vectoruωλof weight ωλgenerates aU (n)-submoduleU (n)uωλ. The formal character of this submodule is given by Demazure’s character formula [1], [5]. The Demazure characters corresponding to the general linear Lie algebragl_n(C)are equivalent to the key polynomials, which are described [11] as the sums of the weights of semi-standard Young tableaux (SSYT) whose right key is bounded by a certain keyK(ω, λ).

Lascoux and Schützenberger [9] study the smallest non-intersecting pieces, U(ω, λ), of typeADemazure characters. They call the resulting polynomials stan- dard bases and describe them combinatorially as the sums of the weights of all semi-

Partially supported by NSF postdoctoral research fellowship DMS-0603351 (S.M.).

S. Mason (

⁾

Department of Mathematics, Davidson College, Davidson, USA e-mail:[email protected]

url:http://www.davidson.edu/math/mason

(2)

standard Young tableaux whose right key is equal to the keyK(ω, λ). Each semi- standard Young tableau appears in precisely one such polynomial, implying that the polynomialsU(ω, λ)form a decomposition of the Schur functions.

There exists a decomposition of the Schur functions into the polynomials E_γ(x;0,0), which are obtained by setting q=t =0 in the combinatorial formula for integral form nonsymmetric Macdonald polynomials [2]. TheE_γ(x;0,0)are ob- tained from the weights of semi-skyline augmented fillings, which are fillings of com- position diagrams with positive integers in such a way that the columns are weakly decreasing and the rows satisfy an inversion condition. Semi-skyline augmented fillings are in bijection with semi-standard Young tableaux and satisfy a variation of the Robinson-Schensted-Knuth algorithm [10].

Theorem 1.1 The standard baseU(ω, λ)is equal to the specialized nonsymmetric Macdonald polynomialE_ω(λ)(X;0,0).

We obtain an efficient method for computing the right key of a semi-standard Young tableau as a corollary to Theorem 1.1. Begin with a semi-standard Young tableauT and mapT to the semi-skyline augmented filling(T )whose weight is equal to that ofT. Let the shape of(T )be given by the compositionγ. Then the right key ofT is the unique key with weightγ.

The Demazure characterκ_ω(λ)corresponding to a partitionλand permutationω can be described combinatorially as the sum of the weights of all SSYT whose right key is less than or equal toK(ω, λ). (In this paper we use the notationκω(λ)as in [11]

for ease of notation and to emphasize the fact that the Demazure characters we are working with coincide with the key polynomials described by Reiner and Shimozono.

The notationD_ω(e^λ)typically refers to the Demazure character corresponding to a highest-weight module of weightωλ over an arbitrary symmetrizable Kac-Moody Lie algebra [7].)

Demazure characters can be computed by summing over Demazure atoms. That is,

κ_ω(λ)=

τ≤ω

U(τ, λ),

where the ordering on the permutations is the Bruhat order. A permuted-basement semi-skyline augmented filling is defined by rules similar to those which describe an ordinary semi-skyline augmented filling. Permuting the basements of semi-skyline augmented fillings provides an alternate method for computing Demazure characters combinatorially.

Theorem 1.2 The Demazure characterκ_ω(λ)is equal to the sum of the weights of all permuted-basement semi-skyline augmented fillings of shapeλwith basementω.

A similar connection exists between nonsymmetric Macdonald polynomials specialized toq =t = ∞ and Demazure characters of the corresponding affine Kac- Moody algebra [4]. This correspondence and its proof provide a representation- theoretic perspective on the role of nonsymmetric Macdonald polynomials in the study of affine Lie algebras.

(3)

2 Demazure characters

Let g=gln(C) be the general linear Lie algebra and let be the corresponding root system whose highest weights are partitions. If nis the subalgebra ofgwith basisX_α (α∈⁺), thenU (n)is the universal enveloping algebra. LetV (λ)be the irreducible highest-weight module of weightλ. Given a permutationω, letu_ωλbe the extremal vector of weightωλofV (λ). Then the characterκ_ω(λ)ofU (n)u_ωλis given by the Demazure character formula. In this section we describe the explicit formula using Demazure operators.

2.1 The Demazure operator

LetP be the polynomial ringZ[x₁, x₂, . . .]and letS_∞be the permutation group of the positive integers. This group acts onP by permuting the indices of the variables.

Ifsi is the elementary transposition(i, i+1), define the linear operators∂iandπias in [11] by

∂_i= 1−si

xi−xi+1

, π_i=∂_ix_i. (2.1)

Givenω∈S_∞, letω=s_i₁s_i₂. . . s_i_k be a decomposition ofωinto elementary transpositions. When the numberkof transpositions in such a product is minimized, the wordi1i2. . . ik is called a reduced word forω. The operator πω=πi₁πi₂. . . πi_k is obtained by applying the product of the operatorsπi_j, wherei1i2. . . ik is a reduced word for ω. This operator is the Demazure operator [1], [5] for the general linear Lie algebragl_n(C). One obtains the Demazure character corresponding to a parti- tionλand a permutationωby applying the operatorπ_ω to the dominant monomial x^λ=

ix_i^λⁱ. For example, ifλ=(2,1)andω=(1,2,3), then the corresponding Demazure character isπ₁π₂(x₁²x₂)=x₁²x₂+x₁²x₃+x₁x₂²+x₁x₂x₃+x₂²x₃. 2.2 An equivalent definition [11]

A key is a semi-standard Young tableau such that the set of entries in the(j+1)^{t h} column form a subset of the set of entries in thej^{t h}column, for allj≥1. A bijection exists between weak compositions and keys given byγ =(γ1, γ2, . . .)→key(γ ), where key(γ )is the key such that for allj, the firstγj columns contain the letterj. To invert this map, send the keyT to the composition describing the content ofT. Figure1depicts key(2,1,1,4,0,3), written in French notation.

Fig. 1 T=key(2,1,1,4,0,3)

(4)

Fig. 2 Herevis not column-frank butwis

Let col(T )be the word obtained from an SSYTT by reading the column entries ofT from top to bottom, left to right. If a wordwis Knuth equivalent [8] to col(T ), writew∼T. There exists a unique wordvin each Knuth equivalence class such that v=col(T )for some semi-standard Young tableauT.

The column form of a wordw, denoted colform(w), is the composition consist- ing of the lengths of the strictly decreasing subwords of w. Let w be an arbitrary word such thatw∼T forT of shapeλ. The wordw is said to be column-frank if colform(w)is a rearrangement of the nonzero parts ofλ, whereλ is the conjugate shape of the partitionλobtained by reflecting the Ferrers diagram ofλacross the line x=y. (In Figure2,vis not column-frank butwis.)

LetT be a semi-standard Young tableau of shapeλ. The right key ofT, denoted K₊(T ), is defined in [11] to be the unique key of shapeλwhosej^{t h}column is given by the last column of any column-frank word v such that v∼T and colform(v) is of the form(. . . , λ_j). For example, S=5 3 2 1·4 2 in Figure 2 has right key K₊(T )=5 4 2 1·4 2.

Given an arbitrary partitionλand permutationω (written in one-line notation), there exists an associated keyK(ω, λ) defined as follows. Consider the subword consisting of the first λ₁ letters of ω and reorder the letters in decreasing order. This is the first column ofK(ω, λ). The second column ofK(ω, λ) contains the first λ2 letters of ω in decreasing order. Continuing this way, one derives the word col(K(ω, λ))[9]. For example,ω=241635 andλ=(4,2,2,1)give the key K(ω, λ)=6 4 2 1·4 2·4 2·2.

Define a partial order on the set of all semi-standard Young tableaux of shapeλby settingT ≤Sif and only if the entry in thei^{t h}row andj^{t h}column ofT is less than or equal to the corresponding entry inSfor alliandj. The key polynomialκ_ω(λ)is defined [11] as the sum of the weights of all SSYT having right key less than or equal toK(ω, λ). This polynomial is precisely the typeADemazure characterπω(x^λ)[9], so we use these terms interchangeably.

2.3 Intersections of key polynomials

Notice that for a fixed partitionλ, the sets of semi-standard Young tableaux contribut- ing weights to the polynomialsπ_ω(x^λ)intersect nontrivially. For example,

π(1,2,3)(x^(2,1))=π1π2(x₁²x2)=x²₁x2+x₁²x3+x1x₂²+x1x2x3+x₂²x3, π₂(x^(2,1))=π₂(x₁²x₂)=x₁²x₂+x₁²x₃,

(5)

π₁(x^(2,1))=π₁(x₁²x₂)=x₁²x₂+x₁x₂²

Here the monomialx₁²x3appears in bothπ1π2(x₁²x2)andπ2(x^(2,1)), but the SSYT T with column word col(T )=3 1·1 is the only SSYT of shape λ=(2,1)and weightx₁²x3.

In fact, the definition of the operatorπω implies that ifωis longer than σ and ω=siσ, then the semi-standard Young tableaux appearing as monomials inπσ(x^λ) are a subset of those appearing inπ_ω(x^λ)=π_iπ_σ(x^λ). Therefore it makes sense to consider the intersections and complements of Demazure characters.

Letωbe a permutation of lengthk. Consider all permutationsσless thanωin the Bruhat order. We study the subset of monomials inπ_ω(x^λ)which do not appear in πσ(x^λ)for any suchσ. The sum of these monomials is the polynomial obtained by replacing the operatorsπi by the operatorsπi=πi−1 in the formulaπω(x^λ). The operatorπi=πs_iis therefore defined by

f−→(s_i(f )−f )/(1−x_i/x_i+1)=π_i(f ),

and, given any reduced words_i₁s_i₂. . . s_i_k for ω, defineπ_ω(f )=π_i₁(f )π_i₂(f ) . . . π_i_k(f ). For example, iff =x₁²x2x3, thenπ1f =^(x¹^x₍₁²²^x₋³_x^−x₁_/x²¹₂^x₎²^x³⁾ =x1x₂²x3.

Lascoux and Schützenberger [9] call these polynomials the standard bases and prove that the standard basisU(ω, λ)equals the sum of the weights of all SSYT having right key equal toK(ω, λ). We retain the notationU(ω, λ)but call the polynomi- als Demazure atoms to avoid confusion with various objects referred to as standard bases.

The operators π_i satisfy the Coxeter relations π_iπ_i₊1π_i =π_i₊1π_iπ_i₊1 and π_iπ_j=π_jπ_i forj −i>1 [9]. Lift the operatorπ_i to an operatorθ_i on the free algebra by the following process. Giveniand a wordwin the commutative alphabet X=(x1, x2, . . .), letmjbe the number of occurrences of the letterxjinw, for eachj. Letk=mi−mi+1. Ifk≥0, thenwandw^sⁱ differ by the exchange of a subword x_i^k with the subwordx_i^k₊₁. The analogous statement is true fork <0. Whenk≥0, definewθ_ito be the sum of all words in which the subwordx_i^kofwhas been changed respectively intox^k_i⁻¹xi+1, x_i^k⁻²x_i²₊₁, . . . , x_i^k₊₁. For example, ifw=x₁³x₂⁴x3x5x₇³, thenwθ₂=x₁³x₂³x₃²x₅x₇³+x₁³x₂²x₃³x₅x₇³+x₁³x₂x₃⁴x₅x³₇.

Every partitionλ=(λ₁, λ₂, . . .)has a corresponding dominant monomial, x^λ=

i

x_i^λⁱ,

which equals the weight of the Yamanouchi tableau of shapeλ. (The Yamanouchi tableau is the SSYT such that, for eachi, the entries in thei^{t h}row are all equal toi.) Theorem 2.1 (Lascoux-Schützenberger [9]) Letx^λbe the dominant monomial cor- responding toλand lets_i₁s_i₂. . . s_i_k be any reduced decomposition of a permutation π. ThenU(ω, λ)=x^λθi₁θi₂. . . θi_k.

Theorem2.1provides an inductive method for constructing the Demazure atom U(ω, λ). Begin with U(id, λ)=x^λ and apply θ_i₁ to determineU(s_i₁, λ). Then ap-

(6)

Fig. 3 The crystal graph forλ=(2,1)

plyθ_i₂ toU(s_i₁, λ)to determineU(s_i₁s_i₂, λ). Continue this process until the desired standard basisU(ω, λ)is obtained.

Lascoux and Schützenberger further break down this procedure to produce a crystal graph structure [9]. (Throughout this paper, our crystallographic notation will follow the notation appearing in [6].) To describe the operatorf_i needed for this procedure, let col(T ) be the column word corresponding to the semi-standard young tableauT. Change all occurrences ofiin col(T )to right parentheses and all occurrences ofi+1 in col(T )to left parentheses. Ignore all other entries in col(T )and match the parentheses in the usual manner. If there are no unmatched right parentheses, thenfi(col(T ))=col(T ). Otherwise replace the rightmost unmatched right parenthesis by a left parenthesis and convert the parentheses back to occurrences ofi andi+1. The resulting word isf_i(col(T )). Figure3depicts the crystal graph corresponding to the partition(2,1).

The Demazure character corresponding toω=s_i₁s_i₂. . . s_i_k is obtained from this procedure by applying the appropriatef_ioperators. To see this, begin with the SSYT

(7)

of highest weight, which corresponds to the monomialx^λ. Applyf_i^m^ik

k , wheremi_k

is the number of unmatched right parantheses. Add the resulting monomials to the initial monomial to obtain the Demazure characterκ_s_ik_(λ). Next applyf_i^m^ik⁻¹

k−1 to the monomials inκ_s_ik_(λ)and collect these monomials together with the monomials ofκ_s_ik to obtainκ_s

ik−1s_ik(λ). Continue this procedure to obtainκ_ω(λ).

3 Combinatorial description ofE_γ(X;0,0)

The polynomialsE_γ(X;0,0)are obtained from the nonsymmetric Macdonald polynomials by lettingqandtapproach 0. The combinatorial formula for nonsymmetric Macdonald polynomials provided by Haglund, Haiman, and Loehr [2] can be specialized in this manner to obtain a combinatorial formula forEγ(X;0,0). Several definitions are needed to describe this formula.

Letγ =(γ₁, γ₂, . . .)be a weak composition ofn. The column diagram ofγ is a figuredg(γ )consisting ofncells arranged into columns, as in [2]. Thei^{t h}column containsγ_i cells, and the number of cells in a column is called the height of that column. A cellain a column diagram is denoteda=(i, j ), whereiis the row andj is the column of the cell containinga.

For example, the following depicts the column diagram ofγ=(0,2,0,3,1,2,0, 0,1).

dg(γ )=

The augmented diagram ofγ, defined bydg(γ )=dg(γ )∪ {(0, i):1≤i≤m} (where mis the number of parts of γ), is the column diagram withmextra cells adjoined in row 0. In this paper the adjoined row, called the basement, always contains the numbers 1 throughmin strictly increasing order.

The augmented diagram forγ=(0,2,0,3,1,2,0,0,1)is depicted below.

dg(γ )=

An augmented filling, σ, of an augmented diagram dg(γ ) is a function σ : dg(γ )→Z₊, which we picture as an assignment of positive integer entries to the cells ofγ. Letσ (k)denote the entry in thek^{t h}cell of the augmented diagram en- countered whendg(γ ) is read across rows from left to right, beginning at the highest row and working downward. This ordering of the cells is called the reading order.

(A cella=(i, j )is greater than a cellb=(i, j )in the reading order if eitheri > i ori =iandj < j.) The reading word read(σ )is obtained by recording the entries in this reading order. The content of a fillingσ is the multiset of entries which appear

(8)

in the filling. The cellsa₁=(i₁, j₁)anda₂=(i₂, j₂)ofγ are said to be attacking if any of the following three conditions are true:

• i1=i2

• i1−i2=1 andj2< j1

• i2−i1=1 andj1< j2.

A filling is said to be non-attacking if for every pair of attacking cells{a₁, a₂}, we haveσ (a₁)=σ (a₂). The fillings utilized in the combinatorial description of De- mazure atoms are non-attacking fillings with additional row and column restrictions.

The following triples of cells are introduced to provide restrictions on the row entries of a filling. Note that the triple types are not related to symmetry types. TypeA and typeBmerely refer to the positions of the cells in the diagram.

Leta1=(i1, j1), a2=(i2, j2),anda3=(i3, j3)be three cells indg(γ ) such that columnj1is taller than or equal in height to columnj2. Ifi1=i2,i1−i3=1, and j1=j3, thena1, a2,anda3are said to form a typeAtriple, as depicted below.

Define forx, y∈Z+

I (x, y)=

1 ifx > y 0 ifx≤y .

Let σ be an augmented filling and let {σ (a1), σ (a2), σ (a3)} be the entries of σ in the cells{a1, a2, a3}, respectively, of a type A triple. The triple {a1, a2, a3} is called a typeAinversion triple if and only ifI (σ (a1), σ (a2))+I (σ (a2), σ (a3))− I (σ (a1), σ (a3))=1.

Consider the following ordering of the cellsa1, a2, a3obtained from their entries.

Leta_i < a_j if eitherσ (a_i) < σ (a_j)or σ (a_i)=σ (a_j)anda_i comes before a_j in reading order. If this ordering produces a counter-clockwise orientation of the cells a₁, a₂, a₃when read from smallest to largest, then the cells form a typeAinversion triple. This definition is equivalent to that given by the functionI (x, y).

Similarly, consider three cells{a1=(i1, j1, a2=(i2, j2), a3=(i3, j3)} ∈λsuch that columnj2is strictly taller then columnj1. The cells{a1, a2, a3}are said to form a typeBtriple ifi1=i2,j2=j3, andi3−i2=1, as shown below.

Letσ be an augmented filling and let{σ (a1), σ (a2), σ (a3)}be the entries ofσ in the cells{a1, a2, a3}of a typeBtriple. The triple{a1, a2, a3}is called a typeBinver- sion triple if and only ifI (σ (a3), σ (a1))+I (σ (a1), σ (a2))−I (σ (a3), σ (a2))=1.

As for typeAinversion triples, there is an equivalent definition for type B inversion triples. Again leta_i < a_j if eitherσ (a_i) < σ (a_j)orσ (a_i)=σ (a_j)anda_i comes beforea_j in reading order. The three cells form a typeB inversion triple if

(9)

the ordering of the cells, when read from smallest to largest, produces a clockwise orientation.

Define a semi-skyline augmented filling of an augmented diagramdg(γ ) to be an augmented fillingF such that the entries in each column (read top to bottom) are weakly increasing and every typeAor typeB triple of cells is an inversion triple.

Corollary 2.4 of [10] states that these conditions are enough to guarantee that the filling is non-attacking. Specializing the combinatorial formula for the nonsymmetric Macdonald polynomialsE_γ(x;q, t )given in [2] implies that

E_γ(x;0,0)=

F∈SSAF (dg(γ ))

x^F,

whereSSAF (dg(γ ))is the set of all semi-skyline augmented fillings of shapeγ.

4 Proof of Theorem1.1

The set of Demazure atoms for the partitionλcan be considered as a decomposition of the Schur functions_λ. For any partitionλofn, it is known [9] that

ω∈Sn

U(ω, λ)=sλ.

The functionsE_γ(X;0,0)are also a decomposition of the Schur functions [10], so it is natural to determine their relationship to the Demazure atoms. Theorem1.1states thatU(ω, λ)=N Sω(λ), whereω(λ)denotes the action ofωon the parts ofλwhenλ is considered as a partition ofnintonnon-negative parts.

4.1 Several useful lemmas

Section 3.1 of [10] provides a bijection ρ between row-strict plane partitions and semi-skyline augmented fillings which preserves the entries in each row. The map can be considered as a map from a collection{R_i}of sets of row entries to an SSAF.

Insert the rows from lowest to highest. Assume that the lowestj rows and the largest kentries of rowj+1 have been inserted. Considerα_k₊1, the(k+1)^{t h}largest entry in rowj+1. Placeαk+1on top of the leftmost entry,β, of rowj such that the cell on top ofβis empty andβ≥αk+1. Continue in this manner until all the row entries have been placed into the diagram. The result is the unique SSAF with row entries{Ri}.

A different bijection,, is described in [10] to map directly between SSYTs and SSAFs. Begin with a semi-standard Young tableauT of shapeλand insert its entries into an empty SSAF, using the following insertion procedure. When inserting an entry α1into an SSAFF, find the first entryα2ofF in reading order which is greater than or equal toα1. If there is no entry on top ofα2, placeα1on top ofα2and the insertion is complete. If the entry directly aboveα2is greater thanα1, continue to the next entry in reading order which is greater than or equal toα₁and repeat. If the entry,α₃, directly aboveα₂is less thanα₁, replace it withα₁and find the next entry in reading order which is greater than or equal toα₃. Repeat this procedure until the insertion is

(10)

complete. Applying this insertion to the columns ofT, beginning with the smallest entry in the rightmost column and moving through the column entries from smallest to largest, rightmost column to leftmost column, produces a semi-skyline augmented filling whose shape is a rearrangement ofλ. This map is a weight-preserving, shape-rearranging bijection between semi-standard Young tableaux and semi-skyline augmented fillings [10].

Proposition 4.1 There exists a mapi:SSAF−→SSAF such that the following dia- gram commutes for all SSYTT.

T

fi

T

F

i

F

(Heref_i is the crystal operator described in Section2.)

Proof LetF be an arbitrary semi-skyline augmented filling and let read(F )be the reading word obtained by readingF left to right, top to bottom, as described in Sec- tion3. First match any pairiandi+1 which occur in the same row ofF and remove these entries from the reading word ofF. Next apply the parenthetical matching procedure of [9] described in Section2.3to the reading word to determine which of the remaining occurrences ofi andi+1 are unmatched. In other words, replace each i+1 by a left (open) parenthesis and eachiby a right (closed) parenthesis and match left and right parenthesis.

Pick the rightmost unmatchedi. Convert it to ani+1. (If there is no unmatched i, theni(F )=F.) The result is a collection of row entries which differ from those of read(F )in precisely one entry. Use the procedureρdescribed above to map this collection of rows to a unique SSAF. (This map is well-defined for our collection of row entries because the row directly below the rightmost unmatchedieither does not contain the entryi or contains both the entryi and the entryi+1.) The resulting SSAF is_i(F )=F . We must show that_i((T ))=(f˜_i(T )).

Recall that the mapρis a bijection between semi-skyline augmented fillings and row-strict plane partitions which preserves the entries in each row. The inverse of ρsends the entries in ther^{t h}row of an SSAFF to ther^{t h}row of a row-strict plane partition in decreasing order. The reading word for a row-strict plane partition is given by reading the rows from left to right, top to bottom. The matching procedure on this word and therefore the operatorf_i are the same as those applied to the column word of an SSYT. This means that the resulting crystal graph is the image of the ordinary crystal graph under the weight-preserving bijection between SSYT of a fixed shape and row-strict plane partitions of the transposed shape. Therefore it is enough to show

(11)

that the following diagram commutes for all row-strict plane partitionsP.

P

f_i

ρ

P

ρ

F

i

F

We claim that if the rightmost unmatchediinF appears in ther^{t h}row ofF, then the rightmost unmatchediinρ⁻¹(F )appears in ther^{t h}row ofρ⁻¹(F ). Moreover, if there is no unmatchediinF, then there is no unmatchediinρ(F ).

Notice that the first step in the procedure for matching entries inFis to match each pair of entries{i, i+1}appearing in the same row ofF. These entries will also appear in the same row ofρ(F ). Since the row entries inρ(F )appear in strictly decreasing order, thei+1 appears first in the reading word. Therefore this pair of entries will be matched inρ(F ). Once these entries are matched, the remaining occurrences of i andi+1 appear in the same order in the reading word forF as in the reading word forρ(F ). Therefore the rightmost unmatchediappears in the same row ofF as inρ(F ), and if eachiis matched inF then eachiis matched inρ(F ).

To see that the proposition follows from this claim, first consider the situation in which there is no unmatchediinF. The claim implies that there is no unmatchedi inρ(F ). Then_i(F )=F andf_i(T )=T. The diagram commutes sinceF =ρ(T ).

Next leti_r be the rightmost unmatchediinF, appearing in ther^{t h}row ofF. Ther^{t h} row of_i(F )is the only row whose entries are different fromF. Theiin this row was changed to ani+1. Similarly, ther^{t h}row off_i(ρ(F ))is the only row which whose entries are different fromρ(F ), and the difference is anireplaced by ani+1.

Thereforefi(ρ(F ))is the image ofi(F )underρand the diagram commutes.

We need one additional Lemma to prove Theorem1.1.

Lemma 4.1 Let F ∈ SSAF (γ ). Then either _i(F )∈ SSAF (γ ) or _i(F )∈ SSAF (s_iγ ).

Proof Assume thatF ∈SSAF (γ ). If_i(F )=F, then_i(F )∈SSAF (γ ). We must prove that when an unmatchediis sent toi+1, the resulting semi-skyline augmented filling is either inSSAF (γ )or inSSAF (s_iγ ). Leti_r denote the rightmost unmatched iinF, whereris the row in whichi_r appears. Similarly, let(i+1)r denote thei+1 which replacesir ini(F ).

Ifi_r appears in F immediately above an entry greater than i, then (i+1)r is mapped to the same position byρ. In this case the remaining entries of ther^{t h}row are mapped to the same positions in_i(F )as in F. If the (r+1)^{t h}row does not contain ani+1, its entries are sent to the same positions as inF and therefore the shape ofi(F )is equal to the shape of F. If there exists ani+1=(i+1)r+1in the(r+1)^{t h}row ofF, then there must also be ani=ir+1sinceir is unmatched.

The only situation in which the placement of this row into_i(F )differs from its placement inF is if(i+1)r+1appears to the right ofi_r inF. In this case(i+1)r+1

(12)

would be inserted on top of(i+1)r andi_r₊₁would replace(i+1)r+1. The remaining entries of rowr+1 would be inserted into the same positions in_i(F )as inF. The remaining rows of_i(F )are inserted into the same positions as inF unless row r+2 contains aniand ani+1. If rowr+2 does contain bothiandi+1, then a similar argument shows that eitheri_r₊₂and(i+1)r+2appear in the same positions as inF or switch positions ini(F ). Repeating this argument for each row implies that the shape ofi(F )is the same as that ofF.

Ifir appears inF immediately above another entry equal toi, denote this entry byir−1. Sinceir is the rightmost unmatchediinread(F ), rowr−1 must contain ani+1=(i+1)r−1. This entry must appear to the right ofir−1, for otherwiseir

would appear on top of(i+1)r−1inF. In this case the entry immediately belowi_r₋1

must be equal toi=i_r₋2 (regardless of the column heights) in order to satisfy the inversion conditions of an SSAF. Then there must be ani+1 to the right ofi_r₋2in this row as well. Applying the same arguments inductively to each row ofF implies that there must be aniand ani+1 in the first row ofF. The semi-skyline augmented filling conditions imply that an entryαin the first row ofF must appear in theα^{t h} column ofF [10]. Therefore the entriesiandi+1 in the first row ofF must lie in thei^{t h}and(i+1)^{t h}columns respectively. Thusi_r₋₁appears in thei^{t h}column ofF and(i+1)r−1appears in the(i+1)^{t h}column. The entry(i+1)r therefore passes thei^{t h}column and is placed into the(i+1)^{t h}column of_i(F ).

If there is no entry on top of(i+1)r−1inF, then all other entries in rowr ofF are placed in the same positions ini(F ). If an entry appears in the(i+1)^{t h}column ofF, then this entry will be inserted onto thei^{t h}column ini(F ). In both cases, the entries in thei^{t h}and(i+1)^{t h}column are permuted and all other entries remain the same.

Letβ be the (possibly empty) entry which lies in the(i+1)^{t h}column of ther^{t h} row ofF and hence thei^{t h}column of ther^{t h}row of_i(F ). This entryβ must be less thani. If there is noi+1 in rowr+1 ofF, then the entries on top ofβ and i+1 in_i(F )might be permuted but the other entries in rowr+1 of_i(F )retain the same positions they held inF. In this case the remaining rows are the same as in F up to a permutation of the entries in thei^{t h}and(i+1)^{t h}column and hence_i(F ) is either inSSAF (γ )orSSAF (s_i(γ )). If there is ani+1 in rowr+1 ofF, then there is aniin rowr+1 as well sincei_r is unmatched inF. Theni_r₊₁must lie in thei^{t h}column ofF and(i+1)r+1must lie to the right ofi_r₊₁. Therefore(i+1)r+1

is placed on top of(i+1)r in_i(F )andi_r₊₁is placed in the cell which contained (i+1)r+1inF. If an entry appears on top ofβinF, this same entry appears on top ofβ ini(F ). All other entries in rowr+1 ofi(F )remain in the same positions as inF.

The entries in rowr+2 follow a similar pattern. If there is ani+1=(i+1)r+2

in this row ofF, there must also be an i=ir+2. Thenir+2occupies ini(F )the position occupied by(i+1)_r+2inF. The entry in the(i+1)^{t h}column ofF occupies thei^{t h}column of_i(F ), and(i+1)_r+2occupies the(i+1)^{t h}column. Otherwise the only entries affected are the entries in thei^{t h}and(i+1)^{t h}column, which are possibly permuted. Eventually a row is reached which does not contain ani+1. At this point the argument in the previous paragraph implies that the resulting shape of

_i(F )is eitherγ ors_i(γ ).

(13)

Consider a semi-standard Young tableau T whose weight appears in U(ω, λ).

We abuse notation and write T ∈ U(ω, λ). If s_iω is longer than ω, then Las- coux and Schützenberger’s definition off_i implies that eitherf_i(T )∈U(ω, λ)or f_i(T )∈U(s_iω, λ). To see that the objects under consideration are the same, we must show that the operatorsf_i act the same as the operators_i.

4.2 Proof of Theorem1.1

We are now ready to prove that the Demazure atomsU(ω, λ)are equivalent to the polynomialsEω(λ)(X;0,0). We abuse notation by writingF∈Eω(λ)(X;0,0)when- everF is an SSAF of shapeω(λ). This abuse is justified by the fact that the monomial x^F appears inEω(λ)(X;0,0).

Proof Fix a partitionλand argue by induction on the length of the permutationωin U(ω, λ). First letωbe the identity. ThenU(ω, λ)is the dominant monomial. Consider λas a composition ofnintonparts by adding zeros to the right if necessary. Each cella in the first column must haveF (a)=1, since the columns ofF are weakly increasing from top to bottom and the basement entry in this column is 1. Each cell bin the second column must haveF (b)≤2 since the columns are weakly increasing when read top to bottom and the basement entry is 2. Each cell in the second column attacks the cell immediately to its left, and therefore cannot contain the entry 1. This means that each cell in the second column must contain the entry 2. Continuing inductively, we see that for alli, each cellcin thei^{t h}column must haveF (c)=i. To see that this is indeed an SSAF, we only need to check typeAtriples. But if the two cells in the left-hand column are equal and less than the cell in the right-hand column, the result is a typeAinversion triple. Therefore, theEλ(X;0,0)=U(id, λ).

Next assume thatU(ω, λ)=E_ω(λ)(X;0,0), for all permutationsωof length less than or equal tok, for somek≥0. (Hereω(λ)is the composition obtained by applying the permutationωto the columns ofλwhenλis considered as a composition of nintonparts.) Then each permutation of lengthk+1 is obtained from a permutation of lengthkby applying an elementary transpositions_i. Letτ be an arbitrary such permutation of lengthk+1 such thatτ =s_iωfor someωof lengthk. The monomials inU(τ, λ)are obtained from the monomials ofU(ω, λ)whose image under (possibly multiple applications of)θ˜_i is not a monomial ofU(ω, λ). LetT be an arbitrary SSYT ofU(s_iω, λ)such thatT =(θ˜_i)^m(S)for some SSYTS∈U(ω, λ)and some positive integerm.

Repeated application of Proposition4.1implies that((θ˜_i)^m(S))=(_i)^m((S)).

Since (S) ∈ E_ω(λ)(X;0,0) by the inductive hypothesis, Lemma 4.1 implies that either (_i)^m((S))∈E_ω(λ)(X;0,0) or (_i)^m((S))∈E_s_i_ω(λ)(X;0,0). If (i)^m((S))∈Eω(λ)(X;0,0), then ((θ˜i)^m(S))∈Eω(λ)(X;0,0), so (θ˜i)^m(S)∈ U(ω, λ)becauseU(ω, λ)=Eω(λ)(X;0,0)by the inductive hypothesis. This contra- dicts the assumption that(θ˜_i)^m(S)∈U(s_iω, λ), so(_i)^m((S))∈E_s_i_ω(λ)(X;0,0).

Therefore,U(s_iω, λ)⊆E_s_i_ω(λ)(X;0,0), and soU(τ, λ)⊆E_{τ (λ)}(X;0,0).

To see the reverse containment, letF be a filling represented by a monomial in E_s_i_ω(λ)(X;0,0). Then F is an SSAF of shape γ =s_iω(λ)=τ (λ). Consider the smallestj such thatγ_j< γ_j₊₁. (Such aj must exist, for otherwiseF∈E_λ(X;0,0).)

(14)

The typeB inversion condition implies that all of the entries in columnj must be equal toj and the lowestγ_j+1 entries in columnj+1 must be equal toj+1. The entryj cannot appear in rowγ_j+1 ofF, because if it did it would be to the right of thej^{t h} column and therefore attack thej in rowγ_j. This implies that the entry j+1 in rowγj+1 is unmatched, and in fact it is the rightmost unmatchedj+1 in read(F ), since each row below rowγj+1 contains both aj and aj+1.

Consider the procedure which sends the leftmost unmatchedj+1 inF to ajand then inserts the resulting row entries back into an SSAF. This is precisely the inverse of the map_j. Lemma4.1implies thatF =⁻_j¹(F )either has shapeτ (λ)or shape σ (λ)for some permutationσ of lengthk such thatsiσ=τ. If F has shapeσ (λ), then the inductive hypothesis implies thatF =(T )for some SSYTT ∈U(σ, λ).

Then_j(F )=(θ˜_j)(T )by Proposition4.1. Since(θ˜_j)(T )is either inU(σ, λ)or U(τ, λ)andF =(θ˜_j)(T )is not inU(σ, λ), thenF=(θ˜_j)(T )∈U(τ, λ).

Apply⁻_j¹until F^(m)=(⁻_j¹)^(m)(F )has shapeσ (λ). This occurs for somem less than or equal to the number of unmatched(j+1)sinF. To see this, letmbe the number of unmatched(j+1)sinF and assume thatF^(m⁻¹⁾=(⁻_j¹)^(m⁻¹⁾(F ) has shapeτ. Sinceτ =σ, columnj is strictly shorter than columnj +1. Apply_j toF^(m⁻¹⁾to map thej +1 in rowγ_j+1 toj =j₀. Thenj₀lies in thej^{t h}column ofF^(m) but the other entries in this row ofF^(m) remain in the same positions as in F^(m⁻¹⁾. This arrangement of the entries in rowγ_j+1 implies that columnj+1 of F^(m)has heightγj, and hence the shape ofF^(m)is different from the shape ofF^(m⁻¹⁾. Since the shape ofF^(m)must be equal to eithersjσ orσ, the shape ofF^(m)must be σ. The inductive hypothesis implies thatF^(m)=(T )for someT ∈U(σ, λ), since σ has length less than that ofτ=s_jσ. Proposition4.1implies thatF=(θ˜_j)^m(T ), which means thatF ∈U(τ, λ). ThereforeE_{τ (λ)}(X;0,0)⊆U(τ, λ).

The above shows thatE_{τ (λ)}(X;0,0)=U(τ, λ)for an arbitrary choice of permu- tationτ of length k+1. Therefore it is true for all permutations of lengthk+1.

Applying the principle of mathematical induction completes the proof.

Theorem1.1provides a non-inductive construction of the Demazure atoms. In particular, given a partitionλnand a permutationω∈Sn, first considerλas a composition ofnintonparts by appending zeros if necessary. Then apply the permutation ωto the columns ofλto obtain the shapeω(λ). Finally, determine all semi-skyline augmented fillings of the shapeω(λ). The monomials given by the weights of these SSAFs are the monomials appearing in the Demazure atomU(ω, λ).

5 Computation of right keys

Recall that the Demazure atomU(ω, λ)is equal to the sum of the weights of all SSYT with right keyK(ω, λ). Therefore all of the SSYT which map to an SSAF of shape ω(λ)have the same right key,K(ω, λ). Theorem1.1provides a simple method to determine the right key of a semi-standard Young tableau. The super SSAF (denoted super(γ )) of a compositionγis the SSAF of shapeγwhosei^{t h}column contains only the entriesi. The weight of this SSAF is the dominant monomial in the polynomial U(ω, λ)under lexicographic ordering.

(15)

Corollary 5.1 Given an arbitrary SSYT T, let γ be the shape of (T ). Then K₊(T )=key(γ ).

Proof We must show that the map:SSY T →SSAF sends a keyT to super(γ ), whereγis the composition content(T ). We prove this by induction on the number of columns ofT. IfT has only one column,C1=α1α2. . . αl, then this column maps to a fillingF with one row such that theα_i^{t h}column contains the entryαi for eachi.

This is precisely super(content(T )).

Next assume that(T )=super(content(T ))for all keysT with less than or equal tom−1 columns. LetSbe a key withmcolumns. After the insertion of the rightmost m−1 columns, the figure is super(content(S\C₁))by the inductive hypothesis. We must show that the insertion of the leftmost column produces super(content(S)).

Let super(content(S\C1))have shapeγ=(γ1, γ2, . . . , γ_n). For eachi, ifγ_i=0, theni=αis an entry inC1sinceSis a key. Before the insertion ofC1, each of the cells in thei^{t h}column each contain the entryi. Thereforeαcannot be bumped further in the reading order than the cell in rowγi+1 of columni. This implies that each of the non-zero entries ofγ inC₁must appear at or above their respective columns, and the pigeon-hole principle therefore implies that each appears at the top of its column.

The new columns are created by the entries inC₁which do not appear in any of the subsequent columns ofS. Therefore the result is indeed the SSAF super(content(S)).

Since super(ω(λ))∈U(ω, λ) andU(ω, λ)is a collection of all SSYT with the same right key, each SSYT which maps to a SSAF of shapeω(λ)has the same right key as super(ω(λ)). Therefore, ifT ∈U(ω, λ), thenK₊(T )=key(ω(λ)).

Corollary 5.1 provides a quick procedure for calculating the right key of any SSYT. In particular, if T is an arbitrary SSYT, then the right key of T is given by key(shape((T ))). (See Figure 4 for an example.) This calculation facilitates the computation of Demazure atoms and Demazure characters. Letγ be a composition which rearranges a partitionλ, so thatγ =ω(λ). The key polynomial κ_γ is given by the weights of all semi-standard Young tableauxT of shape λ such that K₊(T )≤key(γ )[9]. Therefore

κ_γ=

α≤γ

N S_α,

whereα≤γ if and only ifω1(α)=λfor some permutationω1such thatω1≤ωin the Bruhat order.

Fig. 4 Computation of the key of an SSYT