Notes on Schubert, Grothendieck and Key Polynomials

Notes on Schubert, Grothendieck and Key Polynomials

We introduce common generalization of (double) Schubert, Grothendieck, Demazure, dual and stable Grothendieck polynomials, and Di Francesco-Zinn-Justin polynomials. Our approach is based on the study of algebraic and combinatorial properties of the reduced rectangular plactic algebra and associated...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2016
1. Verfasser: Kirillov, A.N.
Format: Artikel
Sprache:English
Veröffentlicht: Інститут математики НАН України 2016
Schriftenreihe:Symmetry, Integrability and Geometry: Methods and Applications
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/147725
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Notes on Schubert, Grothendieck and Key Polynomials / A.N. Kirillov // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 72 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-147725
record_format dspace
spelling irk-123456789-1477252019-02-16T01:24:55Z Notes on Schubert, Grothendieck and Key Polynomials Kirillov, A.N. We introduce common generalization of (double) Schubert, Grothendieck, Demazure, dual and stable Grothendieck polynomials, and Di Francesco-Zinn-Justin polynomials. Our approach is based on the study of algebraic and combinatorial properties of the reduced rectangular plactic algebra and associated Cauchy kernels. 2016 Article Notes on Schubert, Grothendieck and Key Polynomials / A.N. Kirillov // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 72 назв. — англ. 1815-0659 2010 Mathematics Subject Classification: 05E05; 05E10; 05A19 DOI:10.3842/SIGMA.2016.034 http://dspace.nbuv.gov.ua/handle/123456789/147725 en Symmetry, Integrability and Geometry: Methods and Applications Інститут математики НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
description We introduce common generalization of (double) Schubert, Grothendieck, Demazure, dual and stable Grothendieck polynomials, and Di Francesco-Zinn-Justin polynomials. Our approach is based on the study of algebraic and combinatorial properties of the reduced rectangular plactic algebra and associated Cauchy kernels.
format Article
author Kirillov, A.N.
spellingShingle Kirillov, A.N.
Notes on Schubert, Grothendieck and Key Polynomials
Symmetry, Integrability and Geometry: Methods and Applications
author_facet Kirillov, A.N.
author_sort Kirillov, A.N.
title Notes on Schubert, Grothendieck and Key Polynomials
title_short Notes on Schubert, Grothendieck and Key Polynomials
title_full Notes on Schubert, Grothendieck and Key Polynomials
title_fullStr Notes on Schubert, Grothendieck and Key Polynomials
title_full_unstemmed Notes on Schubert, Grothendieck and Key Polynomials
title_sort notes on schubert, grothendieck and key polynomials
publisher Інститут математики НАН України
publishDate 2016
url http://dspace.nbuv.gov.ua/handle/123456789/147725
citation_txt Notes on Schubert, Grothendieck and Key Polynomials / A.N. Kirillov // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 72 назв. — англ.
series Symmetry, Integrability and Geometry: Methods and Applications
work_keys_str_mv AT kirillovan notesonschubertgrothendieckandkeypolynomials
first_indexed 2025-07-11T02:43:15Z
last_indexed 2025-07-11T02:43:15Z
_version_ 1837316781954301952
fulltext Symmetry, Integrability and Geometry: Methods and Applications SIGMA 12 (2016), 034, 57 pages Notes on Schubert, Grothendieck and Key Polynomials Anatol N. KIRILLOV †‡§ † Research Institute of Mathematical Sciences (RIMS), Kyoto, Sakyo-ku 606-8502, Japan E-mail: kirillov@kurims.kyoto-u.ac.jp URL: http://www.kurims.kyoto-u.ac.jp/~kirillov/ ‡ The Kavli Institute for the Physics and Mathematics of the Universe (IPMU), 5-1-5 Kashiwanoha, Kashiwa, 277-8583, Japan § Department of Mathematics, National Research University Higher School of Economics, 7 Vavilova Str., 117312, Moscow, Russia Received March 26, 2015, in final form February 28, 2016; Published online March 29, 2016 http://dx.doi.org/10.3842/SIGMA.2016.034 Abstract. We introduce common generalization of (double) Schubert, Grothendieck, De- mazure, dual and stable Grothendieck polynomials, and Di Francesco–Zinn-Justin polyno- mials. Our approach is based on the study of algebraic and combinatorial properties of the reduced rectangular plactic algebra and associated Cauchy kernels. Key words: plactic monoid and reduced plactic algebras; nilCoxeter and idCoxeter alge- bras; Schubert, β-Grothendieck, key and (double) key-Grothendieck, and Di Francesco– Zinn-Justin polynomials; Cauchy’s type kernels and symmetric, totally symmetric plane partitions, and alternating sign matrices; noncrossing Dyck paths and (rectangular) Schu- bert polynomials; multi-parameter deformations of Genocchi numbers of the first and the second types; Gandhi–Dumont polynomials and (staircase) Schubert polynomials; double affine nilCoxeter algebras 2010 Mathematics Subject Classification: 05E05; 05E10; 05A19 To the memory of Alexander Grothendieck (1928–2014) Contents 1 Introduction 2 2 Plactic, nilplactic and idplactic algebras 10 3 Divided difference operators 17 4 Schubert, Grothendieck and key polynomials 18 5 Cauchy kernel 28 5.1 Plactic algebra Pn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2 Nilplactic algebra NPn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Idplactic algebra IPn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.4 NilCoxeter algebra NCn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.5 IdCoxeter algebras IC±n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6 F-kernel and symmetric plane partitions 41 A Appendix 45 A.1 Some explicit formulas for n = 4 and compositions α such that αi ≤ n− i for i = 1, 2, . . . 45 A.2 MacMeille completion of a partially ordered set . . . . . . . . . . . . . . . . . . . . . . . . 52 References 54 mailto:kirillov@kurims.kyoto-u.ac.jp http://www.kurims.kyoto-u.ac.jp/~kirillov/ http://dx.doi.org/10.3842/SIGMA.2016.034 2 A.N. Kirillov Extended abstract We introduce certain finite-dimensional algebras denoted by PCn and PFn,m which are certain quotients of the plactic algebra Pn, which had been introduced by A. Lascoux and M.-P. Schüt- zenberger [46]. We show that dim(PFn,k) is equal to the number of symmetric plane partitions fitting inside the box n × k × k, dim(PCn) is equal to the number of alternating sign matrices of size n× n, moreover, dim(PFn,n) = TSPP(n+ 1)× TSSCPP(n), dim(PFn,n+1) = TSPP(n+ 1)× TSSCPP(n+ 1), dim(PFn+2,n) = dim(PFn,n+1), dim(PFn+3,n) = 1 2 dim(PFn+1,n+1), and study decomposition of the Cauchy kernels corresponding to the algebras PCn and PFn,m; as well as introduce polynomials which are common generalizations of the (double) Schubert, β-Grothendieck, Demazure (known also as key polynomials), (plactic) key-Grothendieck, (plac- tic) Stanley and stable β-Grothendieck polynomials. Using a family of the Hecke type divided difference operators we introduce polynomials which are common generalizations of the Schu- bert, β-Grothendieck, dual β-Grothendieck, β-Demazure–Grothendieck, and Di Francesco–Zinn- Justin polynomials. We also introduce and study some properties of the double affine nilCoxeter algebras and related polynomials, put forward a q-deformed version of the Knuth relations and plactic algebra. 1 Introduction The Grothendieck polynomials had been introduced by A. Lascoux and M.-P. Schützenberger in [48] and studied in detail in [39]. There are two equivalent versions of the Grothendieck polynomials depending on a choice of a basis in the Grothendieck ring K?(F ln) of the complete flag variety F ln. The basis {exp(ξ1), . . . , exp(ξn)} in K∗(F ln) is one choice, and another choice is the basis {1 − exp(−ξj), 1 ≤ j ≤ n}, where {ξj , 1 ≤ j ≤ n} denote the Chern classes of the tautological linear bundles Lj over the flag variety F ln. In the present paper we use the basis in a deformed Grothendieck ring K∗,β(Fn) of the flag variety F ln generated by the set of elements {xi = x (β) i = 1− exp(βξi), i = 1, . . . , n}. This basis has been introduced and used for construction of the β-Grothendieck polynomials in [17, 19]. A basis in the classical Grothendieck ring of the flag variety in question corresponds to the choice β = −1. For arbitrary β the ring generated by the elements { x (β) i , 1 ≤ i ≤ n } has been identified with the Grothendieck ring corresponding to the generalized cohomology theory associated with the multiplicative formal group law F (x, y) = x + y + βxy, see [23]. The Grothendieck polynomials corresponding to the classical K-theory ring K?(F ln), i.e., the case β = −1, had been studied in depth by A. Lascoux and M.-P. Schützenberger in [49]. The β-Grothendieck polynomials has been studied in [17, 18, 23]. The plactic monoid over a finite totally ordered set A = {a < b < c < · · · < d} is the quotient of the free monoid generated by elements from A subject to the elementary Knuth transformations [29] bca = bac & acb = cab, and bab = bba & aba = baa, (1.1) for any triple {a < b < c} ⊂ A. To our knowledge, the concept of “plactic monoid” has its origins in a paper by C. Schen- sted [64], concerning the study of the longest increasing subsequence of a permutation, and Notes on Schubert, Grothendieck and Key Polynomials 3 a paper by D. Knuth [29], concerning the study of combinatorial and algebraic properties of the Robinson–Schensted correspondence1. As far as we know, this monoid and the (unital) algebra P(A) corresponding to that monoid2, had been introduced, studied and used by M.-P. Schützenberger, see [65, Section 5], to give the first complete proof of the famous Littlewood–Richardson rule in the theory of symmetric functions. A bit later this monoid, was named the “monöıde plaxique” and studied in depth by A. Lascoux and M.-P. Schützenberger [46]. The algebra corresponding to the plactic monoid is commonly known as plactic algebra. One of the basic properties of the plactic algebra [65] is that it contains the distinguished commutative subalgebra which is generated by noncommutative elementary (quasi-symmetric) polynomials3 ek(An) = ∑ i1>i2>···>ik ai1ai2 · · · aik , k = 1, . . . , n, see, e.g., [65, Corollary 5.9] and [16]. We refer the reader to nice written overview [44] of the basic properties and applications of the plactic monoid in combinatorics. It is easy to see that the plactic relations for two letters a < b, namely, aba = baa, bab = bba, imply the commutativity of noncommutative elementary polynomials in two variables. In other words, the plactic relations for two letters imply that ba(a+ b) = (a+ b)ba, a < b. It has been proved in [16] that these relations together with the Knuth relations (1.1) for three letters a < b < c, imply the commutativity of noncommutative elementary quasi-symmetric polynomials for any number of variables. In the present paper we prove that in fact the commutativity of noncommutative elementary quasi-symmetric polynomials for n = 2 and n = 3 implies the commutativity of that polynomials for all n, see Theorem 2.234. One of the main objectives of the present paper is to study combinatorial properties of the generalized plactic Cauchy kernel C(Pn, U) = n−1∏ i=1  i∏ j=n−1 (1 + pi,j−i+1uj)  , where Pn stands for the set of parameters {pij , 2 ≤ i + j ≤ n + 1, i > 1, j > 1}, and U := Un stands for a certain noncommutative algebra we are interested in, see Section 5. We also want to bring to the attention of the reader on some interesting combinatorial properties of rectangular Cauchy kernels F(Pn,m, U) = n−1∏ i=1  1∏ j=m−1 (1 + p i,i−j+1 (m)uj)  , where Pn,m = {pij} 1≤i≤n 1≤j≤m ; see Definition 6.6 for the meaning of symbol a(m). 1See, e.g., https://en.wikipedia.org/wiki/Robinson-Schensted_correspondence. 2If A = {1 < 2 < · · · < n}, the elements of the algebra P(A) can be identified with semistandard Young tableaux. It was discovered by D. Knuth [29] that modulo Knuth equivalence the equivalence classes of semistan- dard Young tableaux form an algebra, and he has named this algebra by tableaux algebra. It is easily seen that the tableaux algebra introduced by D. Knuth is isomorphic to the algebra introduced by M.-P. Schützenberger [65]. 3See, e.g., [36] for definition of noncommutative quasi-symmetric functions and polynomials. 4Let us stress that conditions necessary and sufficient to assure the commutativity of noncommutative elemen- tary polynomials for the number of variables equals n = 2 and n = 3 turn out to be weaker then that listed in [16]. https://en.wikipedia.org/wiki/Robinson-Schensted_correspondence 4 A.N. Kirillov We treat these kernels in the (reduced) plactic algebras PCn and PFn,m correspondingly. The algebras PCn and PFn,m are finite-dimensional and have bases parameterized by certain Young tableaux described in Sections 5.1 and 6 correspondingly. Decomposition of the rectangular Cauchy kernel with respect to the basis in the algebra PFn,m mentioned above, gives rise to a set of polynomials which are common generalizations of the (double) Schubert. β-Gro- thendieck, Demazure and Stanley polynomials. To be more precise, the polynomials listed above correspond to certain quotients of the plactic algebra PFn,m and appropriate specializations of parameters {pij} involved in our definition of polynomials Uα({pij}), see Section 6. As it was pointed out in the beginning of Introduction, the Knuth (or plactic) relations (1.1) have been discovered in [29] in the course of the study of algebraic and combinatorial proper- ties of the Robinson–Schensted correspondence. Motivated by the study of basic properties of a quantum version of the tropical/geometric Robinson–Schensted–Knuth correspondence – work in progress, but see [3, 26, 28, 59, 60] for definition and basic properties of the tropical/geometric RSK, – the author of the present paper came to a discovery that certain deformations of the Knuth relations preserve the Hilbert series (resp. the Hilbert polynomials) of the plactic alge- bras Pn and Fn (resp. the algebras PCn and PFn). More precisely, let {q2, . . . , qn} be a set of (mutually commuting) parameters, and Un := {u1, . . . , un} be a set of generators of the free associative algebra over Q of rank n. Let Y,Z ⊂ [1, n] be subsets such that Y ∪ Z = [1, n] and Y ∩ Z = ∅. Let us set p(a) = 0, if a ∈ Y and p(a) = 1, if a ∈ Z. Define q-deformed super Knuth relations among the generators u1, . . . , un as follows: SPLq : (−1)p(i)p(k)qkujuiuk = ujukui, i < j ≤ k, (−1)p(i)p(k)qkuiukuj = ukuiuj , i ≤ j < k. We define • q-deformed superplactic algebra SQPn to be the quotient of the free associative alge- bra Q〈u1, . . . , un〉 by the two-sided ideal generated by the set of q-deformed Knuth rela- tions (SPLq), • reduced q-deformed superplactic algebras SQPCn and SQPFn,m to be the quotient of the algebra SQPn by the two-sided ideals described in Definitions 5.18 and 6.7 correspon- dingly. We state Conjecture 1.1. The algebra SQPn and the algebras SQPCn and SQPFn,m, are flat defor- mations of the algebras Pn, PCn and PFn,m correspondingly. In fact one can consider more general deformation of the Knuth relations, for example take a set of parameters Q := {qik, 1 ≤ i < k ≤ n} and impose on the set of generators {u1, . . . , un} the following relations qikujuiuk = ujukui, i < j ≤ k, qikuiukuj = ukuiuj , i ≤ j < k. However we don’t know how to describe a set of conditions on parameters Q which imply the flatness of the corresponding quotient algebra(s), as well as we don’t know an interpretation and dimension of the algebras SQPCn and SQPFn,m for a “generic” values of parameters Q. We expect the dimension of algebras SQPCn and SQPFn,m each depends piece-wise polynomially on a set of parameters {qij ∈ Z≥0, 1 ≤ i < j ≤ n}, and pose a problem to describe its polynomiality chambers. We also mention and leave for a separate publication(s), the case of algebras and polynomials associated with superplactic monoid [38, 56], which corresponds to the relations SPLq with Notes on Schubert, Grothendieck and Key Polynomials 5 qi = 1, ∀ i. Finally we point out an interesting and important paper [55] wherein the case Z = ∅, and the all deformation parameters are equal to each other, has been independently introduced and studied in depth. Let us repeat that the important property of plactic algebras Pn is that the noncommutative elementary polynomials ek(u1, . . . , nn−1) := ∑ n−1≥a1≥a2≥ak≥1 ua1 · · ·uak , k = 1, . . . , n− 1, generate a commutative subalgebra inside of the plactic algebra Pn, see, e.g., [16, 46]. Therefore all our finite-dimensional algebras introduced in the present paper, have a distinguished finite- dimensional commutative subalgebra. We have in mined to describe these algebras explicitly in a separate publication. In Section 2 we state and prove necessary and sufficient conditions in order the elementary noncommutative polynomials form a mutually commuting family. Surprisingly enough to check the commutativity of noncommutative elementary polynomials for any n, it’s enough to check these conditions only for n = 2, 3. However a combinatorial meaning of a generalization of the Lascoux–Schützenberger plactic algebra Pn obtained in this way, is still missing. The plactic algebra PFn,m introduced in Section 6, has a monomial basis parametrized by the set of Young tableaux of shape λ ⊂ (nm) filled by the numbers from the set {1, . . . ,m}. In the case n = m it is well-known [20, 35, 58], that this number is equal to the number of symmetric plane partitions fitting inside the cube n × n × n. Surprisingly enough this number admits a factorization in the product of the number of totally symmetric plane partitions (TSPP) by the number of totally symmetric self-complementary plane partitions (TSSCPP) fit inside the same cube. A similar phenomenon happens if |m − n| ≤ 2, see Section 6. More precisely, we add to the well-known equalities #|B1,n| = 2n, #|B2,n| = ( 2n+ 1 n ) , #|B3,n| = 2n Catn+1 [67, A003645], #|B4,n| = 1 2 Catn+1 Catn+2 [67, A000356], #|Bn,5| = ( n+5 5 )( n+7 7 )( n+9 9 )( n+2 2 )( n+4 4 ) [67, A133348], the following relations #|Bn,n| = TSPP(n+ 1)×ASM(n), #|Bn,n+1| = TSPP(n+ 1)×ASM(n+ 1), #|Bn+2,n| = #|Bn,n+1|, #|Bn+3,n| = 1 2 #|Bn+1,n+1|, #|PP(n)| = #|TSSCPP(n)| ×#|ASMHT(2n)| = #|CSSCPP(2n)| ×#|CSPP(n)|, #|CSPP(2n)| = #|TSPP(2n)| ×#|CSTCPP(2n)|, #|CSPP(2n+ 1)| = 22n#|TSPP(2n+ 1)| ×#|TSPP(2n)|, where PP(n) stands for the set of plane partitions fit in a cub of size n × n × n; AMSHT(2n) denotes the set of alternating sign matrices of size 2n × 2n invariant under a half-turn and CSSPP(2n) denotes the set of cyclically symmetric self-complementary plane partitions fitting inside a cub of size 2n × 2n × 2n, see, e.g., [6]; CSTCPP(n) stands for the set of cyclically symmetric transpose complementary plane partitions fitting inside a cub of size 2n × 2n × 2n, see, e.g., [67, A051255]. See Section 6 for the definition of the sets Bn,m and examples. In Exercise 6.3 we state some (new) divisibility properties of the numbers #|Bn+4,n|. 6 A.N. Kirillov It is well-known that ASMHT(2n) = ASM(n)×CSPP(n), where CSPP(n) denotes the number of cyclically symmetric plane partitions fitting inside n-cube, and CSSCPP(2n) = ASM(n)2, see, e.g., [6, 37] and [67, A006366]. Problem 1.2. • Construct bijection between the set of plane partitions fit inside n-cube and the set of (ordered) triples (π1, π2, ℘), where (π1, π2) is a pair of TSSCPP(n) and ℘ is a cyclically symmetric plane partition fitting inside n-cube. • Describe the involution κ : PP(n) −→ PP(n) which is induced by the involution (π1, π2, ℘) −→ (π2, π1, ℘) on the set TSSCPP(n)×TSSCP(n)×CSPP(n), and its fixed points. Clearly one has #|Fix(κ)| = ASMHT(2n). • Characterize pairs of plane partitions (Π1,Π2) ∈ PP(n)× PP(n) such that (a) ℘(Π1) = ℘(Π2); (b) (π1(Π1), π2(Π1)) = (π1(Π2), π2(Π2)). These relations have straightforward proofs based on the explicit product formulas for the numbers #|SPP(n)| = ∏ 1≤i≤j≤k n+ i+ j + k − 1 i+ j + k − 1 , #|TSPP(n)| = n∏ i=1 n∏ j=i n∏ k=j i+ j + k − 1 i+ j + k − 2 , #|PP(n)| = n∏ i=0 n−1∏ j=1 3n− i− j 2n− i− j = n∏ i=1 ( 2n+i n )( n+i n ) , but bijective proofs of these identities are an open problem. It follows from [42, 46] that the dimension of the (reduced) plactic algebra PCn is equal to the number of alternating sign matrices of size n × n (note that ASM(n) = TSSCPP(n)). Therefore the key-Grothendieck polynomials can be obtained from U -polynomials (see Section 6, Theorem 6.12) after the specialization pij = 0, if i+ j > n+ 1. In Section 4 following [27] we introduce and study a family of polynomials which are a com- mon generalization of the Schubert, β-Grothendieck, dual β-Grothendieck, β-Demazure, β-key- Grothendieck, Bott–Samelson and q-Demazure polynomials, Whittaker functions (see [7] and Lemma 4.18) and Di Francesco–Zinn-Justin polynomials (see Section 4). Namely, for any per- mutation w ∈ Sn and composition ζ ⊂ δn := (n− 1, n− 2, . . . , 2, 1), we introduce polynomials KN (β,α,γ,h) w (Xn) = h`(w)Tsi1 · · ·Tsi` ( xδn ) , KD (β,α,γ,h) ζ (Xn) = h`(vζ)Tsi1 · · ·Tsi` ( xζ +) , where Ti := T (β,α,γ,h) i = −α+ ((α+ β + γ)xi + γxi+1 + h + h−1(α+ γ)(β + γ)xixi+1)∂i,i+1, i = 1, . . . , n− 1, denote a collection of divided difference operators which satisfy the Coxeter and Hecke relations TiTjTi = TjTiTj , if |i− j| = 1; TiTj = TjTi, if |i− j| ≥ 2, T 2 i = (β − α)Ti + βα, i = 1, . . . , n− 1; Notes on Schubert, Grothendieck and Key Polynomials 7 by definition for any permutation w ∈ Sn we set Tw := Tsi1 · · ·Tsi` , for any reduced decomposition w = si1 · · · si` of a permutation in question; ζ+ denotes a unique partition obtained from ζ by ordering its parts, and vζ ∈ Sn denotes the minimal length permu- tation such that vζ(ζ) = ζ+. Assume that h = 1.5 If α = γ = 0, these polynomials coincide with the β-Grothendieck polynomials [17], if β = α = 1, γ = 0 these polynomials coincide with the Di Francesco–Zinn- Justin polynomials [12], if β = γ = 0, these polynomials coincide with dual α-Grothendieck polynomials H(α) w (Xn),6 where by definition we set Xn := (x1, . . . , xn). Conjecture 1.3. For any permutation w ∈ Sn and any composition ζ ⊂ δn, polynomials KN (β,α,γ,h) w (Xn) and KD (α,β,γ,h) ζ (Xn) have nonnegative coefficients, i.e., KN (β,α,γ,h) w (Xn) ∈ N[α, β, γ, h][Xn], KD (β,α,γ,h) ζ (Xn) ∈ N[α, β, γ, h][Xn]. We expect that these polynomials have some geometrical meaning to be discovered. More generally we study divided difference type operators of the form Tij := T (a,b,c,h,e) ij = a+ (bxi + cxj + h+ exixj)∂ij , depending on parameters a, b, c, h, e and satisfying the 2D-Coxeter relations TijTjkTij = TjkTijTjk, 1 ≤ i < j < k ≤ n, TijTkl = TklTij , if {i, j} ∩ {k, l} = ∅. We find that the necessary and sufficient condition which ensure the validity of the 2D-Coxeter relations is the following relation among the parameters7: (a+ b)(a− c) + he = 0. Therefore, if the above relation between parameters a, b, c, h, e holds, then for any permu- tation w ∈ Sn the operator Tw := T (a,b,c,h,e) w = T (a,b,c,h,e) i1 · · ·T (a,b,c,h,e) i` , 5Clearly that if h 6= 0, then after rescaling parameters α, β and γ one can assume that h = 1. However, see, e.g., [27, Section 5], the parameter h plays important role in the study of different specializations of the variables xi, 1 ≤ i ≤ n− 1 and parameters α, β and γ. 6To avoid the reader’s confusion, let us explain that in our paper we use the letter α either as the lower index to denote a composition, or as the upper index to denote a parameter which appears in certain polynomials treated in our paper. For example H(α) α (Xn) denotes the dual α-Grothendieck polynomial corresponding to a composition α. Note that the α-Grothendieck polynomial G (α) w (Xn) can be obtained from the polynomial G (β) w (Xn) by replacing β by α. 7In other words, the divided difference operators {Tij := T (a,b,c,h,e) ij } which obey the 2D-Coxeter relations, have the following form: T (a,b,c,h) ij = ( 1 + (a+ b) h xi )( 1 + c− a h xj ) ∂ij + aσij , if h 6= 0, a, b, c arbitrary. If h = 0, then either Tij = ((c− a)xj + exixj)∂ij + aσij , or Tij = (a+ b)xi + exixj)∂ij + aσij , where σij stands for the exchange operator: σij(F (zi, zj)) = F (zj , zi). 8 A.N. Kirillov where w = si1 · · · si` is any reduced decomposition of w, is well-defined. Hence under the same assumption on parameters, for any permutation w ∈ Sn one can attach the well-defined polynomial G(a,b,c,h,e) w (X,Y ) := T (x) w (a,b,c,h,e) ( ∏ i≥1,j≥1 i+j≤n+1 (xi + yj) ) , and in much the same fashion to define polynomials D(a,b,c,h,e) α (X,Y ) := T (x) wα (a,b,c,h,e)( xα +) for any composition α such that αi ≤ n− i, ∀ i. We have used the notation T (x)(a,b,c,h,e) w to point out that this operator acts only on the variables X = (x1, . . . , xn); for any composition α ∈ Zn≥0, α+ denotes a unique partition obtained from α by reordering its parts in (weakly) decreasing order, and wα denotes a unique minimal length permutation in the symmetric group Sn such that wα(α) = α+. In the present paper we are interested in to list a conditions on parameters A := {a, b, c, h, e} with the constraint (a+ b)(a− c) + he = 0, which ensure that the above polynomials G (a,b,c,h,e) w (X) and D (a,b,c,h,e) α (X) or their specialization xi = 1, ∀ i, have nonnegative coefficients. We state the following conjectures: • KN (β,α,γ) w (Xn) ∈ N[α, β, γ][Xn], • G(−b,a+b+c,c,1,(b+c)(a+c) w (Xn) ∈ N[a, b, c][Xn], • G(−b,a+b+c,c+d,1,(b+c+d)(a+c) w (xi = 1, ∀ i) ∈ N[a, b, c, d], where a, b, c, d are free parameters. In the present paper we treat the case A = (−β, β + α+ γ, γ, 1, (α+ γ)(β + γ)). (1.2) As it was pointed above, in this case polynomials GAw(X) are common generalization of Schu- bert, β-Grothendieck and dual β-Grothendieck, and Di Francesco–Zinn-Justin polynomials. We expect a certain interpretation of the polynomials GAw for general β, α and γ. As it was pointed out earlier, one of the basic properties of the plactic monoid Pn is that the noncommutative elementary symmetric polynomials {ek(u1, . . . , un−1)}1≤k≤n−1 generate a com- mutative subalgebra in the plactic algebra in question. One can reformulate this statement as follows. Consider the generating function Ai(x) := i∏ a=n−1 (1 + xua) = i∑ a=0 ea(un−1, . . . , ui)x i−a, where we set e0(U) = 1. Then the commutativity property of noncommutative elementary symmetric polynomials is equivalent to the following commutativity relation in the plactic as well as in the generic plactic, algebras Pn and Pn [16], and Theorem 2.23, Ai(x)Ai(y) = Ai(y)Ai(x), 1 ≤ i ≤ n− 1. Now let us consider the Cauchy kernel C(Pn, U) = A1(z1) · · ·An−1(zn−1), Notes on Schubert, Grothendieck and Key Polynomials 9 where we assume that the pairwise commuting variables z1, . . . , zn−1 commute with the all generators of the algebras Pn and Pn. In what follows we consider the natural completion P̂n of the plactic algebra Pn to allow consider elements of the form (1 +xui) −1. Elements of this form exist in any Hecke type quotient of the plactic algebra P̃n. Having in mind this assumption, let us compute the action of divided difference operators ∂zi,i+1 on the Cauchy kernel. In the computation below, the commutativity property of the elements Ai(x) and Ai(y) plays the key role. Let us start computation of ∂zi,i+1(C(Pn, U)) = ∂zi,i+1(A1(z1) · · ·An−1(zn−1)). First of all write Ai+1(zi+1) = Ai(zi+1)(1+zi+1ui) −1. According to the basic property of the elements Ai(x), one sees that the expression Ai(zi)Ai(zi+1) is symmetric with respect to zi and zi+1, and hence is invariant under the action of divided difference operator ∂zi,i+1. Therefore, ∂zi,i+1(C(Pn, U)) = A1(z1) · · ·Ai(zi)Ai(zi+1)∂zi,i+1 ( (1 + zi+1ui) −1 ) ×Ai+2(zi+2) · · ·An−1(zn−1). It is clearly seen that ∂zi,i+1((1 + zi+1ui) −1) = (1 + ziui) −1(1 + zi+1ui) −1ui. Therefore, ∂zi,i+1(C(Pn, U)) = A1(z1) · · ·Ai(zi)Ai+1(zi+1)(1 + ziui) −1uiAi+2(zi+2) · · ·An−1(zn−1). It is easy to see that if one adds Hecke’s type relations on the generators u2 i = (a+ b)ui + ab, i = 1, . . . , n− 1, then (1 + zui) −1ui = ui − zab (1 + bz)(1− az) . Therefore in the quotient of the plactic algebra Pn by the Hecke type relations listed above and by the “locality” relations uiuj = ujui, if |i− j| ≥ 2, one obtains (−b+ (1 + zib))∂ z i,i+1 (A1(z1) · · ·An−1(zn−1)) = (A1(z1) · · ·An−1(zn−1)) ( ei − b 1− azi ) . Finally, if a = 0, then the above identity takes the following form ∂zi,i+1 ((1 + zi+1b)A1(z1) · · ·An−1(zn−1)) = (A1(z1) · · ·An−1(zn−1)) (ei − b). In other words the above identity is equivalent to the statement [19] that in the idCoxeter algebra ICn the Cauchy kernel C(Pn, U) is the generating function for the b-Grothendieck poly- nomials. Moreover, each (generalized) double b-Grothendieck polynomial is a positive linear combination of the key-Grothendieck polynomials. A proof of this statement is a corollary of the more general statement which will be frequently used throughout the present paper, namely, if an equivalence relation ≈2 is a refinement of that ≈1, that is if assumption a≈2 b =⇒ a≈1 b holds ∀ a, b, then each equivalence class w.r.t. relation ≈1 is disjoint union of the equivalence classes w.r.t. relation ≈2. In the special case b = −1 and Pij = xi + yj if 2 ≤ i + j ≤ n + 1, pij = 0, if i + j > n + 1, this result had been stated in [43]. As a possible mean to define affine versions of polynomials treated in the present paper, we introduce the double affine nilCoxeter algebra of type A and give construction of a generic family of Hecke’s type elements8 we will be put to use in the present paper. 8Remind that by the name a family of Hecke’s type elements we mean a set of elements {e1, . . . , en} such that e2i = Aei +B, A, B are parameters (Hecke type relations), eiej = ejei, if |i− j| ≥ 2, eiejei = ejeiej , if |i− j| = 1 (Coxeter relations). 10 A.N. Kirillov In Section 5.1 we suggest a common generalization of some combinatorial formulas from [10] and [21]. Namely, we give explicit formula ∏ 1≤i≤k, 1≤j≤n j−i≤n−k N − i− j + 1 i+ j − 1 ∏ 1≤i≤k, 1≤j≤n j−i>n−k N + i+ j − 1 i+ j − 1 (1.3) for the number of k-tuples of noncrossing Dyck paths connecting the points (0, 0) and (N,N − n−k). Interpretations of the number (1.3) as the number of certain k-triangulations of a convex (N + 1)-gon, or that of certain alternating sign matrices of size N ×N , are interesting tasks. In the case N = n + k we recover the [10, r.h.s. of formula (2)]. In the case k = 2 our formula (1.3) is equivalent to that obtained in [21]. Our proof that the number (1.3) counts certain k-tuples of noncrossing Dyck paths is based on the study of combinatorial properties of the so-called column multi-Schur functions s∗λ(Xn) introduced in Theorem 5.6, cf. [58, 72]. In particular we show that for rectangular partition λ = (nk) the polynomial s∗λ(Xn+k) is essentially coincide with the Schubert polynomial corresponding to the Richardson permutation 1k ×w(n) 0 . We introduce also a multivariable deformation of the numbers ASM(n), namely, ASM(Xn−1; t) := ∑ λ⊂δn s∗λ(X)t|λ|. Finally, in Section 5.1 we give combinatorial interpretations of rectangular and staircase compo- nents of the refined TSSCP vector [12] in terms of k-fans of noncrossing Dyck paths in rectangular case and Gandhi–Dumont polynomials and Genocchi numbers in staircase case. As Appendix we include several examples of polynomials studied in the present paper to illustrate results obtained in these notes. We also include an expository text concerning the MacNeille completion of a poset to draw attention of the reader to this subject. It is an exami- nation of the MacNeille completion of the poset associated with the (strong) Bruhat order on the symmetric group, that was one of the main streams of the study in the present paper. Namely, our concern was the challenge how to attach to each edge e of the MacNeille completionMN (Sn) of the Bruhat order poset on the symmetric group Sn an operator ∂e acting on the ring of polynomials Z[Xn], such that ∂e(Kh(e)) = Kt(e) together with compatibility conditions among the set of operators {∂e}e∈MN (Sn), that is for any two vertices of MN (Sn), say α and β, and a path pα,β in the MacNeille completion which connects these vertices, the naturally defined operator ∂pα,β depends only on the vertices α and β taken, and doesn’t depend on a path pα,β selected. As far as I know, this problem is still open. 2 Plactic, nilplactic and idplactic algebras Definition 2.1 ([46]). The plactic algebra Pn is an (unital) associative algebra over Z generated by elements {u1, . . . , un−1} subject to the set of relations (PL1) ujuiuk = ujukui, uiukuj = ukuiuj , if i < j < k, (PL2) uiujui = ujuiui, ujuiuj = ujujui, if i < j. Proposition 2.2 ([46]). Tableau words9 in the alphabet U = {u1, . . . , un−1} form a basis in the plactic algebra Pn. 9For the reader convenience we recall a definition of a tableau word. Let T be a (regular shape) semistandard Young tableau. The tableau word w(T ) associated with T is the reading word of T is the sequence of entries of T obtained by concatenating the columns of T bottom to top consecutively starting from the first column. For Notes on Schubert, Grothendieck and Key Polynomials 11 In other words, each plactic class contain a unique tableau word. In particular, Hilb(Pn+1, t) = (1− t)−n ( 1− t2 )−(n2). Remark 2.3. There exists another algebra over Z which has the same Hilbert series as that of the plactic algebra Pn. Namely, define algebra Ln to be an associative algebra over Z generated by the elements {e1, e2, . . . , en−1}, subject to the set of relations (ei, (ej , ek)) := eiejek − ejeiek − ejekei + ekejei = 0, for all1 ≤ i, j, k ≤ n− 1, j < k. Observe that the number of defining relations in the algebra Ln is equal to 2 ( n 3 ) . Note that elements e1 + e2 and e2e1 do not commute in the algebra L3, but do commute if are considered as elements in the plactic algebra P3. See Example 5.29(C) for some details. Exercise 2.4. • Show that the dimension of the degree k homogeneous component L(k) n of the algebra Ln is equal to the number semistandard Young tableaux of the size k filled by the numbers from the set {1, 2, . . . , n− 1}. • Let us set eij := (ei, ej) := eiej − ejei, i < j. Show that the elements {eij}1≤i<j≤n−1 generate the center of the algebra Ln. Definition 2.5. (a) The local plactic algebra LPn, see, e.g., [16], is an associative algebra over Z generated by elements {u1, . . . , un−1} subject to the set of relations uiuj = ujui, if |i− j| ≥ 2, uju 2 i = uiujui, u2 jui = ujuiuj , if |i− j| = 1. One can show (A.K.) that Hilb(LPn, t) = n∏ j=1 ( 1 1− tj )n+1−j . (b) The affine local plactic algebra P̂Ln, see [34], is an associative algebra over Q generated by the elements {e0, . . . , en−1} subject to the set of relations listed in item (a), where all indices are understood modulo n. (c) Let q be a parameter, the affine quantum local plactic algebra P̂L (q) n is an associative algebra over Q[q] generated by the elements {e0, . . . , en−1} subject to the set of relations example, take T = 1 2 3 3 2 3 4 3 4 5 The corresponding tableau word is w(T ) = 5321432433. By definition, a tableau word is the tableau word corresponding to some (regular shape) semistandard Young tableau. It is well-known [53] that the number of tableau subwords contained in the staircase word I (n) 0 := un−1un−2 · · ·u2u1︸ ︷︷ ︸un−1un−2 · · ·u2︸ ︷︷ ︸ · · ·un−1uu−2︸ ︷︷ ︸un−1︸ ︷︷ ︸ is equal to the number of alternating sign matrices ASM(n). 12 A.N. Kirillov (i) eiej = ejei, if |i− j| > 1, (ii) (1+q)eiejei = qe2 i ej +eje 2 i , (1+q)ejeiej = qeie 2 j +e2 jei, if |i−j| = 1, where all indices appearing in the relation (ii) are understood modulo n. It was observed in [33] that the relations listed in (ii) are the Serre relations of U≥q ( ĝl(n) ) rewritten10 in generators kiEi. Some interesting properties and applications of the local and affine local plactic algebras one can find in [33, 34, 36]. It seems an interesting problem to investigate properties and applications of the affine pseudoplactic algebra which is the quotient of the affine local plactic algebra L̂Pn by the two-sided ideal generated by the set of elements {(ej , (ei, ek)), 0 ≤ i < j < k ≤ n− 1}. Definition 2.6 (nil Temperley–Lieb algebra). Denote by T L(0) n the quotient of the local plactic algebra LPn by the two-sided ideal generated by the elements { u2 1, . . . , u 2 n−1 } . It is well-known that dim T Ln = Cn, the n-th Catalan number. One also has Hilb ( T L(0) 4 , t ) = (1, 3, 5, 4, 1), Hilb ( T L(0) 5 , t ) = (1, 4, 9, 12, 10, 4, 2), Hilb(T L6, t) = (1, 5, 14, 25, 31, 26, 16, 9, 4, 1). Proposition 2.7. The Hilbert polynomial Hilb(T Ln, t) is equal to the generating function for the number or 321-avoiding permutations of the set {1, 2, . . . , n} having the inversion number equals to k, see [67, A140717], for other combinatorial interpretations of the polynomials Hilb(T Ln, t). Exercise 2.8. • Show that degt Hilb(T Ln, t) = [ n2 4 ] . • Show that lim k→∞ tk 2 Hilb ( T L2k, t −1 ) = ∏ n≥1 ( 1− t4n−2 )( 1− t2n−1 )4( 1− t4n ) = ∑ n≥0 ant n, where an is equal to the number of 2-colored generalized Frobenius partitions, see, e.g., [67, A051136] and the literature quoted therein11. • Show that lim k→∞ tk(k+1) Hilb ( T L2k+1, t −1 ) = 2 ∏ n≥1 (1 + tn) ( 1 + t2n )2 1− tn = 2 ∑ n≥0 bnt n. See [67, A201078] for more details concerning relations of this exercise with the Ramanujan theta functions12. 10For the reader convenient, we recall, see, e.g., [33] the definition of algebra U≥q (ĝl(n)). Namely, this algebra is an unital associative algebra over Q(q±1) generated by the elements {k±1 i , Ei}i=0,...,n−1, subject to the set of relations (R1) kikj = kjki, kik −1 i = k−1 i = 1, ∀ i, j, (R2) kiEj = qδi,j−δi,j+1Ejki, (R3) (Serre relations) E2 iEi+1 − ( q + q−1)EiEi+1Ei + Ei+1E 2 i = 0, E2 i+1Ei − ( q + q−1)Ei+1EiEi+1 + EiE 2 i+1 = 0, where all indices are understood modulo n, e.g., en = e0. It is clearly seen that after rewriting the Serre relations (R3) in terms of the elements {ei := kiEi}0≤i≤n−1, one comes to the relations (ii) which have been listed in (c). 11The second equality in the above formula is due to G. Andrews [1]. The second formula for the generating function of the numbers {an}n≥0 displayed in [67, A051136], either contains misprints or counts something else. 12See, e.g., http://en.wikipedia.org/wiki/Ramanujan_theta_function. http://en.wikipedia.org/wiki/Ramanujan_theta_function Notes on Schubert, Grothendieck and Key Polynomials 13 We denote by T H(β) n the quotient of the local plactic algebra LPn by the two-sided ideal generated by the elements { u2 i − βui, i = 1, . . . , n− 1 } . Definition 2.9. The modified plactic algebra MPn is an associative algebra over Z generated by {u1, . . . , un−1} subject to the set of relations (PL1) and that ujujui = ujuiui, and uiujui = ujuiuj , if 1 ≤ i < j ≤ n− 1. Definition 2.10. The nilplactic algebra NPn is an associative algebra over Q generated by {u1, . . . , un−1}, subject to set of relations u2 i = 0, uiui+1ui = ui+1uiui+1, the set of relations (PL1), and that uiujui = ujuiuj , if |i− j| ≥ 2. Proposition 2.11 ([52]). Each nilplactic class not containing zero, contains one and only one tableau word. Proposition 2.12. The nilplactic algebra NPn has finite dimension, its Hilbert polynomial Hilb(NPn, t) has degree ( n 2 ) , and dimQ(NPn)(n2) = 1. Example 2.13. Hilb(NP3, t) = (1, 2, 2, 1), Hilb(NP4, t) = (1, 3, 6, 6, 5, 3, 1), Hilb(NP5, t) = (1, 4, 12, 19, 26, 26, 22, 15, 9, 4, 1), dimQ(NP5) = 139, Hilb(NP6, t) = (1, 5, 20, 44, 84, 119, 147, 152, 140, 224, 81, 52, 29, 14, 5, 1), dimQ(NP6) = 1008. Definition 2.14. The idplactic algebra IPn := IP(β) n is an associative algebra over Q[β] gene- rated by elements {u1, . . . , un−1} subject to the set of relations u2 i = βui, uiujui = ujuiuj , i < j, (2.1) and the set of relations (PL1). In other words,the idplactic algebra IP(β) n is the quotient of the modified plactic algebraMPn by the two-sided ideal generated by the elements { u2 i − βui, 1 ≤ i ≤ n } . Proposition 2.15. Each idplactic class not containing zero, contains a unique tableau word associated with a row strict semistandard Young tableau13. For each word w denote by rl(w) the length of a unique tableau word of minimal length which is idplactic equivalent to w. Example 2.16. Consider words in the alphabet {a < b < c < d}. Then rl(dbadc) = 4 = rl(cadbd), rl(dbadbc) = 5 = rl(cbadbd). Indeed, dbadc ∼ dbdac ∼ dbdca ∼ ddbca ∼ dbac, dbadbc ∼ dbabdc ∼ dabadc ∼ adbdac ∼ abdbca ∼ abbdca ∼ dbabc. 13Recall that a row strict semistandard Young tableau, say T , is a tableau such that the numbers in each row and each column of T are strictly increasing. For example, 1 2 3 5 6 2 3 6 8 4 5 7 14 A.N. Kirillov Note that according to our definition, tableau words w = 31, w = 13 and w = 313 belong to different idplactic classes. Proposition 2.17. The idplactic algebra IP(β) n has finite dimension, and its Hilbert polynomial has degree ( n 2 ) . Example 2.18. Hilb(IP3, t) = (1, 2, 2, 1), Hilb(IP4, t) = (1, 3, 6, 7, 5, 3, 1), dim(IP4) = 26, Hilb(IP5, t) = (1, 4, 12, 22, 30, 32, 24, 15, 9, 4, 1), dim(IP5) = 154, Hilb(IP6, t) = (1, 5, 20, 50, 100, 156, 188, 193, 173, 126, 84, 52, 29, 14, 5, 1), dim(IP6) = 1197, dim(IP7) = 9401. Note that for a given n some words corresponding to strict semistandard Young tableaux of size between 5 and ( n−1 2 ) are idplactic equivalent to zero. For example, 1 2 4 3 4 ∼ 31424 ∼ 31242 ∼ 13242 ∼ 13422 ∼ 0, 1 2 3 2 4 4 ∼ 421423 ∼ 421243 ∼ 412143 ∼ 142413 ∼ 124213 ∼ 122431 ∼ 0. It seems an interesting problem to count the number of all row strict semistandard Young tableaux contained in the staircase (n, n − 1, . . . , 2, 1) and bounded by n, as well as count the number the number of such tableaux which are idplactic equivalent to zero. For n = 2 these numbers are (6, 6), for n = 3 these numbers are (26, 26), for n = 4 these numbers are (160, 154) and for n = 5 they are (1427, 1197). Definition 2.19. The idplactic Temperly–Lieb algebra PT L(β) n is define to be the quotient of the idplactic algebra IP(β) n by the two-sided ideal generated by the elements {uiujui, ∀ i 6= j}. For example, Hilb ( PT L(0) 4 , t ) = (1, 3, 6, 4, 1)t, Hilb ( PT L(0) 5 , t ) = (1, 4, 12, 16, 14, 4, 2)t, Hilb ( PT L(0) 6 , t ) = (1, 5, 20, 40, 60, 46, 32, 10, 4, 1)t, Hilb ( PT L(0) 7 , t ) = (1, 6, 30, 80, 170, 216, 238, 152, 96, 44, 14, 4, 2)t. One can show that degt Hilb ( PT L(0) n , t ) = [ n2 4 ] , and Coefftmax Hilb(PT Ln, t) = { 1, if n is even, 2, if n is odd. Definition 2.20. The nilCoxeter algebra NCn is defined to be the quotient of the nilplactic algebra NPn by the two-sided ideal generated by elements {uiuj − ujui, |i− j| ≥ 2}. Notes on Schubert, Grothendieck and Key Polynomials 15 Clearly the nilCoxeter algebra NCn is a quotient of the modified plactic algebra MPn by the two-sided ideal generated by the elements {uiuj − ujui, |i− j| ≥ 2}. Definition 2.21. The idCoxeter algebra IC(β) n is defined to be the quotient of the idplactic algebra IP(β) n by the two-sided ideal generated by the elements {uiuj − ujui, |i− j| ≥ 2}. It is well-known, see, e.g., [42], that the algebra NCn and IC(β) n has dimension n!, and the elements {uw := ui1 · · ·ui`}, where w = si1 · · · si` is any reduced decomposition of w ∈ Sn, form a basis in the nilCoxeter and idCoxeter algebras NCn and IC(β) n . Remark 2.22. There is a common generalization of the algebras defined above which is due to S. Fomin and C. Greene [16]. Namely, define generalized plactic algebra P̃n to be an associative algebra generated by elements u1, . . . , un−1, subject to the relations (PL2) and relations ujui(ui + uj) = (ui + uj)ujui, i < j. (2.2) The relation (2.2) can be written also in the form uj(uiuj − ujui) = (uiuj − ujui)ui, i < j. Theorem 2.23 ([16]). For each pair of numbers 1 ≤ i < j ≤ n define Ai,j(x) = i∏ k=j (1 + xuk). Then the elements Ai,j(x) and Ai,j(y) commute in the generalized plactic algebra P̃n. Corollary 2.24. Let 1 ≤ i < j ≤ n be a pair of numbers. Noncommutative elementary polynomials eija := ∑ j≥i1≥···≥ik≥i ui1 · · ·uia, i ≤ a ≤ j, generate a commutative subalgebra Ci,j of rank j − i+ 1 in the plactic algebra Pn. Moreover, the algebra C1,n is a maximal commutative subalgebra of Pn. To establish Theorem 2.23, we are going to prove more general result. To start with, let us define generic plactic algebra Pn. Definition 2.25. The generic plactic algebra Pn is an associative algebra over Z generated by {e1, . . . , en−1} subject to the set of relations ej(ei, ej) = (ei, ej)ei, if i < j, (2.3) (ej , (ei, ek)) = 0, if i < j < k, (2.4) (ej , ek)(ei, ek) = 0, if i < j < k. (2.5) Hereinafter we shell use the notation (a, b) := [a, b] := ab− ba. Clearly seen that relations (2.3)–(2.5) are consequence of the plactic relations (PL1) and (PL2), but not vice versa. Theorem 2.26. Define An(x) = 1∏ k=j (1 + xek). Then the elements An(x) and An(y) commute in the generic plactic algebra Pn. Moreover the elements An(x) and An(y) commute if and only if the generators {e1, . . . , en−1} satisfy the relations (2.3)–(2.5). 16 A.N. Kirillov Proof. For n = 2, 3 the statement of Theorem 2.26 is obvious. Now assume that the state- ment of Theorem 2.26 is true in the algebra Pn. We have to prove that the commutator [An+1(x), An+1(y)] is equal to zero. First of all, An+1(x) = (1 + xen)An(x). Therefore [An+1(x), An+1(y)] = (1 + xen)[An(x), 1 + yen]An(y)− [An(y), 1 + xen]An(x). Using the standard identity [ab, c] = a[b, c] + [a, c]b, one finds that 1 xy [An(x), 1 + yen] = n−1∑ i= i+1∏ a=n−1 (1 + xea)(ei, en) 1∏ a=i−1 (1 + xea). Using relations (2.3) we can move the commutator (ei, en) to the left, since i < a < n, till we meet the term (1 + xen). Using relations (2.4) we see that (1 + xen)(ei, n) = (ei, n)(1 + xei). Therefore we come to the following relation 1 xy [An(x), 1 + yen] = 1∑ i=n−1 (ei, en) (1 + xei) 1∏ a=n−1 a6=i (1 + xea)An(y)− (1 + yei) 1∏ a=n−1 a6=i (1 + yea)An(x)  . Finally let us observe that according to the relation (2.5), (ei, en) ( (1 + xei)(1 + xen−1)− (1 + xen−1)(1 + xei) ) = x2(ei, en)(ei, en−1) = 0. Indeed, (ei, en)(ei, en−1) = (ei, en)eien−1 − (ei, en)en−1ei = enen−1(ei, en)− en−1en(ei, en) = 0. Therefore 1 xy [An(x), 1 + yen] = ( 1∑ i=n−1 (ei, en) ) [An(x), An(y)] = 0 according to the induction assumption. Finally, if i < j, then (ei + ej , ejei) = 0 ⇐⇒ (2.3); if i < j < k, and the relations 2.3 hold, then (ei + ej + ek, ejei + ekej + ekei) = 0 ⇐⇒ (2.4); if i < j < k, and relations (2.3) and (2.4) hold, then (ei + ej + ek, ekejei) = 0 ⇐⇒ (2.5); the relations (ejei + ekej + ekei, ekejei) = 0 are consequences of the above ones. � Let T be a semistandard tableau and w(T ) be the column reading word corresponding to the tableau T . Denote by R(T ) (resp. IR(T )) the set of words which are plactic (resp. idplactic) equivalent to w(T ). Let a = (a1, . . . , an) ∈ R(T ), where n := |T | (resp. a = (a1, . . . , am) ∈ IR(T ), where m ≥ |T |). Definition 2.27 (compatible sequences b). Given a word a ∈ R(T ) (resp. a ∈ IR(T )), denote by C(a) (resp. IC(a)) the set of sequences of positive integers, called compatible sequences, b := (b1 ≤ b2 ≤ · · · ≤ bm) such that bi ≤ ai, and if ai ≤ ai+1, then bi < bi+1. Finally, define the set C(T ) (resp. IC(T )) to be the union ⋃ C(a) (resp. the union ⋃ IC(a)), where a runs over all words which are plactic (resp. idplactic) equivalent to the word w(T ). Notes on Schubert, Grothendieck and Key Polynomials 17 Example 2.28. Take T = 2 3 3 . The corresponding tableau word is w(T ) = 323. We have R(T ) = {232, 323} and IR(T ) = R(T ) ⋃ {2323, 3223, 3232, 3233, 3323, 32323, . . . }. Moreover, C(T ) = { a : 232 323 323 323 323 b : 122 112 113 123 223 } , IC(T ) = C(T ) ⋃{ a : 2323 3223 3232 3233 3323 32323 b : 1223 1123 1122 1123 1223 11223 } . Let P := Pn := {pi,j , i ≥ 1, j ≥ 1, 2 ≤ i + j ≤ n + 1} be the set of (mutually commuting) variables. Definition 2.29. (1) Let T be a semistandard tableau, and n := |T |. Define the double key polynomial KT (P) corresponding to the tableau T to be KT (P) = ∑ b∈C(T ) n∏ i=1 pbi,ai−bi+1. (2) Let T be a semistandard tableau, and n := |T |. Define the double key Grothendieck polynomial GKT (P) corresponding to the tableau T to be GKT (P) = ∑ b∈IC(T ) m∏ i=1 pbi,ai−bi+1. In the case when pi,j = xi + yj , ∀ i, j, where X = {x1, . . . , xn} and Y = {y1, . . . , yn} denote two sets of variables, we will write KT (X,Y ), GKT (X,Y ), . . . , instead of KT (P), GKT (P), . . .. Definition 2.30. Let T be a semistandard tableau, denote by α(T ) = (α1, . . . , αn) the exponent of the smallest monomial in the set { xb := m∏ i=1 xbii , b ∈ C(T ) } with respect to the lexicographic order. We will call the composition α(T ) to be the bottom code of tableau T . 3 Divided difference operators In this subsection we remind some basic properties of divided difference operators will be put to use in subsequent sections. For more details, see [57]. Let f be a function of the variables x and y (and possibly other variables), and η 6= 0 be a parameter. Define the divided difference operator ∂xy(η) as follows ∂xy(η)f(x, y) = f(x, y)− f(η−1y, ηx) x− η−1y . Equivalently, (x− η−1y)∂xy(η) = 1− sηxy, where the operator sηxy acts on the variables (x, y, . . .) according to the rule: sηxy transforms the pair (x, y) to (η−1y, ηx), and fixes all other variables. We set by definition, sηyx := sη −1 xy . The operator ∂xy(η) takes polynomials to polynomials and has degree −1. The case η = 1 corresponds to the Newton divided difference operator ∂xy := ∂xy(1). 18 A.N. Kirillov Lemma 3.1. (0) sηxys ηξ xz = sξyzs η xy, sηxys ηξ xzs ξ yz = sξyzs ηξ xzs η xy, (1) ∂yx(η) = −η∂xy(η−1), sηxy∂yz(ξ) = η−1∂xz(ηξ)s η xy, (2) ∂xy(η)2 = 0, (3) (three term relation) ∂xy(η)∂yz(ξ) = η−1∂xz(ηξ)∂xy(η) + ∂yz(ξ)∂xz(ηξ). (4) (twisted Leibniz rule) ∂xy(η)(fg) = ∂xy(η)(f)g + sηxy(f)∂xy(η)(g), (5) (crossing relations, cf. [19, formula (4.6)]) • x∂xy(η) = η−1∂xy(η)y + 1, y∂xy(η) = η∂xy(η)x− η, • ∂xy(η)y∂yz(ξ) = ∂xz(ηξ)x∂xy(η) + ξ−1∂yz(ξ)z∂xz(ηξ), (6) ∂xy∂xz∂yz∂xz = 0. Let x1, . . . , xn be independent variables, and let Pn := Q[x1, . . . , xn]. For each i < j put ∂ij := ∂xixj (1) and ∂ji = −∂ij . From Lemma 3.1 we have ∂2 ij = 0, ∂ij∂jk + ∂ki∂ij + ∂jk∂ki = 0, ∂ijxj∂jk + ∂kixi∂ij + ∂jkxk∂ki, if i, j, k are distinct. It is interesting to consider also an additive or affine analog ∂xy[k] of the divided difference operators ∂xy(η), namely, ∂xy[k](f(x, y)) = f(x, y)− f(y − k, x+ k) x− y + k . One has ∂yx[k] = −∂xy[−k], and ∂xy[p]∂yz[q] = ∂xz[p+ q]∂xy[p] + ∂yz[q]∂xz[p+ q]. A short historical comments in order. As far as I know, the divided difference operator had been invented by I. Newton in/around the year 1687, see, e.g., [42, Ref. [142]]. Since that time the literature concerning divided differences, a plethora of its generalizations and applications in different fields of mathematics and physics, grows exponentially and essentially is immense. To the best of our knowledge, the first systematic use of the isobaric divided difference operators, namely πi(f) = ∂i(xif), and πi := πi − 1, goes back to papers by M. Demazure concerning the study of desingularization of Schubert varieties and computation of characters of certain modules which is nowadays called Demazure modules, see, e.g., [11] and the literature quoted therein; the first systematic use and applications of divided difference operators to the study of cohomology rings of partial flag varieties G/P and description of Schubert classes inside the former, goes back to a paper by I.N. Berstein, I.M. Gelfand and S.I. Gelfand [4]; it is A. Lascoux and M.-P. Schützenberger who had discovered a polynomial representative of a Schubert class in the cohomology ring of the type A complete flag varieties, and developed a rich and beautiful combinatorial theory of these polynomials, see [47, 49, 50, 51, 52] for acquainting the reader with basic ideas and results concerning the Lascoux–Schützenber Schubert polynomials. 4 Schubert, Grothendieck and key polynomials Let w ∈ Sn be a permutation, X = (x1, . . . , xn) and Y = (y1, . . . , yn) be two sets of variables. Denote by w0 ∈ Sn the longest permutation, and by δn = (n − 1, n − 2, . . . , 1) the staircase partition. For each partition λ define Rλ(X,Y ) := ∏ (i,j)∈λ (xi + yj). (4.1) Notes on Schubert, Grothendieck and Key Polynomials 19 For i = 1, . . . , n− 1, let si = (i, i+ 1) ∈ Sn denote the simple transposition that interchanges i and i + 1 and fixes all other elements of the set {1, . . . , n}. If α = (α1, . . . , αi, αi+1, . . . , αn) is a composition, we will write siα = (α1, . . . , αi+1, αi, . . . , αn). Definition 4.1 (cf. [42] and the literature quoted therein). • For each permutation w ∈ Sn the double Schubert polynomial Sw(X,Y ) is defined to be ∂ (x) w−1w0 (Rδn(X,Y )). • Let α be a composition. The key polynomials K[α](X) are defined recursively as follows: if α is a partition, then K[α](X) = xα; otherwise, if α and i are such that αi < αi+1, then K[si(α)](X) = ∂i ( xiK[α](X) ) . • The reduced key polynomials K̂[α](X) are defined recursively as follows: if α is a partition, then K̂[α](X) = K[α](X) = xα; otherwise, if α and i are such that αi < αi+1, then K̂[si(α)](X) = xi+1∂i ( K̂[α](X) ) . • For each permutation w ∈ Sn the double β-Grothendieck polynomial Gβw(X,Y ) is defined recursively as follows: if w = w0 is the longest element, then Gw0(X,Y ) = Rδn(X,Y ); if w and i are such that wi > wi+1, i.e., l(wsi) = l(w)− 1, then Gβwsi(X,Y ) = ∂ (x) i ( (1 + βxi+1)Gβw(X,Y ) ) . • For each permutation w ∈ Sn the double dual β-Grothendieck polynomial Hβw(X,Y ) is defined recursively as follows: if w = w0 is the longest element, then Hw0(X,Y ) = Rδn(X,Y ); if w and i are such that wi > wi+1, i.e., l(wsi) = l(w)− 1, then Hβwsi(X,Y ) = (1 + βxi)∂ (x) i ( Hβw(X,Y ) ) . • The key β-Grothendieck polynomials KG[α](X;β) are defined recursively as follows14: if α is a partition, then KG[α](X;β) = xα; otherwise, if α and i are such that αi < αi+1, then KG[si(α)](X;β) = ∂i ( (xi + βxixi+1) KG[α](X;β) ) . 14In the case β = −1 divided difference operators Di := ∂i(xi − xixi+1) [41, formula (6)] had been used by A. Lascoux to describe the transition on Grothendieck polynomials, i.e., stable decomposition of any Grothendieck polynomial corresponding to a permutation w ∈ Sn. into a sum of Grasmannian ones corresponding to a collection of Grasmannin permutations vλ ∈ S∞, see [41] for details. The above mentioned operators Di had been used in [41] to construct a basis Ωα|α ∈ Z≥0 that deforms the basis which is built up from the Demazure (known also as key) polynomials. Therefore polynomials KG[α](X;β = −1) coincide with those introduced by A. Lascoux in [41]. In [63] the authors give a conjectural construction for polynomials Ωα based on the use of extended Kohnert moves, see, e.g., [58, Appendix by N. Bergeron] for definition of the Kohnert moves. We state conjecture that J(β) α = KG[α](X;β), where polynomials J β) α are defined in [63] using the K-theoretic versions of the Kohnert moves. For β = −1 this Conjecture has been stated by C. Ross and A. Yong in [63]. It seems an interesting problem to relate the K-theoretic Kohnert moves with certain moves of first introduced in [17]. 20 A.N. Kirillov • The reduced key β-Grothendieck polynomials K̂G[α](X;β) are defined recursively as fol- lows: if α is a partition, then K̂G[α](X;β) = xα; otherwise, if α and i are such that αi < αi+1, then K̂G[si(α)](X;β) = (xi+1 + βxixi+1)∂i ( K̂G[α](X;β) ) . For brevity, we will write KG[α](X) and K̂G[α](X) instead of KG[α](X;β) and K̂G[α](X;β). Remark 4.2. We can also introduce polynomials Zw, which are defined recursively as follows: if w = w0 is the longest element, then Zw0(X) = xδn ; if w and i are such that wi > wi+1, i.e., l(wsi) = l(w)− 1, then Zwsi(X) = ∂i ( (xi+1 + xixi+1)Zw(X) ) . However, one can show that Zw(x1, . . . , xn) = (x1 · · ·xn)n−1Gw0ww0 ( x−1 n , . . . , x−1 1 ) . Theorem 4.3. The polynomials Sw(X,Y ), K[α](X), K̂[α](X), Gw(X,Y ), Hw(X,Y ), KG[α](X) and K̂G[α](X) have nonnegative integer coefficients. The key step in a proof of Theorem 4.3 is an observation that for a given n the all algebras involved in the definition of the polynomials listed in that theorem, happen to be a suitable quotients of the reduced plactic algebra Pn, and can be extracted from the Cauchy kernel associated with the algebra Pn (or that Pn,n). We will use notation Sw(X), Gw(X), . . . , for polynomials Sw(X, 0), Gw(X, 0), . . . . Definition 4.4. For each permutation w ∈ Sn the Di Francesco–Zinn-Justin polynomials DZw(X) are defined recursively as follows: if w is the longest element in Sn, then DZw(X) = Rδn(X, 0); otherwise, if w and i are such that wi > wi+1, i.e., l(wsi) = l(w)− 1, then DZwsi(X) = ( (1 + xi)∂ (x) i + ∂ (x) i (xi+1 + xixi+1) ) DZw(X). Conjecture 4.5. (1) Polynomials DZw(X) have nonnegative integer coefficients. (2) For each permutation w ∈ Sn the polynomial DZw(X) is a linear combination of key polynomials K[α](X) with nonnegative integer coefficients. As for defi nition of the double Di Francesco–Zinn-Justin polynomials DZw(X,Y ) they are well defined, but may have negative coefficients. Let β and α be two parameters, consider divided difference operator Ti := T β,αi = −β + ((β + α)xi + 1 + βαxixi+1)∂i,i+1. Definition 4.6. Let w ∈ Sn, define Hecke–Grothendieck polynomials KN β,α w (Xn) to be KN (β,α) w (Xn) := T β,αw ( xδn ) , where as before xδn := xn−1 1 xn−2 2 · · ·xn−1; if u ∈ Sn, then set T β,αu := T β,αi1 · · ·T β,αi` , where w = si1 · · · si` is any reduced decomposition of a permutation taken. Notes on Schubert, Grothendieck and Key Polynomials 21 More generally, let β, α and γ be parameters, consider divided difference operators Ti := T β,α,γi = −β + ((α+ β + γ)xi + γxi+1 + 1 + (β + γ)(α+ γ)xixi+1)∂i,i+1, i = 1, . . . , n− 1. For a permutation w ∈ Sn define polynomials KN (β,α,γ) w (Xn) := T β,α,γi1 · · ·T β,α,γi` ( xδn ) , where w = si1 · · · si` is any reduced decomposition of w. Remark 4.7. A few comments in order. (a) The divided difference operators { Ti := T (β,α,γ) i , i = 1, . . . , n − 1 } satisfy the following relations • (Hecke relations) T 2 i = (α− β)Ti + αβ, • (Coxeter relations) TiTi+1Ti = Ti+1TiTi+1, TiTj = TjTi, if |i− j| ≥ 2. Therefore the elements T β,α,γw are well defined for any w ∈ Sn. • (Inversion) (1 + xTi) −1 = 1 + (α− β)x− xTi (1− βx)(1 + αx) . (b) Polynomials KN (β,α,γ) w constitute a common generalization of • the β-Grothendieck polynomials, namely, G(β) w = KN (β,α=0,γ=0) w0w−1 , • the Di Francesco–Zinn-Justin polynomials, namely, DZw = KN (β=α=1,γ=0) w , • the dual α-Grothendieck polynomials, namely, KN (β=0,α,γ=0) w0w−1 = Hαw(X). Proposition 4.8. • (Duality) Let w ∈ Sn, ` = `(w) denotes its length, then (αβ 6= 0) KN (β,α) w (1) = (βα)`KN (α−1,β−1) w−1 (1). • (Stability) Let w ∈ Sn be a permutation and w = si1si2 · · · si` be any its reduced de- composition. Assume that ia ≤ n − 3, ∀ 1 ≤ a ≤ `, and define permutation w̃ := si1+1si2+1 · · · si`+1 ∈ Sn. Then KN (β,α) w (1) = KN (β,α) w̃ (1). It is well-known that • the number KN (β=1,α=1) w0 (1) is equal to the degree of the variety of pairs commuting ma- trices of size n× n [13, 30]. 22 A.N. Kirillov • the bidegree of the affine homogeneous variety Vw, w ∈ Sn [12] is equal to A(n2)−`(w)B(n2)+`(w)KN (β=α=A/B) w (1), see [9, 12, 30] for more details and applications. Conjecture 4.9. • Polynomials KN (β,α,γ) w (X) have nonnegative integer coefficients KN (β,α,γ) w (X) ∈ N[β, α, γ][Xn]. • Polynomials KN (β,α,γ) w (x1 = 1, ∀ i) have nonnegative integer coefficients KN (β,α,γ) w (xi = 1,∀i) ∈ N[β, α, γ]. • Double polynomials KN (β=0,α,γ) w (X,Y ) = T β=0,α,γ w (x) ∏ i+j≤n+1 i≥1, j≥1 (xi + yj) are well defined and have nonnegative integer coefficients15. • Consider permutation w = [n, 1, 2, . . . , n − 1] ∈ Sn. Clearly w = sn−1sn−2 · · · s2s1. The number KN (β=1,α=1,γ=0) w (1) is equal to the number of Schröder paths of semilength (n−1) in which the (2, 0)-steps come in 3 colors and with no peaks at level 1, see [67, A162326] for further properties of these numbers. It is well-known, see, e.g., [67, A126216], that the polynomial KN (β,α=0) w (1) counts the number of dissections of a convex (n+ 1)-gon according the number of diagonals involved, where as the polynomial KN (β,α) w (1) (up to a normalization) is equal to the bidegree of certain algebraic varieties introduced and studied by A. Knutson [30]. A few comments in order. (a) One can consider more general family of polynomials KN (a,b,c,d) w (Xn) by the use of the divided difference operators T a,b,c,di := −b+ ((b+ d)xi + cxi+1 + 1 + d(b+ c)xixi+1)∂xi,i+1 instead of that T β,α,γi . However the polynomials KN (a,b,c,d) w (1) ∈ Z[a, b, c, d] may have negative coefficients in general. Conjecturally, to ensure the positivity of polynomials KN (a,b,c,d) w (Xn), it is necessary take d := a+ c+ r. In this case we state conjecture KN (a,b,c,a+c+r) w (Xn) ∈ N[a, b, c, r]. We state more general Conjecture 1.1 in introduction. In the present paper we treat only the case r = 0, since a combinatorial meaning of polynomials KN (a,b,c,a+c+r) w (1) in the case r 6= 0 is missed for the author. (b) If γ 6= 0, the polynomials KN (β,α,γ) w (Xn) ∈ Z[α, β, γ][Xn] may have negative coefficients in general. Theorem 4.10. Let T be a semistandard tableau and α(T ) be its bottom code, see Defini- tion 2.27. Then KT (X) = K[α(T )](X), KGT (X) = KG[α(T )](X). 15Note that the assumption β = 0 is necessary. Notes on Schubert, Grothendieck and Key Polynomials 23 Let α = (α1 ≤ α2 ≤ · · · ≤ αr) be a composition, define partition α+ = (αr ≥ · · · ≥ α1). Proposition 4.11. If α = (α1 ≤ α2 ≤ · · · ≤ αr) is a composition and n ≥ r, then K[α](Xn) = sα+(Xr). For example, K[0, 1, 2, . . . , n−1] = ∏ 1≤i<j≤n (xi+xj). Note that K̂[0, 1, 2, . . . , n−1] = n∏ i=2 xi−1 i . Proposition 4.12. If α = (α1 ≤ α2 ≤ · · · ≤ αr) is a composition and n ≥ r, then KG[α](Xn) = G[α+](Xr). For example, KG[0, 1, 2, . . . , n− 1] = ∏ 1≤i<j≤n (xi + xj + xixj). Note that K̂G[0, 1, 2, . . . , n− 1] = n∏ i=2 xi−1 i n−1∏ i=1 (1 + xi) n−i. Definition 4.13. Define degenerate affine 2D nil-Coxeter algebra ANC(2) n to be an associative algebra over Q generated by the set of elements {{ui,j}1≤i<j≤n, x1, . . . , xn} subject to the set of relations • xixj = xjxi for all i 6= j, xiuj,k = uj,kxi, if i 6= j, k, • ui,juk,l = uk,lui,j , if i, j, k, l are pairwise distinct, • (2D-Coxeter relations) ui,juj,kui,j = uj,kui,juj,k, if 1 ≤ i < j < k ≤ n, • xiui,j = ui,jxj + 1, xjui,j = ui,jxi − 1. Now for a set of parameters16 A := (a, b, c, h, e) define elements Tij := a+ (bxi + cxj + h+ exixj)ui,j , i < j. Throughout the present paper we set Ti := Ti,i+1. Lemma 4.14. (1) T 2 i,j = (2a+ b− c)Ti,j − a(a+ b− c), if a = 0, then T 2 ij = (b− c)Tij. (2) 2D-Coxeter relations Ti,jTj,kTi,j = Tj,kTi,jTj,k are valid, if and only if the following relation among parameters a, b, c, e, h holds17 (a+ b)(a− c) + he = 0. (4.2) (3) Yang–Baxter relations Ti,jTi,kTj.k = Tj,kTi,kTi,j are valid if and only if b = c = e = 0, i.e., Tij = a+ duij. (4) T 2 ij = 1 if and only if a = ±1, c = b± 2, he = (b± 1)2. (5) Assume that parameters a, b, c, h, e satisfy the conditions (4.2) and that bc + 1 = he. Then TijxiTij = (he− bc)xj + (h+ (a+ b)(xi + xj) + exixj)Tij . 16By definition, a parameter is assumed to be belongs to the center of the algebra in question. 17The relation (4.1) between parameters a, b, c, e, h defines a rational four-dimensional hypersurface. Its open chart {eh 6= 0} contains, for example, the following set (cf. [41]): {a = p1p4 − p2p3, b = p2p3, c = p1p4, e = p1p3, h = p2p4}, where (p1, p2, p3, p4) are arbitrary parameters. However the points (−b, a + b + c, c, 1, (a + c)(b + c), (a, b, c) ∈ N3} do not belong to this set. 24 A.N. Kirillov Some special cases • (representation of affine modified Hecke algebra [71]) if A = (a,−a, c, h, 0), then TijxiTij = acxj + hTij, i < j, • if A = (−a, a+ b+ c, c, 1, (a+ c)(b+ c), then TijxiTij = abxj + (1 + (b+ c)(xi + xj) + (a+ c)(b+ c)xixj)Tij . (6) (Quantum Yang–Baxter relations, or baxterization of Hecke’s algebra generators.) Assume that parameters a, b, c, h, e satisfy the conditions (4.2) and that β := 2a+b−c 6= 0. Then (cf. [24, 44] and the literature quoted therein) the elements Rij(u, v) := 1 + λ−µ βµ Tij satisfy the twisted quantum Yang–Baxter relations Rij(λi, µj)Rjk(λi, νk)Rij(µj , νk) = Rjk(µj , νk)Rij(λi, νk)Rjk(λi, µj), i < j < k, where {λi, µi, νi}1≤i≤n are parameters. Corollary 4.15. If (a+ b)(a− c) + he = 0, then for any permutation w ∈ Sn the element Tw := Ti1 · · ·Til ∈ ANC (2) n , where w = si1 · · · sil is any reduced decomposition of w, is well-defined. Example 4.16. • Each of the set of elements s (h) i = 1 + (xi+1 − xi + h)ui,i+1 and t (h) i = −1 + (xi − xi+1 + h(1 + xi)(1 + xi+1))uij , i = 1, . . . , n− 1, by itself generate the symmetric group Sn. • If one adds the affine elements s (h) 0 := πs (h) n−1π −1 and t (h) 0 := πt (h) n−1π −1, then each of the set of elements { s (h) j , j ∈ Z/nZ } and { t (h) j , j ∈ Z/nZ } by itself generate the affine symmetric group Saff n , see (4.3) for a definition of the transformation π. • It seems an interesting problem to classify all rational, trigonometric and elliptic divided difference operators satisfying the Coxeter relations. A general divided difference ope- rator with polynomial coefficients had been constructed in [50], see also Lemma 4.14, relation (4.1). One can construct a family of rational representations of the symmetric group (as well as its affine extension) by “iterating” the transformations s (h) j , j ∈ Z/nZ. For example, take parameters a and b, define secondary divided difference operator ∂[a,b] xy := −1 + (b+ y − x)∂[a] xy , where ∂[a] xy := 1− s(a) xy a− x+ y , s(a) xy := −1 + (a+ x− y)∂xy. Observe that the set of operators { s [a,b] i := s [a,b] xi,xi+1 , i ∈ Z/nZ } gives rise to a rational repre- sentation of the affine symmetric group Saff n on the field of rational functions Z[a, b](Xn). In the special case a := A, b := A/h, h := 1 − β/2 the operators s [a,b] i coincide with operators Θi, i ∈ Z/nZ have been introduced in [31, equation (4.17)]. Notes on Schubert, Grothendieck and Key Polynomials 25 Let A = (a, b, c, h, e) be a sequence of integers satisfying the conditions (4.1). Denote by ∂Ai the divided difference operator ∂Ai = a+ (bxi + cxi+1 + h+ exixi+1)∂i, i = 1, . . . , n− 1. It follows from Lemma 4.14 that the operators { ∂Ai } 1≤i≤n satisfy the Coxeter relations ∂Ai ∂ A i+1∂ A i = ∂Ai+1∂ A i ∂ A i+1, i = 1, . . . , n− 1. Definition 4.17. (1) Let w ∈ Sn be a permutation. Define the generalized Schubert polynomial corresponding to permutation w as follows SA w(Xn) = ∂Aw−1w0 xδn , xδn := xn−1 1 xn−2 2 · · ·xn−1, and w0 denotes the longest element in the symmetric group Sn. (2) Let α be a composition with at most n parts, denote by wα ∈ Sn the permutation such that wα(α) = α+. Let us recall that α+ denotes a unique partition corresponding to composition α. Lemma 4.18. Let w ∈ Sn be a permutation. • If A = (0, 0, 0, 1, 0), then SA w(Xn) is equal to the Schubert polynomial Sw(Xn). • If A = (−β, β, 0, 1, 0), then SA w(Xn) is equal to the β-Grothendieck polynomial G (β) w (Xn) introduced in [17]. • If A = (0, β, 0, 1, 0) then SA w(Xn) is equal to the dual β-Grothendieck polynomial H(β) w (Xn), studied in depth for β = −1 and in the basis {xi := exp(ξl)} in [39]. • If A = (−1, 2, 0, 1, 1), then SA w(Xn) is equal to the Di Francesco–Zinn-Justin polynomials introduced in [12]. • If A = (1,−1, 1, h, 0), then SA w(Xn) is equal to the h-Schubert polynomials. In all cases listed above the polynomials SA w(Xn) have non-negative integer coefficients. Define the generalized key or Demazure polynomial corresponding to a composition α as follows KA α (Xn) = ∂Awαx α+ . • If A = (1, 0, 1, 0, 0), then KA α (Xn) is equal to key (or Demazure) polynomial corresponding to α. • If A = (0, 0, 1, 0, 0), then KA α (Xn) is equal to the reduced key polynomial. • If A = (1,0,1,0,β), then KA α (Xn) is equal to the key β-Grothendieck polynomial KG (β) α (Xn). • If A = (0, 0, 1, 0, β), then KA α (Xn) is equal to the reduced key β-Grothendieck polynomials. In all cases listed above the polynomials SA w(Xn) have non-negative integer coefficients. • If A = (−1, q−1,−1, 0, 0) and λ is a partition, then (up to a scalar factor) polynomial KA λ (Xn) can be identify with a certain Whittaker function (of type A), see [7, Theorem A]. Note that operator TAi := −1 + (q−1xi − xi+1)∂i, 1 ≤ i ≤ n − 1, satisfy the Coxeter and Hecke relations, namely (TAi )2 = (q−1 − 1)TAi + q−1. In [7] the operator TAi has been denoted by Ti. 26 A.N. Kirillov • Let w ∈ Sn be a permutation and m = (i1, . . . , i`) be a reduced word for w, i.e., w = si1 · · · si` and `(w) = `. Denote by Zm the Bott–Samelson nonsingular variety corre- sponding to the reduced word m. It is well-known that the Bott–Samelson variety Zm is birationally isomorphic to the Schubert variety Xw associated with permutation w, i.e., the Bott–Samelson variety Zm is a desingularization of the Schubert variety Xw. Following [7] define the Bott–Samelson polynomials Zm(x, λ, v) as follows Zm(x, λ, v) = ( 1 + TAi1 ) · · · ( 1 + TAi` ) xλ, where A = (−v,−1, 1, 0). Note that ( 1+TAi )2 = (1+v) ( 1+TAi ) , and the divided difference operators 1 + TAi = 1 + v + (xi+1 − vxi)∂i do not satisfy the Coxeter relations. • If A = (−β, β + α, 0, 1, βα), then SA w(Xn) constitutes a common generalization of the β-Grothendieck and the Di Francesco–Zinn-Justin polynomials. • If A = (t,−1, t, 1, 0), then the divided difference operators TAi := t+ (−xi + txi+1 + 1)∂i, 1 ≤ i ≤ n− 1, their baxterizations and the raising operator φ := (xn − 1)π, where π denotes the q−1-shift operator, namely π(x1, . . . , xn) = (xn/q, x1, . . . , xn−1), can be used to generate the interpolation Macdonald polynomials as well as the nonsymmetric Macdonald polynomials, see [45] for details. In similar fashion, relying on the operator φ, operators T β,α,γ,hi := −β + ((α+ β + γ)xi + γxi+1 + h + h−1(α+ γ)(β + γ)xixi+1)∂i, 1 ≤ i ≤ n− 1, and their baxterization, one (A.K.) can introduce polynomials Mβ,α,γ,q δ (Xn), where δ is a com- position. These polynomials are common generalizations of the interpolation Macdonald poly- nomials Mδ(Xn; q, t) (the case β = −t, α = −1, γ = t), as well as the Schubert, β-Grothendieck and its dual, Demazure and Di Francesco–Zinn-Justin polynomials, and conjecturally their affine analogues/versions. Details will appear elsewhere. Double aff ine nilCoxeter algebra. Let t, q, a, b, c, h, d be parameters. Definition 4.19. Define double affine nil-Coxeter algebra DANCn to be (unital) associative algebra over Q ( q±1, t±1 ) with the set of generators { e1, . . . , en−1, x1, . . . , xn, π ±1 } subject to relations • (nilCoxeter relations) eiej = ejei, if |i− j| ≥ 2, e2 i = 0, ∀ i, eiejei = ejeiej , if |i− j| = 1; • (crossing relations) xiek = ekxi, if k 6= i, i+ 1, xiei − eixi+1 = 1, eixi − xi+1ei = 1; • (affine crossing relations) πxi = xi+1π, if i < n, πxn = q−1x1π, πei = ei+1π, if i < n− 1, π2en−1 = qe1π 2. Notes on Schubert, Grothendieck and Key Polynomials 27 Now let us introduce elements e0 := πen−1π −1 and T0 := T a,b,c,h,d0 = πTn−1π −1 = a+ ( bxn + q−1cx1 + h+ q−1dx1xn ) e0. It is easy to see that πe0 = qe1π, πT a,b,c,h,d0 = T a,b,c,qh,q −1d 1 e1π = T a,b,c,h,d1 + ( (1− q)h+ ( 1− q−1 ) dx1x2 ) e1. Now let us assume that a = t, b = −t, d = e = 0, c = 1. Then, Ti = t+ (xi+1 − txi)ei, i = 1, . . . , n− 1, T0 = t+ ( q−1x1 − txn ) e0, T 2 i = (t− 1)T + t, 0 ≤ i < n, TixiTi = txi+1, 1 ≤ i < n, T0xnT0 = tq−1x1, T0T1T0 = T1T0T1, Tn−1T0Tn−1 = T0Tn−1T0, T0Ti = TiT0, if 2 ≤ i < n− 1. The operators Ti := T t,−t,1,0,0i , 0 ≤ i ≤ n− 1 have been used in [45] to give an “elementary” construction of nonsymmetric Macdonald polynomials. Indeed, one can realize the operator π as follows: π(f) = f(xn/q, x1, x2, . . . , xn−1), so that π−1(f) = (x2, . . . , xn, qx1), (4.3) and introduce the raising operator [45] to be φ(f(Xn)) = (xn − 1)π(f(Xn)). It is easily seen that φTi = Ti+1φ, i = 0, . . . , n− 2, and φ2Tn−1 = T1φ 2. It has been established in [45] how to use the operators φ, T1, . . . , Tn−1 to to give formulas for the interpolation Mac- donald polynomials. Using operators φ, T (a,b,c,h,d) i , i = 1, . . . , n − 1 instead of φ, T1, . . . , Tn−1, 1 ≤ i ≤ n−1, one get a 4-parameter generalization of the interpolation Macdonald polynomials, as well as the nonsymmetric Macdonald polynomials. It follows from the nilCoxeter relations listed above, that the Dunkl–Cherednik elements, cf. [8], Yi := ( 1∏ a=i−1 T−1 a ) π ( i+1∏ a=n−1 Ta ) , i = 1, . . . , n, where Ti = T t,−t,1,0,0i , generate a commutative subalgebra in the double affine nilCoxeter al- gebra DANCn. Note that the algebra DANCn contains lot of other interesting commutative subalgebras, see, e.g., [24]. It seems interesting to give an interpretation of polynomials generated by the set of opera- tors T t,−t,1,h,ei , i = 0, . . . , n − 1 in a way similar to that given in [45]. We expect that these polynomials provide an affine version of polynomials KN (−t,−1,1,1,0) w (X), w ∈ Sn ⊂ Saff n , see Remark 4.7. Note that for any affine permutation v ∈ Saff n , the operator T (a,b,c,h,d) v = T (a,b,c,h,d) i1 · · ·T (a,b,c,h,d) i` , where v = si1 · · · si` is any reduced decomposition of v, is well-defined up to the sign ±1. It seems an interesting problem to investigate properties of polynomials Lv[α](Xn), where v ∈ Saff n and α ∈ Zn≥0, and find its algebro-geometric interpretations. 28 A.N. Kirillov 5 Cauchy kernel Let u1, u2, . . . , un−1 be a set of generators of the free algebra Fn−1, which are assumed also to be commute with the all variables Pn := {pi,j , 2 ≤ i+ j ≤ n+ 1, i ≥ 1, j ≥ 1}. Definition 5.1. The Cauchy kernel C(Pn, U) is defined to be as the ordered product C(Pn, U) = n−1∏ i=1  i∏ j=n−1 (1 + pi,j−i+1uj)  . (5.1) For example, C(P4, U) = (1 + p1,3u3)(1 + p1,2u2)(1 + p1,1u1)(1 + p2,2u3)(1 + p2,1u2)(1 + p3,1u3). In the case {pij = xi, ∀ j} we will write Cn(X,U) instead of C(Pn, U). Lemma 5.2. C(Pn, U) = ∑ (a,b)∈Sn p∏ j=1 p{aj ,bj}w(a,b), (5.2) where a = (a1, . . . , ap), b = (b1, . . . , bp), w(a,b) = p∏ j=1 uaj+bj−1, and the sum in (5.2) runs over the set Sn := { (a,b) ∈ Np × Np |a = (a1 ≤ a2 ≤ · · · ≤ ap), ai + bi ≤ n, and if ai = ai+1 =⇒ bi > bi+1 } . We denote by S(0) n the set {(a,b) ∈ Sn |w(a,b) is a tableau word}. The number of terms in the r.h.s. of (5.1) is equal to 2(n2), and therefore is equal to the number #|STY(δn,≤ n)| of semistandard Young tableaux of the staircase shape δn := (n − 1, n− 2, . . . , 2, 1) filled by the numbers from the set {1, 2, . . . , n}. It is also easily seen that the all terms appearing in the r.h.s. of (5.2) are different, and thus #|Sn| = #|STY(δn,≤ n)|. We are interested in the decompositions of the Cauchy kernel C(Pn, U) in the algebras Pn, NPn, IPn, NCn and ICn. 5.1 Plactic algebra Pn Let λ be a partition and α be a composition of the same size. Denote by S̃TY(λ, α) the set of semistandard Young tableaux T of the shape λ and content α which must satisfy the following conditions: for each k = 1, 2, . . . , the all numbers k are located in the first k columns of the tableau T . In other words, the all entries T (i, j) of a semistandard tableau T ∈ S̃TY(λ, α) have to satisfy the following conditions: Ti,j ≥ j. For a given (semi-standard) Young tableau T let us denote by Ri(T ) the set of numbers placed in the i-th row of T , and denote by S̃TY0(λ, α) the subset of the set S̃TY(λ, α) involving only tableaux T which satisfy the following constrains R1(T ) ⊃ R2(T ) ⊃ R3(T ) ⊃ · · · . To continue, let us denote by An (respectively by A(0) n ) the union of the sets S̃TY(λ, α) (resp. that of S̃TY0(λ, α)) for all partitions λ such that λi ≤ n − i for i = 1, 2, . . . , n − 1, and all compositions α, l(α) ≤ n − 1. Finally, denote by An(λ) (resp. A(0) n (λ)) the subset of An (resp. A(0) n (λ)) consisting of all tableaux of the shape λ. Notes on Schubert, Grothendieck and Key Polynomials 29 Lemma 5.3. • |An(δn)| = 1, |An(δn−1)| = (n− 1)!, |An((n− 1))| = Cn−1 the (n− 1)-th Catalan number. More generally,∣∣An((1k))∣∣ = ( n− 1 k ) , |An((k))| = n− k n ( n+ k − 1 k ) = dimS(n−1,k) n+k−1 , k = 1 . . . , n− 1, cf. [67, A009766]; here dimSλn stands for the dimension of the irreducible representation of the symmetric group Sn corresponding to a partition λ ` n. • Let k ≥ ` ≥ 2, n ≥ k + 2, then |An((k, `))| = (n− k)(n− `+ 1)(k − `+ 1)(n2 − n− `(k + 1)) `!(k + 1)k(n+ k) ( n+ k k − 1 ) `−2∏ i=1 (n+ i), k = 1, . . . , n. The case k = ` has been studied in [21] where one can find a combinatorial interpretation of the numbers |An((k, k))| for all positive integers n; see also [67, A005701, A033276] for more details concerning the cases k = 2 and k = 3. Note that in the case k = ` one has n2−n−k(k+1) = (n+k)(n−k−1), and the above formula can be rewritten as follows (k ≥ 2) |An((k, k))| = (n− k − 1)(n− k)(n− k − 1) (k + 1)k2(k − 1) ( n+ k − 2 k − 2 ) ( n+ k − 1 k − 1 ) . • Boundary case: the number |AN ((nk))| for N = n+ k,18 ∣∣Ak+n (( nk ))∣∣ = ∣∣Ak+n (( (n+ 1)k )) | = det |Catn+i+j−1 |1≤i,j≤k = ∏ 1≤i≤j≤n i+ j + 2k i+ j . • More generally (A.K.),∣∣AN((nk))| = ∏ 1≤i≤k, 1≤j≤n j−i≤n−k N − i− j + 1 i+ j − 1 ∏ 1≤i≤k, 1≤j≤n j−i>n−k N + i+ j − 1 i+ j − 1 . Moreover, the number |AN ((nk))| also is equal to the number of k-tuples of noncrossing Dyck paths staring from the point (0, 0) and ending at the point (N,N − n− k).19 • There exists a bijection ρn : An −→ ASM(n) such that the image Im ( A(0) n ) contains the set of n× n permutation matrices. • The number of row strict (as well as column strict) diagrams λ ⊂ δn+1 is equal to 2n. Recall that a row-strict diagram20 λ is on such that λi − λi+1 ≥ 1, ∀ i; δn := (n − 1, n− 2, . . . , 2, 1). 18So far as we know, the third equality has been proved for the first time in [10]. The both sides of the third identity have a big variety of combinatorial interpretations such as the number of k-tuples of noncrossing Dyck paths; that of k-tringulations of a convex (n+ k+ 1)-gon; that of semistandard Young tableaux with entries from the set {1, . . . , n} having only columns of an even length and bounded by height 2k [10]; that of pipe dreams (or compatible sequences) associated with the Richardson permutation 1k × w (n) 0 ∈ Sn+k, etc., see, e.g., [67, A078920] and the literature quoted therein. It seems an interesting task to read off an alternating sign matrix of size (n+ k)× (n+ k) from a given k-triangulation of a convex n+ k + 1)-gon. 19So far as we know, for the case k = 2 an equivalent formula for the number of pairs of noncrossing Dyck paths connecting the points (0, 0) and (N,N − n− 2), has been obtained for the first time in [21]. 20Known also as a strict partition. 30 A.N. Kirillov Example 5.4. Take n = 5 so that ASM(5) = 429 and Cat(5) = 42. One has∣∣A(0) 5 ∣∣ = ∑ λ⊂δ4:=(4,3,2,1) λi−λi+1≥1 ∀ i ∣∣A(0) 5 (λ) ∣∣ = ∣∣A(0) 5 (∅) ∣∣+ ∣∣A(0) 5 ((1)) ∣∣+ ∣∣A(0) 5 ((2)) ∣∣+ ∣∣A(0) 5 ((3)) ∣∣ + ∣∣A(0) 5 ((2, 1)) ∣∣+ ∣∣A(0) 5 ((4)) ∣∣+ ∣∣A(0) 5 ((3, 1)) ∣∣+ ∣∣A(0) 5 ((3, 2)) ∣∣+ ∣∣A(0) 5 ((4, 1)) ∣∣ + ∣∣A(0) 5 ((4, 2)) ∣∣+ ∣∣A(0) 5 ((3, 2, 1)) ∣∣+ ∣∣A(0) 5 ((4, 3)) ∣∣+ ∣∣A(0) 5 ((4, 2, 1)) ∣∣ + ∣∣A(0) 5 ((4, 3, 1)) ∣∣+ ∣∣A(0) 5 ((4, 3, 2)) ∣∣+ ∣∣A(0) 5 ((4, 3, 2, 1)) ∣∣ = 1 + 4 + 9 + 14 + 6 + 14 + 16 + 4 + 21 + 14 + 4 + 1 + 9 + 2 + 1 + 1 = 121 (sum of 16 terms), 4∑ k=0 |A5((k))| = 1 + 4 + 9 + 14 + 14 = 42. We expect that the image ρn (⋃n−1 k=0 An((k)) ) coincides with the set of n × n permutation matrices corresponding to either 321-avoiding (or 132-avoiding) permutations. Now we are going to define a statistic n(T ) on the set An. Definition 5.5. Let λ be a partition, α be a composition of the same size. For each tableau T ∈ S̃TY(λ, α) ⊂ An(λ) define n(T ) = αn = #|{(i, j) ∈ λ|T (i, j) = n}|. Clearly, n(T ) ≤ λ1. Define polynomials Aλ(t) := ∑ T∈An(λ) tλ1−n(T ). It is instructive to display the numbers {An(λ), λ ⊂ δn} as a vector of the length equals to the n-th Catalan number. For example, A4(∅,(1), (2), (1, 1), (3), (2, 1), (1, 1, 1), (3, 1), (2, 2), (2, 1, 1), (3, 2), (3, 1, 1), (2, 2, 1), (3, 2, 1)) = (1, 3, 5, 3, 5, 6, 1, 6, 3, 2, 3, 2, 1, 1). It is easy to see that the above data, as well as the corresponding data for n = 5, coincide with the list of refined totally symmetric self-complementary plane partitions that fit in the box 2n× 2n× 2n (TSSCPP(n) for short) listed for n = 1, 2, 3, 4, 5 in [12, Appendix D]. In fact we have Theorem 5.6. The sequence {An(λ), λ ⊂ δn} coincides with the set of refined TSSCPP(n) numbers as defined in [12]. More precisely, • |An(λ;N)| = det ∣∣( N−i λ′j−j+i )∣∣ 1≤i,j≤`(λ) , • we have Aλ(N ; t) := det ∣∣∣∣∣ ( N − i− 1 λ′j − j + i− 1 ) + t ( N − i− 1 λ′j − j + i )∣∣∣∣∣ 1≤i,j≤`(λ) , Notes on Schubert, Grothendieck and Key Polynomials 31 • let λ be a partition, |λ| = n, consider the column multi-Schur polynomial and t-deformation thereof s∗λ(XN ) := det |eλ′j−j+i(XN−i)|1≤i,j≤`(λ), cf. [58, Chapter III], [72], and s∗λ(XN ; t) := det |xN−ieλ′j−j+i−1(XN−i−1) + teλ′j−j+i(XN−i−1)|1≤i,j≤`(λ), then, assuming that λ ⊂ δn and N ≥ λ1 + λ′`(λ), the polynomial s∗λ(XN ) has nonnegative (integer) coefficients, • polynomial Aλ(t) is equal to a t-analog of refined TSSCPP(n) numbers Pn(λ′n−1 + 1, . . . , λ′n−i+i, . . . , λ ′ 1 +n−1|t) introduced by means of recurrence relations in [12, relation (3.5)], • one has s∗((nk))(Xn+k) = Mn,k(Xn+k)S1k×w(n) 0 ( x−1 1 , . . . , x−1 k+n ) , where S 1k×w(n) 0 (Xn+k) denotes the Schubert polynomial corresponding to the permutation 1k × w(n) 0 = [1, 2, . . . , k, n+ k, n+ k − 1, . . . , k + 1], and Mn,k(Xn+k) = k∏ a=1 x−1 a n+k∏ a=1 x min(n+k−a+1,n) a . In particular, ∑ λ⊂δn Aλ(t) = ∑ 1≤j≤n−1 An,jt j−1, where An,j stands for the number of alternating sign matrices (ASMn for short) of size n× n with a 1 on top of the j-th column. Corollary 5.7 ([40, 46]). The number of different tableau subwords in the word w0 := n−1∏ j=1 { j∏ a=n−1 a } is equal to the number of alternating sign matrices of size n× n, i.e., |An| = |TSSCPP(n)| = |ASMn |. It is well-known [6] that An,j = ( n+ j − 2 j − 1 ) (2n− j − 1)! (n− j)! n−2∏ i=0 (3i+ 1)! (n+ i)! , and the total number An of ASM of size n× n is equal to An ≡ An+1,1 = n∑ j=1 An,j = n−1∏ i=0 (3i+ 1)! (n+ i)! . Theorem 5.8 (the case λ = δn := (n− 1, n− 2, . . . , 2, 1)). • One has Aδn(n+ 1; t) = n∏ j=2 (1 + jt). 32 A.N. Kirillov • Gandhi–Dumont polynomials (see [14] and [67, A036970]), Aδn(n+ 2; t) = n∑ k=2 Bn,kt k, Bn,k = ∑ {kj} n−1∏ j=2 ( 2j − kj−1 2j − kj ) , where the sum runs over set of sequences {1 ≤ k1 < k2 < · · · < kn−2 < kn−1 = 2n− k}. • In particular, Aδn(n+ 2; 0) = G2n, Aδn(n+ 2; 1) = G2n+2, where G2n = 2(22n − 1)B2n and B2n denotes the unsigned Genocchi numbers21, and B2n denotes the Bernoulli number, see, e.g., [67, A027642]. • Aδn(n+ 2;−1) = (−1)n. • Let Aδn(N ; t, q) denote the principal specialization xi := qi−1, i ≥ 1, of the polynomial s∗δn(XN ; t), and write Aδn(n+ 2; t, q) = n−1∑ k=2 Bn,k(q)t k. Then Bn,k(q) ∈ N[q]. For example, Aδ6(8; t) = (2073, 8146, 12840, 10248, 4200, 720)t, 2073 = G12, Aδ6(8; 1) = 38227 = G14, cf. [67, A036970]; A(2,1)(5; t, q) = q [ 4 2 ] q + t(q + q2)3 + t2q5 [ 3 1 ] q . The last example shows that the polynomials A(δn)(n + 2; t, q) give rise to a q-deformation of the polynomials pn+2(t; δn) associated with refined TSSCPP(n) introduced in [12] which appeared to be coin- cide (A.K.) with the Gandhi polynomials introduced, e.g., in [14]. However, the polynomials A(δn)(n+ 2; t, q) are different from a q-deformation of Gandhi polynomials defined in [22]. It is easy to see that Aδn(Xn+2; t) = A(1) δn (Xn; t) + xn+1A(2) δn (Xn; t) for some polynomials depending on the variables {x1, . . . , xn} with nonnegative integer coefficients. Theorem 5.9 (the Genocchi numbers of the second kind, [67, A005439]). • A(1) δn (t; xi = 1, ∀ i ∈ [1, n]) is a polynomial of the following form A(1) δn (t; xi = 1, ∀ i ∈ [1, n]) = tG (2) n−2 + · · ·+ (n− 1)!tn−2, A(1) δn (t = 1; xi = 1, ∀ i ∈ [1, n]) = G (2) n−2, where G (2) n stands for the n-th Genocchi number of the second kind. It is well known that G (2) n = 2n−1G (m) n , where G (m) n denotes the so-called n-th median Genocchi number [67, A000366]. • A(2) δn (t = 0; xi = 1, ∀ i ∈ [1, n]) = Gn−1, where as before, Gn denotes the n-th Genocchi number (of the first kind) [67, A036970]. Example 5.10. (1) Take λ = δ3 and n = 5, then Aδ3(X4; t) = t(x1 + x2) ( x2 3 + t(x1x2 + x1x3 + x2x3) ) + x4(x1x2 + x1x3 + x3x3 + t(x1 + x1)(x1 + x2 + x3)). Therefore, Aδ3(xi = 1, ∀ i ∈ [1, 3]; t) = 2t+ 6t2 + x4(3 + 6t). 21Recall that the unsigned Genocchi numbers are defined through the generting function 2t et + 1 = ∑ n≥1 G2n (2n)! (−1)nt2n, see, e.g., [14], or https://en.wikipedia.org/wiki/Genocchi_number. https://en.wikipedia.org/wiki/Genocchi_number Notes on Schubert, Grothendieck and Key Polynomials 33 (2) Take λ = δ4 and n = 6, then Aδ4(xi = 1, ∀ i ∈ [1, 4]; t) = 8t ( 1 + 3t+ 3t2 ) + x5 ( 17 + 46t+ 36t2 ) . (3) Take λ = δ5 and n = 7, then Aδ5(xi = 1, ∀ i ∈ [1, 5]; t) = t(56, 192, 240, 120)t + 5x6(31, 100, 114, 48)t. Therefore, the polynomialsAδn(Xn+1; t) andA(1) δn (Xn; t) define multi-parameter deformations of the Genocchi numbers of the first and the second types correspondingly. It is an interesting task to relate these polynomials with those have been studied in [22], if so. Problem 5.11. Give combinatorial interpretations of polynomials Apδn(N ;t,q) and A(nk)(N ;t,q) for all N ≥ pn− 1. Let as before STY(δn ≤ n) := ST n denotes the set of all semistandard Young tableaux of the staircase shape δn = (n − 1, n − 2, . . . , 2, 1) filled by the numbers from the set {1, . . . , n}. Denote by ST (0) n the subset of “anti-diagonally” increasing tableaux, i.e., ST (0) n = {T ∈ STY(δn,≤ n) |Ti,j ≥ Ti−1,j+1 for all 2 ≤ i ≤ n− 1, 1 ≤ j ≤ n− 2}. One (A.K.) can construct bijections ιn : Sn ∼ ST n, ζn : An ∼ ST (0) n such that Im(ιn) = Im(ζn). Proposition 5.12.∑ λ=(λ1,...,λn) ρn≥λ Kρn,λ ( n m0(λ), m1(λ), . . . , mn(λ) ) = 2(n2), ∑ λ=(λ1,...,λn) ρn≥λ ( n m0(λ), m1(λ), . . . , mn(λ) ) = Fn, where Fn denotes the number of forests of trees on n labeled nodes; Kρn,λ denotes the Kostka number, i.e., the number of semistandard Young tableaux of the shape ρn := (n − 1, n − 2, . . . , 1) and content/weight λ; for any partition λ = (λ1 ≥ λ2 ≥ · · · ≥ λn ≥ 0) we set mi(λ) = {j |λj = i}. Let α be a composition, we denote by α+ the partition obtained from α by reordering of its parts. For example, if α = (0, 2, 0, 3, 1, 0) then α+ = (3, 2, 1). Note that `(α) = 6, but `(α+) = 3. Now let α be a composition such that ρn ≥ α+, `(α) ≤ n, that is αj = 0, if j > `(α), |α| = ( n 2 ) and ∑ k≤j (ρn)k ≥ ∑ k≤j (α+)k, ∀ j. There is a unique semistandard Young tableau Tn(α) of shape ρn and content α which corre- sponds to the maximal configuration of type (ρn;α) and has all quantum numbers (riggings) equal to zero. It follows from Proposition 5.12 that #{α | `(α) ≤ n, ρn ≥ α+} = Fn. There- fore there is a natural embedding of the set of forests on n labeled nodes to the set of semi- standard Young tableaux of shape ρn filled by the numbers from the set [1, . . . , n]. We de- note by FT n ⊂ STY(ρn,≤ n) the subset {Tn(α) | ρn ≥ α+, `(α) ≤ n}. Note that the set 34 A.N. Kirillov Kn := {α | `(α) = n, (α)+ = ρn} contains n! compositions, and under the rigged configuration bijection the elements of the set Kn correspond to the key tableaux [52] of shape ρn. See also [2] for connections of the Lascoux–Schützenberger keys and ASM. Let us say a few words about the Kostka numbers Kρn,α. First of all, it’s clear that if α = (α1, α2, . . . ) is a composition such that α1 = n − 1, then Kρn,α = Kρn−1,α[1], where we set α[1] := (α2, . . .). Now assume that n = 2k + 1 is an odd integer, and consider partitions νn := (kn) and µn := ((k + 1)k, kk). Then Kρn,νn = Coeff(x1x2···xn)k  ∏ 1≤i<j≤n (xi + xj)  , ( 2k k ) Kρn,µn = Kρn,νn . It is well-known that the number Kρn,νn is equal to number of labeled regular tournaments with n := 2k + 1 nodes, see, e.g., [67, A007079]. In the case when n = 2k is an even number, one can show that Kρn,νn = Kρn−1,νn−1 , Kρn,µn = Kρn+1,µn+1 . Note that the rigged configuration bijection gives rise to an embedding of the set of labeled regular tournaments with n := 2k + 1 nodes to the set STY(ρn,≤ n), if n is an odd integer, and to the set STY(ρn−1,≤ n− 1), if n is even integer. Theorem 5.13. (1) In the plactic algebra Pn the Cauchy kernel has the following decomposition Cn(P, U) = ∑ T∈An KT (P)uw(T ). (2) Let T ∈ An, and α(T ) be its bottom code. Then KT (P)− ∏ (i,j)∈T p{i,T (i,j)−j+1} ≥ 0, and equality holds if and only if the bottom code α(T ) is a partition. Note that the number of different shapes among the tableaux in the set An is equal to the Catalan number Cn := 1 n+1 ( 2n n ) . Problem 5.14. Construct a bijection between the set An and the set of alternating sign matrices ASMn. Example 5.15. For n = 4 one has C4(X,U) = K[0] +K[1]u1 +K[01]u2 +K[001]u3 +K[11](u12 + u22) +K[2](u21 + u31) +K[101]u13 +K[02]u32 +K[011](u23 + u33) +K[3]u321 +K[12](u312 + u322) +K[21]u212 +K[111](u123 + u133 + u233 + u223 + u333) +K[021]u323 +K[201](u313 + u213) +K[31]u3212 +K[301]u3213 +K[22](u3132 + u2132 + u3232) +K[121](u3123 + u3233 + u3223) +K[211](u2123 + u2133 + u3133) +K[32]u32132 +K[311](u32123 + u32133) +K[221](u21323 + u31323 + u32323) +K[321]u321323. Notes on Schubert, Grothendieck and Key Polynomials 35 Let w ∈ Sn be a permutation with the Lehmer code α(w). Definition 5.16. Define the plactic polynomial PLw(U) to be PLw(U) = { ∑ T∈An, α(T )=α(w) uw(T ) } . Comments 5.17. It is easily seen from a definition of the Cauchy kernel that Cn(X,U) = ∑ α⊂δn K[α](X)PLw0w −1 α (U), where wα denotes a unique permutation in Sn with the Lehmer code equals α; K[α](X) denotes the key polynomial corresponding to composition α ⊂ δn. The polynomials PLw0w −1 α can be treated as a plactic version of noncommutative Schur and Schubert polynomials introduced and studied in [16, 29, 42, 52, 54]. Now let X = {x1, . . . , xn} be a set of mutually commuting variables, and I (n) 0 := { n− 1, n− 2, . . . , 2, 1︸ ︷︷ ︸ n−1 , . . . , n− 1, , n− 2, . . . , k + 1, k︸ ︷︷ ︸ n−k , . . . , n− 1, n− 2︸ ︷︷ ︸ 2 , n− 1 } be lexicographically maximal reduced expression for the longest element w0 ∈ Sn. Let I be a tableau subword of the set I0 := I (n) 0 . One can show (A.K.) that under the specialization ui = { xi, if i ∈ I0\I, 1, if i ∈ I the polynomial PLw0w −1 α (U) turns into the Schubert polynomial Swα(X). In a similar fashion, consider the decomposition Cn(X,U) = ∑ α⊂δn KG[α](X;−β)PLw0w −1 α (U ;β). One can show (A.K.) that under the same specialization as has been listed above, the polynomial PLw0w −1 α (U ;β) turns into the β-Grothendieck polynomial Gβwα(X). Definition 5.18. Define algebra PCn to be the quotient of the plactic algebra Pn by the two- sided ideal Jn by the set of monomials {ui1ui2 · · ·uin}, 1 ≤ i1 ≤ i2 ≤ · · · ≤ in ≤ n, #{a|ia = j} ≤ j, ∀ j = 1, . . . , n. Theorem 5.19. • The algebra PCn has dimension equals to ASM(n), • Hilb(PCn, q) = ∑ λ∈δn−1 |An(λ)|q|λ|, • Hilb((PCn+1)ab, q) = n∑ k=0 n−k+1 n+1 ( n+k n ) qk, cf. [67, A009766]. Definition 5.20. Denote by PC]n the quotient of the algebra PCn by the two-sided ideal gene- rated by the elements {uiuj − ujui, |i− j| ≥ 2}. Proposition 5.21. Dimension dimPC]n of the algebra PC]n is equal to the number of Dyck paths whose ascent lengths are exactly {1, 2, . . . , n+ 1}. 36 A.N. Kirillov See [67, A107876, A107877] where the first few of these numbers are displayed. Example 5.22. Hilb ( PC]5, t ) = (1, 4, 12, 27, 48, 56, 54, 38, 20, 7, 1)t, dimPC]5 = 268, Hilb ( PC]6, t ) = (1, 5, 18, 50, 116, 221, 321, 398, 414, 368, 275, 175, 89, 35, 9, 1)t, dimPC]6 = 2496, dimPC]7 = 28612. Example 5.23. Hilb(PC3, q) = (1, 2, 3, 1)q, Hilb(PC4, q) = (1, 3, 8, 12, 11, 6, 1)q, Hilb(PC5, q) = (1, 4, 15, 35, 69, 91, 98, 70, 35, 10, 1)q, Hilb(PC6, q) = (1, 5, 24, 74, 204, 435, 783, 1144, 1379, 1346, 1037, 628, 275, 85, 15, 1)q, Hilb(PC7, q) = (1, 6, 35, 133, 461, 1281, 3196, 6686, 12472, 19804, 27811, 33271, 34685, 30527, 22864, 14124, 7126, 2828, 840, 175, 21, 1)q. Problem 5.24. Denote by An the algebra generated by the curvature of 2-forms of the tautolo- gical Hermitian linear bundles ξi, 1 ≤ i ≤ n, over the flag variety F ln [66]. It is well-known [62] that the Hilbert polynomial of the algebra An is equal to Hilb(An, t) = ∑ F∈Fn tinv(F ) = ∑ F∈Fn tmaj(F ), where the sum runs over the set Fn of forests F on the n labeled vertices, and inv(F ) (resp. maj(F )) denotes the inversion index (resp. the major index) of a forest F .22 Clearly that dim(An)(n2) = dim(PCn)(n2) = dim(H?(F ln,Q))(n2) = 1. For example, Hilb(PC6, t) = (1, 5, 24, 74, 204, 435, 783, 1144, 1379, 1346, 1037, 628, 275, 85, 15, 1)t, Hilb(A6, t) = (1, 5, 15, 35, 70, 126, 204, 300, 405, 490, 511, 424, 245, 85, 15, 1)t, Hilb(H?(F ln,Q), t) = (1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1)t. We expect that dim(PCn)(n2)−1 = ( n 2 ) and dim(PCn)(n2)−2 = 3n+5 4 ( n+2 3 ) = s(n + 2, 2), where s(n, k) denotes the Stirling number of the first kind, see, e.g., [67, A000914]. Problem 5.25. (1) Is it true that Hilb(PCn, t) − Hilb(An, t) ∈ N[t]? If so, as we expect, does there exist an embedding of sets ι : F(n) ↪→ An such that inv(F ) = n(ι(F )) for all F ∈ Fn? See Section 5.1, Definition 5.5, for definitions of the set An and statistics n(T ), T ∈ An. 22For the readers convenience we recall definitions of statistics inv(F ) and maj(F ). Given a forest F on n labeled vertices, one can construct a tree T by adding a new vertex (root) connected with the maximal vertices in the connected components of F . The inversion index inv(F ) is equal to the number of pairs (i, j) such that 1 ≤ i < j ≤ n, and the vertex labeled by j lies on the shortest path in T from the vertex labeled by i to the root. The major index maj(F ) is equal to ∑ x∈Des(F ) h(x); here for any vertex x ∈ F , h(x) is the size of the subtree rooted at x; the descent set Des(F ) of F consists of the vertices x ∈ F which have the labeling strictly greater than the labeling of its child. Notes on Schubert, Grothendieck and Key Polynomials 37 (2) Define a “natural” bijection κ : STY(δn,≤ n)←→ 2δn such that the set κ(MT(n)) admits a “nice” combinatorial description. Here MT(n) denotes the set of (increasing) monotone triangles, namely, a subset of the set STY(δn,≤ n) consisting of tableaux {T = (ti,j) | i + j ≤ n + 1, i ≥ 1, j ≥ 1} such that ti,j ≥ ti−1,j+1, 2 ≤ i ≤ n, 1 ≤ j < n, cf. [68]; δn = (n − 1, n − 2, . . . , 2, 1); STY(δn,≤ n) denotes the set of semistandard Young tableaux of shape δn with entries bounded by n; 2δn stands for the set of all subsets of boxes of the staircase diagram δn. It is well-known that #| STY(δn,≤ n)| = 2δn = 2(n2). Comments 5.26. One can ask a natural question: when do noncommutative elementary poly- nomials e1(A), . . . , en(A) form a q-commuting family, i.e., ei(A)ej(A) = qej(A)ei(A), 1 ≤ i < j ≤ n? Clearly in the case of two variables one needs to necessitate the following relations eiejei + ejejei = qejeiei + qejeiej , i < j. Having in mind to construct a q-deformation of the plactic algebra Pn such that the wanted q-commutativity conditions are fulfilled, one would be forced to add the following relations qejeiej = ejejei and qejeiei = eieiejei, i < j. It is easily seen that these two relations are compatible iff q2 = 1. Indeed, ejejeiej = qejeiejei = q2ejejeiei =⇒ q2 = 1. In the case q = 1 one comes to the Knuth relations (PL1) and (PL2). In the case q = −1 one comes to the “odd” analogue of the Knuth relations, or “odd” plactic relations (OPLn), i.e., (OPLn) : ujuiuk = −ujukui, if i < j ≤ k ≤ n, and uiukuj = −ukuiuj , if i ≤ j < k ≤ n. Proposition 5.27 (A.K.). Assume that the elements {u1, . . . , un−1} satisfy the odd plactic rela- tions (OPLn). Then the noncommutative elementary polynomials e1(U), . . . , en(U) are mutually anticommute. More generally, let Qn := {qij}1≤i<j≤n−1 be a set of parameters. Define generalized plactic algebra QPn to be (unital) associative algebra over the ring Z[{q±1 ij }1≤i<j≤n−1] generated by elements u1, . . . , un−1 subject to the set of relations qikujuiuk = ujukui, if i < j ≤ k, and qikuiukuj = ukuiuj , if i ≤ j < k. (5.3) Proposition 5.28. Assume that qij := qj, ∀ 1 ≤ i < j be a set of invertible parameters. Then the reduced generalized plactic algebra QPCn is a free Z[q±1 2 , . . . , q±1 n−1]-module of rank equals to the number of alternating sign matrices ASM(n). Moreover, Hilb(QPCn, t) = Hilb(PCn, t),Hilb(QPn, t) = Hilb(Pn, t). Recall that reduced generalized plactic algebra QPCn is the quotient of the generalized plactic algebra by the two-sided ideal Jn introduced in Definition 5.18. 38 A.N. Kirillov Example 5.29. (A) Super plactic monoid [38, 56]. Assume that the set of generators U := {u1, . . . , un−1} is divided on two non-crossing subsets, say Y and Z, Y ∪ Z = U, Y ∩ Z = ∅. To each element u ∈ U let us assign the weight wt(u) as follows: wt(u) = 0 if u ∈ Y , and wt(u) = 1 if u ∈ Z. Finally, define parameters of the generalized plactic algebra QPn to be qij = (−1)wt(ui)wt(uj). As a result we led to conclude that the generalized plactic algebra QPn in question coincides with the super plactic algebra PS(V ) introduced in [56]. We will denote this algebra by SPk,l, where k = |Y |, l = |Z|. We refer the reader to papers [56] and [38] for more details about connection of the super plactic algebra and super Young tableaux, and super analogue of the Robinson–Schensted–Knuth correspondence. We are planning to report on some properties of the Cauchy kernel in the (reduced) super plactic algebra elsewhere. (B) q-analogue of the plactic algebra. Now let q 6= 0,±1 be a parameter, and assume that qij = q, ∀ 1 ≤ i < j ≤ n − 1. This case has been treated recently in [55]. We expect that the generalized Knuth relations (5.3) are related with quantum version of the tropi- cal/geometric RSK-correspondence (work in progress), and, as expected, with a q-weighted version of the Robinson–Schensted algorithm, presented in [60]. Another interesting prob- lem is to understand a meaning of Q-plactic polynomials coming from the decomposition of the (plactic) Cauchy kernels Cn and Fn in the reduced generalized plactic algebra QPCn (work in progress). (C) Quantum pseudoplactic algebra PPL (q) n [36]. By definition, the quantum pseudoplactic algebra PPLn (q) is an associative algebra, generated, say over Q, by the set of elements {e1, . . . , en−1} subject to the set of defining relations (a) (1 + q)eiejei − qe2 i ej − eje2 i = 0, (1 + q)ejeiej − e2 jej − qeie2 j = 0, i < j, (b) (ej , (ei, ek)) := ejeiek − ejekei − eiekej + ekeiej = 0, i < j < k. Note that if q = 1, then the relations (a) can be written in the form (ei, (ei, ej)) = 0 and (e2, (ej , (ei, ej)) = 0 correspondingly. Therefore, PPL (q=1) 3 is the universal enveloping algebra over Q of the Lie algebra sl+3 . The quotient of the algebra PPLq=1 n by the two-sided ideal generated by the elements (ei, (ej , ek)), i, j, k are distinct, is isomorphic to the algebra from Remark 2.3. Define noncommutative q-elementary polynomials Λk(q;Xn), cf. [36], as follows Λk(X; q) := ∑ n≥i1>i2>···>ik≥1 (xi1 , (xi2 , (. . . , (xik−1 , xik)q) · · · )q)q. (5.4) Proposition 5.30 ([36]). The noncommutative q-elementary polynomials {Λk(En−1;q)}1≤k≤n−1} are pairwise commute in the algebra PPL (q) n . 5.2 Nilplactic algebra NPn Let λ be a partition and α be a composition of the same size. Denote by ŜTY(λ, α) the set of columns and rows strict Young tableaux T of the shape λ and content α such that the corresponding tableau word w(T ) is reduced, i.e., l(w(T )) = |T |. Denote by Bn the union of the sets ŜTY(λ, α) for all partitions λ such that λi ≤ n − i for i = 1, 2, . . . , n− 1, and all compositions α, α ⊂ δn. For example, |Bn| = 1, 2, 6, 25, 139, 1008, . . . , for n = 1, 2, 3, 4, 5, 6, . . . . Notes on Schubert, Grothendieck and Key Polynomials 39 Theorem 5.31. (1) In the nilplactic algebra NPn the Cauchy kernel has the following decomposition Cn(P, U) = ∑ T∈Bn KT (P)uw(T ). (2) Let T ∈ Bn be a tableau, and assume that its bottom code is a partition. Then KT (P) = ∏ (i,j)∈T p{i,T (i,j)−j+1}. Example 5.32. For n = 4 one has C4(X,U) = K[0] +K[1]u1 +K[01]u2 +K[001]u3 +K[11]u12 +K[2](u21 + u31) +K[101]u13 +K[02]u32 +K[011]u23 +K[3]u321 +K[12]u312 +K[21]u212 +K[111]u123 +K[021]u323 +K[201]u213 +K[31]u3212 +K[301]u3213 +K[22]u2132 +K[121]u3123 +K[211]u2123 +K[32]u32132 +K[311]u32123 +K[221]u21323 +K[321]u321323. 5.3 Idplactic algebra IPn Let λ be a partition and α be a composition of the same size. Denote by STY(λ, α) the set of columns and rows strict Young tableaux T of the shape λ and content α such that l(w(T )) = rl(w(T )), i.e., the tableau word23 w(T ) is a unique tableau word of minimal length in the idplactic class of w(T ), cf. Example 2.16. Denote by Dn the union of the sets STY(λ, α) for all partitions λ such that λi ≤ n − i for i = 1, 2, . . . , n− 1, and all compositions α, l(α) ≤ n− 1. For example, #|Dn| = 1, 2, 6, 26, 154, 1197, . . . , for n = 1, 2, 3, 4, 5, 6, . . . . Theorem 5.33. (1) In the idplactic algebra IPn the Cauchy kernel has the following decomposition Cn(X,Y, U) = ∑ T∈Dn KGT (X,Y )uw(T ). (2) Let T ∈ Dn be a tableau, and assume that its bottom code is a partition. Then KGT (X,Y ) = KT (X,Y ) = ∏ (i,j)∈T (xi + yT (i,j)−j+1). Example 5.34. For n = 4 one has C4(X,U) = KG[0] + KG[1]u1 + KG[01]u2 + KG[001]u3 + KG[11]u12 + KG[2](u21 + u31) + KG[101]u13 + KG[02]u32 + KG[011]u23 + KG[3]u321 + KG[12]u312 + KG[21]u212 + KG[111]u123 + KG[021]u323 + KG[201](u313 + u213) +K[31]u3212 + KG[301]u3213 + KG[22]u2132 + KG[121]u3123 + KG[211]u2123 + KG[32]u32132 + KG[311]u32123 + KG[221]u21323 + KG[321]u321323. Theorem 5.35. For each composition α the key Grothendieck polynomial KG[α](X) is a linear combination of key polynomials K[β](X) with nonnegative integer coefficients. 23See page 11 for the definition of tableau word. 40 A.N. Kirillov 5.4 NilCoxeter algebra NCn Theorem 5.36. In the nilCoxeter algebra NCn the Cauchy kernel has the following decompo- sition Cn(X,Y, U) = ∑ w∈Sn Sw(X,Y )uw. Let w ∈ Sn be a permutation, denote by R(w) the set of all its reduced decompositions. Since the nilCoxeter algebra NCn is the quotient of the nilplactic algebra NPn, the set R(w) is the union of nilplactic classes of some tableau words w(Ti): R(w) = ⋃ C(Ti). Moreover, R(w) consists of only one nilplactic class if and only if w is a vexillary permutation. In general case we see that the set of compatible sequences CR(w) for permutation w is the union of sets C(Ti). Corollary 5.37. Let w ∈ Sn be a permutation of length l, then (1) Sw(X,Y ) = ∑ b∈CR(w) xb1 · · ·xbl. (2) Double Schubert polynomial Sw(X,Y ) is a linear combination of double key polynomials KT (X,Y ), T ∈ Bn, w = w(T ), with nonnegative integer coefficients. 5.5 IdCoxeter algebras IC±n Theorem 5.38. In the IdCoxeter algebra IC+ n with β = 1, the Cauchy kernel has the following decomposition Cn(X,Y, U) = ∑ w∈Sn Gw(X,Y )uw. Theorem 5.39. In the IdCoxeter algebra IC−n with β = −1, one has the following decomposition n−1∏ i=1  i∏ j=n−1 ((1 + xi)(1 + yj−i+1) + (xi + yj−i+1)uj)  = ∑ w∈Sn Hw(X,Y )uw. A few remarks in order. (a) The (dual) Cauchy identity (5.4) is still valid in the idplactic algebra with constrain u2 i = −βui, i = 1, . . . , n− 1. (b) The left hand side of the identity (5.4) can be written in the following form ∏ 1≤i,j≤n i+j≤n (xi + yj) n−1∏ i=1  i∏ j=n−1 1 1− (xi + yj−i+1 + βxiyj−i+1)uj  . Indeed, (1 + βx+ xui)(1− xui) = 1 + βx, since u2 i = −βui. Let w ∈ Sn be a permutation, denote by IR(w) the set of all decompositions in the idCoxeter algebra ICn of the element uw as the product of the generators ui, 1 ≤ i ≤ n − 1, of the algebra ICn. Since the idCoxeter algebra ICn is the quotient of the idplactic algebra IPn, the set IR(w) is the union of idplactic classes of some tableau words w(Ti): IR(w) = ⋃ IR(Ti). Moreover, the set of compatible sequences IC(w) for permutation w is the union of sets IC(Ti). Corollary 5.40. Let w ∈ Sn be a permutation of length l, then (1) Gw(X,Y ) = ∑ b∈IC(w) l∏ i=1 (xbi + yai−bi+1). (2) Double Grothendieck polynomial Gw(X,Y ) is a linear combination of double key Grothen- dieck polynomials KGT (X,Y ), T ∈ Bn, w = w(T ), with nonnegative integer coefficients. Notes on Schubert, Grothendieck and Key Polynomials 41 6 F-kernel and symmetric plane partitions Let us fix natural number n and k, and a partition λ ⊂ (nk). Clearly the number of such partitions is equal to ( n+k n ) ; note that in the case n = k the number ( 2n n ) is equal to the Catalan number of type Bn. Denote by Bn,k(λ) the set of semistandard Young tableaux of shape λ ⊂ (nk) filled by the numbers from the set {1, 2, . . . , n}. For a tableau T ∈ Bn,k set as before, n(T ) := Card{(i, j) ∈ λ | T (i, j) = n}, and define polynomial Bn,k(λ)(q) := ∑ T∈Bn,k(λ) qλ1−n(T ). (6.1) Denote by Bn,k := ⋃ λ⊂(nk) Bn,k(λ). Lemma 6.1 ([20, 35]). The number of elements in the set Bn,k is equal to #|Bn,k| = ∏ 1≤i≤j≤k i+ j + n− 1 i+ j − 1 = ∏ 0≤2a≤k−1 ( n+2k−2a−1 n )( n+2a n ) . See also [67, A073165] for other combinatorial interpretations of the numbers #|Bn,k|. For example, the number #|Bn,k| is equal to the number of symmetric plane partitions that fit inside the box n × k × k. Note that Bn,k = T (n + k, k), where the triangle of positive integers {T (n+ k, k)} can be found in [67, A102539]. Proposition 6.2. One has • #|Bn,n| := SPP(n+ 1) = TSPP(n+ 1)×ASM(n), #|Bn,n+1| = TSPP(n+ 1)×ASM(n+ 1), where TSPP(n) denotes the number of totally symmetric plane partitions f it inside the n×n×n- box, see, e.g., [67, A005157], whereas ASM(n) = TSSCPP(2n) denotes the of n× n alternating sign matrices, and TSSCPP(2n) denotes the number of totally symmetric self-complimentary plane partitions fit inside the 2n× 2n× 2n-box. • #|Bn+2,n| = #|Bn,n+1|. Note that in the case n = k the number Bn := Bn,n is equal to the number of symmetric plane portions fitting inside the n× n× n-box, see [67, A049505]. Let us point out that in general it may happen that the number #|Bn,n+2| is not divisible by any ASM(m), m ≥ 3. For example, B3,5 = 4224 = 25×3×11. On the other hand, it’s possible that the number #|Bn,n+2| is divisible by ASM(n+ 1), but does not divisible by ASM(n+ 2). For example, B4,6 = 306735 = 715×429, but 306735 - 7436 = ASM(6). Exercise 6.3. (a) Show that Bn+4,n is divisible by TSPP(n+ 2), if n ≡ 1 (mod 2), n ≥ 3, ASM(n+ 2), if n ≡ 2 (mod 8), ASM(n+ 1) and ASM(n+ 2), if n ≡ 4 (mod 8), n 6= 4; B8,4 = ASM(5)2, ASM(n+ 1) and ASM(n+ 2), if n ≡ 6 (mod 8), ASM(n+ 1), if n ≡ 0 (mod 8), n ≥ 1. 42 A.N. Kirillov (b) Show that Bn,n+4 is divisible by{ ASM(n+ 1), if n ≡ 0 (mod 2), TSPP(n+ 1), if n ≡ 1 (mod 2). In all cases listed in Exercise 6.3, it is an open problem to give combinatorial interpretations of the corresponding ratios. Problem 6.4. Let a is equal to either 0 or 1. Construct bijection between the set SPP(n, n+ a, n+ a) of symmetric plane partitions fitting inside the box n× n+ a× n+ a and the set of pairs (P,M) where P is the totally symmetric plane partitions fitting inside the box n× n× n and M is an alternating sign matrix of size n+ a× n+ a. Example 6.5. Take n = 3. One has #|B3| = 112 = 16× 7. The number of partitions λ ⊂ (33) is equal to 20, namely, the following partitions{ ∅, (1), (2), (1, 1), (3), (2, 1), ( 13 ) , (3, 1), (2, 2), ( 2, 12 ) , (3, 2), ( 3, 12 ) , ( 22, 1 ) , ( 32 ) , (3, 2, 1), ( 23 ) , ( 32, 1 ) , ( 3, 22 ) , ( 32, 2 ) , ( 33 )} , and B3(q) := ∑ λ⊂(33) #|B3(λ)|q|λ| = (1, 3, 9, 19, 24, 24, 19, 9, 3, 1) = (1 + q)3(1 + q2) ( 1 + 5q2 + q4 ) . Note, however, that∑ λ⊂(44) #|B4(λ)|q|λ| = (1, 4, 16, 44, 116, 204, 336, 420, 490, 420, 336, 204, 116, 44, 16, 4, 1) is an irreducible polynomial, but its value at q = 1 is equal to 2772 = 66× 42. Let p = (pi,j)1≤i≤n,1≤j≤k be a n× k matrix of variables. Definition 6.6. Define the kernel Fn,k(p, U) as follows Fn,k(p, U) = k−1∏ i=1 1∏ j=n−1 (1 + p i,j−i+1 (n)uj), where for a fixed n ∈ N and an integer a ∈ Z, we set a = a(n) := { a, if a ≥ 1, n+ a− 1, if a ≤ 0. For example, F3(p, U) = (1 + p1,2u2)(1 + p1,1u1)(1 + p2,1u2)(1 + p2,2u1). In the plactic algebra FP3,3 one has F3,3(p, U) = 1 + (p1,1 + p2,2)u1 + (p1,2 + p2,1)u2 + p1,1p2,1u11 + p1,1p2,1u12 + (p1,2p1,1 + p1,2p2,2 + p2,1p2,2)u21 + p1,2p2,1u22 + (p1,1p1,2p2,2 + p1,2p2,2p2,1)u212 + (p1,1p1,2p2,2 + p1,1p2,2p2,1)u211 + p1,1p1,2p2,1p2,2u2121. Notes on Schubert, Grothendieck and Key Polynomials 43 Definition 6.7. Define algebra PFn,k to be the quotient of the plactic algebra Pn by the two-sided ideal In generated by the set of monomials {ui1ui2 · · ·uik}, 1 ≤ i1 ≤ i2 ≤ · · · ≤ ik ≤ n− 1. Theorem 6.8. Hilb(PFn,k, q) = Bn−1,k−1(q), In particular, • The algebra PFn,n has dimension equals to the number of symmetric plane partitions SPP(n− 1), Hilb(PFn,k, q) = q kn 2 so( k 2 )n ( q±1, . . . , q±1︸ ︷︷ ︸ k , 1 ) , where so( k 2 )n ( q±1, . . . , q±1︸ ︷︷ ︸ k , 1 ) denotes the specialization x2j = q, x2j−1 = q−1, 1 ≤ j ≤ k, of the character soλ ( x1, x −1 1 . . . , xk, x −1 k , 1 ) of the odd orthogonal Lie algebra so(2k + 1) corresponding to the highest weight λ = ( k 2 , . . . , k 2︸ ︷︷ ︸ n ) . • degq Hilb(PFn,k, q) = (n− 1)(k − 1), and dim(PFn,k)(n−1)(k−1) = 1. • The Hilbert polynomial Hilb(PFn,k, q) is symmetric and unimodal polynomial in the va- riable q. • Hilb((PFn,k)ab, q) = k−1∑ j=0 ( n+j−2 n−2 ) qj, dim (PFn,k)ab = ( n+k−2 k−1 ) . The key step in proofs of Lemma 6.1 and Theorem 6.8 is based on the following identity∑ λ⊂(nk) sλ(x1, . . . , xk) = (x1 · · ·xk)n/2so( k 2 )n ( x1, x −1 1 , . . . , xk, x −1 k , 1 ) , see, e.g., [58, Chapter I, Section 5, Example 19], [35] and the literature quoted therein. Problem 6.9. Let Γ := Γn,m k,` = (nk,m`), n ≥ m be a “fat hook”. Find generalizations of the identity (6.1) and those listed in [25, p. 71], to the case of fat hooks, namely to find “nice” expressions for the following sums∑ λ⊂Γ sλ(Xk+`), ∑ λ⊂Γ sλ(Xk+`)sλ(Yk+`). Find “bosonic” type formulas for these sum at the limit n −→∞, ` −→∞, m, k are fixed. Example 6.10. Hilb(PF2,3, q) = (1, 3, 9, 9, 9, 3, 1)q, dim(PF2,4) = 35 = 5× 7, dim(PF2,5) = 126 = 3× 42, dimPF2,n = ( 2n+ 1 n ) = (2n+ 1) Catn (see, e.g., [67, A001700]), Hilb(PF3,4, q) = (1, 4, 16, 44, 81, 120, 140, 120, 81, 44, 16, 4, 1)q, dim(PF3,4) = 672 = 16× 42, Hilb(PF5, q) = (1, 4, 16, 44, 116, 204, 336, 420, 490, 420, 336, 204, 116, 44, 16, 4, 1)q, dim(PF5,5) = 2772 = 66× 42. 44 A.N. Kirillov Proposition 6.11. Hilb(PF2,n, q) = 2n∑ k=0 ( n[ k 2 ])( n[ k+1 2 ])qk; recall dim(PF2,n) = ( 2n+ 1 n ) . Therefore, Hilb(PF2,n, q) is equal to the generating function for the number of symmetric Dyck paths of semilength 2n− 1 according to the number of peaks, see [67, A088855], dim(PF3,n) = 2n Catn+1, if n ≥ 1. For example, dim(PF3,6) = 27456 = 64× 429, Hilb(PF3,6, q) = (1, 6, 36, 146, 435, 1056, 2066, 3276, 4326, 4760, 4326, 3276, 2066, 1056, 435, 146, 36, 6, 1). Several interesting interpretations of these numbers are given in [67, A003645]. Theorem 6.12. • Symmetric plane partitions and Catalan numbers: #|B4,n| = 1 2 Catn+1×Catn+2 . • Symmetric plane partitions and alternating sign matrices: #|Bn+3,n| = 1 2 TSPP(n+ 1)×ASM(n+ 1) = 1 2 #|Bn+1,n+1|. • Plane partitions and alternating sign matrices invariant under a half-turn: #|PP(n)| = ASM(n)×ASMHT(2n), where PP (n) denotes the number of plane partitions fitting inside an n × n × n box, see, e.g., [6, 37, 58], [67, A008793] and the literature quoted theirin; ASMHT(2n) denotes the number of alternating sign 2n × 2n-matrices invariant under a half-turn, see, e.g., [6, 37, 61, 68], [67, A005138]. • Plactic decomposition of the Fn-kernel: Fn,m(p, U) = ∑ T uTUT ({pij}), (6.2) where summation runs over the set of semistandard Young tableaux T of shape λ ⊂ (n)m filled by the numbers from the set {1, . . . ,m}. • UT ({pij = 1, ∀ i, j}) = dimV gl(m) λ′ , where λ denotes the shape of a tableau T , and λ′ denotes the conjugate/transpose of a partition λ. Exercise 6.13. It is well-known [21] that that the number Catn+1 Catn+2 counts the num- ber S (4) n+1 of standard Young tableaux having 2n+1 boxes and at most four rows. Give a bijective proof of the equality #|B4,n| = 1 2S (4) n+1. Notes on Schubert, Grothendieck and Key Polynomials 45 A Appendix A.1 Some explicit formulas for n = 4 and compositions α such that αi ≤ n− i for i = 1, 2, . . . (1) Schubert and (−β)-Grothendieck polynomials G−[α] := G−β[α] for n = 4: S1234 = S[0] = 1 = G−[0], S2134 = S[1] = x1 = G−[1], S1324 = S[01] = x1 + x2 = G−[01] + βG−[11], S1243 = S[001] = x1 + x2 + x3 = G−[001] + βG−[011] + β2G−[111], S3124 = S[2] = x2 1 = G−[2], S2314 = S[11] = x1x2 = G−[11], S2143 = S[101] = x2 1 + x1x2 + x1x3 = G−[101] + βG−[201] + β2G−[111], S1342 = S[011] = x1x2 + x1x3 + x2x3 = G−[011] + 2βG−[111], S1423 = S[02] = x2 1 + x1x2 + x2 2 = G−[02] + βG−[12] + β2G−[22], S4123 = S[3] = x3 1 = G−[3], S3214 = S[21] = x2 1x2 = G−[21], S2341 = S[111] = x1x2x3 = G−[111], S2413 = S[12] = x2 1x2 + x1x 2 2 = G−[12] + βG−[22], S1432 = S[021] = x2 1x2 + x2 1x3 + x1x 2 2 + x2 2x3 + x1x2x3 = G−[021] + 2βG−[121] + βG−[22] + β2G−[221], S3142 = S[201] = x2 1x2 + x2 1x3 = G−[201] + βG−[211], S4213 = S[31] = x3 1x2 = G−[31], S3412 = S[22] = x2 1x 2 2 = G−[22], S4132 = S[301] = x3 1x2 + x3 1x3 = G−[301] + βG−[311], S3241 = S[211] = x2 1x2x3 = G−[211], S2431 = S[121] = x2 1x2x3 + x1x 2 2x3 = G−[121] + βG−[221], S4312 = S[32] = x3 1x 2 2 = G−[32], S4231 = S[311] = x3 1x2x3 = G−[311], S3421 = S[221] = x2 1x 2 2x3 = G−[211], S4321 = S[321] = x3 1x 2 2x3 = G−[321]. Theorem A.1 (cf. [49, Section 5.5]). Each Schubert polynomial is a linear combination of (−β)-Grothendieck polynomials with nonnegative coefficients from the ring N[β]. (2) Key and reduced key polynomials: K[0] = 1 = K̂[0], K[1] = x1 = K̂[1], K[01] = x1 + x2, K̂[01] = x2, K[001] = x1 + x2 + x3, K̂[001] = x3, K[2] = x2 1 = K̂[2], K[11] = x1x2 = K̂[11], K[101] = x1x2 + x1x3, K̂[101] = x1x3, K[02] = x2 1 + x1x2 + x2 2, K̂[02] = x1x2 + x2 2, K[011] = x1x2 + x1x3 + x2x3, K̂[011] = x2x3, K[3] = x3 1 = K̂[3], K[21] = x2 1x2 = K̂[21], K[111] = x1x2x3 = K̂[111], K[12] = x2 1x2 + x1x 2 2, K̂[12] = x1x 2 2, K[021] = x2 1x2 + x2 1x3 + x1x 2 2 + x2 2x3 + x1x2x3, K̂[021] = x1x2x3 + x2 2x3, K[201] = x2 1x2 + x2 1x3, K̂[201] = x2 1x3, K[31] = x3 1x2 = K̂[31], K[22] = x2 1x 2 2 = K̂[22], K[211] = x2 1x2x3 = K̂[211], K[301] = x3 1x2 + x3 1x3, K̂[301] = x3 1x3, K[121] = x2 1x2x3 + x1x 2 2x3, K̂[121] = x1x 2 2x3, K[32] = x3 1x 2 2 = K̂[32], K[311] = x3 1x2x3 = K̂[311], K[221] = x2 1x 2 2x3 = K̂[221], 46 A.N. Kirillov K[321] = x3 1x 2 2x3 = K̂[321]. Note that if n = 4, then S[α] = K[α] for all α ⊂ δ4, except α = (101) in which S[101] = K[2] +K[101]. (3) Grothendieck and dual Grothendieck polynomials for β = 1: G1234 = G[0] = 1 = S[0], H[0] = (1 + x1)3(1 + x2)2(1 + x3), G2134 = G[1] = x1 = S[1], H[1] = (1 + x1)2(1 + x2)2(1 + x3)G[1], G1324 = G[01] = x1 + x2 + x1x2 = S[01] + S[11], H[01] = (1 + x1)2(1 + x2)(1 + x3)G[01], G1243 = G[001] = x1 + x2 + x3 + x1x2 + x1x3 + x2x3 + x1x2x3 = S[001] + S[011] + S[111], H[001] = (1 + x1)2(1 + x2)G[001], G3124 = G[2] = x2 1 = S[2], H[2] = (1 + x1)(1 + x2)2(1 + x3)G[2], G2314 = G[11] = x1x2 = S[11], H[11] = (1 + x1)2(1 + x2)(1 + x3)G[11], G2143 = G[101] = x2 1 + x1x2 + x1x3 + x2 1x2 + x2 1x3 + x1x2x3 + x2 1x2x3 = S[101] + S[201] + S[111] + S[211], H[101] = (1 + x1)(1 + x2)G[101], G1342 = G[011] = x1x2 + x1x3 + x2x3 + 2x1x2x3 = S[011] + 2S[111], H[011] = (1 + x1)2(1 + x2)(x1x2 + x1x3 + x2x3 + x1x2x3), G1423 = G[02] = x2 1 + x1x2 + x2 2 + x2 1x2 + x1x 2 2 = S[02] + S[12], H[02] = (1 + x1)(1 + x3)(x2 1 + x1x2 + x2 2 + 2x2 1x2 + 2x1x 2 2 + x2 1x 2 2), G4123 = G[3] = x3 1 = S[3], H[3] = (1 + x1)2(1 + x3)G[3], G3214 = G[21] = x2 1x2 = S[21], H[21] = (1 + x1)(1 + x2)(1 + x3)G[21], G2341 = G[111] = x1x2x3 = S[111], H[111] = (1 + x1)2(1 + x2)G[111], G2413 = G[12] = x2 1x2 + x1x 2 2 + x2 1x 2 2 = S[12] + S[22], H[12] = (1 + x1)(1 + x3)G[12], G1432 = G[021] = x2 1x2 + x2 1x3 + x1x 2 2 + x2 2x3 + x1x2x3 + 2x1x2x3(x1 + x2) + x2 1x 2 2 + x2 1x 2 2x3 = S[021] + 2S[121] + S[22] + S[211], H[021] = (1 + x1)G[021], G3142 = G[201] = x2 1x2 + x2 1x3 + x2 1x2x3 = S[201] + S[211], H[201] = (1 + x1)(1 + x2)G[201], G4213 = G[31] = x3 1x2 = S[31], H[31] = (1 + x2)(1 + x3)G[31], G3412 = G[22] = x2 1x 2 2 = S[22], H[22] = (1 + x1)(1 + x3)G[22], G4132 = G[301] = x3 1x2 + x3 1x3 + x3 1x2x3 = S[301] + S[311], H[301] = (1 + x2)G[301], G3241 = G[211] = x2 1x2x3 = S[211], H[211] = (1 + x2)G[211], G2431 = G[121] = x2 1x2x3 + x1x 2 2x3 + x2 1x 2 2x3 = S[121] + S[221], H[121] = (1 + x1)(1 + x2)G[121], G4312 = G[32] = x3 1x 2 2 = S[32], H[32] = (1 + x3)G[32], G4231 = G[311] = x3 1x2x3 = S[311], H[311] = (1 + x2)G[311], Notes on Schubert, Grothendieck and Key Polynomials 47 G3421 = G[221] = x2 1x 2 2x3 = S[221], H[221] = (1 + x1)G[221], G4321 = G[321] = x3 1x 2 2x3 = S[321] = H[321]. Clearly that any β-Grothendieck polynomial is a linear combination of Schubert polynomials with coefficients from the ring N[β]. (4) Key and reduced key Grothendieck polynomials: KG[0] = 1 = K̂G[0], KG[1] = x1 = K̂G[1], KG[01] = x1 + x2 + x1x2, K̂G[01] = x2 + x1x2, KG[001] = x1 + x2 + x3 + x1x2 + x1x3 + x2x3 + x1x2x3, K̂G[001] = x3 + x1x3 + x2x3 + x1x2x3, KG[2] = x2 1 = K̂G[2], KG[11] = x1x2 = K̂G[11], KG[101] = x1x2 + x1x3 + x1x2x3, K̂G[101] = x1x3 + x1x2x3, KG[02] = x2 1 + x1x2 + x2 2 + x2 1x2 + x1x 2 2, K̂G[02] = x1x2 + x2 2 + x2 1x2 + x1x 2 2, KG[011] = x1x2 + x1x3 + x2x3 + 2x1x2x3, K̂G[011] = x2x3 + x1x2x3, KG[3] = x3 1 = K̂G[3], KG[21] = x2 1x2 = K̂G[21], KG[111] = x1x2x3 = K̂G[111], KG[12] = x2 1x2 + x1x 2 2 + x2 1x 2 2, K̂G[12] = x1x 2 2 + x2 1x 2 2, KG[201] = x2 1x2 + x2 1x3 + x2 1x2x3, K̂G[201] = x2 1x3 + x2 1x2x3, KG[021] = x2 1x2 + x2 1x3 + x1x 2 2 + x1x2x3 + x2 2x3 + 2x2 1x2x3 + 2x1x 2 2x3 + x2 1x 2 2 + x2 1x 2 2x3, K̂G[021] = x1x2x3 + x2 2x3 + x2 1x2x3 + 2x1x 2 2x3 + x2 1x 2 2x3, KG[31] = x3 1x2 = K̂G[31], KG[22] = x2 1x 2 2 = K̂G[22], KG[211] = x2 1x2x3 = K̂G[211], KG[301] = x3 1x2 + x3 1x3 + x3 1x2x3, K̂G[301] = x3 1x3 + x3 1x2x3, KG[121] = x2 1x2x3 + x1x 2 2x3 + x2 1x 2 2x3, K̂G[121] = x1x 2 2x3 + x2 1x 2 2x3, KG[32] = x3 1x 2 2 = K̂G[32], KG[311] = x3 1x2x3 = K̂G[311], KG[221] = x2 1x 2 2x3 = K̂G[221], KG[321] = x3 1x 2 2x3 = K̂G[321]. (5) 42 (deformed) double key polynomials for n = 4: Kid = 1, K1 = p1,1, K2 = p1,2 + p2,1, K3 = p1,3 + p2,2 + p3,1, K12 = p1,1p2,1, K21 = p1,2p1,1, K23 = p1,2p2,2 + p1,2p3,1 + p2,1p3,1, K32 = p1,3p1,2 + p1,3p2,1 + p2,2p2,1, K13 = p1,1p2,2 + p1,1p3,1, K31 = p1,3p1,1, K22 = p1,2p2,1, K33 = p1,3p2,2 + p1,3p3,1 + p2,2p3,1, K123 = p1,1p2,1p3,1, K133 = p1,1p2,2p3,1, K212 = p1,2p1,1p2,1, K213 = p1,2p1.1p2,2 + p1,2p1,1p3,1, K223 = p1,2p2,1p3,1, K233 = p1,2p2,2p3,1, K321 = p1,3p1,2p1,1, K312 = p1,3p1,1p2,1 + q−1 13 p1,1p2,2p2,1, K313 = p1,3p1,1p2,2 + p1,3p1,1p3,1, K322 = p1,3p1,2p2,1 + q−1 23 p1,2p2,2p2,1, K323 = p1,3p1,2p2,2 + p1,3p1,2p3,1 + p1,3p2,1p3,1 + p2,2p2,1p3,1 + q23p1,3p2,2p2,1 K333 = p1,3p2,2p3,1, K2123 = p1,2p1,1p2,1p3,1, K2132 = p1,2p1,1p2,2p2,1, K2133 = p1,2p1,1p2,2p3,1, K3123 = p1,3p1,1p2,1p3,1 + q−1 13 p1,1p2,2p2,1p3,1, K3132 = p1,3p1,1p2,2p2,1, K3133 = p1,3p1,2p2,2p3,1, K3212 = p1,3p1,2p1,1p2,1, K3213 = p1,3p1,2p1,1p2,2 + p1,3p1,2p1,1p3,1, K3223 = p1,3p1,2p2,1p3,1 + q−1 23 p1,2p2,2p2,1p3,1, 48 A.N. Kirillov K3232 = p1,3p1,2p2,2p2,1, K3233 = p1,3p1,2p2,2p3,1 + q23p1,3p2,2p2,1p3,1, K21323 = p1,2p1,1p2,2p2,1p3,1, K31323 = p1,3p1,1p2,2p2,1p3,1, K32123 = p1,3p1,2p1,1p2,1p3,1, K32132 = p1,3p1,2p1,1p2,2p2,1, K32133 = p1,3p1,2p1,1p2,2p3,1, K32323 = p1,3p1,2p2,2p2,1p3,1, K321323 = p1,3p1,2p1,1p2,2p2,1p3,1. Theorem A.2 (cf. [43, the case β = −1]). Each double β-Grothendieck polynomials is a linear combination of double key polynomials with the coefficients from the ring N[β]. Let us remind that the total number of double key polynomials is equal to the number of alternating sign matrices. We expect that the interrelations between double key polynomials which follow from the structure of the plactic algebra PCn, see Section 5.1, can be identified with the graph corresponding to the MacNeile completion of the poset associated with the Bruhat order on the symmetric group Sn, see Section A.2 for a definition of the MacNeile completion. It is an interesting problem to describe interrelation graph associated with the (rectangular) key polynomials corresponding to the Cauchy kernel for the algebra PFn,m. (6) 26 double key Grothendieck polynomials for n = 4: GKid = 1, GK1 = p1,1 = K1 GK2 = p1,2 + p2,1 + p1,2p2,1 = K2 +K22, GK3 = p1,3 + p1,2 + p3,1 + p1,3p2,2 + p1,3p3,1 + p2,2p3,1 + p1,3p2,2p3,1 = K3 +K33 +K333, GK12 = p1,1p2,1 = K12, GK21 = p2,1p1,1 = K21, GK13 = p1,1p2,2 + p1,1p3,1 + p1,1p2,2p3,1 = K13 +K133, GK31 = p3,1p1,1 = K31, GK23 = p1,1p2,2 + p1,2p3,1 + p2,1p3,1 + p1,2p2,1p3,1 + p1,2p2,2p3,1 = K23 +K223 +K233, GK32 = p1,3p1,2 + p1,3p2,1 + p2,2p2,1 + p1,3p1,2p2,1 + p1,2p2,1p2,2 = K32 +K322, GK123 = p1,1p2,1p3,1 = K123, GK212 = p1,2p1,1p2,1 = K212, GK213 = p1,2p1,1p2,2 + p2,1p1,1p3,1 + p1,2p1,1p2,2p3,1 = K213 +K2133, GK312 = p1,3p1,1p2,1 + p1,1p2,2p2,1 + p1,2p1,1p2,2p2,1 = K312 +K2132, GK313 = p1,3p1,1p2,2 + p1,3p1,1p3,1 + p1,3p1,1p2,2p3,1 = K313 +K3133, GK321 = p1,1p1,2p1,3 = K123, GK323 = p1,3p1,2p2,2 + p1,3p1,2p3,1 + p1,3p2,1p3,1 + p2,2p2,1p3,1 + p1,3p2,2p2,1 + p1,3p1,2p2,1p2,2 + p1,2p2,1p2,2p3,1 + p1,3p1,2p2,2p3,1 + p1,3p1,2p2,1p3,1 + p1,2p2,2p2,1p3,1 + p1,3p1,2p2,2p2,1p3,1 = K323 +K3232 +K3233 +K3223 +K32323, GK2123 = p1,2p1,1p2,1p3,1 = K2123, GK2132 = p1,2p1,1p2,2p2,1 = K2132, GK3123 = p1,3p1,1p2,1p3,1p1,1p2,2p2,1p3,1 + p1,3p1,1p2,2p2,1p3,1 = K3123 +K31323, GK3212 = p1,3p1,2p1,1p2,1 = K3212, GK3213 = p1,3p1,2p1,1p2,2 + p1,3p1,2p1,1p3,1 + p1,3p1,2p1,1p2,2p3,1 = K3213 +K32133, GK21323 = p1,2p1.1p2,2p2,1p3,1 = K21323, GK32123 = p1,3p1,2p1,1p2,1p31 = K32123, GK32132 = p1,3p1,2p1,1p2,2p2,1 = K32132, GK321323 = p3,1p2,1p1,1p2,2p2,1p3,1 = K321323. (7) 14 double local key polynomials for n = 4: LKid = 1, LK1 = K1, LK2 = K2, LK3 = K3, LK12 = K12, LK21 = K21 +K212, LK13 = K13 +K31 +K313, LK23 = K23, LK32 = K32 +K323, LK123 = K123, LK213 = K213 +K2123, LK312 = K312 +K3123, LK321 = K321 +K3212 +K3213 +K32123 +K32132 +K321323, LK2132 = K2132 +K21323. Notes on Schubert, Grothendieck and Key Polynomials 49 (8) 35 (2, 3)-key polynomials: Uid = 1, U1 = p11 + p23, U2 = p12 + p21, U3 = p13 + p22, U11 = p11p23, U12 = p11p21, U13 = p11p22, U21 = p12p11 + p12p23 + p21p23, U23 = p12p22, U22 = p12p21, U31 = p13p11 + p13p23 + p22p23, U32 = p13p12 + p13p21 + p22p21, U33 = p13p22, U211 = p12p11p23 + p11p21p23, U212 = p12p11p21 + p12p21p23, U213 = p12p11p22 + p12p22p23, U311 = p13p11p23 + p11p22p23, U312 = p13p11p21 + p11p22p21, U313 = p13p11p22 + p13p22p23, U321 = p13p12p11 + p13p12p23 + p13p21p23 + p22p21p23, U322 = p13p12p21 + p12p22p21, U323 = p13p12p22 + p13p22p21, U2121 = p12p11p21p23, U2131 = p12p11p22p23, U2132 = p12p11p22p23, U3132 = p13p11p22p23, U3131 = p13p11p22p23, U3232 = p13p21p22p23, U3211 = p13p12p11p23 + p13p11p21p23 + p11p22p21p23, U3212 = p13p12p11p22 + p13p12p21p23 + p12p21p22p23, U3213 = p13p12p11p21 + p13p22p21p23 + p12p22p21p23, U32121 = p12p11p22p21p23 + p13p12p11p21p23, U32131 = p13p12p11p22p23 + p13p11p22p21p23, U32132 = p13p12p11p22p21 + p13p12p22p21p23, U321321 = p13p12p11p22p21p23. (9) Polynomials KNw := KN (β,α) w (1) for n = 4: KN id = 1, KN 1 = KN 2 = KN 3 = β + 1 + αβ, KN 12 = 1 + 2α+ α2 + 3αβ + 3α2β + αβ2 + 2α2β2, (13), KN 21 = 2 + 3α+ α2 + β + 3αβ + 2α2β + α2β2, (13), KN 13 = 1 + 2α+ α2 + 2αβ + 2α2β + α2β2 = (1 + α+ αβ)2, (9), KN 23 = KN 12, KN 32 = KN 21, KN 132 = 2 + 5α+ 4α2 + α3 + β + 7αβ + 10α2β + 4α3β + 2αβ2 + 7α2β2 + 5α3β2 + α2β3 + 2α3β3 = (1 + α+ αβ) ( 2 + 3α+ α2 + β + 4αβ + 3α2β + αβ2 + 2α2β2 ) , (51), KN 121 = 1 + 3α+ 3α2 + α3 + 4αβ + 7α2β + 3α3β + αβ2 + 4α2β2 + 3α3β2 + α3β3, (31), KN 321 = 5 + 10α+ 6α2 + α3 + 5β + 14αβ + 12α2β + 3α3β + β2 + 4αβ2 + 6α2β2 + 3α3β2 + α3β3, (71), KN 232 = KN 121, KN 123 = 1 + 3α+ 3α2 + α3 + 6αβ + 12α2β + 6α3β + 4αβ2 + 14α2β2 + 10α3β2 + αβ3 + 5α2β3 + 5α3β3 = β3α3KN (β−1,α−1) 321 (1), (71), KN 213 = (αβ)3KN (α−1,β−1) 132 , KN 3121 = 3 + 10α+ 12α2 + 6α3 + α4 + 2β + 16αβ + 29α2β + 19α3β + 4α4β + 7αβ2 + 21α2β2 + 20α3β2 + 6α4β2 + αβ3 + 4α2β3 + 7α3β3 + 4α4β3 + α4β4, (173), KN 2321 = (αβ)4KN (α−1,β−1) 3121 , KN 1213 = 1 + 4α+ 6α2 + 4α3 + α4 + 7αβ + 20α2β + 19α3β + 6α4β + 4αβ2 + 21α2β2 + 29α3β2 + 12α4β2 + αβ3 + 7α2β3 + 16α3β3 + 10α4β3 + 2α3β4 + 3α4β4, (173), KN 1232 = (αβ)4KN (α−1,β−1) 1213 , 50 A.N. Kirillov KN 2132 = 3 + 9α+ 10α2 + 5α3 + α4 + 3β + 16αβ + 28α2β + 20α3β + 5α4β + β2 + 7αβ2 + 24α2β2 + 28α3β2 + 10α4β2 + 7α2β3 + 16α3β3 + 9α4β3 + α2β4 + 3α3β4 + 3α4β4, (209), KN 21321 = 3 + 12α+ 19α2 + 15α3 + 6α4 + α5 + 3β + 21αβ + 49α2β + 52α3β + 26α4β + 5α5β + β2 + 9αβ2 + 39α2β2 + 64α3β2 + 43α4β2 + 10α5β2 + 10α2β3 + 32α3β3 + 32α4β3 + 10α5β3 + α2β4 + 5α3β4 + 9α4β4 + 5α5β4 + α5β5, (483), KN 12312 = 1 + 5α+ 10α2 + 10α3 + 5α4 + α5 + 9αβ + 32α2β + 43α3β + 26α4β + 6α5β + 5αβ2 + 32α2β2 + 64α3β2 + 52α4β2 + 15α5β2 + αβ3 + 10α2β3 + 39α3β3 + 49α4β3 + 19α5β3 + 9α3β4 + 21α4β4 + 12α5β4 + α3β5 + 3α4β5 + 3α5β5, (483), KN 12321 = 2 + 9α+ 16α2 + 14α3 + 6α4 + α5 + β + 18αβ + 54α2β + 64α3β + 33α4β + 6α5β + 14αβ2 + 65α2β2 + 101α3β2 + 64α4β2 + 14α5β2 + 6αβ3 + 33α2β3 + 65α3β3 + 54α4β3 + 16α5β3 + αβ4 + 6α2β4 + 14α3β4 + 18α4β4 + 9α5β4 + α4β5 + 2α5β5, (707), KN 121321 = 1 + 6α+ 15α2 + 20α3 + 15α4 + 6α5 + α6 + 10αβ + 45α2β + 81α3β + 73α4β + 33α5β + 6α6β + 5αβ2 + 44α2β2 + 116α3β2 + 135α4β2 + 73α5β2 + 15α6β2 + αβ3 + 15α2β3 + 69α3β3 + 116α4β3 + 81α5β3 + 20α6β3 + α2β4 + 15α3β4 + 44α4β4 + 45α5β4 + 15α6β4 + α3β5 + 5α4β5 + 10α5β5 + 6α6β5 + α6β6 = β6α6KN (α−1,β−1) 121321 (1), (1145). (10) Polynomials KN (β,α,γ) w := KN (β,α,γ) w (1) for n = 3: KN (β,α,γ) id = 1, KN (β,α,γ) 1 = KN (β,α,γ) 2 = 1 + (β + γ)(1 + α+ γ), (7), KN (β,α,γ) 12 = 1 + 2α+ α2 + 3αβ + 3α2β + αβ2 + 2α2β2 + 5γ + 8αγ + 3α2γ + 4βγ + 11αβγ + 4α2βγ + β2γ + 4αβ2γ + 9γ2 + 10αγ2 + 2α2γ2 + 8βγ2 + 8αβγ2 + 2β2γ2 + 7γ3 + 4αγ3 + 4βγ3 + 2γ4, (109), KN (β,α,γ) 21 = 2 + 3α+ α2 + β + 3αβ + 2α2β + α2β2 + 7γ + 8αγ + 2α2γ + 4βγ + 7αβγ + 2α2βγ + 2αβ2γ + 9γ2 + 7αγ2 + α2γ2 + 5βγ2 + 4αβγ2 + β2γ2 + 5γ3 + 2αγ3 + 2βγ3 + γ4, (82), KN (β,α,γ) 121 = 1 + 3α+ 3α2 + α3 + 4αβ + 7α2β + 3α3β + αβ2 + 4α2β2 + 3α3β2 + α3β3 + 6γ + 15αγ + 12α2γ + 3α3γ + 3βγ + 20αβγ + 22α2βγ + 6α3βγ + 7αβ2γ + 12α2β2γ + 3α3β2γ + 3α2β3γ + 15γ2 + 30αγ2 + 18α2γ2 + 3α3γ2 + 12βγ2 + 37αβγ2 + 24α2βγ2 + 3α3βγ2 + 3β2γ2 + 15αβ2γ2 + 9α2β2γ2 + 3αβ3γ2 + 20γ3 + 30αγ3 + 12α2γ3 + α3γ3 + 18βγ3 + 30αβγ3 + 9α2βγ3 + 6β2γ3 + 9αβ2γ3 + β3γ3 + 15γ4 + 15αγ4 + 3α2γ4 + 12βγ4 + 9αβγ4 + 3β2γ4 + 6γ5 + 3αγ5 + 3βγ5 + γ6, (521). Notes on Schubert, Grothendieck and Key Polynomials 51 (11) Few more examples: KN (β,α,γ=0) 4321 (1) = 14 + 35α+ 30α2 + 10α3 + α4 + 21β + 65αβ + 70α2β + 30α3β + 4α4β + 9β2 + 35αβ2 + 50α2β2 + 30α3β2 + 6α4β2 + β3 + 5αβ3 + 10α2β3 + 10α3β3 + 4α4β3 + α4β4, KN (β=1,α=1,γ) 4321 (1) = (441, 1984, 3754, 3882, 2385, 885, 192, 22, 1)γ , KN (β=1,α=1,γ) 54321 = (1 + γ)(2955, 13297, 25678, 27822, 18553, 7852, 2094, 336, 29, 1)γ . Note that polynomial Ln(γ) := KN (β=1,α=1,γ) n,n−1,...,2,1 (1) has degree 2n and Ln(γ = −1) = 0. h3KN (β=1,α=1,γ,h) 321 = (1, 3, 7, 9, 7, 1)h + γ(6, 18, 32, 32, 18, 6)h + γ2(15, 42, 58, 42, 15)h + γ3(20, 48, 48, 20)h + γ4(15, 27, 15)h + γ5(6, 6)h + γ6h6, KN (a=1,b=1,c,r) 121 (1) = 31 + 112c+ 168c2 + 124c3 + 44c4 + 6c5 + ( 60 + 176c+ 195c2 + 93c3 + 16c4 ) r + ( 38 + 85c+ 61c2 + 14c3 ) r2 + ( 8 + 12c+ 4c2 ) r3. Problem A.3. Let n ≥ k ≥ 0 be integers, consider permutation wn,k := [k, k − 1, . . . , 1, n, n−1, n−2, . . . , k+1] ∈ Sn. Give combinatorial interpretations of polynomials Ln,k(α, β, γ) := KN (α,β,γ) wm,k (1). Conjecture A.4. Set d := γ − 1. • For any permutation w ∈ Sn, KN (β,α=1,γ=d−1) w (1) is a polynomial in β and d with non- negative coefficients. • The polynomial Ln(d) has non-negative coefficients, and polynomial Ln(d) + dn is sym- metric and unimodal. • Ln,1(α = 1, β, d) ∈ dN[β, d]. • Ln,1(α, β = 0, d) ∈ dn−1(α + d)N[α, d], Ln,1(α = 1, β = 0, d = 1) = 2 Schn+1, Ln,1(α = 0, β = 0, d = 2) = 2n Schn+1 (see [67, A156017] for a combinatorial interpretation of these numbers), where Schn denotes the n-th Schröder number, see, e.g., [67, A001003]. • Ln,1(α = 0, β = t − 1, γ) ∈ N[t, γ], Ln,1(α = 0, β = −1, γ = 1) is equal to the number of Dyck (n+1)-paths ([67, A000108]) in which each up step (U) not at ground level is colored red (R) or blue (B), [67, A064062]. Note that the number 2 Schn known also as large Schröder number, see, e.g., [67, A006318]. For example, L3,1(α = 1, β, d) = d ( β2 + 5βd+ 4β2d+ 5d2 + 14βd2 + 6β2d2 + β3d2 + 10d3 + 12βd3 + 3β2d3 + 6d4 + 3βd4 + d5 ) , L7,1(1, 1, d) = d(1, 27, 260, 1245, 3375, 5495, 5494, 3375, 1245, 260, 27, 1)d, L7,1(α, β = 0, d) = d6(α+ d)(1 + α+ d) ( 1 + 14α+ 36α2 + 14α3 + α4 + 14d+ 72αd + 42α2d+ 4α3d+ 36d2 + 42αd2 + 6α2d2 + 14d3 + 4αd3 + d4 ) , L7,1(α = 0, β = t− 1, γ = 1) = (14589, 39446, 39607, 18068, 3627, 246, 1)t. We expect a similar conjecture for polynomials Ln,k(α = 1, β = 1, γ), k ≥ 1. 52 A.N. Kirillov A.2 MacMeille completion of a partially ordered set Let24 (Σ,≤) be a partially ordered set (poset for short) and X ⊆ Σ. Define • The set of upper bounds for X, namely, Xup := {z ∈ Σ |x ≤ z, ∀x ∈ X}. • The set of lower bounds for X, namely, X lo := {z ∈ Σ | z ≤ x ∀x ∈ X}. • A poset (MN (Σ),≤), namely, MN (Σ) := {MN (X)|X ⊆ Σ}, where MN (X) := ( Xup )lo . Clearly, X ⊆MN (X) and MN (MN (X)) =MN (X). • A map κ : Σ −→MN (Σ), namely, κ(X) =MN (X), X ⊆ Σ. Proposition A.5. • The map κ is an embedding, that is for X,Y ⊆ Σ, X ≤ Y if and only if κ(X) ⊆ κ(Y ), • Poset (MN (Σ),≤) is a lattice, called the MacNeille completion of poset (Σ,≤). Proposition A.6. Let (Σ,≤) be a poset25. Then there is a poset (L,≤) and a map κ : Σ −→ L such that (1) κ is an embedding, (2) (L,≤) is a complete lattice26, (3) for each element a ∈ L one has (a) MN ({x ∈ Σ |κ(x) ≤ a}) = {x ∈ Σ |κ(x) ≤ a}, (b) a = ∨ {κ(x) |x ∈ Σ, κ(x) ≤ a}. Moreover, the pair (κ, (L,≤)) is defined uniquely up to an order preserving isomorphism. Therefore, the lattice (L,≤), is an order-isomorphic to the MacNeille completionMN (Σ) of a poset Σ. Problem A.7. Let Σ be a (finite) graded poset27, denote by rΣ(t) := ∑ a∈Σ tr(a), the rank generating function of a poset Σ. Here r(a) denotes the rank/degree of an element a ∈ Σ. Describe polynomial rMN (Σ)(t). 24For the reader convenience we review a definition and basic facts concerning the MacNeille completion of a poset, see for example, notes by E. Turunen, available at http://math.tut.fi/~eturunen/AppliedLogics007/ Mac1.pdf. 25See https://en.wikipedia.org/wiki/Graded_poset. 26That is every subset of L has a meet and join, see, e.g., [69, p. 249]. 27See, e.g., [69, p. 244], or https://en.wikipedia.org/wiki/Graded_poset. http://math.tut.fi/~eturunen/AppliedLogics007/Mac1.pdf http://math.tut.fi/~eturunen/AppliedLogics007/Mac1.pdf https://en.wikipedia.org/wiki/Graded_poset https://en.wikipedia.org/wiki/Graded_poset Notes on Schubert, Grothendieck and Key Polynomials 53 In the present paper we are interesting in properties of the MacNeille completion of the Bruhat poset Bn = B(Sn) corresponding to the symmetric group Sn. Below we briefly describe a const- ruction of the MacNeille completion Ln(Sn) :=MN n(Bn) following [46] and [70, p. 552, d]. Let w = (w1w2 . . . wn) ∈ Sn, associate with w a semistandard Young tableaux T (w) of the staircase shape δn = (n − 1, n − 2, . . . , 2, 1) filled by integer numbers from the set [1, n] := {1, 2, . . . , n} as follows: the i-th row of of T (w), denoted by Ri(w), consists of the numbers w1, . . . , wn−i+1 in increasing order. Clearly the tableaux T (w) = [Ti,j(w)]1≤i<j≤n−1 obtained in such a manner, satisfies the so-called monotonic and flag conditions, namely, (1) (monotonic conditions) T1,i ≥ T2,i−1 ≥ · · · ≥ Ti,1, i = 1, . . . , n− 1, (2) (flag conditions) R1(w) ⊃ R2(w) ⊃ · · · ⊃ Rn−1(w). Denote by L(Sn) the subset of the set of all Young tableaux T ∈ STY(δn ≤ n) consisting of that T which satisfies the monotonicity conditions (1). The set L(Sn) has the natural poset struc- ture denoted by “≥”, and defined as follows: if T (1) = [t (1) ij ]1≤i<j≤n−1 and T (2) = [t (2) ij ]1≤i<j≤n−1 belong to the set L(Sn), then by definition T (1) ≥ T (2) if and only if t (1) ij ≥ t (2) ij for all 1 ≤ i < j ≤ n− 1. It is clearly seen that the set L(Sn) is closed under the following operations • ( meet T (1)T (2) ) ∧ ( T (1), T (2) ) := T (1) ∧ T (2) = [ min ( t (1) i,j , t (2) i,j )] , • ( join T (1)T (2) ) ∨ ( (T (1), T (2) ) := T (1) ∨ T (2) = [ max ( t (1) i,j , t (2) i,j )] . Theorem A.8 ([46]). The poset L(Sn) is a complete distributive lattice with number of vertices equals to the number ASM(n) that is the number of alternating sigh matrices of size n × n. Moreover, the lattice L(Sn) is order isomorphic to the MacNeille completion of the Bruhat poset Bn. Indeed it is not difficult to prove that the set of all monotonic triangles obtained by applying repeatedly operation ∨ (= meet) to the set {T (w), w ∈ Sn} of triangles corresponding to all elements of the symmetric group Sn, coincides with the set of all monotonic triangles L(Sn). The natural map κ : Sn −→ L(Sn) is obviously embedding, and all other conditions of Proposition A.6 are satisfied. Therefore L(Sn) =MN (Bn). The fact that the lattice L(Sn) is a distributive one follows from the well-known identities max(x,min(y, z)) = min ( max(x, y),max(x, z) ) , x, y, z ∈ ( R≥0 )3 . In the lattice L(Sn this identity can be written in the following forms T (1) ∨( T (2) ∧ T (3) ) = ( T (1) ∧ T (2) )∨( T (1) ∧ T (3) ) , T (1) ∧( T (2) ∨ T (3) ) = ( T (1) ∨ T (2) )∧( T (1) ∨ T (3) ) . Finally the fact that the cardinality of the lattice L(Sn) is equal to the number ASM(n) had been proved by A. Lascoux and M.-P. Schützenberger [46]. If T = [tij ] ∈ L(Sn), define rank of T , denoted by r(T ), as follows: r(T ) = ∑ 1≤i<j≤n−1 tij − ( n 3 ) . It had been proved by C. Ehresmann [15] that v ≤ w with respect to the Bruhat order in the symmetric group Sn if and only if Ti,j(v) ≤ Ti,j(w) for all 1 ≤ i < j ≤ n− 1. 54 A.N. Kirillov It follows from an improved tableau criterion for Bruhat order on the symmetric group [5] that28 the length `(w) of a permutation w ∈ Sn can be computed as follows `(w) = r(T (w))− ∑ (i,j)∈I(w) (j − i− 1), where I(w) := {(i, j) | 1 ≤ i < j ≤ n, wi > wj} denotes the set of inversions of permutation w; a detailed proof can be found in [32]. For example, consider permutation w = [4, 6, 2, 7, 5, 1, 3]. Then the code c(w) of w is equal to c(w) = (3, 4, 1, 3, 2), and w has the length `(w) = 13. The corresponding Young tableau or monotonic triangle displayed below T (w) =  1 2 4 5 6 7 2 4 5 6 7 2 4 6 7 2 4 6 4 6 4  . Wherefore, r(T (w)) = |T (w)| − ( 7 3 ) = 94 − 56 = 38. On the other hand, the inversion set I(w) = {(1, 3), (1, 6), (1, 7), (2, 3), (2, 5), (2, 6), (2, 7), (3, 6), (4, 5), (4, 6), (4, 7), (5, 6), (5, 7)}, hence∑ (i,j)∈I(w) (j − i− 1) = 10 + 9 + 2 + 3 + 1 = 25 and `(w) = 38− 25 = 13, as it should be. It is easily seen that the polynomial rMNn(t) is symmetric and deg(rMNn(t)) = ( n+1 3 ) , For example, r(MN 3) = (1, 2, 1, 2, 1), r(MN 4) = (1, 3, 3, 5, 6,6, 6, 5, 3, 3, 1), r(MN 5) = (1, 4, 6, 10, 16, 20, 27, 34, 37, 40,39, 40, 37, 34, 27, 20, 16, 10, 6, 4, 1), r(S3 ⊂MN 3) = (1, 2, 0, 2, 1), r(S4 ⊂MN 4) = (1, 3, 1, 4, 2,2, 2, 4, 1, 3, 1)), r(S5 ⊂MN 5) = (1, 4, 3, 6, 7, 6, 4, 10, 6, 10,6, 10, 6, 10, 4, 6, 7, 6, 3, 4, 1). Conjecture A.9. The number Coeff [(n+1 3 )/2] rMNn(t) is a divisor of the number ASM(n). Acknowledgements A bit of history. Originally these notes have been designed as a continuation of [17]. The main purpose was to extend the methods developed in [18] to obtain by the use of plactic algebra, a noncommutative generating function for the key (or Demazure) polynomials introduced by A. Lascoux and M.-P. Schützenberger [53]. The results concerning the polynomials introduced in Section 4, except the Hecke–Grothendieck polynomials, see Definition 4.6, has been presented in my lecture-courses “Schubert Calculus” and have been delivered at the Graduate School of Mathematical Sciences, the University of Tokyo, November 1995 – April 1996, and at the Graduate School of Mathematics, Nagoya University, October 1998 – April 1999. I want to thank Professor M. Noumi and Professor T. Nakanishi who made these courses possible. Some early versions of the present notes are circulated around the world and now I was asked to put it for the wide audience. I would like to thank Professor M. Ishikawa (Department of Mathematics, Faculty of Education, University of the Ryukyus, Okinawa, Japan) and Professor S. Okada (Graduate School of Mathematics, Nagoya University, Nagoya, Japan) for valuable comments. My special thanks to the referees for very careful reading of a preliminary version of the present paper and many valuable remarks, comments and suggestions. 28It has been proved in [5, Corollary 5], that the Ehresmann criterion stated above is equivalent to either the criterion T (1) i,j ≤ T (2) i,j for all j such that wj > wj+1 and 1 ≤ i ≤ j, or that T (1) i,j ≤ T (2) i,j for all j ∈ {1, 2, . . . , n− 1}\{k | vk > vk+1} and 1 ≤ i ≤ j. Notes on Schubert, Grothendieck and Key Polynomials 55 References [1] Andrews G.E., Generalized Frobenius partitions, Mem. Amer. Math. Soc. 49 (1984), iv+44 pages. [2] Aval J.-C., Keys and alternating sign matrices, Sém. Lothar. Combin. 59 (2008), Art. B59f, 13 pages, arXiv:0711.2150. [3] Berenstein A., Kirillov A.N., The Robinson–Schensted–Knuth bijection, quantum matrices and piece-wise linear combinatorics, in Proceedings of the 13th International Conference on Formal Power Series and Algebraic Combinatorics (Arizona, 2001), Arisona State University, USA, 2001, 1–12. [4] Berenstein I.N., Gelfand I.M., Gelfand S.I., Schubert cells, and the cohomology of the spaces G/P , Russ. Math. Surv. 28 (1973), no. 3, 1–26. [5] Björner A., Brenti F., An improved tableau criterion for Bruhat order, Electron. J. Combin. 3 (1996), 22, 5 pages. [6] Bressoud D.M., Proofs and confirmations. The story of the alternating sign matrix conjecture, MAA Spec- trum, Mathematical Association of America, Washington, DC, Cambridge University Press, Cambridge, 1999. [7] Brubaker B., Bump D., Licata A., Whittaker functions and Demazure operators, J. Number Theory 146 (2015), 41–68, arXiv:1111.4230. [8] Cherednik I., Double affine Hecke algebras, London Mathematical Society Lecture Note Series, Vol. 319, Cambridge University Press, Cambridge, 2005. [9] de Gier J., Nienhuis B., Brauer loops and the commuting variety, J. Stat. Mech. Theory Exp. 2005 (2005), P01006, 10 pages, math.AG/0410392. [10] de Sainte-Catherine M., Viennot G., Enumeration of certain Young tableaux with bounded height, in Combinatoire énumérative, Lecture Notes in Math., Vol. 1234, Springer, Berlin, 1986, 58–67. [11] Demazure M., Une nouvelle formule des caractères, Bull. Sci. Math. 98 (1974), 163–172. [12] Di Francesco P., A refined Razumov–Stroganov conjecture, J. Stat. Mech. Theory Exp. 2004 (2004), P08009, 16 pages, cond-mat/0407477. [13] Di Francesco P., Zinn-Justin P., Inhomogeneous model of crossing loops and multidegrees of some algebraic varieties, Comm. Math. Phys. 262 (2006), 459–487, math-ph/0412031. [14] Dumont D., Sur une conjecture de Gandhi concernant les nombres de Genocchi, Discrete Math. 1 (1972), 321–327. [15] Ehresmann C., Sur la topologie de certains espaces homogènes, Ann. of Math. 35 (1934), 396–443. [16] Fomin S., Greene C., Noncommutative Schur functions and their applications, Discrete Math. 193 (1998), 179–200. [17] Fomin S., Kirillov A.N., Yang–Baxter equation, symmetric functions and Grothendieck polynomials, hep-th/9306005. [18] Fomin S., Kirillov A.N., Grothendieck polynomials and the Yang–Baxter equation, in Formal Power Series and Algebraic Combinatorics, DIMACS, Piscataway, NJ, 1994, 183–189. [19] Fomin S., Kirillov A.N., Quadratic algebras, Dunkl elements, and Schubert calculus, in Advances in Geo- metry, Progr. Math., Vol. 172, Birkhäuser Boston, Boston, MA, 1999, 147–182. [20] Gordon B., A proof of the Bender–Knuth conjecture, Pacific J. Math. 108 (1983), 99–113. [21] Gouyou-Beauchamps D., Chemins sous-diagonaux et tableau de Young, Lecture Notes in Math., Springer, Berlin, Vol. 1234, 1986, 112–125. [22] Han G.-N., Zeng J., q-polynômes de Gandhi et statistique de Denert, Discrete Math. 205 (1999), 119–143. [23] Hudson T., A Thom–Porteous formula for connective K-theory using algebraic cobordism, J. K-Theory 14 (2014), 343–369, arXiv:1310.0895. [24] Isaev A.P., Kirillov A.N., Bethe subalgebras in Hecke algebra and Gaudin models, Lett. Math. Phys. 104 (2014), 179–193, arXiv:1302.6495. [25] King R.C., Row and column length restrictions of some classical Schur function identities and the connection with Howe dual pairs, Slides of the talk at 8th International Conference on Combinatorics and Representation Theory, Graduate School of Mathematics, Nagoya University, Nagoya, Japan, September 2008, available at http://www.math.nagoya-u.ac.jp/en/research/conference/2008/download/nagoya2008_king.pdf. http://dx.doi.org/10.1090/memo/0301 http://arxiv.org/abs/0711.2150 http://dx.doi.org/10.1070/RM1973v028n03ABEH001557 http://dx.doi.org/10.1070/RM1973v028n03ABEH001557 http://dx.doi.org/10.1016/j.jnt.2014.01.001 http://arxiv.org/abs/1111.4230 http://dx.doi.org/10.1017/CBO9780511546501 http://dx.doi.org/10.1088/1742-5468/2005/01/P01006 http://arxiv.org/abs/math.AG/0410392 http://dx.doi.org/10.1007/BFb0072509 http://dx.doi.org/10.1088/1742-5468/2004/08/P08009 http://arxiv.org/abs/cond-mat/0407477 http://dx.doi.org/10.1007/s00220-005-1476-5 http://arxiv.org/abs/math-ph/0412031 http://dx.doi.org/10.1016/0012-365X(72)90039-8 http://dx.doi.org/10.2307/1968440 http://dx.doi.org/10.1016/S0012-365X(98)00140-X http://arxiv.org/abs/hep-th/9306005 http://dx.doi.org/10.1007/978-1-4612-1770-1_8 http://dx.doi.org/10.2140/pjm.1983.108.99 http://dx.doi.org/10.1007/BFb0072513 http://dx.doi.org/10.1016/S0012-365X(97)00189-1 http://dx.doi.org/10.1017/is014005031jkt266 http://arxiv.org/abs/1310.0895 http://dx.doi.org/10.1007/s11005-013-0660-3 http://arxiv.org/abs/1302.6495 http://www.math.nagoya-u.ac.jp/en/research/conference/2008/download/nagoya2008_king.pdf 56 A.N. Kirillov [26] Kirillov A.N., Introduction to tropical combinatorics, in Physics and Combinatorics, 2000 (Nagoya), World Sci. Publ., River Edge, NJ, 2001, 82–150. [27] Kirillov A.N., On some algebraic and combinatorial properties of Dunkl elements, Internat. J. Modern Phys. B 26 (2012), 1243012, 28 pages. [28] Kirillov A.N., Berenstein A.D., Groups generated by involutions, Gelfand–Tsetlin patterns, and combina- torics of Young tableaux, St. Petersburg Math. J. 7 (1996), 77–127. [29] Knuth D.E., Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34 (1970), 709–727. [30] Knutson A., Some schemes related to the commuting variety, J. Algebraic Geom. 14 (2005), 283–294, math.AG/0306275. [31] Knutson A., Zinn-Justin P., The Brauer loop scheme and orbital varieties, J. Geom. Phys. 78 (2014), 80–110, arXiv:1001.3335. [32] Kobayashi M., Schubert numbers, Ph.D. Thesis, University of Tennessee, 2010, available at http://trace. tennessee.edu/utk_graddiss/715. [33] Korff C., Cylindric versions of specialised Macdonald functions and a deformed Verlinde algebra, Comm. Math. Phys. 318 (2013), 173–246, arXiv:1110.6356. [34] Korff C., Stroppel C., The ŝl(n)k-WZNW fusion ring: a combinatorial construction and a realisation as quotient of quantum cohomology, Adv. Math. 225 (2010), 200–268, arXiv:0909.2347. [35] Krattenthaler C., Guttmann A.J., Viennot X.G., Vicious walkers, friendly walkers and Young tableaux. II. With a wall, J. Phys. A: Math. Gen. 33 (2000), 8835–8866, cond-mat/0006367. [36] Krob D., Thibon J.-Y., Noncommutative symmetric functions. IV. Quantum linear groups and Hecke alge- bras at q = 0, J. Algebraic Combin. 6 (1997), 339–376. [37] Kuperberg G., Symmetry classes of alternating-sign matrices under one roof, Ann. of Math. 156 (2002), 835–866, math.CO/0008184. [38] La Scala R., Nardozza V., Senato D., Super RSK-algorithms and super plactic monoid, Internat. J. Algebra Comput. 16 (2006), 377–396, arXiv:0904.0605. [39] Lascoux A., Anneau de Grothendieck de la variété de drapeaux, in The Grothendieck Festschrift, Vol. III, Progr. Math., Vol. 88, Birkhäuser Boston, Boston, MA, 1990, 1–34. [40] Lascoux A., Square-ice enumeration, Sém. Lothar. Combin. 42 (1999), Art. B42p, 15 pages. [41] Lascoux A., Transition on Grothendieck polynomials, in Physics and Combinatorics, 2000 (Nagoya), World Sci. Publ., River Edge, NJ, 2001, 164–179. [42] Lascoux A., Symmetric functions and combinatorial operators on polynomials, CBMS Regional Conference Series in Mathematics, Vol. 99, Amer. Math. Soc., Providence, RI, 2003. [43] Lascoux A., ASM matrices and Grothendieck polynomials, 2012, available at http://www.uec.tottori-u. ac.jp/~mi/workshop/pdf/GrothASM_Nara.pdf. [44] Lascoux A., Leclerc B., Thibon J.-Y., The plactic monoid, in Algebraic Combinatorics on Words, Encyclo- pedia of Mathematics and its Applications, Vol. 90, Cambridge University Press, Cambridge, 2002, 164–196. [45] Lascoux A., Rains E.M., Warnaar S.O., Nonsymmetric interpolation Macdonald polynomials and gln basic hypergeometric series, Transform. Groups 14 (2009), 613–647, arXiv:0807.1351. [46] Lascoux A., Schützenberger M.-P., Le monöıde plaxique, in Noncommutative Structures in Algebra and Geometric Combinatorics (Naples, 1978), Quad. “Ricerca Sci.”, Vol. 109, CNR, Rome, 1981, 129–156. [47] Lascoux A., Schützenberger M.-P., Polynômes de Schubert, C. R. Acad. Sci. Paris Sér. I Math. 294 (1982), 447–450. [48] Lascoux A., Schützenberger M.-P., Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une variété de drapeaux, C. R. Acad. Sci. Paris Sér. I Math. 295 (1982), 629–633. [49] Lascoux A., Schützenberger M.-P., Symmetry and flag manifolds, in Invariant Theory (Montecatini, 1982), Lecture Notes in Math., Vol. 996, Springer, Berlin, 1983, 118–144. [50] Lascoux A., Schützenberger M.-P., Symmetrization operators in polynomial rings, Funct. Anal. Appl. 21 (1987), 324–326. [51] Lascoux A., Schützenberger M.-P., Fonctorialité des polynômes de Schubert, in Invariant Theory (Denton, TX, 1986), Contemp. Math., Vol. 88, Amer. Math. Soc., Providence, RI, 1989, 585–598. [52] Lascoux A., Schützenberger M.-P., Tableaux and noncommutative Schubert polynomials, Funct. Anal. Appl. 23 (1989), 223–225. http://dx.doi.org/10.1142/9789812810007_0005 http://dx.doi.org/10.1142/9789812810007_0005 http://dx.doi.org/10.1142/S0217979212430126 http://dx.doi.org/10.1142/S0217979212430126 http://dx.doi.org/10.2140/pjm.1970.34.709 http://dx.doi.org/10.1090/S1056-3911-04-00389-3 http://arxiv.org/abs/math.AG/0306275 http://dx.doi.org/10.1016/j.geomphys.2014.01.006 http://arxiv.org/abs/1001.3335 http://trace.tennessee.edu/utk_graddiss/715 http://trace.tennessee.edu/utk_graddiss/715 http://dx.doi.org/10.1007/s00220-012-1630-9 http://dx.doi.org/10.1007/s00220-012-1630-9 http://arxiv.org/abs/1110.6356 http://dx.doi.org/10.1016/j.aim.2010.02.021 http://arxiv.org/abs/0909.2347 http://dx.doi.org/10.1088/0305-4470/33/48/318 http://arxiv.org/abs/cond-mat/0006367 http://dx.doi.org/10.1023/A:1008673127310 http://dx.doi.org/10.2307/3597283 http://arxiv.org/abs/math.CO/0008184 http://dx.doi.org/10.1142/S0218196706003025 http://dx.doi.org/10.1142/S0218196706003025 http://arxiv.org/abs/0904.0605 http://dx.doi.org/10.1007/978-0-8176-4576-2_1 http://dx.doi.org/10.1142/9789812810007_0007 http://dx.doi.org/10.1142/9789812810007_0007 http://dx.doi.org/10.1090/cbms/099 http://dx.doi.org/10.1090/cbms/099 http://www.uec.tottori-u.ac.jp/~mi/workshop/pdf/GrothASM_Nara.pdf http://www.uec.tottori-u.ac.jp/~mi/workshop/pdf/GrothASM_Nara.pdf http://dx.doi.org/10.1017/CBO9781107326019.006 http://dx.doi.org/10.1017/CBO9781107326019.006 http://dx.doi.org/10.1007/s00031-009-9061-1 http://arxiv.org/abs/0807.1351 http://dx.doi.org/10.1007/BFb0063238 http://dx.doi.org/10.1007/BF01077811 http://dx.doi.org/10.1090/conm/088/1000001 http://dx.doi.org/10.1007/BF01079531 Notes on Schubert, Grothendieck and Key Polynomials 57 [53] Lascoux A., Schützenberger M.-P., Treillis et bases des groupes de Coxeter, Electron. J. Combin. 3 (1996), 27, 35 pages. [54] Lenart C., Noncommutative Schubert calculus and Grothendieck polynomials, Adv. Math. 143 (1999), 159– 183. [55] Li Y., On q-symmetric functions and q-quasisymmetric functions, J. Algebraic Combin. 41 (2015), 323–364, arXiv:1306.0224. [56] Loday J.-L., Popov T., Parastatistics algebra, Young tableaux and the super plactic monoid, Int. J. Geom. Methods Mod. Phys. 5 (2008), 1295–1314, arXiv:0810.0844. [57] Macdonald I.G., Notes on Schubert polynomials, Publications du LaCIM, Vol. 6, Université du Québec à Montréal, 1991. [58] Macdonald I.G., Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. [59] Noumi M., Yamada Y., Tropical Robinson–Schensted–Knuth correspondence and birational Weyl group actions, in Representation Theory of Algebraic Groups and Quantum Groups, Adv. Stud. Pure Math., Vol. 40, Math. Soc. Japan, Tokyo, 2004, 371–442, math-ph/0203030. [60] O’Connell N., Pei Y., A q-weighted version of the Robinson–Schensted algorithm, arXiv:1212.6716. [61] Okada S., Enumeration of symmetry classes of alternating sign matrices and characters of classical groups, J. Algebraic Combin. 23 (2006), 43–69, math.CO/0408234. [62] Postnikov A., Shapiro B., Shapiro M., Algebras of curvature forms on homogeneous manifolds, in Differential Topology, Infinite-Dimensional Lie Algebras, and Applications, Amer. Math. Soc. Transl. Ser. 2, Vol. 194, Amer. Math. Soc., Providence, RI, 1999, 227–235, math.AG/9901075. [63] Ross C., Yong A., Combinatorial rules for three bases of polynomials, Sém. Lothar. Combin. 74 (2015), Art. B74a, 11 pages, arXiv:1302.0214. [64] Schensted C., Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191. [65] Schützenberger M.-P., La correspondance de Robinson, in Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976), Lecture Notes in Math., Vol. 579, Springer, Berlin, 1977, 59–113. [66] Shapiro B., Shapiro M., On ring generated by Chern 2-forms on SLn/B, C. R. Acad. Sci. Paris Sér. I Math. 326 (1998), 75–80. [67] Sloane N.J.A., The on-line encyclopedia of integer sequences, available https://oeis.org/. [68] Stanley R.P., A baker’s dozen of conjectures concerning plane partitions, in Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985), Lecture Notes in Math., Vol. 1234, Springer, Berlin, 1986, 285–293. [69] Stanley R.P., Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, Vol. 49, 2nd ed., Cambridge University Press, Cambridge, 2012. [70] Stanley R.P., Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, Vol. 62, Cambridge University Press, Cambridge, 1999. [71] Tolstoy V.N., Ogievetsky O.V., Pyatov P.N., Isaev A.P., Modified affine Hecke algebras and Drinfeldians of type A, in Quantum Theory and Symmetries (Goslar, 1999), World Sci. Publ., River Edge, NJ, 2000, 452–458, math.QA/9912063. [72] Wachs M.L., Flagged Schur functions, Schubert polynomials, and symmetrizing operators, J. Combin. Theo- ry Ser. A 40 (1985), 276–289. http://dx.doi.org/10.1006/aima.1998.1795 http://dx.doi.org/10.1007/s10801-014-0538-1 http://arxiv.org/abs/1306.0224 http://dx.doi.org/10.1142/S0219887808003351 http://dx.doi.org/10.1142/S0219887808003351 http://arxiv.org/abs/0810.0844 http://arxiv.org/abs/math-ph/0203030 http://arxiv.org/abs/1212.6716 http://dx.doi.org/10.1007/s10801-006-6028-3 http://arxiv.org/abs/math.CO/0408234 http://arxiv.org/abs/math.AG/9901075 http://arxiv.org/abs/1302.0214 http://dx.doi.org/10.4153/CJM-1961-015-3 http://dx.doi.org/10.1007/BFb0090012 http://dx.doi.org/10.1007/BFb0090012 http://dx.doi.org/10.1016/S0764-4442(97)82716-4 https://oeis.org/ http://dx.doi.org/10.1007/BFb0072521 http://dx.doi.org/10.1017/CBO9781139058520 http://dx.doi.org/10.1017/CBO9780511609589 http://arxiv.org/abs/math.QA/9912063 http://dx.doi.org/10.1016/0097-3165(85)90091-3 http://dx.doi.org/10.1016/0097-3165(85)90091-3 1 Introduction 2 Plactic, nilplactic and idplactic algebras 3 Divided difference operators 4 Schubert, Grothendieck and key polynomials 5 Cauchy kernel 5.1 Plactic algebra Pn 5.2 Nilplactic algebra NPn 5.3 Idplactic algebra IPn 5.4 NilCoxeter algebra NCn 5.5 IdCoxeter algebras ICn 6 F-kernel and symmetric plane partitions A Appendix A.1 Some explicit formulas for n=4 and compositions such that i n-i for i=1,2,… A.2 MacMeille completion of a partially ordered set References

Ähnliche Einträge