Schubert and Macdonald Polynomials, a parallel Alain Lascoux ooo’ooo ooo’ooo ooo’ooo ooo’ooo ooo’ooo oooo’oo oooo’oo oooo’oo oooo’oo oooo’oo oooo’oo ooo’ooo ooo’ooo ooo’ooo ooo’ooo ooo’ooo Abstract Schubertand(non-symmetric)Macdonaldpolynomialsaretwolin- earbasesoftheringofpolynomialswhichcanbecharacterizedbyvan- ishingconditions. Weshowthatbothfamiliessatisfysimilarbranching rulesrelatedtothemultiplicationby asinglevariable. Theserulesare su(cid:14)cient to recover a great part of the theory of Schubert and Mac- donald polynomials. 1 Introduction Letnbeapositiveinteger, x = x ;:::;x . Schubertpolynomials Y : v 1 n v f g f 2 Nn and Macdonald polynomials Mv : v Nn are two linear bases of the g f 2 g ring of polynomials in x, which are triangular (with respect to two di(cid:11)erent orders) in the basis of monomials. In the case of Schubert polynomials, one takes coe(cid:14)cients in an in(cid:12)nite set of indeterminates y = y ;y ;::: . In 1 2 f g the case of Macdonald polynomials, coe(cid:14)cients are rational functions in two parameters t;q. These polynomials can be de(cid:12)ned by vanishing conditions. Writing v := j j v + +v ,thenonerequires,bothforSchubertandMacdonaldpolynomials, 1 n (cid:1)(cid:1)(cid:1) the vanishing in d 1 speci(cid:12)c points, where d = n+v is the dimension of j j (cid:0) n the space of polynomials in x of degree v . It just remains to (cid:12)x a (cid:20) j j (cid:0) (cid:1) normalization condition to determine these polynomials uniquely. The interpolation points are chosen in such a way that there is an easy relation between the polynomials Y and Y (resp. M and M ), where s v vsi v vsi i is a simple transposition. In fact, these relations reduce to a simple compu- tation in the ring of polynomials in x ;x as a free module over symmetric i i+1 polynomials in x ;x . As such, this space is a two-dimensional space with i i+1 basis 1;x . The relations are given by Newton’s divided di(cid:11)erences in the i f g (cid:12)rst case, and a deformation of them in the case of Macdonald polynomials (the generators of the Hecke algebra). 1 Thereisan extra"a(cid:14)ne" operation, whichsendsM onto M , withv(cid:28) = v v(cid:28) [v2;:::;vn;v1+1]. Together with v ! vsi, i = 1;:::;n(cid:0)1, the a(cid:14)ne operation su(cid:14)ces to generate all Macdonald polynomials starting from M = 1. 0;:::;0 InthecaseofSchubertpolynomials, oneneedsmorestartingpoints. They are the polynomials Y , with v dominant, i.e. such that v v v . v 1 2 n (cid:21) (cid:21) (cid:1)(cid:1)(cid:1) (cid:21) We also say that v is a partition and write v Part. In that case Y is a v 2 product of linear factors x y , which can be read instantly by representing i j (cid:0) v by a diagram of boxes in the plane. Having a distinguished linear basis, one has to recover the multiplicative structure. In the Schubert world, it is Monk’s formula, describing the prod- uct by any x , which answers this problem. We give a similar formula for i Macdonald polynomials. Coe(cid:14)cientsarenomore 1, butproductsoffactors (cid:6) of the type tiqj 1. (cid:0) Given v, one can choose an i such that the multiplication by x furnishes i a transition formula which allows to decompose the polynomial Y (resp M ) v v into "smaller" polynomials. Iterating, one gets a canonical decomposition of Y into "shifted monomials" (meaning products of x y ), and a canonical v i j (cid:0) decomposition of M into "shifted monomials" which are now products of v x qj tk. i (cid:0) As in every interpolation problem, it is useful to know a point where @ the polynomials take explicit and all di(cid:11)erent values. In the case of Schubert polynomials, this point is just the origin [0;:::;0], but one can also use [1;t;:::;tn 1], or specialize instead the y ’s : y ti 1. In the case of (cid:0) i i (cid:0) ! Macdonald polynomials, one takes = [utn 1;:::;ut;u], with u = 1. (cid:0) @ 6 We mention at the end an interesting domain, introduced by Feigin, Jimbo, Miwa and Mukhin [5], which ought to be further developed, that is, the specialization of Macdonald polynomials under a wheel condition t(cid:11)q(cid:12) = 1, with (cid:11);(cid:12) Z. 2 2 Interpolation in the case of a single variable Faced with ; ; ; ; ; ::: everybody continues with ; ; ::: 2 Galileo, recording the positions of a falling stone at regular intervals of time, confronted to a little more di(cid:14)cult task : I; IV; IX; XVI; XXV; XXXVI; ::: but was fortunately guided by the metaphysical principle that if it is not the increment of space which is constant, then it must be the increment of velocity1. Before being able to formulate any algebraic law concerning gravitation, Newton had to address the question of transforming discrete sets of data, say the positions of a planet at di(cid:11)erent times, into algebraic functions. Con- trary to the case of a stone solved by Galileo, comets are not likely to appear at regularly spaced times, and to handle their seemingly erratic apparitions, Newton found the solution of normalizing di(cid:11)erences of positions by the in- tervaloftimetowhichtheycorrespond. TheseoperationsarecalledNewton’s divided di(cid:11)erences, we shall see more about them later. Thanks to them, Newton was able to write an interpolation formula for the position f(t) of a comet at times t ;t ;:::: 0 1 f(t) = f(t )+f@(t t )+f@@(t t )(t t )+ 0 0 0 1 (cid:0) (cid:0) (cid:0) (cid:1)(cid:1)(cid:1) where the coe(cid:14)cients f@, f@@ are the successive divided di(cid:11)erences of the positions at time t ;t ;t ;:::. 0 1 2 Of course, one can characterize Newton’s polynomials 1; (t t ); (t 0 (cid:0) (cid:0) t )(t t );::: by their respective degrees and vanishing properties. Writing 0 1 (cid:0) the specializations of Newton’s formula at times t , t ;::: allows then to 0 1 recover the recursive de(cid:12)nition of f@, f@@;:::. 1Quando, dunque, osservo che una pietra, che discende dall’alto a partire dalla qui- ete, acquista via nuovi incrementi di velocita(cid:18), perch(cid:19)e non dovrei credere che tali aumenti avvengano secondo la pi semplice e pi ovvia proporzione? Ora, se consideriamo atten- tamente la cosa, non troveremo nessun aumento o incremento piu(cid:18) semplice di quello che aumentasemprenelmedesimomodo. Ilchefacilmenteintenderemoconsiderandolastretta connessionetratempoemoto: comeinfattilaequabilita(cid:18)euniformita(cid:18)delmotoside(cid:12)nisce esiconcepiscesullabasedellaeguaglianzadeitempiedeglispazi(infattichiamiamoequa- bile il moto, allorch(cid:19)e in tempi eguali vengono percorsi spazi eguali), cos(cid:18)(cid:16), mediante una medesima suddivisione uniforme del tempo, possiamo concepire che gli incrementi di ve- locitavvenganocon[altrettanta]semplicita(cid:18);[lopossiamo]inquantostabiliamoinastratto cherisultiuniformementee,nelmedesimomodo,continuamenteaccelerato,quelmotoche in tempi eguali, comunque presi, acquista eguali aumenti di velocita(cid:18). 3 In fact, all classical interpolation formulas in one variable rely on the fact that if one knows the value of a polynomial P(t) in a, then (P(t) P(a))(t a) 1 (divided di(cid:11)erence !) is a polynomial of smaller degree. (cid:0) (cid:0) (cid:0) Thesituationisnotatallthesameinthecaseofseveralvariables,because it is not evident how to reduce the degree of a polynomial, knowing its values in some points. Nevertheless,weshallgivetwofamiliesofpolynomialsinseveralvariables, Schubert and Macdonald polynomials, which behave almost as simply as the polynomials of Newton, and can be de(cid:12)ned by vanishing properties. Schubert polynomials have originally been de(cid:12)ned as representatives of Schubert varieties [15], but, due to their close relation with the Ehresmann- Bruhat order on the symmetricgroup [16, 17], it is clear that they can also be characterized by vanishing properties. It is more surprising, and due to Sahi, Knop and Okounkov [24, 25, 11, 9, 10, 20, 21], that Macdonald polynomials can also be de(cid:12)ned by vanishing conditions. We shall study both families of polynomials by using interpolation meth- ods only, i.e. by computing specializations (Grothendieck polynomials [16] could have been treated in the like manner). 3 Schubert polynomials Given n, let Pol(x;y) (resp. Pol (x;y)) be the space of polynomials in d x = x ;:::;x with polynomial coe(cid:14)cients in y = y ;y ;:::;y (resp. 1 n 1 2 f g f 1g of total degree d in x). (cid:20) We need to use two di(cid:11)erent indexings, either by permutations or by codes, for the polynomials that we want to describe. Given (cid:27) in the symmetric group S , its code c((cid:27)) is the vector v of com- N ponentsvi := # j : j > i&(cid:27)i > (cid:27)j . Oneidenti(cid:12)es(cid:27) and[(cid:27);N+1;N+2;:::]; f g this corresponds to concatenating 0’s to the code of (cid:27). We write (cid:27) = v h i when c((cid:27)) = v (up to terminal zeros), and y(cid:27) = y ;y ;::: . f (cid:27)1 (cid:27)2 g De(cid:12)nition 1 Given v Nn, the Schubert polynomial Yv(x), also denoted 2 X (x) with (cid:27) = v , is the only polynomial in Pol (x;y) such that (cid:27) h i jvj Y (y u ) = 0; u = v; u v (1) v h i 6 j j (cid:20) j j Yv(yhvi) = e(v) := (y(cid:27)i (cid:0)y(cid:27)j) (2) i<jY;(cid:27)i>(cid:27)j 4 The space Pol (x;y) has dimension exactly the number of conditions v j j that we have just imposed on the putative Y (x). The existence (unicity is v clear) of this polynomial will follow from the recursive construction that (1, 2) imply. Polynomials which are products of linear factors x y are easy to spe- i j (cid:0) cialize. A "pigeon-hole" analysis gives the following lemma. Lemma 2 Let v Nn be dominant. Then 2 n vi (x y ) i j (cid:0) i=1 j=1 YY satis(cid:12)es (1, 2). We can now reason by induction on the number of indices i such that v < v to treat the general case. i i+1 Given a polynomial f(x ;:::;x ), and i : 1 i n 1, denote fsi the 1 n (cid:20) (cid:20) (cid:0) image of f under the exchange of x ;x . Let f f@ := (f fsi)(x i i+1 i i ! (cid:0) (cid:0) x ) 1 be the i-th Newton’s divided di(cid:11)erence (denoted on the right). i+1 (cid:0) Lemma 3 Let v Nn, (cid:27) = v , i be such that vi > vi+1. Suppose that Yv 2 h i satis(cid:12)es (1, 2). Then f := X(cid:27)(x)@i = X(cid:27)(x) X(cid:27)(xsi) (xi xi+1)(cid:0)1 (cid:0) (cid:0) also satis(cid:12)es (1, 2) for the ind(cid:0)ex v = [v ;:::;v (cid:1) ;v ;v 1;v ;:::;v ]. 0 1 i(cid:0)1 i+1 i(cid:0) i+2 n Proof. The polynomial f vanish in all x = y u , u < v , except for u = v , h i 0 j j j j becauseX (x)aswellasX (xsi)vanishinthesepoints. Moreover, X (y(cid:27)) (cid:27) (cid:27) (cid:27) (cid:0) X(cid:27)(y(cid:27)si) (y(cid:27)i (cid:0)y(cid:27)i+1)(cid:0)1 is indeed equal to e((cid:27)si), the two permu(cid:0)tations (cid:27) and (cid:27)s having the same inversions, except the inversion (cid:27) ;(cid:27) . Q.E.D. i i i+1 (cid:1) In conclusion, conditions (1, 2) de(cid:12)ne a linear basis of Pol(x;y), Lemma 3 showing that the Schubert polynomials can be generated by divided di(cid:11)er- ences from the dominant Schubert polynomials. Aswealreadysaid,weshallrecoverthemultiplicativestructureofPol(x;y) by describing the e(cid:11)ect of multiplying the Schubert basis by x ;:::;x . 1 n De(cid:12)nition 4 v Nn is a successor of u if v = u + 1 & Yu(yhvi) = 0. 2 j j j j 6 Correspondingly, for two permutations (cid:16);(cid:27), (cid:16) is a successor of (cid:27) i(cid:11) ‘((cid:16)) = ‘((cid:27))+1 and X (y(cid:16)) = 0. (cid:27) 6 5 Theorem 5 (cid:16) is a successor of (cid:27) i(cid:11) (cid:16)(cid:27) 1 is a transposition (a;b), and ‘((cid:16)) = (cid:0) ‘((cid:27))+1. In that case, X(cid:27)(y(cid:16)) = e(c((cid:16)))(y(cid:16)b (cid:0)y(cid:16)a)(cid:0)1: Proof. If u = c((cid:27)) is dominant, then it is immediate to write the specializa- tions of Y and check the proposition in that case. Let us therefore suppose u thatthereexistsi : ui < ui+1,andlet(cid:17) = u1;:::;ui 1;ui+1+1;ui;ui+2;:::;un . h (cid:0) i Since for any (cid:16), X(cid:17)(y(cid:16))(cid:0)X(cid:17)(y(cid:16)si) (y(cid:16)i (cid:0)y(cid:16)i+1)(cid:0)1 = X(cid:27)(y(cid:16)); (cid:0) (cid:1) then (cid:16) can be a successor of (cid:27) only if (cid:16) = (cid:17), or if (cid:16)s is a successor of (cid:17). In i the (cid:12)rst case, X(cid:27)(y(cid:17)) = X(cid:17)(y(cid:17))(y(cid:17)i (cid:0)y(cid:17)i+1)(cid:0)1 = e(c((cid:17))); while in the second, X(cid:17)(y(cid:16)si) e(c((cid:16)si)) e(c((cid:16))) (cid:0) = = ; y y (y y )(y y ) y y (cid:16)i (cid:0) (cid:16)i+1 (cid:16)i+1 (cid:0) (cid:16)i (cid:16)b (cid:0) (cid:16)a (cid:16)b (cid:0) (cid:16)a and this proves the proposition. Q.E.D. Corollary 6 (Monk formula [12]) Givenv Nn, (cid:27) = v , i 1;:::;n , 2 h i 2 f g then (x y )X (x) = X X ; (3) i (cid:0) (cid:27)i (cid:27) (cid:27)(cid:28)i;j (cid:0) (cid:27)(cid:28)i;j j>i j<i X X summed over all transpositions (cid:28) such that ‘((cid:27)(cid:28) ) = ‘((cid:27))+1. i;j i;j Proof.Thepolynomial(x y )X (x)belongstothelinearspanofY : w = i(cid:0) (cid:27)i (cid:27) w j j v + 1, because it is of degree v + 1 and vanishes in all y w : w v . h i j j j j j j (cid:20) j j Writing it c X (x), and testing all the specializations y(cid:16), one (cid:12)nds that (cid:16) (cid:16) the permutations appearing in the sum are exactly the successors of (cid:27) such P that y = y . Q.E.D. (cid:16)i 6 (cid:27)i Let us put the right lexicographic order on monomials : v u i(cid:11) either (cid:21) v > u or v = u & k : v > u ;v = u ;:::;v = u . The k k k+1 k+1 n n j j j j j j j j 9 recursive de(cid:12)(cid:16)nition of Schubert polynomials provided by Lemma 3(cid:17)entails that Y = xv+ lower terms with respect to this order. v 6 Given v Nn, let k n be such that vk > 0, vk+1 = 0 = = vn, and 2 (cid:20) (cid:1)(cid:1)(cid:1) let v be obtained from v by changing v into v 1 and (cid:27) = v . Then Monk 0 k k(cid:0) h 0i formula rewrites in that case as Y = (x y )Y + Y ; (4) v k (cid:0) (cid:27)k v0 u u X summed over all u such that u = v and u (cid:27) 1 is a transposition (cid:28) with (cid:0) ik j j j j h i i < k. Let us remark that u < v, and therefore, the above equation, called transition formula [15], provides a positive recursive de(cid:12)nition of Schubert polynomials, and decomposes them into sums of "shifted monomials" (x i (cid:0) y ). j Q For example, starting with v = [2;0;3], v = (cid:27) = [3;1;5;2;4], one has 0 h i the following sequence of transitions : Y = (x y )Y +Y +Y ; 203 3 5 202 230 401 (cid:0) Y = (x y )Y +Y ; 230 2 4 220 320 (cid:0) Y = (x y )Y +Y ; 401 3 2 400 410 (cid:0) (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) that one terminates when attaining dominant indices. In (cid:12)nal, writing each shiftedmonomialasadiagramofblacksquaresintheCartesianplane(x y i j (cid:0) gives a box in column i, row j), the polynomial Y reads 203 (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) (cid:4)(cid:4)(cid:1) + (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) (cid:4)(cid:4)(cid:1) + (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) (cid:4)(cid:1)(cid:1) + (cid:1)(cid:1)(cid:1) (cid:4)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) + (cid:4)(cid:4)(cid:1) (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) + (cid:4)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) (cid:4)(cid:1)(cid:1) + (cid:4)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) + (cid:4)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) (cid:4)(cid:1)(cid:1) + (cid:4)(cid:4)(cid:1) (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) (cid:4) (cid:1) (cid:4) (cid:4) (cid:1) (cid:1) (cid:4) (cid:4) (cid:1) (cid:4) (cid:4) (cid:1) (cid:4) (cid:1) (cid:4) (cid:4) (cid:1) (cid:4) (cid:4) (cid:4) (cid:1) (cid:4) (cid:1) (cid:1) (cid:4) (cid:1) (cid:1) (cid:4) (cid:1) (cid:1) (cid:4) (cid:4) (cid:1) (cid:4) (cid:4) (cid:1) (cid:4) (cid:4) (cid:1) (cid:4) (cid:1) (cid:1) (cid:4) (cid:1) (cid:1) (cid:4) (cid:4) (cid:1) (cid:4) (cid:4) (cid:1) (cid:4) (cid:4) (cid:1) the (cid:12)rst diagram, for example, coding (x y )(x y )(x y )(x y )(x 1 1 1 2 3 2 3 4 3 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) y ). 5 FominandKirillov[6]givecon(cid:12)gurationsfromwhichonereadsadi(cid:11)erent decomposition of Schubert polynomials into shifted monomials. 4 Some properties of Schubert polynomials Their de(cid:12)nition by vanishing conditions show that Schubert polynomials are compatible with the embedding Pol(x ;:::;x ) , Pol(x ;:::;x ): 1 n 1 n+1 ! Y = Y . As a consequence, one can index Schubert polynomials by vectors v v;0 v N1 having only a (cid:12)nite number of components di(cid:11)erent from 0, these 2 g 7 polynomials constituting a basis of the ring Pol(x ;x ;:::) of polynomials in 1 2 an in(cid:12)nite number of variables x , with coe(cid:14)cients in y. i Thevanishingconditionsalsoshowasymmetrybetweenxandy: X (x;y) = (cid:27) ( 1)‘((cid:27))X (y;x). The polynomials X (x;0), as well as the polynomials (cid:27) 1 (cid:27) (cid:0) (cid:0) X (0;y) are linearly independent. The polynomials X (x;1=(1 q)) (i.e. (cid:27) (cid:27) (cid:0) specializing y = qi 1) can be used in problems of q-interpolation [23]. i (cid:0) Any simple transposition s can be written @ (x x )+1. More gen- i i i+1 i (cid:0) erally, given a permutation (cid:27) and any decomposition (cid:27) = s s , then i j (cid:1)(cid:1)(cid:1) (cid:27) = @ (x x )+1 @ (x x )+1 : (5) i i+1 i j j+1 j (cid:0) (cid:1)(cid:1)(cid:1) (cid:0) Reordering this exp(cid:0)ression, one can s(cid:1)how(cid:0)[13, Prop 9.6.2] th(cid:1)at (cid:27) = @ X (x(cid:27);x); (cid:16) (cid:16) (cid:16) X de(cid:12)ning @ = @ @ with the help of any reduced decomposition s s = (cid:16) i j i j (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) (cid:16). Thus, Schubert polynomials occur in the expansion of permutations in terms of divided di(cid:11)erences (and also in the expansion of divided di(cid:11)erences in terms of permutations [13, Prop 10.2.5]). Clearly, the permutation (cid:16) obtained by expanding (5) are smaller than (cid:27) in the Bruhat order (since they have a decomposition which is subword of s s ). This implies that X (x(cid:27);x) = 0 for all (cid:16) which are not smaller i j (cid:16) (cid:1)(cid:1)(cid:1) than (cid:27). We have already met this criterium when ‘((cid:27)) = ‘((cid:16)) + 1, the comparison with respect to the Bruhat order corresponding in that case to the requirement in Theorem 5 that (cid:16)(cid:27) 1 be a transposition. Each Schubert (cid:0) polynomial X , apart from X = 1, vanishes for an in(cid:12)nite number of (cid:16) 123::: specializationsX (x(cid:27);x). Forexample,X = x +x y y vanishesfor (cid:16) 13245::: 1 2 1 2 (cid:0) (cid:0) all(cid:27) havingareduceddecompositionwhichdoesnotcontains (equivalently, 2 such that (cid:27) ;(cid:27) = 1;2 ). 1 2 f g f g Lemma 3 shows that Yv : v Nn is symmetrical in xi;xi+1 if vi vi+1. 2 (cid:20) Therefore, if v is anti-dominant (i.e v v v ), then Y is a sym- 1 2 n v (cid:20) (cid:20) (cid:1)(cid:1)(cid:1) (cid:20) metric function, which is called a Grassmannian Schubert polynomial. It is obtained from Y(cid:21), (cid:21) = [vn+n(cid:0)1;:::;v2+1;v1], by a sequence of divided di(cid:11)erences corresponding to the \maximal permutation" ! := [n;:::;1]. In- deed, let @ = @ (@ @ ) (@ @ ) be such a product. Then, thanks to ! 1 2 1 n 1 1 (cid:1)(cid:1)(cid:1) (cid:0) (cid:1)(cid:1)(cid:1) (3), Y @ = Y , divided di(cid:11)erences acting just by reordering and decreasing (cid:21) ! v indices (or by annihilation). On the other hand, @ is an operator which ! commutes with multiplication with symmetric functions, and decreases de- grees by n(n 1)=2. From this, it is easy to conclude that @ is equal to (cid:0) ! 8 Pol(x) f (f=(cid:1))(cid:27), where (cid:1) = (x x ). In the case 3 ! (cid:27) Sn 1 i<j n i (cid:0) j where f = f (x )::2:f (x ), then ( 1)‘((cid:27))f(cid:27)(cid:20)can(cid:20)be written as the deter- 1 1P n n (cid:0) Q minant det(f (x )). In particular, i j P Yv = det(xih(cid:21)ji)=(cid:1); where x k stands for the \modi(cid:12)ed power" (x y ):::(x y ). h i 1 k (cid:0) (cid:0) The special case of Grassmannian Schubert polynomials when y = qi 1 i (cid:0) appear frequently in the literature under the name q-factorial Schur func- tions. 5 Macdonald polynomials As in the case of Schubert polynomials, our fundamental objects will be indexed by elements of Nn, but this time we shall not decode v Nn as a 2 permutation. This is the a(cid:14)ne symmetric group that we have to use now. It is convenient to consider v Nn as the n (cid:12)rst components of an in(cid:12)nite 2 vector v such that vi+rn = vi +r, r Z. Similarly, we shall use an in(cid:12)nite 2 set of indeterminates xi : i Z, such that xi+rn = qrxi. Now, apart from the 2 simple transpositions s , 0 < i < n (which transpose x and x , resp. i i+rn i+1+rn v and v , for all r at the same time), we also have a translation (cid:28) i+rn i+1+rn (cid:28) : x x , v v , and its inverse (cid:28)(cid:22) = (cid:28) 1, that one can also write i i+1 i i+1 (cid:0) ! ! (cid:28) [x ;:::;x ;x ] [x ;:::;x ;qx ]; 1 n 1 n 2 n 1 (cid:0) (cid:0)! (cid:28) [v ;:::;v ;v ] [v ;:::;v ;v +1]: 1 n 1 n 2 n 1 (cid:0) (cid:0)! Let moreover s := (cid:28)s (cid:28)(cid:22) = (cid:28)(cid:22)s (cid:28), and (cid:8) := (cid:28)(cid:22)(x 1). 0 1 n 1 n Given v Nn, one supers(cid:0)criptizes its compo(cid:0)nents with the numbers 2 0;1;:::;n 1,readingbyincreasingvalues,fromrighttoleft(thisisoneofthe (cid:0) many ways to standardize a word). This allows to associate to v a new vector v := [qv1ta;:::;qvntb], where a;:::;b are the superscripts. For example, for h i v = [5;0;8;5], the superscripts are [2;0;3;1], and v = [q5t2;q0t0;q8t3;q5t1]. h i Given u;v Nn, let 2 1 1 t g(u;v) := (cid:0) ; (6) 1(cid:0)t i hviihui(cid:0)i 1 (cid:0)1 Y c product over all i such that v = u . i i h i 6 h i 9 Given u;v Nn such that v is a permutation of w = u(cid:28), let vv, ww be 2 the images of v;w after putting superscripts. Let ((cid:13) t)(t(cid:13) 1) d(u;v) := (cid:0) (cid:0) (7) ((cid:13) t)2 (cid:0) Y products over all pairs i < j such that v < v and va;vb is a subword of vv i j i j and not of ww, with (cid:13) := qvj(cid:0)vitb(cid:0)a. For example, u = [4;5;0;8] gives ww = [52;00;83;51], v = [0;5;5;8] gives vv = [00;52;51;83]. Only the two subwords [00;52], [51;83] contribute to (tq5 1)(t3q5 1)(q3t 1)(q3t3 1) d([4;5;0;8];[0;5;5;8]) = (cid:0) (cid:0) (cid:0) (cid:0) : (q5t2 1)2(q3t2 1)2 (cid:0) (cid:0) We extend the de(cid:12)nition of d(u;v) by requiring that d be invariant under theactionof(cid:28): d(u(cid:28)k;v(cid:28)k) = d(u;v) k 0. Thusd([4;5;0;8];[0;5;5;8]) = 8 (cid:21) d([5;0;8;5];[5;5;8;1]) = d([0;8;5;6];[5;8;1;6]) = d([8;5;6;1];[8;1;6;6]). The lexicographic order is no more convenient. We have to extend the naturalorderonpartitions. Givenv Nn, denote(cid:21)(v)thepartitionobtained 2 by reordering v decreasingly. Then we set u < v i(cid:11) u < v or u = v & (cid:21)(u) < (cid:21)(v) or (cid:21)(u) = (cid:21)(v) & u < v ; S j j j j j j j j (cid:16) (cid:17) (cid:16) (cid:17) <S being the Bruhat order on the permutations of an element of Nn. For example [4;0;0] > [0;0;4] > [2;2;0] > [2;0;2] > [1;2;1] > [3;0;0] is a chain. The leading term of a polynomial is the restriction of the polynomial to its maximal elements with respect to this order. De(cid:12)nition 7 For any v Nn, Mv is the only polynomial such that 2 M ( u ) = 0, u : u v ;u = v, and such that the leading term of M is v v h i 8 j j (cid:20) j j 6 xvq(cid:0) i(v2i). P The number of conditions is v+n , i.e. the dimension of the space of j j n polynomials of degree v . The existence of such a family of polynomials (cid:20) j j (cid:0) (cid:1) will follow from the recursions v vs , and v v(cid:28) that the vanishing i ! ! conditions impose. Okounkov[20,22]considersmoregeneralinterpolationpoints(essentially, he replaces the vectors u by [ u + c u 1;:::; u + c u 1], where c is h i h i1 h i(cid:0)1 h in h i(cid:0)n an extra parameter). 10