Chains in the Bruhat order

DOI 10.1007/s10801-008-0125-4

Chains in the Bruhat order

Alexander Postnikov·Richard P. Stanley

Received: 30 August 2006 / Accepted: 29 January 2008 / Published online: 15 March 2008

© Springer Science+Business Media, LLC 2008

Abstract We study a family of polynomials whose values express degrees of Schu- bert varieties in the generalized complex flag manifoldG/B. The polynomials are given by weighted sums over saturated chains in the Bruhat order. We derive sev- eral explicit formulas for these polynomials, and investigate their relations with Schubert polynomials, harmonic polynomials, Demazure characters, and general- ized Littlewood-Richardson coefficients. In the second half of the paper, we study the classical flag manifold and discuss related combinatorial objects: flagged Schur polynomials, 312-avoiding permutations, generalized Gelfand-Tsetlin polytopes, the inverse Schubert-Kostka matrix, parking functions, and binary trees.

Keywords Flag manifold·Schubert varieties·Bruhat order·Saturated chains· Harmonic polynomials·Grothendieck ring·Demazure modules·Schubert polynomials·Flagged Schur polynomials·312-avoiding permutations·Kempf elements·Vexillary permutations·Gelfand-Tsetlin polytope·Toric degeneration· Parking functions·Binary trees

1 Introduction

The complex generalized flag manifoldG/Bembeds into projective spaceP(V_λ), for an irreducible representationV_λ ofG. The degree of a Schubert varietyX_w⊂G/B

A.P. was supported in part by National Science Foundation grant DMS-0201494 and by Alfred P. Sloan Foundation research fellowship. R.S. was supported in part by National Science Foundation grant DMS-9988459.

A. Postnikov (

Department of Mathematics, M.I.T., Cambridge, MA 02139, USA e-mail:apost@math.mit.edu

R.P. Stanley

e-mail:rstan@math.mit.edu

in this embedding is a polynomial function ofλ. The aim of this paper is to study the family of polynomialsD_winr=rank(G)variables that express degrees of Schubert varieties. According to Chevalley’s formula [6], also known as Monk’s rule in typeA, these polynomials are given by weighted sums over saturated chains fromidtowin the Bruhat order on the Weyl group. These weighted sums over saturated chains ap- peared in Bernstein-Gelfand-Gelfand [2] and in Lascoux-Schützenberger [26]. Stem- bridge [34] recently investigated these sums in the case whenw=w_◦is the longest element in the Weyl group. The valueDw(λ)is also equal to the leading coefficient in the dimension of the Demazure modulesVkλ,w, ask→ ∞.

The polynomialsDw are dual to the Schubert polynomials Sw with respect a certain natural pairing on the polynomial ring. They form a basis in the space of W-harmonic polynomials. We show that Bernstein-Gelfand-Gelfand’s results [2] eas- ily imply two different formulas for the polynomialsD_w. The first “top-to-bottom”

formula starts with the top polynomial D_w◦, which is given by the Vandermonde product. The remaining polynomialsD_w are obtained fromD_w◦ by applying differ- ential operators associated with Schubert polynomials. The second “bottom-to-top”

formula starts withD_id=1. The remaining polynomialsD_w are obtained fromD_id by applying certain integration operators. Duan’s recent result [9] about degrees of Schubert varieties can be deduced from the bottom-to-top formula.

Let c^w_u,v be the generalized Littlewood-Richardson coefficients defined as the structure constants of the cohomology ring ofG/Bin the basis of Schubert classes.

The coefficientsc_u,v^w are related to the polynomialsDwin two different ways. Define a more general collection of polynomialsDu,was sums over saturated chains fromu towin the Bruhat order with similar weights. (In particular,Dw=Did,w.) The poly- nomialsDu,w extend theDwin the same way as the skew Schur polynomials extend the usual Schur polynomials. The expansion coefficients ofD_u,w in the basis ofD_v’s are exactly the generalized Littlewood-Richardson coefficients:D_u,w=

vc^w_u,vD_v. On the other hand, we haveD_w(y+z)=

u,vc^w_u,vD_u(y)D_w(z), whereD_w(y+z) denote the polynomial in pairwise sums of two setsyandzof variables.

We pay closer attention to the Lie type A case. In this case, the Weyl group is the symmetric groupW =S_n. Schubert polynomials for vexillary permutations, i.e., 2143-avoiding permutations, are known to be given by flagged Schur polynomi- als. From this we derive a more explicit formula for the polynomialsD_w for 3412- avoiding permutationswand, in particular, an especially nice determinant expression forDw in the case whenwis 312-avoiding.

It is well-known that the number of 312-avoiding permutations inSn is equal to the Catalan numberCn= _n+¹_12n

n

. Actually, these permutations are exactly the Kempf elements studied by Lakshmibai [23] (though her definition is quite differ- ent). We show that the charactersch(Vλ,w)of Demazure modules for 312-avoiding permutations are given by flagged Schur polynomials. (Here flagged Schur polyno- mials appear in a different way than in the previous paragraph.) This expression can be geometrically interpreted in terms of generalized Gelfand-Tsetlin polytopesPλ,w

studied by Kogan [18]. The Demazure characterch(V_λ,w)equals a certain sum over lattice points inPλ,w, and thus, the valueD_w(λ) equals the normalized volume of Pλ,w. The generalized Gelfand-Tsetlin polytopesPλ,ware related to the toric degen- eration of Schubert varietiesX_w constructed by Gonciulea and Lakshmibai [14].

One can expand Schubert polynomials as nonnegative sums of monomials using RC-graphs. We call the matrixK of coefficients in these expressions the Schubert- Kostka matrix, because it extends the usual Kostka matrix. It is an open problem to find a subtraction-free expression for entries of the inverse Schubert-Kostka matrix K⁻¹. The entries ofK⁻¹are exactly the coefficients of monomials in the polynomi- alsD_w normalized by a product of factorials. On the other hand, the entries ofK⁻¹ are also the expansion coefficients of Schubert polynomials in terms of standard ele- mentary monomials. We give a simple expression for entries ofK⁻¹corresponding to 312-avoiding permutations and 231-avoiding permutations. Actually, these special entries are always equal to±1, or 0.

We illustrate our results by calculating the polynomialD_wfor the long cyclew= (1,2, . . . , n)∈S_n in five different ways. First, we show thatD_w equals a sum over parking functions. This polynomial appeared in Pitman-Stanley [29] as the volume of a certain polytope. Indeed, the generalized Gelfand-Tsetlin polytopePλ,wfor the long cyclew, which is a 312-avoiding permutation, is exactly the polytope studied in [29]. Then the determinant formula leads to another simple expression for Dw

given by a sum of 2ⁿ monomials. Finally, we calculate Dw by counting saturated chains in the Bruhat order and obtain an expression for this polynomial as a sum over binary trees.

The general outline of the paper follows. In Section2, we give basic notation re- lated to root systems. In Section3, we recall classical results about Schubert calculus forG/B. In Section4, we define the polynomials Dw andDu,w and discuss their geometric meaning. In Section5, we discuss the pairing on the polynomial ring and harmonic polynomials. In Section6, we prove the top-to-bottom and the bottom-to- top formulas for the polynomialDw and give several corollaries. In particular, we show how these polynomials are related to the generalized Littlewood-Richardson coefficients. In Section7, we give several examples and deduce Duan’s formula. In Section8, we recall a few facts about the K-theory ofG/B. In Section9, we give a simple proof of the product formula forDw_◦. In Section10, we mention a formula for the permanent of a certain matrix. The rest of the paper is concerned with the type Acase. In Section 11, we recall Lascoux-Schützenberger’s definition of Schubert polynomials. In Section12, we specialize the results of the first half of the paper to typeA. In Section13, we discuss flagged Schur polynomials, vexillary and dominant permutations, and give a simple formula for the polynomialsDw, for 312-avoiding permutations. In Section14, we give a simple proof of the fact that Demazure charac- ters for 312-avoiding permutations are given by flagged Schur polynomials. In Sec- tion15, we interpret this claim in terms of generalized Gelfand-Tsetlin polytopes.

In Section17, we discuss the inverse of the Schubert-Kostka matrix. In Section18, we discuss the special case of the long cycle related to parking functions and binary trees.

2 Notations

LetGbe a complex semisimple simply-connected Lie group. Fix a Borel subgroup Band a maximal torusT such thatG⊃B⊃T. Lethbe the corresponding Cartan

subalgebra of the Lie algebragof G, and letr be its rank. Let⊂h^∗ denote the corresponding root system. Let⁺⊂be the set of positive roots corresponding to our choice ofB. Thenis the disjoint union of⁺and⁻= −⁺. LetV ⊂h^∗be the linear space overQspanned by. Letα1, . . . , αr ∈⁺be the associated set of simple roots. They form a basis of the spaceV. Let(x, y)denote the scalar product onV induced by the Killing form. For a rootα∈, the corresponding coroot is given byα^∨=2α/(α, α). The collection of coroots forms the dual root system^∨.

The Weyl groupW⊂Aut(V )of the Lie groupGis generated by the reflectionss_α: y→y−(y, α^∨) α, forα∈andy∈V. Actually, the Weyl groupW is generated by simple reflectionss₁, . . . , s_r corresponding to the simple roots,s_i=s_αi, subject to the Coxeter relations:(s_i)²=1 and(s_is_j)^mij =1, wherem_ij is half the order of the dihedral subgroup generated bys_i ands_j.

An expression of a Weyl group elementwas a product of generatorsw=s_i1· · ·s_il of minimal possible lengthlis called a reduced decomposition forw. Its lengthlis called the length ofwand denoted(w). The Weyl groupWcontains a unique longest elementw_◦of maximal possible length(w_◦)= |⁺|.

The Bruhat order on the Weyl groupW is the partial order relation “≤” which is the transitive closure of the following covering relation: uw, for u, w∈W, wheneverw=u sα, for someα∈⁺, and(u)=(w)−1. The Bruhat order has the unique minimal element id and the unique maximal elementw_◦. This order can also be characterized, as follows. For a reduced decompositionw=s_i1· · ·s_il ∈W andu∈W,u≤wif and only if there exists a reduced decompositionu=s_j1· · ·s_js such thatj1, . . . , js is a subword ofi1, . . . , il.

Let denote the weight lattice= {λ∈V |(λ, α^∨)∈Zfor anyα∈}. It is generated by the fundamental weightsω₁, . . . , ω_rthat form the dual basis to the basis of simple coroots, i.e.,(ω_i, α_j^∨)=δ_ij. The set⁺of dominant weights is given by ⁺= {λ∈|(λ, α^∨)≥0 for anyα∈⁺}. A dominant weightλis called regular if(λ, α^∨) >0 for anyα∈⁺. Letρ=ω1+ · · · +ωr=¹₂

α∈⁺αbe the minimal regular dominant weight.

3 Schubert calculus

In this section, we recall some classical results of Borel [5], Chevalley [6], De- mazure [8], and Bernstein-Gelfand-Gelfand [2].

The generalized flag variety G/B is a smooth complex projective variety. Let H^∗(G/B)=H^∗(G/B,Q)be the cohomology ring ofG/Bwith rational coefficients.

LetQ[V^∗] =Sym(V )be the algebra of polynomials on the spaceV^∗ with rational coefficients. The action of the Weyl groupW on the spaceV induces aW-action on the polynomial ringQ[V^∗]. According to Borel’s theorem [5], the cohomology of G/Bis canonically isomorphic¹to the quotient of the polynomial ring:

H^∗(G/B)Q[V^∗]/IW, (3.1)

1The isomorphism is given byc₁(Lλ)→λ(modIW), wherec₁(Lλ)is the first Chern class of the line bundleLλ=G×BC−λoverG/B, forλ∈⁺.

whereIW=

f ∈Q[V^∗]^W|f (0)=0

is the ideal generated byW-invariant polyno- mials without constant term. Let us identify the cohomology ringH^∗(G/B)with this quotient ring. For a polynomialf∈Q[V^∗], letf¯=f (mod IW) be its coset modulo IW, which we view as a class in the cohomology ringH^∗(G/B).

One can construct a linear basis ofH^∗(G/B)using the following divided differ- ence operators (also known as the Bernstein-Gelfand-Gelfand operators). For a root α∈, letAα:Q[V^∗] →Q[V^∗]be the operator given by

A_α:f→ f−sα(f )

α . (3.2)

Notice that the polynomial f −sα(f )is always divisible byα. The operatorsAα

commute with operators of multiplication byW-invariant polynomials. Thus theAα

preserve the idealIW and induce operators acting onH^∗(G/B), which we will de- note by the same symbolsA_α.

LetA_i=A_αi, fori=1, . . . , r. The operatorsA_i satisfy the nilCoxeter relations A_iA_jA_i· · ·

m_ijterms

=A_jA_iA_j· · ·

m_ijterms

and (A_i)²=0.

For a reduced decompositionw=s_i1· · ·s_il ∈W, defineA_w =A_i1· · ·A_il. The op- erator A_w depends only on w∈W and does not depend on a choice of reduced decomposition.

Let us define the Schubert classesσ_w∈H^∗(G/B),w∈W, by σ_w◦ = |W|⁻¹

α∈⁺

α (modIW), for the longest elementw_◦∈W;

σ_w=A_w−1w_◦(σ_w◦), for anyw∈W.

The classes σ_w have the following geometrical meaning. Let X_w =BwB/B, w ∈ W, be the Schubert varieties in G/B. According to Bernstein-Gelfand- Gelfand [2] and Demazure [8], σw= [Xw_◦w] ∈H^2(w)(G/B)are the cohomology classes of the Schubert varieties. They form a linear basis of the cohomology ring H^∗(G/B). In the basis of Schubert classes, the divided difference operators can be expressed, as follows (see [2]):

A_i(σ_w)=

σws_i if(wsi)=(w)−1,

0 if(ws_i)=(w)+1. (3.3)

Remark 3.1 There are many possible choices for polynomial representatives of the Schubert classes. In type An−1, Lascoux and Schützenberger [25] introduced the polynomial representatives, called the Schubert polynomials, obtained from the monomial x₁ⁿ⁻¹x₂ⁿ⁻²· · ·x_n−1 by applying the divided difference operators. Here x₁, . . . , x_n are the coordinates in the standard presentation for type A_n−1 roots α_ij =x_i−x_j (see [17]). Schubert polynomials have many nice combinatorial prop- erties; see Section11below.

Forσ ∈H^∗(G/B), let σ =

G/Bσ be the coefficient of the top class σ_w◦ in the expansion ofσ in the Schubert classes. Thenσ·θ is the Poincaré pairing on H^∗(G/B). In the basis of Schubert classes the Poincaré pairing is given by

σu·σw =δu, w_◦w. (3.4)

The generalized Littlewood-Richardson coefficientsc^w_u,v, are given by σu·σv=

w∈W

c^w_u,vσw, foru, v∈W.

Let c_u,v,w = σ_u·σ_v·σ_w be the triple intersection number of Schubert varieties.

Then, according to (3.4), we havec_u,v^w =c_u,v,w◦w.

For a linear formy ∈V ⊂Q[V^∗], lety¯∈H^∗(G/B) be its coset² moduloIW. Chevalley’s formula [6] gives the following rule for the product of a Schubert class σ_w,w∈W, withy:¯

¯

y·σw=

(y, α^∨) σws_α, (3.5)

where the sum is over all rootsα∈⁺such that(w s_α)=(w)+1, i.e., the sum is over all elements inW that coverwin the Bruhat order. The coefficients(y, α^∨), which are associated to edges in the Hasse diagram of the Bruhat order, are called the Chevalley multiplicities. Figure1shows the Bruhat order on the symmetric group W=S3 with edges of the Hasse diagram marked by the Chevalley multiplicities, whereY1=(y, α₁^∨)andY2=(y, α^∨₂).

We have,σid= [G/B] =1. Chevalley’s formula implies thatσs_i = ¯ωi (the coset of the fundamental weightω_i).

4 Degrees of Schubert varieties

Fory∈V, letm(uus_α)=(y, α^∨)denote the Chevalley multiplicity of a covering relationuu s_α in the Bruhat order on the Weyl groupW. Let us define the weight

Fig. 1 The Bruhat order onS₃ marked with the Chevalley multiplicities

2Equivalently,y¯=c₁(Lλ), ify=λis in the weight lattice.

m_C=m_C(y)of a saturated chainC=(u₀u₁u₂· · ·u_l)in the Bruhat order as the product of Chevalley multiplicities:

mC(y)= l i=1

m(ui−1ui).

Then the weightmC∈Q[V]is a polynomial function ofy∈V.

For two Weyl group elements u, w∈W, u≤w, let us define the polynomial Du,w(y)∈Q[V]as the sum

D_u,w(y)= 1 ((w)−(u))!

C

m_C(y) (4.1)

over all saturated chainsC=(u₀u₁u₂· · ·u_l)in the Bruhat order fromu₀=u tou_l =w. In particular,D_w,w=1. LetD_w=Did,w. It is clear from the definition thatD_wis a homogeneous polynomial of degree(w)andD_u,wis homogeneous of degree(w)−(u).

Example 4.1 ForW=S3, we haveDid,231=¹₂(Y1Y2+Y2(Y1+Y2))andD132,321=

1

2((Y₁+Y₂)Y₁+Y₁Y₂), whereY₁=(y, α₁^∨)andY₂=(y, α₂^∨)(see Figure1).

According to Chevalley’s formula (3.5), the values of the polynomialsD_u,w(y) are the expansion coefficients in the following product in the cohomology ring H^∗(G/B):

[e^y] ·σ_u=

w∈W

D_u,w(y)·σ_w, for anyy∈V , (4.2) where[e^y] :=1+ ¯y+ ¯y²/2! + ¯y³/3! + · · · ∈H^∗(G/B). Note that[e^y]involves only finitely many nonzero summands, becauseH^k(G/B)=0, for sufficiently largek.

Equation (4.2) is actually equivalent to definition (4.1) of the polynomialsDu,w. The values of the polynomialsDw(λ)at dominant weightsλ∈⁺ have the fol- lowing natural geometric interpretation. Forλ∈⁺, letVλbe the irreducible repre- sentation of the Lie groupGwith the highest weightλ, and letv_λ∈V_λbe a highest weight vector. Lete:G/B→P(V_λ)be the map given bygB→g(v_λ), forg∈G.

If the weight λ is regular, then e is a projective embedding G/B →P(V_λ). Let w∈W be an element of lengthl=(w). Let us define theλ-degree deg_λ(X_w)of the Schubert varietyX_w⊂G/Bas the number of points in the intersection ofe(X_w) with a generic linear subspace inP(V_λ)of complex codimensionl. The pull-back of the class of a hyperplane in H²(P(V_λ)) is λ¯ =c1(Lλ)∈H²(G/B). Then the λ-degree of Xw is equal to the Poincaré pairing deg_λ(Xw)=

[Xw] · ¯λ^l

. In other words, deg_λ(Xw)equals the coefficient of the Schubert classσw, which is Poincaré dual to[Xw] =σw_◦w, in the expansion ofλ¯^l in the basis of Schubert classes. Cheval- ley’s formula (3.5) implies the following well-known statement; see, e.g., [4].

Proposition 4.2 Forw∈W and λ∈⁺, the λ-degree deg_λ(X_w)of the Schubert varietyX_wis equal to the sum

m_C(λ)over saturated chainsCin the Bruhat order

from id tow. Equivalently,

deg_λ(X_w)=(w)! ·D_w(λ).

Ifλ=ρ, we will call deg(Xw)=deg_ρ(Xw)simply the degree ofXw.

5 Harmonic polynomials

We discuss harmonic polynomials and the natural pairing on polynomials defined in terms of partial derivatives. Constructions in this section are essentially well-known;

cf. Bergeron-Garsia [1].

The space of polynomialsQ[V]is the graded dual toQ[V^∗], i.e., the correspond- ing finite-dimensional graded components are dual to each other.

Let us pick a basis v₁, . . . , v_r in V, and let v₁^∗, . . . , v_r^∗ be the dual basis in V^∗. Forf ∈Q[V^∗]andg∈Q[V], let f (x1, . . . , x_r)=f (x1v^∗₁+ · · · +x_rv_r^∗)and g(y1, . . . , y_r)=g(y1v1+ · · · +y_rv_r)be polynomials in the variablesx1, . . . , x_r and y1, . . . , yr, correspondingly. For eachf ∈Q[V^∗], let us define the differential opera- torf (∂/∂y)that acts on the polynomial ringQ[V]by

f (∂/∂y):g(y1, . . . , yr)−→f (∂/∂y₁, . . . , ∂/∂y_r)·g(y1, . . . , yr),

where∂/∂y_i denotes the partial derivative with respect toyi. The operatorf (∂/∂y) can also be described without coordinates as follows. Letdv:Q[V] →Q[V]be the differentiation operator in the direction of a vectorv∈V given by

d_v:g(y)→ d

d tg(y+t v) t=0

. (5.1)

The linear mapv→d_vextends to the homomorphismf →d_f from the polynomial ringQ[V^∗] =Sym(V )to the ring of operators onQ[V]. Thend_f =f (∂/∂y).

One can extend the usual pairing between V andV^∗ to the following pairing between the spacesQ[V^∗]andQ[V]. Forf ∈Q[V^∗]andg∈Q[V], let us define the D-pairing(f, g)_Dby

(f, g)D=CT(f (∂/∂y)·g(y))=CT(g(∂/∂x)·f (x)), where the notation CT means taking the constant term of a polynomial.

A graded basis of a polynomial ring is a basis that consists of homogeneous poly- nomials. Let us say that a gradedQ-basis{f_u}u∈U inQ[V^∗]is D-dual to a graded Q-basis{g_u}u∈UinQ[V]if(f_u, g_v)_D=δ_u,v, for anyu, v∈U.

Example 5.1 Letx^a=x₁^a1· · ·x_r^ar andy^(a)=^y_a^a1₁¹_! · · ·^y_a^rar_r!, fora=(a1, . . . , a_r). Then the monomial basis{x^a}ofQ[V^∗]is D-dual to the basis{y^(a)}ofQ[V].

This example shows that the D-pairing gives a non-degenerate pairing of corre- sponding graded components ofQ[V^∗]andQ[V]and vanishes on different graded

components. Thus, for a graded basis inQ[V^∗], there exists a unique D-dual graded basis inQ[V]and vice versa.

For a graded spaceA=A⁰⊕A¹⊕A²⊕ · · ·, letA_∞be the space of formal series a₀+a₁+a₂+ · · ·, where a_i ∈Aⁱ. For example, Q[V]_∞=Q[[V]] is the ring of formal power series. The exponentiale^(x,y)=e^{x1y1+···+xryr} given by its Taylor series can be regarded as an element ofQ[[V^∗⊕V]], where(x, y)is the standard pairing betweenx∈V^∗andy∈V.

Proposition 5.2 Let {f_u}u∈U be a graded basis for Q[V^∗], and let {g_u}u∈U be a collection of formal power series in Q[[V]] labeled by the same set U. Then the following two conditions are equivalent:

(1) Theguare the homogeneous polynomials inQ[V]that form the D-dual basis to {f_u}.

(2) The equalitye^(x,y)=

u∈Uf_u(x)·g_u(y)holds identically in the ring of formal power seriesQ[[V^∗⊕V]].

Proof For f ∈Q[V^∗], the action of the differential operator f (∂/∂y) on poly- nomials extends to the action on the ring of formal power series Q[[V]] and on Q[[V^∗⊕V]]. The D-pairing (f, g)D makes sense for any f ∈ Q[V^∗] and g∈ Q[[V]]. Let C=

u∈Uf_u(x)·g_u(y)∈Q[[V^∗⊕V]]. Then CT(fu(∂/∂y)·C)=

v∈U(f_u, g_v)_Df_v(x), for anyu∈U.

Condition (1) is equivalent to the condition that the constant term (with respect to they variables) off (∂/∂y)·Cisf (x), for any basis elementf =f_u ofQ[V^∗].

The latter condition is equivalent to condition (2), which says thatC=e^(x,y). Indeed, the only elementE∈Q[[V^∗⊕V]]that satisfies CT(f (∂/∂y)·E)=f (x), for any f∈Q[V^∗], is the exponentialE=e^(x,y). LetI ⊆Q[V^∗]be a graded ideal. Define the space ofI-harmonic polynomials as

HI= {g∈Q[V] |f (∂/∂y)·g(y)=0, for anyf ∈I}.

Lemma 5.3 The spaceHI ⊆Q[V]is the orthogonal subspace toI ⊆Q[V^∗]with respect to the D-pairing. ThusHIis the graded dual to the quotient spaceQ[V^∗]/I. Proof The idealI is orthogonal toI^⊥:= {g|(f, g)D=0, for anyf ∈I}. Clearly, HI ⊆I^⊥. On the other hand, if(f, g)_D=CT(f (∂/∂y)·g(y))=0, for anyf ∈I, thenf (∂/∂y)·g(y)=0, for anyf∈I, becauseI is an ideal. ThusHI=I^⊥. Letf¯:=f (modI) denote the coset of a polynomialf ∈Q[V^∗]modulo the ideal I. Forg∈HI, the differentiationf (∂/∂y)¯ ·g:=f (∂/∂y)·gdoes not depend on the choice of a polynomial representativef of the cosetf¯. Thus we have correctly defined a D-pairing(f , g)¯ _D:=(f, g)_Dbetween the spacesQ[V^∗]/IandHI. Let us say that a graded basis{ ¯f_u}u∈U ofQ[V^∗]/I and a graded basis{g_u}u∈U ofHI are D-dual if(f¯_u, g_v)_D=δ_u,v, for anyu, v∈U.

Proposition 5.4 Let{ ¯f_u}u∈U be a graded basis ofQ[V^∗]/I, and let{g_u}u∈U be a collection of formal power series in Q[[V]] labeled by the same set U. Then the following two conditions are equivalent:

(1) Theg_uare the polynomials that form the graded basis ofHI such that the bases { ¯f_u}u∈U and{g_u}u∈U are D-dual.

(2) The equalitye^(x,y)=

u∈Ufu(x)·gu(y)moduloI_∞⊗Q[[V]]holds identically.

Proof Let us augment the set{f_u}u∈U by a gradedQ-basis{f_u}u∈U of the idealI. Then {f_u}u∈U∪U is a graded basis of Q[V^∗]. A collection {g_u}u∈U is the basis of HI that is D-dual to { ¯fu}u∈U if and only if there are elementsgu∈Q[V], for u∈U, such that{f_u}u∈U∪U and{g_u}u∈U∪U are D-dual bases ofQ[V^∗]andQ[V], correspondingly. The claim now follows from Proposition5.2.

The product mapM:Q[V^∗]/I⊗Q[V^∗]/I→Q[V^∗]/Iis given byM: ¯f⊗ ¯g→ f¯· ¯g. Let us define the coproduct map:HI→HI⊗HI as the D-dual map toM.

Forh∈Q[V], the polynomialh(y+z)of the sum of two vector variablesy, z∈V can be regarded as an element ofQ[V] ⊗Q[V].

Proposition 5.5 The coproduct map:HI→HI⊗HI is given by :g(y)→g(y+z),

for anyg∈HI.

Proof Let{ ¯f_u}u∈U be a graded basis inQ[V^∗]/Iand let{g_u}u∈Ube its D-dual basis inHI. We need to show thatg(y+z)∈HI⊗HIand that the two expressions

f¯_u(x)· ¯f_v(x)=

w∈U

a_u,v^w f¯_w(x) and g_w(y+z)=

u,v∈U

b_u,v^w g_u(y)·g_v(z)

have the same coefficientsa_u,v^w =b_u,v^w . Herex∈V^∗andy, z∈V. Indeed, according to Proposition5.4, we have

u,v,w

a_u,v^w f¯w(x)·gu(y)·gv(z)

=

u

f¯_u(x)·g_u(y)

·

v

f¯_v(x)·g_v(z)

=e^(x,y)e^(x,z)=e^(x,y+z)=

w

f¯w(x)·gw(y+z)

=

u,v,w

b^w_u,vf¯w(x)·gu(y)·gv(z)

in the space(Q[V^∗]/I ⊗Q[V] ⊗Q[V])_∞. This implies that a_u,v^w =b_u,v^w , for any

u, v, w∈U.

In what follows, we will assume thatI =IW ⊂Q[V^∗]is the ideal generated by W-invariant polynomials without constant term, andQ[V^∗]/I =H^∗(G/B) is the cohomology ring ofG/B. LetHW=H_IW ⊂Q[V]be its dual space with respect to the D-pairing. We will callHW the space ofW-harmonic polynomials and call its elementsW-harmonic polynomials inQ[V].

6 Expressions for polynomialsD_u,w

In this section, we give two different expressions for the polynomialsD_u,wand derive several corollaries.

Corollary 6.1 (cf. Bernstein-Gelfand-Gelfand [2, Theorem 3.13]) The collection of polynomials D_w, w∈W, forms a linear basis of the space HW ⊂Q[V] of W-harmonic polynomials. This basis is D-dual to the basis {σ_w}w∈W of Schubert classes inH^∗(G/B).

Proof Formula (4.2), foru=id, can be rewritten ase^(x,y)=

w∈WS_w(x)D_w(y) modulo the ideal(IW)_∞⊗Q[[V]], whereSw(x)∈Q[V^∗]are polynomial represen- tatives of the Schubert classesσw ∈Q[V^∗]/IW. Proposition 5.4implies the state-

ment.

This basis ofW-harmonic polynomials appeared in Bernstein-Gelfand-Gelfand [2, Theorem 3.13] (in somewhat disguised form) and more recently in Kriloff-Ram [20, Sect. 2.2]; see Remark6.6below.

By the definition, the polynomialD_u,w is given by a sum over saturated chains in the Bruhat order. However, this expression involves many summands and is difficult to handle. The following theorem given a more explicit formula forD_u,w.

Letσ_w(∂/∂y)be the differential operator on the space of W-harmonic polyno- mials HW given by σ_w(∂/∂y):g(y)→Sw(∂/∂y)·g(y), where Sw ∈Q[V^∗] is any polynomial representative of the Schubert class σw. According to Section 5, σ_w(∂/∂y)does not depend on the choice of a polynomial representativeS_w. Theorem 6.2 For anyw∈W, we have

D_u,w(y)=σ_u(∂/∂y) σ_w◦w(∂/∂y)·D_w◦(y).

In particular, all polynomialsDu,w areW-harmonic.

Proof According to (4.2), we have D_u,w(λ)=

[e^λ] ·σ_u·σ_w◦w

, for any weight λ∈. Since σ_u·σ_w◦w is a linear combination of σ_v’s, the polynomial D_u,w is a linear combination ofDv’s, so it is a W-harmonic polynomial. Moreover, it fol- lows that the polynomialD_u,w is uniquely determined by the identity(σ,D_u,w)_D= σ·σ_u·σ_w◦w

, for any σ ∈H^∗(G/B). Let us show that the same identity holds

for theW-harmonic polynomialD˜_u,w(y)=σ_u(∂/∂y) σ_w◦w(∂/∂y)·D_w◦(y). Indeed, (σ,D˜_u,w)_Dequals

CT(σ (∂/∂y)·σ_u(∂/∂y)·σ_w◦w(∂/∂y)·D_w◦(y))=(σ·σ_u·σ_w◦w,D_w◦)_D. Since{D_w}w∈W is the D-dual basis to{σ_w}w∈W, the last expression is equal to triple intersection number

σ·σu·σw_◦w

, as needed.

Corollary9.2below gives a simple multiplicative Vandermonde-like expression for D_w◦. Theorem 6.2, together with this expression, gives an explicit “top-to- bottom” differential formula for theW-harmonic polynomialsD_w. Let us give an alternative “bottom-to-top” integral formula for these polynomials.

Forα∈, letIα be the operator that acts on polynomialsg∈Q[V]by I_α:g(y)→

_(y,α∨)

0

g(y−αt ) dt. (6.1)

In other words, the operator Iα integrates a polynomial g on the line interval [y, sα(y)] ⊂V. Clearly, this operator increases the degree of polynomials by 1.

Recall thatA_α:Q[V^∗] →Q[V^∗]is the BGG operator given by (3.2).

Lemma 6.3 Forα∈, the operatorI_α is adjoint to the operatorA_α with respect to the D-pairing. In other words,

(f, Iα(g))D=(Aα(f ), g)D, (6.2) for any polynomialsf ∈Q[V^∗]andg∈Q[V].

Proof Let us pick a basisv₁, . . . , v_rinV and its dual basisv₁^∗, . . . , v_r^∗inV^∗such that v₁=αand(v_i, α)=0, fori=2, . . . , r. Letf (x₁, . . . , x_r)=f (x₁v^∗₁+ · · · +x_rv_r^∗) andg(y1, . . . , yr)=g(y1v1+ · · · +yrvr), for f ∈Q[V^∗] andg∈Q[V]. In these coordinates, the operatorsA_α andI_αcan be written as

A_α:f (x₁, . . . , x_r)→ f (x1, x2, . . . , x_r)−f (−x1, x2, . . . , x_r) x1

I_α:g(y₁, . . . , y_r)→ _y1

−y₁

g(t, y₂, . . . , y_r) dt.

These operators are linear overQ[x2, . . . , x_r]andQ[y2, . . . , y_r], correspondingly. It is enough to verify identity (6.2) forf =x₁^m+1andg=y₁^m. For these polynomials, we haveAα(f )=2x₁^m,Iα(g)=_m²₊₁y₁^m+1, ifmis even; andAα(f )=0,Iα(g)=0, ifmis odd. Thus(f, I_α(g))_D=(A_α(f ), g)_D in both cases.

LetI_i=I_αi, fori=1, . . . , r.

Corollary 6.4 The operatorsI_isatisfy the nilCoxeter relations I_iI_jI_i· · ·

m_ijterms

=I_jI_iI_j· · ·

m_ijterms

and (I_i)²=0.

Also, ifI_α(g)=0, thengis an anti-symmetric polynomial with respect to the reflec- tions_α, and thus,gis divisible by the linear form(y, α^∨)∈Q[V].

Proof The first claim follows from the fact that the BGG operatorsA_i satisfy the nilCoxeter relations. The second claim is clear from the formula forIα given in the

proof of Lemma6.3.

For a reduced decompositionw=s_i1· · ·s_il, let us defineI_w=I_i1· · ·I_sl. The op- eratorI_w depends only onwand does not depend on the choice of reduced decom- position. Lemma6.3implies that the operatorAw:Q[V^∗] →Q[V^∗]is adjoint to the operatorI_w−1:Q[V] →Q[V]with respect to the D-pairing.

Theorem 6.5 (cf. Bernstein-Gelfand-Gelfand [2, Theorem 3.12]) For anyw∈W andi=1, . . . , r, we have

Ii·Dw=

Dws_i if(wsi)=(w)+1, 0 if(ws_i)=(w)−1.

Thus the polynomialsD_ware given by

Dw=I_w−1(1).

Proof Follows from Bernstein-Gelfand-Gelfand formula (3.3), Corollary 6.1, and

Lemma6.3.

Remark 6.6 Theorem 6.5 is essentially contained in [2]. However, Bernstein- Gelfand-Gelfand treated theDw not as (harmonic) polynomials but as linear func- tionals on Q[V^∗]/IW obtained from Id by applying the operators adjoint to the divided difference operators (with respect to the natural pairing between a lin- ear space and its dual). It is immediate that these functionals form a basis in (Q[V^∗]/IW)^∗HW; see [2, Theorem 3.13] and [20, Sect. 2.2]. Note that there are several other constructions of bases ofHW; see, e.g., Hulsurkar [16].

In the next section we show that Duan’s recent result [9] about degrees of Schubert varieties easily follows from Theorem6.5. Note that this integral expression for the polynomialsDw can be formulated in the general Kac-Moody setup. Indeed, unlike the previous expression given by Theorem6.2, it does not use the longest Weyl group elementw_◦, which exists in finite types only.

ForI ⊆ {1, . . . , r}, letWI be the parabolic subgroup inW generated bysi,i∈I. Let⁺_I = {α∈⁺|s_α∈W_I}.

Proposition 6.7 Letw∈W. LetI = {i|(ws_i) < (w)}be the descent set ofw.

Then the polynomialD_w(y)is divisible by the product

α∈⁺_I(y, α^∨)∈Q[V].

Proof According to Corollary6.4, it is enough to check thatI_α(D_w)=0, for any α∈⁺_I. We have I_α(D_w)=I_αI_w−1(1). The operator I_αI_w−1 is adjoint to A_wA_α with respect to the D-pairing. Let us show thatA_wA_α =0, identically. Notice that s_iA_α=A_si(α)s_i, wheres_i is regarded as an operator on the polynomial ringQ[V^∗].

AlsoAi=siAi= −Aisi. Thus, for anyiin the descent setI, we can write A_wA_α=A_wA_iA_α= −A_wA_is_iA_α= −A_wA_iA_si(α)s_i= −A_wA_si(α)s_i, wherew=wsi. Sincesα∈WI, there is a sequencei1, . . . , il∈I andj∈Isuch that si₁· · ·si_l(α)=αj. Thus

A_wA_α= ±A_wA_js_i1· · ·s_il = ±A_wA_jA_js_i1· · ·s_il =0,

as needed.

Corollary 6.8 FixI ⊆ {1, . . . , r}. Let w_I be the longest element in the parabolic subgroupW_I. Then

D_wI(y)=Const·

α∈⁺_I

(y, α^∨),

where Const∈Q.

Proof Proposition6.7says that the polynomialD_wI(y)is divisible by the product

α∈⁺_I(y, α^∨). Since the degree of this polynomial equals degDw_I=(w_I)= |⁺_I| =deg

α∈⁺_I

(y, α^∨),

we deduce the claim.

In Section9below, we will give an alternative derivation for this multiplicative expression forDw_I; see Corollary9.2. We will show that the constant Const in Corol- lary6.8is given by the conditionDw_I(ρ)=1.

We can express the generalized Littlewood-Richardson coefficientsc^w_u,vusing the polynomialsD_u,win two different ways.

Corollary 6.9 For anyu≤winW, we have D_u,w=

v∈W

c^w_u,vD_v.

The polynomialsD_u,w extend the polynomialsD_v in the same way as the skew Schur polynomials extend the usual Schur polynomials. Compare Corollary6.9with a similar formula for the skew Schubert polynomials of Lenart and Sottile [27].

Proof Let us expand theW-harmonic polynomialD_u,w in the basis {D_v|v∈W}, see Theorem6.2and its proof. The coefficient ofD_vin this expansion is equal to the