Notes on Schubert, Grothendieck and Key Polynomials

Notes on Schubert, Grothendieck
and Key Polynomials

Anatol N. KIRILLOV †‡§

A.N. Kirillov

† Research Institute of Mathematical Sciences (RIMS), Kyoto, Sakyo-ku
606-8502, Japan<EMAIL_ADDRESS>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

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.

plactic monoid and reduced plactic algebras; nilCoxeter and idCoxeter
algebras; Schubert, $\beta$-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) Schubert 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

05E05; 05E10; 05A19

To the memory of Alexander Grothendieck (1928–2014)

###### Contents

  1. 1 Introduction
  2. 2 Plactic, nilplactic and idplactic algebras
  3. 3 Divided difference operators
  4. 4 Schubert, Grothendieck and key polynomials
  5. 5 Cauchy kernel
    1. 5.1 Plactic algebra ${\cal P}_{n}$
    2. 5.2 Nilplactic algebra ${\cal{NP}}_{n}$
    3. 5.3 Idplactic algebra ${\cal{IP}}_{n}$
    4. 5.4 NilCoxeter algebra ${\cal{NC}}_{n}$
    5. 5.5 IdCoxeter algebras ${\cal{IC}}_{n}^{\pm}$
  6. 6 ${\cal F}$-kernel and symmetric plane partitions
  7. A Appendix
    1. A.1 Some explicit formulas for $n=4$ and compositions $\alpha$ such that $\alpha_{i}\leq n-i$ for $i=1,2,\dots$
    2. A.2 MacMeille completion of a partially ordered set
    3. Acknowledgements

### Extended abstract

We introduce certain finite-dimensional algebras denoted by ${\cal{PC}}_{n}$
and ${\cal{PF}}_{n,m}$ which are certain quotients of the plactic algebra
${\cal{P}}_{n}$, which had been introduced by A. Lascoux and M.-P.
Schützenberger [46]. We show that $\dim({\cal{PF}}_{n,k})$ is equal to the
number of symmetric plane partitions fitting inside the box $n\times k\times
k$, $\dim({\cal{PC}}_{n})$ is equal to the number of alternating sign matrices
of size $n\times n$, moreover,

$\displaystyle\dim({\cal{PF}}_{n,n})={\rm TSPP}(n+1)\times{\rm TSSCPP}(n),$
$\displaystyle\dim({\cal{PF}}_{n,n+1})={\rm TSPP}(n+1)\times{\rm
TSSCPP}(n+1),$
$\displaystyle\dim({\cal{PF}}_{n+2,n})=\dim({\cal{PF}}_{n,n+1}),\qquad\dim({\cal{PF}}_{n+3,n})={\frac{1}{2}}\dim({\cal{PF}}_{n+1,n+1}),$

and study decomposition of the Cauchy kernels corresponding to the algebras
${\cal{PC}}_{n}$ and ${\cal{PF}}_{n,m}$; as well as introduce polynomials
which are common generalizations of the (double) Schubert,
$\beta$-Grothendieck, Demazure (known also as key polynomials), (plactic) key-
Grothendieck, (plactic) Stanley and stable $\beta$-Grothendieck polynomials.
Using a family of the Hecke type divided difference operators we introduce
polynomials which are common generalizations of the Schubert,
$\beta$-Grothendieck, dual $\beta$-Grothendieck,
$\beta$-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^{\star}({\cal{F}}l_{n})$ of the complete flag variety
${\cal{F}}l_{n}$. The basis $\\{\exp(\xi_{1}),\ldots,\exp(\xi_{n})\\}$ in
$K^{*}({\cal{F}}l_{n})$ is one choice, and another choice is the basis
$\\{1-\exp(-{\xi}_{j}),\,1\leq j\leq n\\}$, where $\\{{\xi}_{j},\,1\leq j\leq
n\\}$ denote the Chern classes of the tautological linear bundles $L_{j}$ over
the flag variety ${\cal{F}}l_{n}$. In the present paper we use the basis in a
deformed Grothendieck ring $K^{*,\beta}({\cal{F}}_{n})$ of the flag variety
${\cal{F}}l_{n}$ generated by the set of elements
$\\{x_{i}=x_{i}^{(\beta)}=1-\exp(\beta{\xi}_{i}),\,i=1,\ldots,n\\}$. This
basis has been introduced and used for construction of the
$\beta$-Grothendieck polynomials in [17, 19].

A basis in the classical Grothendieck ring of the flag variety in question
corresponds to the choice $\beta=-1$. For arbitrary $\beta$ the ring generated
by the elements $\big{\\{}x_{i}^{(\beta)},\,1\leq i\leq n\big{\\}}$ 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+\beta xy$, see [23]. The Grothendieck polynomials corresponding to
the classical $K$-theory ring $K^{\star}({\cal{F}}l_{n})$, i.e., the case
$\beta=-1$, had been studied in depth by A. Lascoux and M.-P. Schützenberger
in [49]. The $\beta$-Grothendieck polynomials has been studied in [17, 18,
23].

The plactic monoid over a finite totally ordered set
$\mathbb{A}=\\{a<b<c<\cdots<d\\}$ is the quotient of the free monoid generated
by elements from $\mathbb{A}$ subject to the elementary Knuth transformations
[29]

$\displaystyle bca=bac\quad\&\quad acb=cab,\qquad\text{and}\qquad
bab=bba\quad\&\quad aba=baa,$ (1.1)

for any triple $\\{a<b<c\\}\subset\mathbb{A}$.

To our knowledge, the concept of “plactic monoid” has its origins in a paper
by C. Schensted [64], concerning the study of the longest increasing
subsequence of a permutation, and a paper by D. Knuth [29], concerning the
study of combinatorial and algebraic properties of the Robinson–Schensted
correspondence111See, e.g., https://en.wikipedia.org/wiki/Robinson-
Schensted_correspondence..

As far as we know, this monoid and the (unital) algebra $\cal{P}(\mathbb{A})$
corresponding to that monoid222If $\mathbb{A}=\\{1<2<\cdots<n\\}$, the
elements of the algebra ${\cal{P}}(\mathbb{A})$ can be identified with
semistandard Young tableaux. It was discovered by D. Knuth [29] that modulo
Knuth equivalence the equivalence classes of semistandard 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]., 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 “monoï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) polynomials333See, e.g., [36] for definition of
noncommutative quasi-symmetric functions and polynomials.

$\displaystyle
e_{k}({\mathbb{A}}_{n})=\sum_{i_{1}>i_{2}>\cdots>i_{k}}a_{i_{1}}a_{i_{2}}\cdots
a_{i_{k}},\qquad k=1,\ldots,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,

$\displaystyle aba=baa,\qquad bab=bba,$

imply the commutativity of noncommutative elementary polynomials in two
variables. In other words, the plactic relations for two letters imply that

$\displaystyle ba(a+b)=(a+b)ba,\qquad 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.23444Let us
stress that conditions necessary and sufficient to assure the commutativity of
noncommutative elementary polynomials for the number of variables equals $n=2$
and $n=3$ turn out to be weaker then that listed in [16]..

One of the main objectives of the present paper is to study combinatorial
properties of the generalized plactic Cauchy kernel

$\displaystyle{\cal
C}({\mathfrak{P}}_{n},U)=\prod_{i=1}^{n-1}\left\\{{\prod_{j=n-1}^{i}(1+p_{i,j-i+1}u_{j})}\right\\},$

where ${\mathfrak{P}}_{n}$ stands for the set of parameters $\\{p_{ij},\,2\leq
i+j\leq n+1,\,i>1,\,j>1\\}$, and $U:=U_{n}$ 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

$\displaystyle{\cal{F}}({\mathfrak{P}}_{n,m},U)=\prod_{i=1}^{n-1}\left\\{\prod_{j=m-1}^{1}(1+p_{i,\overline{i-j+1}^{(m)}}u_{j})\right\\},$

where ${\mathfrak{P}}_{n,m}=\\{p_{ij}\\}_{1\leq i\leq n\atop 1\leq j\leq m}$;
see Definition 6.6 for the meaning of symbol $\overline{a}^{(m)}$.

We treat these kernels in the (reduced) plactic algebras ${\cal{PC}}_{n}$ and
${\cal{PF}}_{n,m}$ correspondingly. The algebras ${\cal{PC}}_{n}$ and
${\cal{PF}}_{n,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 ${\cal{PF}}_{n,m}$ mentioned above, gives rise to a set of
polynomials which are common generalizations of the (double) Schubert.
$\beta$-Grothendieck, Demazure and Stanley polynomials. To be more precise,
the polynomials listed above correspond to certain quotients of the plactic
algebra ${\cal{PF}}_{n,m}$ and appropriate specializations of parameters
$\\{p_{ij}\\}$ involved in our definition of polynomials
$U_{\alpha}(\\{p_{ij}\\})$, 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 properties 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 algebras
${\cal{P}}_{n}$ and ${\cal{F}}_{n}$ (resp. the algebras ${\cal{PC}}_{n}$ and
${\cal{PF}}_{n}$).

More precisely, let $\\{q_{2},\ldots,q_{n}\\}$ be a set of (mutually
commuting) parameters, and ${\mathbb{U}}_{n}:=\\{u_{1},\ldots,u_{n}\\}$ be a
set of generators of the free associative algebra over $\mathbb{Q}$ of rank
$n$. Let $Y,Z\subset[1,n]$ be subsets such that $Y\cup Z=[1,n]$ and $Y\cap
Z=\varnothing$. Let us set $p(a)=0$, if $a\in Y$ and $p(a)=1$, if $a\in Z$.
Define ${q}$-deformed super Knuth relations among the generators
$u_{1},\ldots,u_{n}$ as follows:

$\displaystyle{\rm SPL}_{q}\colon\ $
$\displaystyle(-1)^{p(i)p(k)}q_{k}u_{j}u_{i}u_{k}=u_{j}u_{k}u_{i},\qquad
i<j\leq k,$
$\displaystyle(-1)^{p(i)p(k)}q_{k}u_{i}u_{k}u_{j}=u_{k}u_{i}u_{j},\qquad i\leq
j<k.$

We define

  * •

$q$-deformed superplactic algebra ${\cal{SQP}}_{n}$ to be the quotient of the
free associative algebra $\mathbb{Q}\langle u_{1},\ldots,u_{n}\rangle$ by the
two-sided ideal generated by the set of q-deformed Knuth relations $({\rm
SPL}_{\bf q})$,

  * •

reduced $q$-deformed superplactic algebras ${\cal{SQPC}}_{n}$ and
${\cal{SQPF}}_{n,m}$ to be the quotient of the algebra ${\cal{SQP}}_{n}$ by
the two-sided ideals described in Definitions 5.18 and 6.7 correspondingly.

We state

######  Conjecture 1.1.

The algebra ${\cal{SQP}}_{n}$ and the algebras ${\cal{SQPC}}_{n}$ and
${\cal{SQPF}}_{n,m}$, are flat deformations of the algebras ${\cal{P}}_{n}$,
${\cal{PC}}_{n}$ and ${\cal{PF}}_{n,m}$ correspondingly.

In fact one can consider more general deformation of the Knuth relations, for
example take a set of parameters ${\bf Q}:=\\{q_{ik},\,1\leq i<k\leq n\\}$ and
impose on the set of generators $\\{u_{1},\ldots,u_{n}\\}$ the following
relations

$\displaystyle q_{ik}u_{j}u_{i}u_{k}=u_{j}u_{k}u_{i},\qquad i<j\leq k,\qquad
q_{ik}u_{i}u_{k}u_{j}=u_{k}u_{i}u_{j},\qquad i\leq j<k.$

However we don’t know how to describe a set of conditions on parameters ${\bf
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
${\cal{SQPC}}_{n}$ and ${\cal{SQPF}}_{n,m}$ for a “generic” values of
parameters ${\bf Q}$. We expect the dimension of algebras ${\cal{SQPC}}_{n}$
and ${\cal{SQPF}}_{n,m}$ each depends piece-wise polynomially on a set of
parameters $\\{q_{ij}\in\mathbb{Z}_{\geq 0},\,1\leq i<j\leq 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 ${\rm SPL}_{q}$ with $q_{i}=1$, $\forall\,i$.
Finally we point out an interesting and important paper [55] wherein the case
$Z=\varnothing$, 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 ${\cal{P}}_{n}$
is that the noncommutative elementary polynomials

$\displaystyle e_{k}(u_{1},\ldots,n_{n-1}):=\sum_{n-1\geq a_{1}\geq a_{2}\geq
a_{k}\geq 1}u_{a_{1}}\cdots u_{a_{k}},\qquad k=1,\ldots,n-1,$

generate a commutative subalgebra inside of the plactic algebra
${\cal{P}}_{n}$, 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 ${\cal{P}}_{n}$ obtained in this way,
is still missing.

The plactic algebra ${\cal{PF}}_{n,m}$ introduced in Section 6, has a monomial
basis parametrized by the set of Young tableaux of shape
$\lambda\subset(n^{m})$ filled by the numbers from the set $\\{1,\ldots,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\times
n\times n$. Surprisingly enough this number admits a factorization in the
product of the number of totally symmetric plane partitions (${\rm TSPP}$) by
the number of totally symmetric self-complementary plane partitions (${\rm
TSSCPP}$) fit inside the same cube. A similar phenomenon happens if $|m-n|\leq
2$, see Section 6. More precisely, we add to the well-known equalities

$\displaystyle\\#|{\cal{B}}_{1,n}|=2^{n},\qquad\\#|{\cal{B}}_{2,n}|={2n+1\choose
n},\qquad\\#|{\cal{B}}_{3,n}|=2^{n}\operatorname{Cat}_{n+1}\qquad\cite[cite]{[\@@bibref{}{SL}{}{},
A003645]},$
$\displaystyle\\#|{\cal{B}}_{4,n}|={\frac{1}{2}}\operatorname{Cat}_{n+1}\operatorname{Cat}_{n+2}\qquad\cite[cite]{[\@@bibref{}{SL}{}{},
A000356]},$ $\displaystyle\\#|{\cal{B}}_{n,5}|=\frac{{n+5\choose 5}{n+7\choose
7}{n+9\choose 9}}{{n+2\choose 2}{n+4\choose
4}}\qquad\cite[cite]{[\@@bibref{}{SL}{}{}, A133348]},$

the following relations

$\displaystyle\\#|{\cal{B}}_{n,n}|={\rm TSPP}(n+1)\times{\rm
ASM}(n),\qquad\\#|{\cal{B}}_{n,n+1}|={\rm TSPP}(n+1)\times{\rm ASM}(n+1),$
$\displaystyle\\#|{\cal{B}}_{n+2,n}|=\\#|{\cal{B}}_{n,n+1}|,\qquad\\#|{\cal{B}}_{n+3,n}|={\frac{1}{2}}\\#|{\cal{B}}_{n+1,n+1}|,$
$\displaystyle\\#|{\rm PP}(n)|=\\#|{\rm TSSCPP}(n)|\times\\#|{\rm
ASMHT}(2n)|=\\#|{\rm CSSCPP}(2n)|\times\\#|{\rm CSPP}(n)|,$
$\displaystyle\\#|{\rm CSPP}(2n)|=\\#|{\rm TSPP}(2n)|\times\\#|{\rm
CSTCPP}(2n)|,$ $\displaystyle\\#|{\rm CSPP}(2n+1)|=2^{2n}\\#|{\rm
TSPP}(2n+1)|\times\\#|{\rm TSPP}(2n)|,$

where ${\rm PP}(n)$ stands for the set of plane partitions fit in a cub of
size $n\times n\times n$; ${\rm AMSHT}(2n)$ denotes the set of alternating
sign matrices of size $2n\times 2n$ invariant under a half-turn and ${\rm
CSSPP}(2n)$ denotes the set of cyclically symmetric self-complementary plane
partitions fitting inside a cub of size $2n\times 2n\times 2n$, see, e.g.,
[6]; ${\rm CSTCPP}(n)$ stands for the set of cyclically symmetric transpose
complementary plane partitions fitting inside a cub of size $2n\times 2n\times
2n$, see, e.g., [67, $A051255$]. See Section 6 for the definition of the sets
${\cal{B}}_{n,m}$ and examples. In Exercise 6.3 we state some (new)
divisibility properties of the numbers $\\#|B_{n+4,n}|$.

It is well-known that ${\rm ASMHT}(2n)={\rm ASM}(n)\times{\rm CSPP}(n)$, where
${\rm CSPP}(n)$ denotes the number of cyclically symmetric plane partitions
fitting inside $n$-cube, and ${\rm CSSCPP}(2n)={\rm 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 $(\pi_{1},\pi_{2},\wp)$, where
$(\pi_{1},\pi_{2})$ is a pair of ${\rm TSSCPP}(n)$ and $\wp$ is a cyclically
symmetric plane partition fitting inside $n$-cube.

  * •

Describe the involution $\kappa\colon{\rm PP}(n)\longrightarrow{\rm PP}(n)$
which is induced by the involution $(\pi_{1},\pi_{2},\wp)$
$\longrightarrow(\pi_{2},\pi_{1},\wp)$ on the set ${\rm TSSCPP}(n)\times{\rm
TSSCP}(n)\times{\rm CSPP}(n)$, and its fixed points. Clearly one has $\\#|{\rm
Fix}(\kappa)|={\rm ASMHT}(2n)$.

  * •

Characterize pairs of plane partitions $(\Pi_{1},\Pi_{2})\in{\rm
PP}(n)\times{\rm PP}(n)$ such that

$\displaystyle(a)\quad\wp(\Pi_{1})=\wp(\Pi_{2});\qquad(b)\quad(\pi_{1}(\Pi_{1}),\pi_{2}(\Pi_{1}))=(\pi_{1}(\Pi_{2}),\pi_{2}(\Pi_{2})).$

These relations have straightforward proofs based on the explicit product
formulas for the numbers

$\displaystyle\\#|{\rm SPP}(n)|=\prod_{1\leq i\leq j\leq
k}\frac{n+i+j+k-1}{i+j+k-1},$ $\displaystyle\\#|{\rm
TSPP}(n)|=\prod_{i=1}^{n}\prod_{j=i}^{n}\prod_{k=j}^{n}\frac{i+j+k-1}{i+j+k-2},$
$\displaystyle\\#|{\rm
PP}(n)|=\prod_{i=0}^{n}\prod_{j=1}^{n-1}{\frac{3n-i-j}{2n-i-j}}=\prod_{i=1}^{n}{\frac{{2n+i\choose
n}}{{n+i\choose n}}},$

but bijective proofs of these identities are an open problem.

It follows from [42, 46] that the dimension of the (reduced) plactic algebra
${\cal{PC}}_{n}$ is equal to the number of alternating sign matrices of size
$n\times n$ (note that ${\rm ASM}(n)={\rm TSSCPP}(n)$). Therefore the key-
Grothendieck polynomials can be obtained from $U$-polynomials (see Section 6,
Theorem 6.12) after the specialization $p_{ij}=0$, if $i+j>n+1$.

In Section 4 following [27] we introduce and study a family of polynomials
which are a common generalization of the Schubert, $\beta$-Grothendieck, dual
$\beta$-Grothendieck, $\beta$-Demazure, $\beta$-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 permutation $w\in{\mathbb{S}}_{n}$ and composition
$\zeta\subset\delta_{n}:=(n-1,n-2,\ldots,2,1)$, we introduce polynomials

$\displaystyle{\cal{KN}}_{w}^{(\beta,\alpha,\gamma,h)}(X_{n})=h^{\ell(w)}T_{s_{i_{1}}}\cdots
T_{s_{i_{\ell}}}\big{(}x^{\delta_{n}}\big{)},$ $\displaystyle{\rm
KD}_{\zeta}^{(\beta,\alpha,\gamma,h)}(X_{n})=h^{\ell(v_{\zeta})}T_{s_{i_{1}}}\cdots
T_{s_{i_{\ell}}}\big{(}x^{\zeta^{+}}\big{)},$

where

$\displaystyle\begin{split}&T_{i}:=T_{i}^{(\beta,\alpha,\gamma,h)}=-\alpha+((\alpha+\beta+\gamma)x_{i}+\gamma
x_{i+1}+h\\\
&\hphantom{T_{i}:=T_{i}^{(\beta,\alpha,\gamma,h)}=}{}+h^{-1}(\alpha+\gamma)(\beta+\gamma)x_{i}x_{i+1})\partial_{i,i+1},\qquad
i=1,\dots,n-1,\end{split}$

denote a collection of divided difference operators which satisfy the Coxeter
and Hecke relations

$\displaystyle
T_{i}T_{j}T_{i}=T_{j}T_{i}T_{j},\qquad\text{if}\quad|i-j|=1;\qquad
T_{i}T_{j}=T_{j}T_{i},\qquad\text{if}\quad|i-j|\geq 2,$ $\displaystyle
T_{i}^{2}=(\beta-\alpha)T_{i}+\beta\alpha,\qquad i=1,\ldots,n-1;$

by definition for any permutation $w\in{\mathbb{S}}_{n}$ we set

$\displaystyle T_{w}:=T_{s_{i_{1}}}\cdots T_{s_{i_{\ell}}},$

for any reduced decomposition $w=s_{i_{1}}\cdots s_{i_{\ell}}$ of a
permutation in question; $\zeta^{+}$ denotes a unique partition obtained from
$\zeta$ by ordering its parts, and $v_{\zeta}\in{\mathbb{S}}_{n}$ denotes the
minimal length permutation such that $v_{\zeta}(\zeta)=\zeta^{+}$.

Assume that $h=1$.555Clearly that if $h\not=0$, then after rescaling
parameters $\alpha$, $\beta$ and $\gamma$ 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 $x_{i}$, $1\leq i\leq n-1$
and parameters $\alpha$, $\beta$ and $\gamma$. If $\alpha=\gamma=0$, these
polynomials coincide with the $\beta$-Grothendieck polynomials [17], if
$\beta=\alpha=1$, $\gamma=0$ these polynomials coincide with the Di
Francesco–Zinn-Justin polynomials [12], if $\beta=\gamma=0$, these polynomials
coincide with dual $\alpha$-Grothendieck polynomials
${\cal{H}}_{w}^{(\alpha)}(X_{n})$,666To avoid the reader’s confusion, let us
explain that in our paper we use the letter $\alpha$ 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
${\cal{H}}_{\alpha}^{(\alpha)}(X_{n})$ denotes the dual $\alpha$-Grothendieck
polynomial corresponding to a composition $\alpha$. Note that the
$\alpha$-Grothendieck polynomial ${\mathfrak{G}}_{w}^{(\alpha)}(X_{n})$ can be
obtained from the polynomial ${\mathfrak{G}}_{w}^{(\beta)}(X_{n})$ by
replacing $\beta$ by $\alpha$. where by definition we set
$X_{n}:=(x_{1},\ldots,x_{n})$.

######  Conjecture 1.3.

For any permutation $w\in{\mathbb{S}}_{n}$ and any composition
$\zeta\subset\delta_{n}$, polynomials
${\cal{KN}}_{w}^{(\beta,\alpha,\gamma,h)}(X_{n})$ and ${\rm
KD}_{\zeta}^{(\alpha,\beta,\gamma,h)}(X_{n})$ have nonnegative coefficients,
i.e.,

$\displaystyle{\cal{KN}}_{w}^{(\beta,\alpha,\gamma,h)}(X_{n})\in\mathbb{N}[\alpha,\beta,\gamma,h][X_{n}],\qquad{\rm
KD}_{\zeta}^{(\beta,\alpha,\gamma,h)}(X_{n})\in\mathbb{N}[\alpha,\beta,\gamma,h][X_{n}].$

We expect that these polynomials have some geometrical meaning to be
discovered.

More generally we study divided difference type operators of the form

$\displaystyle
T_{ij}:=T_{ij}^{(a,b,c,h,e)}=a+(bx_{i}+cx_{j}+h+ex_{i}x_{j})\partial_{ij},$

depending on parameters $a$, $b$, $c$, $h$, $e$ and satisfying the
$2D$-Coxeter relations

$\displaystyle T_{ij}T_{jk}T_{ij}=T_{jk}T_{ij}T_{jk},\qquad 1\leq i<j<k\leq
n,$ $\displaystyle
T_{ij}T_{kl}=T_{kl}T_{ij},\qquad\text{if}\quad\\{i,j\\}\cap\\{k,l\\}=\varnothing.$

We find that the necessary and sufficient condition which ensure the validity
of the $2D$-Coxeter relations is the following relation among the
parameters777In other words, the divided difference operators
$\\{T_{ij}:=T_{ij}^{(a,b,c,h,e)}\\}$ which obey the $2D$-Coxeter relations,
have the following form:  $\displaystyle
T_{ij}^{(a,b,c,h)}=\left(1+\frac{(a+b)}{h}x_{i}\right)\left(1+\frac{c-a}{h}x_{j}\right)\partial_{ij}+a\sigma_{ij},\qquad\text{if}\quad
h\not=0,\quad\text{$a$, $b$, $c$ arbitrary}.$ If $h=0$, then either
$T_{ij}=((c-a)x_{j}+ex_{i}x_{j})\partial_{ij}+a\sigma_{ij}$, or
$T_{ij}=(a+b)x_{i}+ex_{i}x_{j})\partial_{ij}+a\sigma_{ij}$, where
$\sigma_{ij}$ stands for the exchange operator:
$\sigma_{ij}(F(z_{i},z_{j}))=F(z_{j},z_{i})$.:

$\displaystyle(a+b)(a-c)+he=0.$

Therefore, if the above relation between parameters $a$, $b$, $c$, $h$, $e$
holds, then for any permutation $w\in{\mathbb{S}}_{n}$ the operator

$\displaystyle T_{w}:=T_{w}^{(a,b,c,h,e)}=T_{i_{1}}^{(a,b,c,h,e)}\cdots
T_{i_{\ell}}^{(a,b,c,h,e)},$

where $w=s_{i_{1}}\cdots s_{i_{\ell}}$ is any reduced decomposition of $w$, is
well-defined. Hence under the same assumption on parameters, for any
permutation $w\in{\mathbb{S}}_{n}$ one can attach the well-defined polynomial

$\displaystyle
G_{w}^{(a,b,c,h,e)}(X,Y):={T_{w}^{(x)}}^{(a,b,c,h,e)}\bigg{(}\prod_{i\geq
1,j\geq 1\atop i+j\leq n+1}(x_{i}+y_{j})\bigg{)},$

and in much the same fashion to define polynomials

$\displaystyle
D_{\alpha}^{(a,b,c,h,e)}(X,Y):={T_{w_{\alpha}}^{(x)}}^{(a,b,c,h,e)}\big{(}x^{\alpha^{+}}\big{)}$

for any composition $\alpha$ such that $\alpha_{i}\leq n-i$, $\forall\,i$. We
have used the notation ${T^{(x)}}_{w}^{(a,b,c,h,e)}$ to point out that this
operator acts only on the variables $X=(x_{1},\ldots,x_{n})$; for any
composition $\alpha\in\mathbb{Z}_{\geq 0}^{n}$, $\alpha^{+}$ denotes a unique
partition obtained from $\alpha$ by reordering its parts in (weakly)
decreasing order, and $w_{\alpha}$ denotes a unique minimal length permutation
in the symmetric group $\mathbb{S}_{n}$ such that
$w_{\alpha}(\alpha)=\alpha^{+}$.

In the present paper we are interested in to list a conditions on parameters
$A:=\\{a,b,c,h,e\\}$ with the constraint

$\displaystyle(a+b)(a-c)+he=0,$

which ensure that the above polynomials $G_{w}^{(a,b,c,h,e)}(X)$ and
$D_{\alpha}^{(a,b,c,h,e)}(X)$ or their specialization $x_{i}=1$, $\forall\,i$,
have nonnegative coefficients. We state the following conjectures:

  * •

${\cal{KN}}_{w}^{(\beta,\alpha,\gamma)}(X_{n})\in\mathbb{N}[\alpha,\beta,\gamma][X_{n}]$,

  * •

$G_{w}^{(-b,a+b+c,c,1,(b+c)(a+c)}(X_{n})\in\mathbb{N}[a,b,c][X_{n}]$,

  * •

$G_{w}^{(-b,a+b+c,c+d,1,(b+c+d)(a+c)}(x_{i}=1,\,\forall\,i)\in\mathbb{N}[a,b,c,d]$,
where $a$, $b$, $c$, $d$ are free parameters.

In the present paper we treat the case

$\displaystyle
A=(-\beta,\beta+\alpha+\gamma,\gamma,1,(\alpha+\gamma)(\beta+\gamma)).$ (1.2)

As it was pointed above, in this case polynomials $G_{w}^{A}(X)$ are common
generalization of Schubert, $\beta$-Grothendieck and dual
$\beta$-Grothendieck, and Di Francesco–Zinn-Justin polynomials. We expect a
certain interpretation of the polynomials $G_{w}^{A}$ for general $\beta$,
$\alpha$ and $\gamma$.

As it was pointed out earlier, one of the basic properties of the plactic
monoid ${\cal{P}}_{n}$ is that the noncommutative elementary symmetric
polynomials $\\{e_{k}(u_{1},\ldots,u_{n-1})\\}_{1\leq k\leq n-1}$ generate a
commutative subalgebra in the plactic algebra in question. One can reformulate
this statement as follows. Consider the generating function

$\displaystyle
A_{i}(x):=\prod_{a=n-1}^{i}(1+xu_{a})=\sum_{a=0}^{i}e_{a}(u_{n-1},\ldots,u_{i})x^{i-a},$

where we set $e_{0}(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
${\cal{P}}_{n}$ and ${\mathfrak{P}}_{n}$ [16], and Theorem 2.23,

$\displaystyle A_{i}(x)A_{i}(y)=A_{i}(y)A_{i}(x),\qquad 1\leq i\leq n-1.$

Now let us consider the Cauchy kernel

$\displaystyle{\cal{C}}({\mathfrak{P}}_{n},U)=A_{1}(z_{1})\cdots
A_{n-1}(z_{n-1}),$

where we assume that the pairwise commuting variables $z_{1},\ldots,z_{n-1}$
commute with the all generators of the algebras ${\cal{P}}_{n}$ and
${\mathfrak{P}}_{n}$. In what follows we consider the natural completion
${\widehat{\mathfrak{P}}}_{n}$ of the plactic algebra ${\mathfrak{P}}_{n}$ to
allow consider elements of the form $(1+xu_{i})^{-1}$. Elements of this form
exist in any Hecke type quotient of the plactic algebra
${\widetilde{\mathfrak{P}}}_{n}$. Having in mind this assumption, let us
compute the action of divided difference operators $\partial_{i,i+1}^{z}$ on
the Cauchy kernel. In the computation below, the commutativity property of the
elements $A_{i}(x)$ and $A_{i}(y)$ plays the key role. Let us start
computation of
$\partial_{i,i+1}^{z}({\cal{C}}({\mathfrak{P}}_{n},U))=\partial_{i,i+1}^{z}(A_{1}(z_{1})\cdots
A_{n-1}(z_{n-1}))$. First of all write
$A_{i+1}(z_{i+1})=A_{i}(z_{i+1})(1+z_{i+1}u_{i})^{-1}$. According to the basic
property of the elements $A_{i}(x)$, one sees that the expression
$A_{i}(z_{i})A_{i}(z_{i+1})$ is symmetric with respect to $z_{i}$ and
$z_{i+1}$, and hence is invariant under the action of divided difference
operator $\partial_{i,i+1}^{z}$. Therefore,

$\displaystyle\partial_{i,i+1}^{z}({\cal{C}}({\mathfrak{P}}_{n},U))=A_{1}(z_{1})\cdots
A_{i}(z_{i})A_{i}(z_{i+1})\partial_{i,i+1}^{z}\big{(}(1+z_{i+1}u_{i})^{-1}\big{)}$
$\displaystyle\hphantom{\partial_{i,i+1}^{z}({\cal{C}}({\mathfrak{P}}_{n},U))=}{}\times
A_{i+2}(z_{i+2})\cdots A_{n-1}(z_{n-1}).$

It is clearly seen that
$\partial_{i,i+1}^{z}((1+z_{i+1}u_{i})^{-1})=(1+z_{i}u_{i})^{-1}(1+z_{i+1}u_{i})^{-1}u_{i}$.
Therefore,

$\displaystyle\partial_{i,i+1}^{z}({\cal{C}}({\mathfrak{P}}_{n},U))=A_{1}(z_{1})\cdots
A_{i}(z_{i})A_{i+1}(z_{i+1})(1+z_{i}u_{i})^{-1}u_{i}A_{i+2}(z_{i+2})\cdots
A_{n-1}(z_{n-1}).$

It is easy to see that if one adds Hecke’s type relations on the generators

$\displaystyle u_{i}^{2}=(a+b)u_{i}+ab,\qquad i=1,\ldots,n-1,$

then

$\displaystyle(1+zu_{i})^{-1}u_{i}=\frac{u_{i}-zab}{(1+bz)(1-az)}.$

Therefore in the quotient of the plactic algebra ${\mathfrak{P}}_{n}$ by the
Hecke type relations listed above and by the “locality” relations

$\displaystyle u_{i}u_{j}=u_{j}u_{i},\qquad\text{if}\quad|i-j|\geq 2,$

one obtains

$\displaystyle(-b+(1+z_{i}b))\partial_{i,i+1}^{z}\left(A_{1}(z_{1})\cdots
A_{n-1}(z_{n-1})\right)=\left(A_{1}(z_{1})\cdots
A_{n-1}(z_{n-1})\right)\left(\frac{e_{i}-b}{1-az_{i}}\right).$

Finally, if $a=0$, then the above identity takes the following form

$\displaystyle\partial_{i,i+1}^{z}\left((1+z_{i+1}b)A_{1}(z_{1})\cdots
A_{n-1}(z_{n-1})\right)=\left(A_{1}(z_{1})\cdots
A_{n-1}(z_{n-1})\right)(e_{i}-b).$

In other words the above identity is equivalent to the statement [19] that in
the idCoxeter algebra ${\cal{IC}}_{n}$ the Cauchy kernel
${\cal{C}}({\mathfrak{P}}_{n},U)$ is the generating function for the
$b$-Grothendieck polynomials. 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 ${\approx}_{2}$ is a refinement of that ${\approx}_{1}$,
that is if assumption $a\,{\approx}_{2}\,b\Longrightarrow a\,{\approx}_{1}\,b$
holds $\forall\,a,\,b$, then each equivalence class w.r.t. relation
${\approx}_{1}$ is disjoint union of the equivalence classes w.r.t. relation
${\approx}_{2}$.

In the special case $b=-1$ and $P_{ij}=x_{i}+y_{j}$ if $2\leq i+j\leq n+1$,
$p_{ij}=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 elements888Remind that
by the name a family of Hecke’s type elements we mean a set of elements
$\\{e_{1},\dots,e_{n}\\}$ such that $e_{i}^{2}=Ae_{i}+B$, $A$, $B$ are
parameters (Hecke type relations), $e_{i}e_{j}=e_{j}e_{i}$, if $|i-j|\geq 2$,
$e_{i}e_{j}e_{i}=e_{j}e_{i}e_{j}$, if $|i-j|=1$ (Coxeter relations). we will
be put to use in the present paper.

In Section 5.1 we suggest a common generalization of some combinatorial
formulas from [10] and [21]. Namely, we give explicit formula

$\displaystyle{\prod_{1\leq i\leq k,\,1\leq j\leq n\atop j-i\leq
n-k}\frac{N-i-j+1}{i+j-1}}{\prod_{1\leq i\leq k,\,1\leq j\leq n\atop
j-i>n-k}\frac{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\times 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_{\lambda}^{*}(X_{n})$ introduced in Theorem 5.6, cf. [58, 72]. In
particular we show that for rectangular partition $\lambda=(n^{k})$ the
polynomial $s_{\lambda}^{*}(X_{n+k})$ is essentially coincide with the
Schubert polynomial corresponding to the Richardson permutation $1^{k}\times
w_{0}^{(n)}$. We introduce also a multivariable deformation of the numbers
$\operatorname{ASM}(n)$, namely,

$\displaystyle\operatorname{ASM}(X_{n-1};t):=\sum_{\lambda\subset\delta_{n}}s_{\lambda}^{*}(X)t^{|\lambda|}.$

Finally, in Section 5.1 we give combinatorial interpretations of rectangular
and staircase components of the refined ${\rm 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 examination 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 completion ${\cal{MN}}({\mathbb{S}}_{n})$ of the Bruhat order
poset on the symmetric group ${\mathbb{S}}_{n}$ an operator $\partial_{e}$
acting on the ring of polynomials $\mathbb{Z}[X_{n}]$, such that
$\partial_{e}(K_{h(e)})=K_{t(e)}$ together with compatibility conditions among
the set of operators $\\{\partial_{e}\\}_{e\in{\cal{MN}}({\mathbb{S}}_{n})}$,
that is for any two vertices of ${\cal{MN}}({\mathbb{S}}_{n})$, say $\alpha$
and $\beta$, and a path $p_{\alpha,\beta}$ in the MacNeille completion which
connects these vertices, the naturally defined operator
$\partial_{p_{\alpha,\beta}}$ depends only on the vertices $\alpha$ and
$\beta$ taken, and doesn’t depend on a path $p_{\alpha,\beta}$ selected. As
far as I know, this problem is still open.

##  2 Plactic, nilplactic and idplactic algebras

######  Definition 2.1 ([46]).

The plactic algebra ${\cal P}_{n}$ is an (unital) associative algebra over
$\mathbb{Z}$ generated by elements $\\{u_{1},\dots,u_{n-1}\\}$ subject to the
set of relations

$\displaystyle\text{(PL1)}\quad u_{j}u_{i}u_{k}=u_{j}u_{k}u_{i},\qquad
u_{i}u_{k}u_{j}=u_{k}u_{i}u_{j},\qquad\text{if}\quad i<j<k,$
$\displaystyle\text{(PL2)}\quad u_{i}u_{j}u_{i}=u_{j}u_{i}u_{i},\qquad
u_{j}u_{i}u_{j}=u_{j}u_{j}u_{i},\qquad\text{if}\quad i<j.$

######  Proposition 2.2 ([46]).

Tableau words999For 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 example, take
$\displaystyle T=\begin{matrix}1&2&3&3\cr 2&3&4\cr 3&4\cr 5\end{matrix}$ 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_{0}^{(n)}:=\underbrace{u_{n-1}u_{n-2}\cdots
u_{2}u_{1}}\underbrace{u_{n-1}u_{n-2}\cdots
u_{2}}\cdots\underbrace{u_{n-1}u_{u-2}}\underbrace{u_{n-1}}$ is equal to the
number of alternating sign matrices ${\rm ASM}(n)$. in the alphabet
$U=\\{u_{1},\dots,u_{n-1}\\}$ form a basis in the plactic algebra ${\cal
P}_{n}$.

In other words, each plactic class contain a unique tableau word. In
particular,

$\displaystyle\operatorname{Hilb}({\cal
P}_{n+1},t)=(1-t)^{-n}\big{(}1-t^{2}\big{)}^{-{n\choose 2}}.$

######  Remark 2.3.

There exists another algebra over $\mathbb{Z}$ which has the same Hilbert
series as that of the plactic algebra ${\cal P}_{n}$. Namely, define algebra
${\cal L}_{n}$ to be an associative algebra over $\mathbb{Z}$ generated by the
elements $\\{e_{1},e_{2},\ldots,e_{n-1}\\}$, subject to the set of relations

$\displaystyle(e_{i},(e_{j},e_{k})):=e_{i}e_{j}e_{k}-e_{j}e_{i}e_{k}-e_{j}e_{k}e_{i}+e_{k}e_{j}e_{i}=0,$

for all$1\leq i,j,k\leq n-1$, $j<k$. Observe that the number of defining
relations in the algebra ${\cal L}_{n}$ is equal to $2{n\choose 3}$. Note that
elements $e_{1}+e_{2}$ and $e_{2}e_{1}$ do not commute in the algebra
${\cal{L}}_{3}$, but do commute if are considered as elements in the plactic
algebra ${\cal{P}}_{3}$. See Example 5.29(C) for some details.

######  Exercise 2.4.

  * •

Show that the dimension of the degree $k$ homogeneous component ${{\cal
L}}^{(k)}_{n}$ of the algebra ${\cal L}_{n}$ is equal to the number
semistandard Young tableaux of the size $k$ filled by the numbers from the set
$\\{1,2,\ldots,n-1\\}$.

  * •

Let us set $e_{ij}:=(e_{i},e_{j}):=e_{i}e_{j}-e_{j}e_{i}$, $i<j$. Show that
the elements $\\{e_{ij}\\}_{1\leq i<j\leq n-1}$ generate the center of the
algebra ${\cal{L}}_{n}$.

######  Definition 2.5.

  1. $(a)$

The local plactic algebra ${\cal LP}_{n}$, see, e.g., [16], is an associative
algebra over $\mathbb{Z}$ generated by elements $\\{u_{1},\ldots,u_{n-1}\\}$
subject to the set of relations

$\displaystyle u_{i}u_{j}=u_{j}u_{i},\qquad\text{if}\quad|i-j|\geq 2,$
$\displaystyle u_{j}u_{i}^{2}=u_{i}u_{j}u_{i},\qquad
u_{j}^{2}u_{i}=u_{j}u_{i}u_{j},\qquad\text{if}\quad|i-j|=1.$

One can show (A.K.) that

$\displaystyle\operatorname{Hilb}({\cal
LP}_{n},t)=\prod_{j=1}^{n}\left({1\over 1-t^{j}}\right)^{n+1-j}.$

  2. $(b)$

The affine local plactic algebra $\widehat{{\cal{PL}}}_{n}$, see [34], is an
associative algebra over $\mathbb{Q}$ generated by the elements
$\\{e_{0},\ldots,e_{n-1}\\}$ subject to the set of relations listed in item
$(a)$, where all indices are understood modulo $n$.

  3. $(c)$

Let $q$ be a parameter, the affine quantum local plactic algebra
$\widehat{{\cal{PL}}}_{n}^{(q)}$ is an associative algebra over
$\mathbb{Q}[q]$ generated by the elements $\\{e_{0},\ldots,e_{n-1}\\}$ subject
to the set of relations

    1. $(i)$

$e_{i}e_{j}=e_{j}e_{i}$, if $|i-j|>1$,

    2. $(ii)$

$(1+q)e_{i}e_{j}e_{i}=qe_{i}^{2}e_{j}+e_{j}e_{i}^{2}$,
$(1+q)e_{j}e_{i}e_{j}=qe_{i}e_{j}^{2}+e_{j}^{2}e_{i}$, 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}^{\geq}\big{(}\hat{\mathfrak{gl}}(n)\big{)}$
rewritten101010For the reader convenient, we recall, see, e.g., [33] the
definition of algebra $U_{q}^{\geq}(\hat{\mathfrak{gl}}(n))$. Namely, this
algebra is an unital associative algebra over $\mathbb{Q}(q^{\pm 1})$
generated by the elements $\\{k_{i}^{\pm 1},E_{i}\\}_{i=0,\ldots,n-1}$,
subject to the set of relations  $(R1)$ $k_{i}k_{j}=k_{j}k_{i}$,
$k_{i}k_{i}^{-1}=k_{i}^{-1}=1$, $\forall\,i,\,j$, $(R2)$
$k_{i}E_{j}=q^{\delta_{i,j}-\delta_{i,j+1}}E_{j}k_{i}$, $(R3)$ (Serre
relations) $\displaystyle
E_{i}^{2}E_{i+1}-\big{(}q+q^{-1}\big{)}E_{i}E_{i+1}E_{i}+E_{i+1}E_{i}^{2}=0,\qquad
E_{i+1}^{2}E_{i}-\big{(}q+q^{-1}\big{)}E_{i+1}E_{i}E_{i+1}+E_{i}E_{i+1}^{2}=0,$
where all indices are understood modulo $n$, e.g., $e_{n}=e_{0}$. It is
clearly seen that after rewriting the Serre relations $(R3)$ in terms of the
elements $\\{e_{i}:=k_{i}E_{i}\\}_{0\leq i\leq n-1}$, one comes to the
relations $(ii)$ which have been listed in $(c)$. in generators $k_{i}E_{i}$.
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
${\widehat{\cal{LP}}}_{n}$ by the two-sided ideal generated by the set of
elements

$\displaystyle\\{(e_{j},(e_{i},e_{k})),\,0\leq i<j<k\leq n-1\\}.$

######  Definition 2.6 (nil Temperley–Lieb algebra).

Denote by ${\cal TL}_{n}^{(0)}$ the quotient of the local plactic algebra
${\cal LP}_{n}$ by the two-sided ideal generated by the elements
$\big{\\{}u_{1}^{2},\ldots,u_{n-1}^{2}\big{\\}}$.

It is well-known that $\dim{\cal{TL}}_{n}=C_{n}$, the $n$-th Catalan number.
One also has

$\displaystyle\operatorname{Hilb}\big{(}{\cal{TL}}_{4}^{(0)},t\big{)}=(1,3,5,4,1),\qquad\operatorname{Hilb}\big{(}{\cal{TL}}_{5}^{(0)},t\big{)}=(1,4,9,12,10,4,2),$
$\displaystyle\operatorname{Hilb}({\cal{TL}}_{6},t)=(1,5,14,25,31,26,16,9,4,1).$

######  Proposition 2.7.

The Hilbert polynomial $\operatorname{Hilb}({\cal{TL}}_{n},t)$ is equal to the
generating function for the number or $321$-avoiding permutations of the set
$\\{1,2,\ldots,n\\}$ having the inversion number equals to $k$, see [67,
$A140717$], for other combinatorial interpretations of the polynomials
$\operatorname{Hilb}({\cal{TL}}_{n},t)$.

######  Exercise 2.8.

  * •

Show that
$\deg_{t}\operatorname{Hilb}({\cal{TL}}_{n},t)=\big{[}{\frac{n^{2}}{4}}\big{]}$.

  * •

Show that

$\displaystyle\lim_{k\rightarrow\infty}t^{k^{2}}\operatorname{Hilb}\big{(}{\cal{TL}}_{2k},t^{-1}\big{)}=\prod_{n\geq
1}{\frac{\big{(}1-t^{4n-2}\big{)}}{\big{(}1-t^{2n-1}\big{)}^{4}\big{(}1-t^{4n}\big{)}}}=\sum_{n\geq
0}a_{n}t^{n},$

where $a_{n}$ is equal to the number of $2$-colored generalized Frobenius
partitions, see, e.g., [67, $A051136$] and the literature quoted
therein111111The second equality in the above formula is due to G. Andrews
[1]. The second formula for the generating function of the numbers
$\\{a_{n}\\}_{n\geq 0}$ displayed in [67, $A051136$], either contains
misprints or counts something else..

  * •

Show that

$\displaystyle\lim_{k\rightarrow\infty}t^{k(k+1)}\operatorname{Hilb}\big{(}{\cal{TL}}_{2k+1},t^{-1}\big{)}=2\prod_{n\geq
1}{\frac{(1+t^{n})\big{(}1+t^{2n}\big{)}^{2}}{1-t^{n}}}=2\sum_{n\geq
0}b_{n}t^{n}.$

See [67, $A201078$] for more details concerning relations of this exercise
with the Ramanujan theta functions121212See, e.g.,
http://en.wikipedia.org/wiki/Ramanujan_theta_function..

We denote by ${\cal{TH}}_{n}^{(\beta)}$ the quotient of the local plactic
algebra ${\cal{LP}}_{n}$ by the two-sided ideal generated by the elements
$\big{\\{}u_{i}^{2}-\beta u_{i},\,i=1,\ldots,n-1\big{\\}}$.

######  Definition 2.9.

The modified plactic algebra ${\cal{MP}}_{n}$ is an associative algebra over
$\mathbb{Z}$ generated by $\\{u_{1},\ldots,u_{n-1}\\}$ subject to the set of
relations (PL1) and that

$\displaystyle u_{j}u_{j}u_{i}=u_{j}u_{i}u_{i},\qquad\text{and}\qquad
u_{i}u_{j}u_{i}=u_{j}u_{i}u_{j},\qquad\text{if}\quad 1\leq i<j\leq n-1.$

######  Definition 2.10.

The nilplactic algebra ${\cal{NP}}_{n}$ is an associative algebra over
$\mathbb{Q}$ generated by $\\{u_{1},\ldots,u_{n-1}\\}$, subject to set of
relations

$\displaystyle u_{i}^{2}=0,\qquad u_{i}u_{i+1}u_{i}=u_{i+1}u_{i}u_{i+1},$

the set of relations (PL1), and that $u_{i}u_{j}u_{i}=u_{j}u_{i}u_{j}$, if
$|i-j|\geq 2$.

######  Proposition 2.11 ([52]).

Each nilplactic class not containing zero, contains one and only one tableau
word.

######  Proposition 2.12.

The nilplactic algebra ${\cal{NP}}_{n}$ has finite dimension, its Hilbert
polynomial $\operatorname{Hilb}({\cal{NP}}_{n},t)$ has degree ${n\choose 2}$,
and $\dim_{\mathbb{Q}}({\cal{NP}}_{n})_{{n\choose 2}}=1$.

######  Example 2.13.

$\displaystyle\operatorname{Hilb}({\cal{NP}}_{3},t)=(1,2,2,1),\qquad\operatorname{Hilb}({\cal{NP}}_{4},t)=(1,3,6,6,5,3,1),$
$\displaystyle\operatorname{Hilb}({\cal{NP}}_{5},t)=(1,4,12,19,26,26,22,15,9,4,1),\qquad\dim_{\mathbb{Q}}({\cal{NP}}_{5})=139,$
$\displaystyle\operatorname{Hilb}({\cal{NP}}_{6},t)=(1,5,20,44,84,119,147,152,140,224,81,52,29,14,5,1),$
$\displaystyle\dim_{\mathbb{Q}}({\cal{NP}}_{6})=1008.$

######  Definition 2.14.

The idplactic algebra ${\cal{IP}}_{n}:={\cal{IP}}_{n}^{(\beta)}$ is an
associative algebra over $\mathbb{Q}[\beta]$ generated by elements
$\\{u_{1},\ldots,u_{n-1}\\}$ subject to the set of relations

$\displaystyle u_{i}^{2}=\beta u_{i},\qquad
u_{i}u_{j}u_{i}=u_{j}u_{i}u_{j},\qquad i<j,$ (2.1)

and the set of relations (PL1).

In other words,the idplactic algebra ${\cal{IP}}_{n}^{(\beta)}$ is the
quotient of the modified plactic algebra ${\cal{MP}}_{n}$ by the two-sided
ideal generated by the elements $\big{\\{}u_{i}^{2}-\beta u_{i},\,1\leq i\leq
n\big{\\}}$.

######  Proposition 2.15.

Each idplactic class not containing zero, contains a unique tableau word
associated with a row strict semistandard Young tableau131313Recall 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,
$\displaystyle\begin{matrix}1&2&3&5&6\\\ 2&3&6&8\\\ 4&5&7\end{matrix}$ .

For each word $w$ denote by $\operatorname{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

$\displaystyle\operatorname{rl}(dbadc)=4=\operatorname{rl}(cadbd),\qquad\operatorname{rl}(dbadbc)=5=\operatorname{rl}(cbadbd).$

Indeed,

$\displaystyle dbadc\sim dbdac\sim dbdca\sim ddbca\sim dbac,$ $\displaystyle
dbadbc\sim dbabdc\sim dabadc\sim adbdac\sim abdbca\sim abbdca\sim dbabc.$

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 ${\cal{IP}}_{n}^{(\beta)}$ has finite dimension, and its
Hilbert polynomial has degree ${n\choose 2}$.

######  Example 2.18.

$\displaystyle\operatorname{Hilb}({\cal{IP}}_{3},t)=(1,2,2,1),\qquad\operatorname{Hilb}({\cal{IP}}_{4},t)=(1,3,6,7,5,3,1),\qquad\dim({\cal{IP}}_{4})=26,$
$\displaystyle\operatorname{Hilb}({\cal{IP}}_{5},t)=(1,4,12,22,30,32,24,15,9,4,1),\qquad\dim({\cal{IP}}_{5})=154,$
$\displaystyle\operatorname{Hilb}({\cal{IP}}_{6},t)=(1,5,20,50,100,156,188,193,173,126,84,52,29,14,5,1),$
$\displaystyle\dim({\cal{IP}}_{6})=1197,\qquad\dim({\cal{IP}}_{7})=9401.$

Note that for a given $n$ some words corresponding to strict semistandard
Young tableaux of size between 5 and ${n-1\choose 2}$ are idplactic equivalent
to zero. For example,

$\displaystyle\begin{matrix}1&2&4\\\ 3&4\end{matrix}\sim 31424\sim 31242\sim
13242\sim 13422\sim 0,$ $\displaystyle\begin{matrix}1&2&3\\\ 2&4\\\
4\end{matrix}\sim 421423\sim 421243\sim 412143\sim 142413\sim 124213\sim
122431\sim 0.$

It seems an interesting problem to count the number of all row strict
semistandard Young tableaux contained in the staircase $(n,n-1,\ldots,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 ${\cal PTL}_{n}^{(\beta)}$ is define to be
the quotient of the idplactic algebra ${\cal IP}_{n}^{(\beta)}$ by the two-
sided ideal generated by the elements

$\displaystyle\\{u_{i}u_{j}u_{i},\,\forall\,i\not=j\\}.$

For example,

$\displaystyle\operatorname{Hilb}\big{(}{\cal{PTL}}_{4}^{(0)},t\big{)}=(1,3,6,4,1)_{t},\qquad\operatorname{Hilb}\big{(}{\cal{PTL}}_{5}^{(0)},t\big{)}=(1,4,12,16,14,4,2)_{t},$
$\displaystyle\operatorname{Hilb}\big{(}{\cal{PTL}}_{6}^{(0)},t\big{)}=(1,5,20,40,60,46,32,10,4,1)_{t},$
$\displaystyle\operatorname{Hilb}\big{(}{\cal{PTL}}_{7}^{(0)},t\big{)}=(1,6,30,80,170,216,238,152,96,44,14,4,2)_{t}.$

One can show that

$\displaystyle\deg_{t}\operatorname{Hilb}\big{(}{\cal{PTL}}_{n}^{(0)},t\big{)}=\left[\frac{n^{2}}{4}\right],$

and

$\displaystyle{\rm
Coef\/f}_{t^{\max}}\operatorname{Hilb}({\cal{PTL}}_{n},t)=\begin{cases}1,&\text{if
$n$ is even},\\\ 2,&\text{if $n$ is odd}.\end{cases}$

######  Definition 2.20.

The nilCoxeter algebra ${\cal{NC}}_{n}$ is defined to be the quotient of the
nilplactic algebra ${\cal{NP}}_{n}$ by the two-sided ideal generated by
elements $\\{u_{i}u_{j}-u_{j}u_{i},\,|i-j|\geq 2\\}$.

Clearly the nilCoxeter algebra ${\cal NC}_{n}$ is a quotient of the modified
plactic algebra ${\cal MP}_{n}$ by the two-sided ideal generated by the
elements $\\{u_{i}u_{j}-u_{j}u_{i},\,|i-j|\geq 2\\}$.

######  Definition 2.21.

The idCoxeter algebra ${\cal{IC}}_{n}^{(\beta)}$ is defined to be the quotient
of the idplactic algebra ${\cal{IP}}_{n}^{(\beta)}$ by the two-sided ideal
generated by the elements $\\{u_{i}u_{j}-u_{j}u_{i},\,|i-j|\geq 2\\}$.

It is well-known, see, e.g., [42], that the algebra ${\cal NC}_{n}$ and ${\cal
IC}_{n}^{(\beta)}$ has dimension $n!$, and the elements
$\\{u_{w}:=u_{i_{1}}\cdots u_{i_{\ell}}\\}$, where $w=s_{i_{1}}\cdots
s_{i_{\ell}}$ is any reduced decomposition of $w\in{\mathbb{S}}_{n}$, form a
basis in the nilCoxeter and idCoxeter algebras ${\cal NC}_{n}$ and ${\cal
IC}_{n}^{(\beta)}$.

######  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
${\widetilde{\cal P}}_{n}$ to be an associative algebra generated by elements
$u_{1},\dots,u_{n-1}$, subject to the relations (PL2) and relations

$\displaystyle u_{j}u_{i}(u_{i}+u_{j})=(u_{i}+u_{j})u_{j}u_{i},\qquad i<j.$
(2.2)

The relation (2.2) can be written also in the form

$\displaystyle
u_{j}(u_{i}u_{j}-u_{j}u_{i})=(u_{i}u_{j}-u_{j}u_{i})u_{i},\qquad i<j.$

######  Theorem 2.23 ([16]).

For each pair of numbers $1\leq i<j\leq n$ define

$\displaystyle A_{i,j}(x)=\prod_{k=j}^{i}(1+xu_{k}).$

Then the elements $A_{i,j}(x)$ and $A_{i,j}(y)$ commute in the generalized
plactic algebra ${\widetilde{\cal P}}_{n}$.

######  Corollary 2.24.

Let $1\leq i<j\leq n$ be a pair of numbers. Noncommutative elementary
polynomials $e_{a}^{ij}:=\sum\limits_{j\geq i_{1}\geq\cdots\geq i_{k}\geq
i}u_{i_{1}}\cdots u_{i_{a}}$, $i\leq a\leq j$, generate a commutative
subalgebra ${\cal C}_{i,j}$ of rank $j-i+1$ in the plactic algebra ${\cal
P}_{n}$.

Moreover, the algebra ${\cal C}_{1,n}$ is a maximal commutative subalgebra of
${\cal P}_{n}$.

To establish Theorem 2.23, we are going to prove more general result. To start
with, let us define generic plactic algebra ${\mathfrak{P}}_{n}$.

######  Definition 2.25.

The generic plactic algebra ${\mathfrak{P}}_{n}$ is an associative algebra
over $\mathbb{Z}$ generated by $\\{e_{1},\dots,e_{n-1}\\}$ subject to the set
of relations

$\displaystyle e_{j}(e_{i},e_{j})=(e_{i},e_{j})e_{i},\qquad$
$\displaystyle\text{if}\quad i<j,$ (2.3)
$\displaystyle(e_{j},(e_{i},e_{k}))=0,\qquad$ $\displaystyle\text{if}\quad
i<j<k,$ (2.4) $\displaystyle(e_{j},e_{k})(e_{i},e_{k})=0,\qquad$
$\displaystyle\text{if}\quad 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

$\displaystyle A_{n}(x)=\prod_{k=j}^{1}(1+xe_{k}).$

Then the elements $A_{n}(x)$ and $A_{n}(y)$ commute in the generic plactic
algebra ${\mathfrak{P}}_{n}$. Moreover the elements $A_{n}(x)$ and $A_{n}(y)$
commute if and only if the generators $\\{e_{1},\ldots,e_{n-1}\\}$ satisfy the
relations (2.3)–(2.5).

###### Proof.

For $n=2,3$ the statement of Theorem 2.26 is obvious. Now assume that the
statement of Theorem 2.26 is true in the algebra $\mathfrak{P}_{n}$. We have
to prove that the commutator $[A_{n+1}(x),A_{n+1}(y)]$ is equal to zero. First
of all, $A_{n+1}(x)=(1+xe_{n})A_{n}(x)$. Therefore

$\displaystyle[A_{n+1}(x),A_{n+1}(y)]=(1+xe_{n})[A_{n}(x),1+ye_{n}]A_{n}(y)-[A_{n}(y),1+xe_{n}]A_{n}(x).$

Using the standard identity $[ab,c]=a[b,c]+[a,c]b$, one finds that

$\displaystyle\frac{1}{xy}[A_{n}(x),1+ye_{n}]=\sum_{i=}^{n-1}\prod_{a=n-1}^{i+1}(1+xe_{a})(e_{i},e_{n})\prod_{a=i-1}^{1}(1+xe_{a}).$

Using relations (2.3) we can move the commutator $(e_{i},e_{n})$ to the left,
since $i<a<n$, till we meet the term $(1+xe_{n})$. Using relations (2.4) we
see that $(1+xe_{n})(e_{i},n)=(e_{i},n)(1+xe_{i})$. Therefore we come to the
following relation

$\displaystyle\frac{1}{xy}[A_{n}(x),1+ye_{n}]$
$\displaystyle\qquad{}=\sum_{i=n-1}^{1}(e_{i},e_{n})\left((1+xe_{i})\prod_{a=n-1\atop
a\not=i}^{1}(1+xe_{a})A_{n}(y)-(1+ye_{i})\prod_{a=n-1\atop
a\not=i}^{1}(1+ye_{a})A_{n}(x)\right).$

Finally let us observe that according to the relation (2.5),

$\displaystyle(e_{i},e_{n})\bigl{(}(1+xe_{i})(1+xe_{n-1})-(1+xe_{n-1})(1+xe_{i})\bigr{)}=x^{2}(e_{i},e_{n})(e_{i},e_{n-1})=0.$

Indeed,

$\displaystyle(e_{i},e_{n})(e_{i},e_{n-1})=(e_{i},e_{n})e_{i}e_{n-1}-(e_{i},e_{n})e_{n-1}e_{i}=e_{n}e_{n-1}(e_{i},e_{n})-e_{n-1}e_{n}(e_{i},e_{n})=0.$

Therefore

$\displaystyle\frac{1}{xy}[A_{n}(x),1+ye_{n}]=\left(\sum_{i={n-1}}^{1}(e_{i},e_{n})\right)[A_{n}(x),A_{n}(y)]=0$

according to the induction assumption.

Finally, if $i<j$, then
$(e_{i}+e_{j},e_{j}e_{i})=0\Longleftrightarrow\eqref{equation2.4}$; if
$i<j<k$, and the relations 2.3 hold, then
$(e_{i}+e_{j}+e_{k},e_{j}e_{i}+e_{k}e_{j}+e_{k}e_{i})=0\Longleftrightarrow\eqref{equation2.5}$;
if $i<j<k$, and relations (2.3) and (2.4) hold, then
$(e_{i}+e_{j}+e_{k},e_{k}e_{j}e_{i})=0\Longleftrightarrow\eqref{equation2.6}$;
the relations $(e_{j}e_{i}+e_{k}e_{j}+e_{k}e_{i},e_{k}e_{j}e_{i})=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 ${\bf
a}=(a_{1},\dots,a_{n})\in R(T)$, where $n:=|T|$ (resp. ${\bf
a}=(a_{1},\dots,a_{m})\in IR(T)$, where $m\geq|T|$).

######  Definition 2.27 (compatible sequences ${\bf b}$).

Given a word ${\bf a}\in R(T)$ (resp. ${\bf a}\in IR(T)$), denote by $C(\bf
a)$ (resp. $IC(\bf a)$) the set of sequences of positive integers, called
compatible sequences, ${\bf b}:=(b_{1}\leq b_{2}\leq\cdots\leq b_{m})$ such
that

$\displaystyle b_{i}\leq a_{i},\qquad\text{and if}\quad a_{i}\leq
a_{i+1},\qquad\text{then}\quad b_{i}<b_{i+1}.$

Finally, define the set $C(T)$ (resp. $IC(T)$) to be the union $\bigcup C({\bf
a})$ (resp. the union $\bigcup IC({\bf a})$), where ${\bf a}$ runs over all
words which are plactic (resp. idplactic) equivalent to the word $w(T)$.

######  Example 2.28.

Take $T=\begin{matrix}2&3\cr 3&\cr\end{matrix}$. The corresponding tableau
word is $w(T)=323$. We have $R(T)=\\{232,323\\}$ and
$IR(T)=R(T)\bigcup\\{2323,3223,3232,3233,3323,32323,\dots\\}$. Moreover,

$\displaystyle C(T)=\left\\{\begin{matrix}{\bf
a}\colon&232&323&323&323&323\cr{\bf
b}\colon&122&112&113&123&223\end{matrix}\right\\},$ $\displaystyle
IC(T)=C(T)\bigcup\left\\{\begin{matrix}{\bf
a}\colon&2323&3223&3232&3233&3323&32323\cr{\bf
b}\colon&1223&1123&1122&1123&1223&11223\end{matrix}\right\\}.$

Let ${\mathfrak{P}}:={\mathfrak{P}}_{n}:=\\{p_{i,j},\,i\geq 1,\,j\geq
1,\,2\leq i+j\leq n+1\\}$ be the set of (mutually commuting) variables.

######  Definition 2.29.

  1. (1)

Let $T$ be a semistandard tableau, and $n:=|T|$. Define the double key
polynomial ${\cal K}_{T}({\mathfrak{P}})$ corresponding to the tableau $T$ to
be

$\displaystyle{\cal K}_{T}(\mathfrak{P})=\sum_{{\bf b}\in
C(T)}\prod_{i=1}^{n}p_{b_{i},a_{i}-b_{i}+1}.$

  2. (2)

Let $T$ be a semistandard tableau, and $n:=|T|$. Define the double key
Grothendieck polynomial ${\cal{GK}}_{T}(\mathfrak{P})$ corresponding to the
tableau $T$ to be

$\displaystyle{\cal{GK}}_{T}({\mathfrak{P}})=\sum_{{\bf b}\in
IC(T)}\prod_{i=1}^{m}p_{b_{i},a_{i}-b_{i}+1}.$

In the case when $p_{i,j}=x_{i}+y_{j}$, $\forall\,i,j$, where
$X=\\{x_{1},\ldots,x_{n}\\}$ and $Y=\\{y_{1},\ldots,y_{n}\\}$ denote two sets
of variables, we will write ${\cal K}_{T}(X,Y)$, ${\cal GK}_{T}(X,Y),\dots$,
instead of ${\cal K}_{T}({\mathfrak{P}})$, ${\cal
GK}_{T}({\mathfrak{P}}),\ldots$.

######  Definition 2.30.

Let $T$ be a semistandard tableau, denote by
$\alpha(T)=(\alpha_{1},\dots,\alpha_{n})$ the exponent of the smallest
monomial in the set $\big{\\{}x^{\bf
b}:=\prod\limits_{i=1}^{m}x_{i}^{b_{i}},\,{\bf b}\in C(T)\big{\\}}$ with
respect to the lexicographic order.

We will call the composition $\alpha(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 $\eta\not=0$ be a parameter. Define the divided difference
operator $\partial_{xy}(\eta)$ as follows

$\displaystyle\partial_{xy}(\eta)f(x,y)={f(x,y)-f(\eta^{-1}y,\eta x)\over
x-\eta^{-1}y}.$

Equivalently, $(x-\eta^{-1}y)\partial_{xy}(\eta)=1-s_{xy}^{\eta}$, where the
operator $s_{xy}^{\eta}$ acts on the variables $(x,y,\ldots)$ according to the
rule: $s_{xy}^{\eta}$ transforms the pair $(x,y)$ to $(\eta^{-1}y,\eta x)$,
and fixes all other variables. We set by definition,
$s_{yx}^{\eta}:=s_{xy}^{{\eta^{-1}}}$.

The operator $\partial_{xy}(\eta)$ takes polynomials to polynomials and has
degree $-1$. The case $\eta=1$ corresponds to the Newton divided difference
operator $\partial_{xy}:=\partial_{xy}(1)$.

######  Lemma 3.1.

  1. $(0)$

$s_{xy}^{\eta}s_{xz}^{\eta\xi}=s_{yz}^{\xi}s_{xy}^{\eta}$,
$s_{xy}^{\eta}s_{xz}^{\eta\xi}s_{yz}^{\xi}=s_{yz}^{\xi}s_{xz}^{\eta\xi}s_{xy}^{\eta}$,

  2. $(1)$

$\partial_{yx}(\eta)=-\eta\partial_{xy}(\eta^{-1})$,
$s_{xy}^{\eta}\partial_{yz}(\xi)=\eta^{-1}\partial_{xz}(\eta\xi)s_{xy}^{\eta}$,

  3. $(2)$

$\partial_{xy}(\eta)^{2}=0$,

  4. $(3)$

$($three term relation$)$
$\partial_{xy}(\eta)\partial_{yz}(\xi)=\eta^{-1}\partial_{xz}(\eta\xi)\partial_{xy}(\eta)+\partial_{yz}(\xi)\partial_{xz}(\eta\xi)$.

  5. $(4)$

$($twisted Leibniz rule$)$
$\partial_{xy}(\eta)(fg)=\partial_{xy}(\eta)(f)g+s_{xy}^{\eta}(f)\partial_{xy}(\eta)(g)$,

  6. $(5)$

$($crossing relations, cf. [19, formula (4.6)])

     * •

$x\partial_{xy}(\eta)=\eta^{-1}\partial_{xy}(\eta)y+1,y\partial_{xy}(\eta)=\eta\partial_{xy}(\eta)x-\eta$,

     * •

$\partial_{xy}(\eta)y\partial_{yz}(\xi)=\partial_{xz}(\eta\xi)x\partial_{xy}(\eta)+\xi^{-1}\partial_{yz}(\xi)z\partial_{xz}(\eta\xi)$,

  7. $(6)$

$\partial_{xy}\partial_{xz}\partial_{yz}\partial_{xz}=0$.

Let $x_{1},\ldots,x_{n}$ be independent variables, and let
$P_{n}:=\mathbb{Q}[x_{1},\ldots,x_{n}]$. For each $i<j$ put
$\partial_{ij}:=\partial_{x_{i}x_{j}}(1)$ and $\partial_{ji}=-\partial_{ij}$.
From Lemma 3.1 we have

$\displaystyle\partial_{ij}^{2}=0,\qquad\partial_{ij}\partial_{jk}+\partial_{ki}\partial_{ij}+\partial_{jk}\partial_{ki}=0,$
$\displaystyle\partial_{ij}x_{j}\partial_{jk}+\partial_{ki}x_{i}\partial_{ij}+\partial_{jk}x_{k}\partial_{ki},\qquad\text{if}\quad\text{$i$,
$j$, $k$ are distinct}.$

It is interesting to consider also an additive or affine analog
$\partial_{xy}[k]$ of the divided difference operators $\partial_{xy}(\eta)$,
namely,

$\displaystyle\partial_{xy}[k](f(x,y))={f(x,y)-f(y-k,x+k)\over x-y+k}.$

One has $\partial_{yx}[k]=-\partial_{xy}[-k]$, and
$\partial_{xy}[p]\partial_{yz}[q]=\partial_{xz}[p+q]\partial_{xy}[p]+\partial_{yz}[q]\partial_{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
$\pi_{i}(f)=\partial_{i}(x_{i}f)$, and $\overline{\pi}_{i}:=\pi_{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\in{\mathbb{S}}_{n}$ be a permutation, $X=(x_{1},\dots,x_{n})$ and
$Y=(y_{1},\dots,y_{n})$ be two sets of variables. Denote by
$w_{0}\in{\mathbb{S}}_{n}$ the longest permutation, and by
$\delta_{n}=(n-1,n-2,\dots,1)$ the staircase partition. For each partition
$\lambda$ define

$\displaystyle R_{\lambda}(X,Y):=\prod_{(i,j)\in\lambda}(x_{i}+y_{j}).$ (4.1)

For $i=1,\dots,n-1$, let $s_{i}=(i,i+1)\in{\mathbb{S}}_{n}$ denote the simple
transposition that interchanges $i$ and $i+1$ and fixes all other elements of
the set $\\{1,\dots,n\\}$. If
$\alpha=(\alpha_{1},\dots,\alpha_{i},\alpha_{i+1},\dots,\alpha_{n})$ is a
composition, we will write

$\displaystyle
s_{i}\alpha=(\alpha_{1},\dots,\alpha_{i+1},\alpha_{i},\dots,\alpha_{n}).$

######  Definition 4.1 (cf. [42] and the literature quoted therein).

  * •

For each permutation $w\in{\mathbb{S}}_{n}$ the double Schubert polynomial
${{\mathfrak{S}}}_{w}(X,Y)$ is defined to be

$\displaystyle\partial_{w^{-1}w_{0}}^{(x)}(R_{\delta_{n}}(X,Y)).$

  * •

Let $\alpha$ be a composition. The key polynomials $K[\alpha](X)$ are defined
recursively as follows: if $\alpha$ is a partition, then
$K[\alpha](X)=x^{\alpha}$; otherwise, if $\alpha$ and $i$ are such that
$\alpha_{i}<\alpha_{i+1}$, then

$\displaystyle
K[s_{i}(\alpha)](X)=\partial_{i}\big{(}x_{i}K[\alpha](X)\big{)}.$

  * •

The reduced key polynomials ${\widehat{K}}[\alpha](X)$ are defined recursively
as follows: if $\alpha$ is a partition, then
${\widehat{K}}[\alpha](X)=K[\alpha](X)=x^{\alpha}$; otherwise, if $\alpha$ and
$i$ are such that $\alpha_{i}<\alpha_{i+1}$, then

$\displaystyle{\widehat{K}}[s_{i}(\alpha)](X)=x_{i+1}\partial_{i}\big{(}{\widehat{K}}[\alpha](X)\big{)}.$

  * •

For each permutation $w\in{\mathbb{S}}_{n}$ the double $\beta$-Grothendieck
polynomial ${\cal G}_{w}^{\beta}(X,Y)$ is defined recursively as follows: if
$w=w_{0}$ is the longest element, then ${\cal
G}_{w_{0}}(X,Y)=R_{\delta_{n}}(X,Y)$; if $w$ and $i$ are such that
$w_{i}>w_{i+1}$, i.e., $l(ws_{i})=l(w)-1$, then

$\displaystyle{\cal
G}_{ws_{i}}^{\beta}(X,Y)=\partial_{i}^{(x)}\big{(}{(1+\beta x_{i+1}){\cal
G}_{w}^{\beta}(X,Y)}\big{)}.$

  * •

For each permutation $w\in{\mathbb{S}}_{n}$ the double dual
$\beta$-Grothendieck polynomial ${\cal H}_{w}^{\beta}(X,Y)$ is defined
recursively as follows: if $w=w_{0}$ is the longest element, then ${\cal
H}_{w_{0}}(X,Y)=R_{\delta_{n}}(X,Y)$; if $w$ and $i$ are such that
$w_{i}>w_{i+1}$, i.e., $l(ws_{i})=l(w)-1$, then

$\displaystyle{\cal H}_{ws_{i}}^{\beta}(X,Y)=(1+\beta
x_{i})\partial_{i}^{(x)}\big{(}{\cal H}_{w}^{\beta}(X,Y)\big{)}.$

  * •

The key $\beta$-Grothendieck polynomials $\operatorname{KG}[\alpha](X;\beta)$
are defined recursively as follows141414In the case $\beta=-1$ divided
difference operators $D_{i}:=\partial_{i}(x_{i}-x_{i}x_{i+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\in{\mathbb{S}}_{n}$. into a sum of
Grasmannian ones corresponding to a collection of Grasmannin permutations
$v_{\lambda}\in{\mathbb{S}}_{\infty}$, see [41] for details. The above
mentioned operators $D_{i}$ had been used in [41] to construct a basis
$\Omega_{\alpha}|\alpha\in\mathbb{Z}_{\geq 0}$ that deforms the basis which is
built up from the Demazure (known also as key) polynomials. Therefore
polynomials $\operatorname{KG}[\alpha](X;\beta=-1)$ coincide with those
introduced by A. Lascoux in [41]. In [63] the authors give a conjectural
construction for polynomials $\Omega_{\alpha}$ 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  $\displaystyle
J_{\alpha}^{(\beta)}=\operatorname{KG}[\alpha](X;\beta),$ where polynomials
$J_{\alpha}^{\beta)}$ are defined in [63] using the $K$-theoretic versions of
the Kohnert moves. For $\beta=-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].:
if $\alpha$ is a partition, then
$\operatorname{KG}[\alpha](X;\beta)=x^{\alpha}$; otherwise, if $\alpha$ and
$i$ are such that $\alpha_{i}<\alpha_{i+1}$, then

$\displaystyle\operatorname{KG}[s_{i}(\alpha)](X;\beta)=\partial_{i}\big{(}(x_{i}+\beta
x_{i}x_{i+1})\operatorname{KG}[\alpha](X;\beta)\big{)}.$

  * •

The reduced key $\beta$-Grothendieck polynomials
${\widehat{\operatorname{KG}}}[\alpha](X;\beta)$ are defined recursively as
follows: if $\alpha$ is a partition, then
${\widehat{\operatorname{KG}}}[\alpha](X;\beta)=x^{\alpha}$; otherwise, if
$\alpha$ and $i$ are such that $\alpha_{i}<\alpha_{i+1}$, then

$\displaystyle{\widehat{\operatorname{KG}}}[s_{i}(\alpha)](X;\beta)=(x_{i+1}+\beta
x_{i}x_{i+1})\partial_{i}\big{(}{\widehat{\operatorname{KG}}}[\alpha](X;\beta)\big{)}.$

For brevity, we will write $\operatorname{KG}[\alpha](X)$ and
${\widehat{\operatorname{KG}}}[\alpha](X)$ instead of
$\operatorname{KG}[\alpha](X;\beta)$ and
${\widehat{\operatorname{KG}}}[\alpha](X;\beta)$.

######  Remark 4.2.

We can also introduce polynomials ${\cal Z}_{w}$, which are defined
recursively as follows: if $w=w_{0}$ is the longest element, then ${\cal
Z}_{w_{0}}(X)=x^{\delta_{n}}$; if $w$ and $i$ are such that $w_{i}>w_{i+1}$,
i.e., $l(ws_{i})=l(w)-1$, then

$\displaystyle{\cal
Z}_{ws_{i}}(X)=\partial_{i}\big{(}(x_{i+1}+x_{i}x_{i+1}){\cal
Z}_{w}(X)\big{)}.$

However, one can show that

$\displaystyle{\cal Z}_{w}(x_{1},\dots,x_{n})=(x_{1}\cdots x_{n})^{n-1}{\cal
G}_{w_{0}ww_{0}}\big{(}x_{n}^{-1},\dots,x_{1}^{-1}\big{)}.$

######  Theorem 4.3.

The polynomials ${{\mathfrak{S}}}_{w}(X,Y)$, $K[\alpha](X)$,
$\widehat{K}[\alpha](X)$, ${\cal G}_{w}(X,Y)$, ${\cal H}_{w}(X,Y)$,
$\operatorname{KG}[\alpha](X)$ and $\widehat{\operatorname{KG}}[\alpha](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
${\cal{P}}_{n}$, and can be extracted from the Cauchy kernel associated with
the algebra ${\cal{P}}_{n}$ (or that ${\cal{P}}_{n,n}$).

We will use notation ${{\mathfrak{S}}}_{w}(X)$, ${\cal G}_{w}(X)$, …, for
polynomials ${{\mathfrak{S}}}_{w}(X,0)$, ${\cal G}_{w}(X,0)$, ….

######  Definition 4.4.

For each permutation $w\in{\mathbb{S}}_{n}$ the Di Francesco–Zinn-Justin
polynomials ${\cal{DZ}}_{w}(X)$ are defined recursively as follows: if $w$ is
the longest element in ${\mathbb{S}}_{n}$, then
${\cal{DZ}}_{w}(X)=R_{\delta_{n}}(X,0)$; otherwise, if $w$ and $i$ are such
that $w_{i}>w_{i+1}$, i.e., $l(ws_{i})=l(w)-1$, then

$\displaystyle{\cal{DZ}}_{ws_{i}}(X)=\big{(}(1+x_{i})\partial_{i}^{(x)}+\partial_{i}^{(x)}(x_{i+1}+x_{i}x_{i+1})\big{)}{\cal{DZ}}_{w}(X).$

######  Conjecture 4.5.

  1. $(1)$

Polynomials ${\cal{DZ}}_{w}(X)$ have nonnegative integer coefficients.

  2. $(2)$

For each permutation $w\in{\mathbb{S}}_{n}$ the polynomial ${\cal{DZ}}_{w}(X)$
is a linear combination of key polynomials $K[\alpha](X)$ with nonnegative
integer coefficients.

As for defi nition of the double Di Francesco–Zinn-Justin polynomials
${\cal{DZ}}_{w}(X,Y)$ they are well defined, but may have negative
coefficients.

Let $\beta$ and $\alpha$ be two parameters, consider divided difference
operator

$\displaystyle
T_{i}:=T_{i}^{\beta,\alpha}=-\beta+((\beta+\alpha)x_{i}+1+\beta\alpha
x_{i}x_{i+1})\partial_{i,i+1}.$

######  Definition 4.6.

Let $w\in{\mathbb{S}}_{n}$, define Hecke–Grothendieck polynomials
${\cal{KN}}_{w}^{\beta,\alpha}(X_{n})$ to be

$\displaystyle{\cal{KN}}_{w}^{(\beta,\alpha)}(X_{n}):=T_{w}^{\beta,\alpha}\big{(}x^{\delta_{n}}\big{)},$

where as before $x^{\delta_{n}}:=x_{1}^{n-1}x_{2}^{n-2}\cdots x_{n-1}$; if
$u\in{\mathbb{S}}_{n}$, then set

$\displaystyle T_{u}^{\beta,\alpha}:=T_{i_{1}}^{\beta,\alpha}\cdots
T_{i_{\ell}}^{\beta,\alpha},$

where $w=s_{i_{1}}\cdots s_{i_{\ell}}$ is any reduced decomposition of a
permutation taken.

More generally, let $\beta$, $\alpha$ and $\gamma$ be parameters, consider
divided difference operators

$\displaystyle
T_{i}:=T_{i}^{\beta,\alpha,\gamma}=-\beta+((\alpha+\beta+\gamma)x_{i}+\gamma
x_{i+1}+1$
$\displaystyle\hphantom{T_{i}:=T_{i}^{\beta,\alpha,\gamma}=}{}+(\beta+\gamma)(\alpha+\gamma)x_{i}x_{i+1})\partial_{i,i+1},\qquad
i=1,\ldots,n-1.$

For a permutation $w\in{\mathbb{S}}_{n}$ define polynomials

$\displaystyle{\cal{KN}}_{w}^{(\beta,\alpha,\gamma)}(X_{n}):=T_{i_{1}}^{\beta,\alpha,\gamma}\cdots
T_{i_{\ell}}^{\beta,\alpha,\gamma}\big{(}x^{\delta_{n}}\big{)},$

where $w=s_{i_{1}}\cdots s_{i_{\ell}}$ is any reduced decomposition of $w$.

######  Remark 4.7.

A few comments in order.

  1. $(a)$

The divided difference operators
$\big{\\{}T_{i}:=T_{i}^{(\beta,\alpha,\gamma)},\,i=1,\dots,n-1\big{\\}}$
satisfy the following relations

     * •

(Hecke relations)

$\displaystyle T_{i}^{2}=(\alpha-\beta)T_{i}+\alpha\beta,$

     * •

(Coxeter relations)

$\displaystyle
T_{i}T_{i+1}T_{i}=T_{i+1}T_{i}T_{i+1},T_{i}T_{j}=T_{j}T_{i},\qquad\text{if}\quad|i-j|\geq
2.$

Therefore the elements $T_{w}^{\beta,\alpha,\gamma}$ are well defined for any
$w\in{\mathbb{S}}_{n}$.

     * •

(Inversion)

$\displaystyle(1+xT_{i})^{-1}=\frac{1+(\alpha-\beta)x-xT_{i}}{(1-\beta
x)(1+\alpha x)}.$

  2. $(b)$

Polynomials ${\cal{KN}}_{w}^{(\beta,\alpha,\gamma)}$ constitute a common
generalization of

     * •

the $\beta$-Grothendieck polynomials, namely,
${\cal{G}}_{w}^{(\beta)}={\cal{KN}}_{w_{0}w^{-1}}^{(\beta,\alpha=0,\gamma=0)}$,

     * •

the Di Francesco–Zinn-Justin polynomials, namely,
${\cal{DZ}}_{w}={\cal{KN}}_{w}^{(\beta=\alpha=1,\gamma=0)}$,

     * •

the dual $\alpha$-Grothendieck polynomials, namely,
${\cal{KN}}_{w_{0}w^{-1}}^{(\beta=0,\alpha,\gamma=0)}={\cal{H}}_{w}^{\alpha}(X)$.

######  Proposition 4.8.

  * •

$($Duality$)$ Let $w\in{\mathbb{S}}_{n}$, $\ell=\ell(w)$ denotes its length,
then $(\alpha\beta\not=0)$

$\displaystyle{\cal{KN}}_{w}^{(\beta,\alpha)}(1)=(\beta\alpha)^{\ell}{\cal{KN}}_{{w^{-1}}}^{(\alpha^{-1},\beta^{-1})}(1).$

  * •

$($Stability$)$ Let $w\in\mathbb{S}_{n}$ be a permutation and
$w=s_{i_{1}}s_{i_{2}}\cdots s_{i_{\ell}}$ be any its reduced decomposition.
Assume that $i_{a}\leq n-3$, $\forall\,1\leq a\leq\ell$, and define
permutation $\widetilde{w}:=s_{i_{1}+1}s_{i_{2}+1}\cdots
s_{i_{\ell}+1}\in\mathbb{S}_{n}$. Then

$\displaystyle{\cal{KN}}_{w}^{(\beta,\alpha)}(1)={\cal{KN}}_{\widetilde{w}}^{(\beta,\alpha)}(1).$

It is well-known that

  * •

the number ${\cal{KN}}_{w_{0}}^{(\beta=1,\alpha=1)}(1)$ is equal to the degree
of the variety of pairs commuting matrices of size $n\times n$ [13, 30].

  * •

the bidegree of the affine homogeneous variety $V_{w}$, $w\in{\mathbb{S}}_{n}$
[12] is equal to

$\displaystyle A^{{n\choose 2}-\ell(w)}B^{{n\choose
2}+\ell(w)}{\cal{KN}}_{w}^{(\beta=\alpha=A/B)}(1),$

see [9, 12, 30] for more details and applications.

######  Conjecture 4.9.

  * •

Polynomials ${\cal{KN}}_{w}^{(\beta,\alpha,\gamma)}(X)$ have nonnegative
integer coefficients

$\displaystyle{\cal{KN}}_{w}^{(\beta,\alpha,\gamma)}(X)\in\mathbb{N}[\beta,\alpha,\gamma][X_{n}].$

  * •

Polynomials ${\cal{KN}}_{w}^{(\beta,\alpha,\gamma)}(x_{1}=1,\,\forall\,i)$
have nonnegative integer coefficients

$\displaystyle{\cal{KN}}_{w}^{(\beta,\alpha,\gamma)}(x_{i}=1,\forall
i)\in\mathbb{N}[\beta,\alpha,\gamma].$

  * •

Double polynomials

$\displaystyle{\cal{KN}}_{w}^{(\beta=0,\alpha,\gamma)}(X,Y)=T_{w}^{\beta=0,\alpha,\gamma}(x)\prod_{i+j\leq
n+1\atop i\geq 1,\,j\geq 1}(x_{i}+y_{j})$

are well defined and have nonnegative integer coefficients151515Note that the
assumption $\beta=0$ is necessary..

  * •

Consider permutation $w=[n,1,2,\dots,n-1]\in\mathbb{S}_{n}$. Clearly
$w=s_{n-1}s_{n-2}\cdots s_{2}s_{1}$. The number
${\cal{KN}}_{w}^{(\beta=1,\alpha=1,\gamma=0)}(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
${\cal{KN}}_{w}^{(\beta,\alpha=0)}(1)$ counts the number of dissections of a
convex $(n+1)$-gon according the number of diagonals involved, where as the
polynomial ${\cal{KN}}_{w}^{(\beta,\alpha)}(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.

  1. $(a)$

One can consider more general family of polynomials
${\cal{KN}}_{w}^{(a,b,c,d)}(X_{n})$ by the use of the divided difference
operators
$T_{i}^{a,b,c,d}:=-b+((b+d)x_{i}+cx_{i+1}+1+d(b+c)x_{i}x_{i+1})\partial_{i,i+1}^{x}$
instead of that $T_{i}^{\beta,\alpha,\gamma}$. However the polynomials
${\cal{KN}}_{w}^{(a,b,c,d)}(1)\in\mathbb{Z}[a,b,c,d]$ may have negative
coefficients in general. Conjecturally, to ensure the positivity of
polynomials ${\cal{KN}}_{w}^{(a,b,c,d)}(X_{n})$, it is necessary take
$d:=a+c+r$. In this case we state conjecture

$\displaystyle{\cal{KN}}_{w}^{(a,b,c,a+c+r)}(X_{n})\in\mathbb{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
${\cal{KN}}_{w}^{(a,b,c,a+c+r)}(1)$ in the case $r\not=0$ is missed for the
author.

  2. $(b)$

If $\gamma\not=0$, the polynomials
${\cal{KN}}_{w}^{(\beta,\alpha,\gamma)}(X_{n})\in\mathbb{Z}[\alpha,\beta,\gamma][X_{n}]$
may have negative coefficients in general.

######  Theorem 4.10.

Let $T$ be a semistandard tableau and $\alpha(T)$ be its bottom code, see
Definition 2.27. Then

$\displaystyle{\cal
K}_{T}(X)=K[\alpha(T)](X),\qquad{\cal{KG}}_{T}(X)=\operatorname{KG}[\alpha(T)](X).$

Let $\alpha=(\alpha_{1}\leq\alpha_{2}\leq\cdots\leq\alpha_{r})$ be a
composition, define partition
$\alpha^{+}=(\alpha_{r}\geq\cdots\geq\alpha_{1})$.

######  Proposition 4.11.

If $\alpha=(\alpha_{1}\leq\alpha_{2}\leq\cdots\leq\alpha_{r})$ is a
composition and $n\geq r$, then

$\displaystyle K[\alpha](X_{n})=s_{\alpha^{+}}(X_{r}).$

For example, $K[0,1,2,\dots,n-1]=\prod\limits_{1\leq i<j\leq n}(x_{i}+x_{j})$.
Note that ${\widehat{K}}[0,1,2,\dots,n-1]=\prod\limits_{i=2}^{n}x_{i}^{i-1}$.

######  Proposition 4.12.

If $\alpha=(\alpha_{1}\leq\alpha_{2}\leq\cdots\leq\alpha_{r})$ is a
composition and $n\geq r$, then

$\displaystyle\operatorname{KG}[\alpha](X_{n})={\cal G}[{\alpha^{+}}](X_{r}).$

For example, $\operatorname{KG}[0,1,2,\dots,n-1]=\prod\limits_{1\leq i<j\leq
n}(x_{i}+x_{j}+x_{i}x_{j})$. Note that

$\displaystyle{\widehat{\operatorname{KG}}}[0,1,2,\dots,n-1]=\prod_{i=2}^{n}x_{i}^{i-1}\prod_{i=1}^{n-1}(1+x_{i})^{n-i}.$

######  Definition 4.13.

Define degenerate affine $2D$ nil-Coxeter algebra ${\cal{ANC}}_{n}^{(2)}$ to
be an associative algebra over $\mathbb{Q}$ generated by the set of elements
$\\{\\{u_{i,j}\\}_{1\leq i<j\leq n},\,x_{1},\ldots,x_{n}\\}$ subject to the
set of relations

  * •

$x_{i}x_{j}=x_{j}x_{i}$ for all $i\not=j$, $x_{i}u_{j,k}=u_{j,k}x_{i}$, if
$i\not=j,k$,

  * •

$u_{i,j}u_{k,l}=u_{k,l}u_{i,j}$, if $i$, $j$, $k$, $l$ are pairwise distinct,

  * •

($2D$-Coxeter relations) $u_{i,j}u_{j,k}u_{i,j}=u_{j,k}u_{i,j}u_{j,k}$, if
$1\leq i<j<k\leq n$,

  * •

$x_{i}u_{i,j}=u_{i,j}x_{j}+1$, $x_{j}u_{i,j}=u_{i,j}x_{i}-1$.

Now for a set of parameters161616By definition, a parameter is assumed to be
belongs to the center of the algebra in question. $A:=(a,b,c,h,e)$ define
elements

$\displaystyle T_{ij}:=a+(bx_{i}+cx_{j}+h+ex_{i}x_{j})u_{i,j},\qquad i<j.$

Throughout the present paper we set $T_{i}:=T_{i,i+1}$.

######  Lemma 4.14.

  1. $(1)$

$T_{i,j}^{2}=(2a+b-c)T_{i,j}-a(a+b-c)$, if $a=0$, then
$T_{ij}^{2}=(b-c)T_{ij}$.

  2. $(2)$

$2D$-Coxeter relations $T_{i,j}T_{j,k}T_{i,j}=T_{j,k}T_{i,j}T_{j,k}$ are
valid, if and only if the following relation among parameters $a$, $b$, $c$,
$e$, $h$ holds171717The relation (4.1) between parameters $a$, $b$, $c$, $e$,
$h$ defines a rational four-dimensional hypersurface. Its open chart
$\\{eh\not=0\\}$ contains, for example, the following set (cf. [41]):
$\\{a=p_{1}p_{4}-p_{2}p_{3},\,b=p_{2}p_{3},\,c=p_{1}p_{4},\,e=p_{1}p_{3}$,
$h=p_{2}p_{4}\\}$, where $(p_{1},p_{2},p_{3},p_{4})$ are arbitrary parameters.
However the points $(-b,a+b+c,c,1,(a+c)(b+c)$, $(a,b,c)\in\mathbb{N}^{3}\\}$
do not belong to this set.

$\displaystyle(a+b)(a-c)+he=0.$ (4.2)

  3. $(3)$

Yang–Baxter relations $T_{i,j}T_{i,k}T_{j.k}=T_{j,k}T_{i,k}T_{i,j}$ are valid
if and only if $b=c=e=0$, i.e., $T_{ij}=a+du_{ij}$.

  4. $(4)$

$T_{ij}^{2}=1$ if and only if $a=\pm 1$, $c=b\pm 2$, $he=(b\pm 1)^{2}$.

  5. $(5)$

Assume that parameters $a$, $b$, $c$, $h$, $e$ satisfy the conditions (4.2)
and that $bc+1=he$. Then

$\displaystyle T_{ij}x_{i}T_{ij}=(he-
bc)x_{j}+(h+(a+b)(x_{i}+x_{j})+ex_{i}x_{j})T_{ij}.$

Some special cases

  * •

$($representation of affine modified Hecke algebra [71]) if $A=(a,-a,c,h,0)$,
then $T_{ij}x_{i}T_{ij}$ $=acx_{j}+hT_{ij}$, $i<j$,

  * •

if $A=(-a,a+b+c,c,1,(a+c)(b+c)$, then

$\displaystyle
T_{ij}x_{i}T_{ij}=abx_{j}+(1+(b+c)(x_{i}+x_{j})+(a+c)(b+c)x_{i}x_{j})T_{ij}.$

  1. $(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 $\beta:=2a+b-c\not=0$. Then $($cf. [24, 44] and the
literature quoted therein$)$ the elements
$R_{ij}(u,v):=1+\frac{\lambda-\mu}{\beta\mu}T_{ij}$ satisfy the twisted
quantum Yang–Baxter relations

$\displaystyle
R_{ij}(\lambda_{i},\mu_{j})R_{jk}(\lambda_{i},\nu_{k})R_{ij}(\mu_{j},\nu_{k})=R_{jk}(\mu_{j},\nu_{k})R_{ij}(\lambda_{i},\nu_{k})R_{jk}(\lambda_{i},\mu_{j}),\qquad
i<j<k,$

where $\\{\lambda_{i},\mu_{i},\nu_{i}\\}_{1\leq i\leq n}$ are parameters.

######  Corollary 4.15.

If $(a+b)(a-c)+he=0$, then for any permutation $w\in{\mathbb{S}}_{n}$ the
element

$\displaystyle T_{w}:=T_{i_{1}}\cdots T_{i_{l}}\in{\cal{ANC}}_{n}^{(2)},$

where $w=s_{i_{1}}\cdots s_{i_{l}}$ is any reduced decomposition of $w$, is
well-defined.

######  Example 4.16.

  * •

Each of the set of elements

$\displaystyle s_{i}^{(h)}=1+(x_{i+1}-x_{i}+h)u_{i,i+1}\qquad\text{and}$
$\displaystyle
t_{i}^{(h)}=-1+(x_{i}-x_{i+1}+h(1+x_{i})(1+x_{i+1}))u_{ij},\qquad
i=1,\ldots,n-1,$

by itself generate the symmetric group ${\mathbb{S}}_{n}$.

  * •

If one adds the affine elements $s_{0}^{(h)}:=\pi s_{n-1}^{(h)}\pi^{-1}$ and
$t_{0}^{(h)}:=\pi t_{n-1}^{(h)}\pi^{-1}$, then each of the set of elements
$\big{\\{}s_{j}^{(h)},\,j\in\mathbb{Z}/n\mathbb{Z}\big{\\}}$ and
$\big{\\{}t_{j}^{(h)},\,j\in\mathbb{Z}/n\mathbb{Z}\big{\\}}$ by itself
generate the affine symmetric group ${\mathbb{S}}_{n}^{\text{af\/f}}$, see
(4.3) for a definition of the transformation $\pi$.

  * •

It seems an interesting problem to classify all rational, trigonometric and
elliptic divided difference operators satisfying the Coxeter relations. A
general divided difference operator 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_{j}^{(h)}$,
$j\in\mathbb{Z}/n\mathbb{Z}$. For example, take parameters $a$ and $b$, define
secondary divided difference operator

$\displaystyle\partial_{xy}^{[a,b]}:=-1+(b+y-x)\partial_{xy}^{[a]},$

where

$\displaystyle\partial_{xy}^{[a]}:=\frac{1-{{\overline{s}}_{xy}^{(a)}}}{a-x+y},\qquad{\overline{s}}_{xy}^{(a)}:=-1+(a+x-y)\partial_{xy}.$

Observe that the set of operators
$\big{\\{}s_{i}^{[a,b]}:=s_{x_{i},x_{i+1}}^{[a,b]},\,i\in\mathbb{Z}/n\mathbb{Z}\big{\\}}$
gives rise to a rational representation of the affine symmetric group
${\mathbb{S}}_{n}^{\text{af\/f}}$ on the field of rational functions
$\mathbb{Z}[a,b](X_{n})$. In the special case $a:=A$, $b:=A/h$, $h:=1-\beta/2$
the operators $s_{i}^{[a,b]}$ coincide with operators $\Theta_{i}$,
$i\in\mathbb{Z}/n\mathbb{Z}$ have been introduced in [31, equation (4.17)].

Let $A=(a,b,c,h,e)$ be a sequence of integers satisfying the conditions (4.1).
Denote by $\partial_{i}^{A}$ the divided difference operator

$\displaystyle\partial_{i}^{A}=a+(bx_{i}+cx_{i+1}+h+ex_{i}x_{i+1})\partial_{i},\qquad
i=1,\ldots,n-1.$

It follows from Lemma 4.14 that the operators
$\big{\\{}\partial_{i}^{A}\big{\\}}_{1\leq i\leq n}$ satisfy the Coxeter
relations

$\displaystyle\partial_{i}^{A}\partial_{i+1}^{A}\partial_{i}^{A}=\partial_{i+1}^{A}\partial_{i}^{A}\partial_{i+1}^{A},\qquad
i=1,\ldots,n-1.$

######  Definition 4.17.

  1. (1)

Let $w\in\mathbb{S}_{n}$ be a permutation. Define the generalized Schubert
polynomial corresponding to permutation $w$ as follows

$\displaystyle\mathfrak{S}_{w}^{A}(X_{n})=\partial_{w^{-1}w_{0}}^{A}x^{\delta_{n}},\qquad
x^{\delta_{n}}:=x_{1}^{n-1}x_{2}^{n-2}\cdots x_{n-1},$

and $w_{0}$ denotes the longest element in the symmetric group
$\mathbb{S}_{n}$.

  2. (2)

Let $\alpha$ be a composition with at most $n$ parts, denote by
$w_{\alpha}\in\mathbb{S}_{n}$ the permutation such that
$w_{\alpha}(\alpha)=\alpha^{+}$. Let us recall that $\alpha^{+}$ denotes a
unique partition corresponding to composition $\alpha$.

######  Lemma 4.18.

Let $w\in\mathbb{S}_{n}$ be a permutation.

  * •

If $A=(0,0,0,1,0)$, then $\mathfrak{S}_{w}^{A}(X_{n})$ is equal to the
Schubert polynomial $\mathfrak{S}_{w}(X_{n})$.

  * •

If $A=(-\beta,\beta,0,1,0)$, then $\mathfrak{S}_{w}^{A}(X_{n})$ is equal to
the $\beta$-Grothendieck polynomial $\mathfrak{G}_{w}^{({\beta})}(X_{n})$
introduced in [17].

  * •

If $A=(0,\beta,0,1,0)$ then $\mathfrak{S}_{w}^{A}(X_{n})$ is equal to the dual
$\beta$-Grothendieck polynomial ${\cal{H}}_{w}^{(\beta)}(X_{n})$, studied in
depth for $\beta=-1$ and in the basis $\\{x_{i}:=\exp(\xi_{l})\\}$ in [39].

  * •

If $A=(-1,2,0,1,1)$, then $\mathfrak{S}_{w}^{A}(X_{n})$ is equal to the Di
Francesco–Zinn-Justin polynomials introduced in [12].

  * •

If $A=(1,-1,1,h,0)$, then $\mathfrak{S}_{w}^{A}(X_{n})$ is equal to the
$h$-Schubert polynomials.

In all cases listed above the polynomials $\mathfrak{S}_{w}^{A}(X_{n})$ have
non-negative integer coefficients.

Define the generalized key or Demazure polynomial corresponding to a
composition $\alpha$ as follows

$\displaystyle K_{\alpha}^{A}(X_{n})=\partial_{w_{\alpha}}^{A}x^{\alpha^{+}}.$

  * •

If $A=(1,0,1,0,0)$, then $K_{\alpha}^{A}(X_{n})$ is equal to key (or Demazure)
polynomial corresponding to $\alpha$.

  * •

If $A=(0,0,1,0,0)$, then $K_{\alpha}^{A}(X_{n})$ is equal to the reduced key
polynomial.

  * •

If $A=(1{,}0{,}1{,}0{,}\beta)$, then $K_{\alpha}^{A}(X_{n})$ is equal to the
key $\beta$-Grothendieck polynomial
$\operatorname{KG}_{\alpha}^{(\beta)}\\!(X_{n})$.

  * •

If $A=(0,0,1,0,\beta)$, then $K_{\alpha}^{A}(X_{n})$ is equal to the reduced
key $\beta$-Grothendieck polynomials.

In all cases listed above the polynomials $\mathfrak{S}_{w}^{A}(X_{n})$ have
non-negative integer coefficients.

  * •

If $A=(-1,q^{-1},-1,0,0)$ and $\lambda$ is a partition, then (up to a scalar
factor) polynomial $K_{\lambda}^{A}(X_{n})$ can be identify with a certain
Whittaker function (of type $A$), see [7, Theorem A]. Note that operator
$T_{i}^{A}:=-1+(q^{-1}x_{i}-x_{i+1})\partial_{i}$, $1\leq i\leq n-1$, satisfy
the Coxeter and Hecke relations, namely
$(T_{i}^{A})^{2}=(q^{-1}-1)T_{i}^{A}+q^{-1}$. In [7] the operator $T_{i}^{A}$
has been denoted by ${\mathfrak{T}}_{i}$.

  * •

Let $w\in{\mathbb{S}}_{n}$ be a permutation and
$\mathfrak{m}=(i_{1},\ldots,i_{\ell})$ be a reduced word for $w$, i.e.,
$w=s_{i_{1}}\cdots s_{i_{\ell}}$ and $\ell(w)=\ell$. Denote by
$Z_{\mathfrak{m}}$ the Bott–Samelson nonsingular variety corresponding to the
reduced word $\mathfrak{m}$. It is well-known that the Bott–Samelson variety
$Z_{\mathfrak{m}}$ is birationally isomorphic to the Schubert variety $X_{w}$
associated with permutation $w$, i.e., the Bott–Samelson variety
$Z_{\mathfrak{m}}$ is a desingularization of the Schubert variety $X_{w}$.
Following [7] define the Bott–Samelson polynomials
$Z_{\mathfrak{m}}(x,\lambda,v)$ as follows

$\displaystyle
Z_{\mathfrak{m}}(x,\lambda,v)=\big{(}1+T_{i_{1}}^{A}\big{)}\cdots\big{(}1+T_{i_{\ell}}^{A}\big{)}x^{\lambda},$

where $A=(-v,-1,1,0)$. Note that
$\big{(}1+T_{i}^{A}\big{)}^{2}=(1+v)\big{(}1+T_{i}^{A}\big{)}$, and the
divided difference operators $1+T_{i}^{A}=1+v+(x_{i+1}-vx_{i})\partial_{i}$ do
not satisfy the Coxeter relations.

  * •

If $A=(-\beta,\beta+\alpha,0,1,\beta\alpha)$, then
${\mathfrak{S}}_{w}^{A}(X_{n})$ constitutes a common generalization of the
$\beta$-Grothendieck and the Di Francesco–Zinn-Justin polynomials.

  * •

If $A=(t,-1,t,1,0)$, then the divided difference operators

$\displaystyle T_{i}^{A}:=t+(-x_{i}+tx_{i+1}+1)\partial_{i},\qquad 1\leq i\leq
n-1,$

their baxterizations and the raising operator

$\displaystyle\phi:=(x_{n}-1)\pi,$

where $\pi$ denotes the $q^{-1}$-shift operator, namely
$\pi(x_{1},\ldots,x_{n})=(x_{n}/q,x_{1},\ldots,x_{n-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 $\phi$, operators

$\displaystyle
T_{i}^{\beta,\alpha,\gamma,h}:=-\beta+((\alpha+\beta+\gamma)x_{i}+\gamma
x_{i+1}+h$
$\displaystyle\hphantom{T_{i}^{\beta,\alpha,\gamma,h}:=}{}+h^{-1}(\alpha+\gamma)(\beta+\gamma)x_{i}x_{i+1})\partial_{i},\qquad
1\leq i\leq n-1,$

and their baxterization, one (A.K.) can introduce polynomials
$M_{\delta}^{\beta,\alpha,\gamma,q}(X_{n})$, where $\delta$ is a composition.
These polynomials are common generalizations of the interpolation Macdonald
polynomials $M_{\delta}(X_{n};q,t)$ (the case $\beta=-t$, $\alpha=-1$,
$\gamma=t$), as well as the Schubert, $\beta$-Grothendieck and its dual,
Demazure and Di Francesco–Zinn-Justin polynomials, and conjecturally their
affine analogues/versions. Details will appear elsewhere.

Double affine nilCoxeter algebra. Let $t$, $q$, $a$, $b$, $c$, $h$, $d$ be
parameters.

######  Definition 4.19.

Define double affine nil-Coxeter algebra $\operatorname{DANC}_{n}$ to be
(unital) associative algebra over $\mathbb{Q}\big{(}q^{\pm 1},t^{\pm
1}\big{)}$ with the set of generators
$\big{\\{}e_{1},\ldots,e_{n-1},x_{1},\ldots,x_{n},\pi^{\pm 1}\big{\\}}$
subject to relations

  * •

(nilCoxeter relations)

$\displaystyle e_{i}e_{j}=e_{j}e_{i},\quad\text{if}\quad|i-j|\geq 2,\qquad
e_{i}^{2}=0,\quad\forall\,i,\qquad
e_{i}e_{j}e_{i}=e_{j}e_{i}e_{j},\quad\text{if}\quad|i-j|=1;$

  * •

(crossing relations)

$\displaystyle x_{i}e_{k}=e_{k}x_{i},\quad\text{if}\quad k\not=i,i+1,\qquad
x_{i}e_{i}-e_{i}x_{i+1}=1,\qquad e_{i}x_{i}-x_{i+1}e_{i}=1;$

  * •

(affine crossing relations)

$\displaystyle\pi x_{i}=x_{i+1}\pi,\quad\text{if}\quad i<n,\qquad\pi
x_{n}=q^{-1}x_{1}\pi,$ $\displaystyle\pi e_{i}=e_{i+1}\pi,\quad\text{if}\quad
i<n-1,\qquad\pi^{2}e_{n-1}=qe_{1}\pi^{2}.$

Now let us introduce elements $e_{0}:=\pi e_{n-1}\pi^{-1}$ and

$\displaystyle T_{0}:=T_{0}^{a,b,c,h,d}=\pi
T_{n-1}\pi^{-1}=a+\big{(}bx_{n}+q^{-1}cx_{1}+h+q^{-1}dx_{1}x_{n}\big{)}e_{0}.$

It is easy to see that $\pi e_{0}=qe_{1}\pi$,

$\displaystyle\pi
T_{0}^{a,b,c,h,d}=T_{1}^{a,b,c,qh,q^{-1}d}e_{1}\pi=T_{1}^{a,b,c,h,d}+\big{(}(1-q)h+\big{(}1-q^{-1}\big{)}dx_{1}x_{2}\big{)}e_{1}.$

Now let us assume that $a=t$, $b=-t$, $d=e=0$, $c=1$. Then,

$\displaystyle T_{i}=t+(x_{i+1}-tx_{i})e_{i},\quad i=1,\ldots,n-1,\qquad
T_{0}=t+\big{(}q^{-1}x_{1}-tx_{n}\big{)}e_{0},$ $\displaystyle
T_{i}^{2}=(t-1)T+t,\quad 0\leq i<n,\qquad T_{i}x_{i}T_{i}=tx_{i+1},\quad 1\leq
i<n,\qquad T_{0}x_{n}T_{0}=tq^{-1}x_{1},$ $\displaystyle
T_{0}T_{1}T_{0}=T_{1}T_{0}T_{1},\qquad
T_{n-1}T_{0}T_{n-1}=T_{0}T_{n-1}T_{0},\qquad
T_{0}T_{i}=T_{i}T_{0},\qquad\text{if}\quad 2\leq i<n-1.$

The operators $T_{i}:=T_{i}^{t,-t,1,0,0}$, $0\leq i\leq n-1$ have been used in
[45] to give an “elementary” construction of nonsymmetric Macdonald
polynomials. Indeed, one can realize the operator $\pi$ as follows:

$\displaystyle\pi(f)=f(x_{n}/q,x_{1},x_{2},\ldots,x_{n-1}),\qquad\text{so
that}\quad\pi^{-1}(f)=(x_{2},\ldots,x_{n},qx_{1}),$ (4.3)

and introduce the raising operator [45] to be

$\displaystyle\phi(f(X_{n}))=(x_{n}-1)\pi(f(X_{n})).$

It is easily seen that $\phi T_{i}=T_{i+1}\phi$, $i=0,\dots,n-2$, and
$\phi^{2}T_{n-1}=T_{1}\phi^{2}$. It has been established in [45] how to use
the operators $\phi$, $T_{1},\ldots,T_{n-1}$ to to give formulas for the
interpolation Macdonald polynomials. Using operators
$\phi,T_{i}^{(a,b,c,h,d)},i=1,\ldots,n-1$ instead of $\phi$,
$T_{1},\ldots,T_{n-1}$, $1\leq i\leq 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],

$\displaystyle
Y_{i}:=\left(\prod_{a=i-1}^{1}T_{a}^{-1}\right)\pi\left(\prod_{a=n-1}^{i+1}T_{a}\right),\qquad
i=1,\ldots,n,$

where $T_{i}=T_{i}^{t,-t,1,0,0}$, generate a commutative subalgebra in the
double affine nilCoxeter algebra $\operatorname{DANC}_{n}$. Note that the
algebra $DANC_{n}$ 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 operators $T_{i}^{t,-t,1,h,e}$, $i=0,\dots,n-1$ in a way similar to
that given in [45]. We expect that these polynomials provide an affine version
of polynomials ${\cal{KN}}_{w}^{(-t,-1,1,1,0)}(X)$,
$w\in{\mathbb{S}}_{n}\subset{\mathbb{S}}_{n}^{\text{af\/f}}$, see Remark 4.7.

Note that for any affine permutation $v\in{\mathbb{S}}_{n}^{\text{af\/f}}$,
the operator

$\displaystyle T_{v}^{(a,b,c,h,d)}=T_{i_{1}}^{(a,b,c,h,d)}\cdots
T_{i_{\ell}}^{(a,b,c,h,d)},$

where $v=s_{i_{1}}\cdots s_{i_{\ell}}$ is any reduced decomposition of $v$, is
well-defined up to the sign $\pm 1$. It seems an interesting problem to
investigate properties of polynomials $L_{v}[\alpha](X_{n})$, where
$v\in{\mathbb{S}}_{n}^{\text{af\/f}}$ and $\alpha\in\mathbb{Z}_{\geq 0}^{n}$,
and find its algebro-geometric interpretations.

##  5 Cauchy kernel

Let $u_{1},u_{2},\dots,u_{n-1}$ be a set of generators of the free algebra
${\cal F}_{n-1}$, which are assumed also to be commute with the all variables
${\mathfrak{P}}_{n}:=\\{p_{i,j},\,2\leq i+j\leq n+1,\,i\geq 1,j\geq 1\\}$.

######  Definition 5.1.

The Cauchy kernel ${\cal C}({\mathfrak{P}}_{n},U)$ is defined to be as the
ordered product

$\displaystyle{\cal
C}({\mathfrak{P}}_{n},U)=\prod_{i=1}^{n-1}\left\\{{\prod_{j=n-1}^{i}(1+p_{i,j-i+1}u_{j})}\right\\}.$
(5.1)

For example,

$\displaystyle{\cal
C}({\mathfrak{P}}_{4},U)=(1+p_{1,3}u_{3})(1+p_{1,2}u_{2})(1+p_{1,1}u_{1})(1+p_{2,2}u_{3})(1+p_{2,1}u_{2})(1+p_{3,1}u_{3}).$

In the case $\\{p_{ij}=x_{i},\,\forall\,j\\}$ we will write
${\cal{C}}_{n}(X,U)$ instead of ${\cal C}({\mathfrak{P}}_{n},U)$.

######  Lemma 5.2.

$\displaystyle{\cal C}({\mathfrak{P}}_{n},U)=\sum_{({\bf a},{\bf b})\in{\cal
S}_{n}}\prod_{j=1}^{p}p_{\\{{a_{j},b_{j}\\}}}w({\bf a},{\bf b}),$ (5.2)

where ${\bf a}=(a_{1},\ldots,a_{p})$, ${\bf b}=(b_{1},\ldots,b_{p})$, $w({\bf
a},{\bf b})=\prod\limits_{j=1}^{p}u_{a_{j}+b_{j}-1}$, and the sum in (5.2)
runs over the set

$\displaystyle{\cal S}_{n}:=\big{\\{}({\bf a},{\bf
b})\in\mathbb{N}^{p}\times\mathbb{N}^{p}\,|\,{\bf a}=(a_{1}\leq
a_{2}\leq\cdots\leq a_{p}),$ $\displaystyle\hphantom{{\cal S}_{n}:=\\{({\bf
a},{\bf b})\in\mathbb{N}^{p}\times\mathbb{N}^{p}\,|\,}{}a_{i}+b_{i}\leq n,\
\text{and if}\ a_{i}=a_{i+1}\Longrightarrow b_{i}>b_{i+1}\big{\\}}.$

We denote by ${\cal S}_{n}^{(0)}$ the set $\\{({\bf a},{\bf b})\in{\cal
S}_{n}\,|\,w({\bf a},{\bf b})\ \text{is a tableau word}\\}$.

The number of terms in the r.h.s. of (5.1) is equal to $2^{{n\choose 2}}$, and
therefore is equal to the number $\\#|\operatorname{STY}(\delta_{n},\leq n)|$
of semistandard Young tableaux of the staircase shape $\delta_{n}:=(n-1$,
$n-2,\ldots,2,1)$ filled by the numbers from the set $\\{1,2,\ldots,n\\}$. It
is also easily seen that the all terms appearing in the r.h.s. of (5.2) are
different, and thus $\\#|{\cal S}_{n}|=\\#|\operatorname{STY}(\delta_{n},\leq
n)|$.

We are interested in the decompositions of the Cauchy kernel ${\cal
C}({\mathfrak{P}}_{n},U)$ in the algebras ${\cal P}_{n}$, ${\cal NP}_{n}$,
${\cal IP}_{n}$, ${\cal NC}_{n}$ and ${\cal IC}_{n}$.

###  5.1 Plactic algebra $\boldsymbol{{\cal P}_{n}}$

Let $\lambda$ be a partition and $\alpha$ be a composition of the same size.
Denote by ${\widetilde{\operatorname{STY}}}(\lambda,\alpha)$ the set of
semistandard Young tableaux $T$ of the shape $\lambda$ and content $\alpha$
which must satisfy the following conditions: for each $k=1,2,\dots$, 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\in{\widetilde{\operatorname{STY}}}(\lambda,\alpha)$ have to satisfy the
following conditions: $T_{i,j}\geq j$.

For a given (semi-standard) Young tableau $T$ let us denote by $R_{i}(T)$ the
set of numbers placed in the $i$-th row of $T$, and denote by
${\widetilde{\operatorname{STY}}}_{0}(\lambda,\alpha)$ the subset of the set
${\widetilde{\operatorname{STY}}}(\lambda,\alpha)$ involving only tableaux $T$
which satisfy the following constrains

$\displaystyle R_{1}(T)\supset R_{2}(T)\supset R_{3}(T)\supset\cdots.$

To continue, let us denote by ${\cal A}_{n}$ (respectively by ${\cal
A}^{(0)}_{n}$) the union of the sets
${\widetilde{\operatorname{STY}}}(\lambda,\alpha)$ (resp. that of
${\widetilde{\operatorname{STY}}}_{0}(\lambda,\alpha)$) for all partitions
$\lambda$ such that $\lambda_{i}\leq n-i$ for $i=1,2,\dots,n-1$, and all
compositions $\alpha$, $l(\alpha)\leq n-1$. Finally, denote by ${\cal
A}_{n}(\lambda)$ (resp. ${\cal A}^{(0)}_{n}(\lambda)$) the subset of ${\cal
A}_{n}$ (resp. ${\cal A}^{(0)}_{n}(\lambda)$) consisting of all tableaux of
the shape $\lambda$.

######  Lemma 5.3.

  * •

$|{\cal A}_{n}(\delta_{n})|=1$, $|{\cal A}_{n}(\delta_{n-1})|=(n-1)!$, $|{\cal
A}_{n}((n-1))|=C_{n-1}$ the $(n-1)$-th Catalan number. More generally,

$\displaystyle\big{|}{\cal
A}_{n}\big{(}\big{(}1^{k}\big{)}\big{)}\big{|}={n-1\choose k},\qquad|{\cal
A}_{n}((k))|=\frac{n-k}{n}{n+k-1\choose
k}=\dim{\mathbb{S}}_{n+k-1}^{(n-1,k)},$

$k=1\dots,n-1$, cf. [67, $A009766$]; here $\dim{\mathbb{S}}_{n}^{\lambda}$
stands for the dimension of the irreducible representation of the symmetric
group ${\mathbb{S}}_{n}$ corresponding to a partition $\lambda\vdash n$.

  * •

Let $k\geq\ell\geq 2$, $n\geq k+2$, then

$\displaystyle|{\cal
A}_{n}((k,\ell))|=\frac{(n-k)(n-\ell+1)(k-\ell+1)(n^{2}-n-\ell(k+1))}{\ell!(k+1)k(n+k)}{n+k\choose
k-1}\prod_{i=1}^{\ell-2}(n+i),$

$k=1,\ldots,n$. The case $k=\ell$ has been studied in [21] where one can find
a combinatorial interpretation of the numbers $|{\cal A}_{n}((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=\ell$ one has
$n^{2}-n-k(k+1)=(n+k)(n-k-1)$, and the above formula can be rewritten as
follows $(k\geq 2)$

$\displaystyle|{\cal
A}_{n}((k,k))|=\frac{(n-k-1)(n-k)(n-k-1)}{(k+1)k^{2}(k-1)}~{}{n+k-2\choose
k-2}~{}{n+k-1\choose k-1}.$

  * •

Boundary case: the number $|{\cal{A}}_{N}((n^{k}))|$ for $N=n+k$,181818So 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,\ldots,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
$1^{k}\times w_{0}^{(n)}\in{\mathbb{S}}_{n+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)\times(n+k)$ from a given
$k$-triangulation of a convex $n+k+1)$-gon.

$\displaystyle\big{|}{\cal{A}}_{k+n}\big{(}\big{(}n^{k}\big{)}\big{)}\big{|}=\big{|}{\cal{A}}_{k+n}\big{(}\big{(}(n+1)^{k}\big{)}\big{)}|=\det|\operatorname{Cat}_{n+i+j-1}|_{1\leq
i,j\leq k}=\\!\\!\prod_{1\leq i\leq j\leq n}\\!\\!\frac{i+j+2k}{i+j}.$

  * •

More generally $($A.K.$)$,

$\displaystyle\big{|}{\cal{A}}_{N}\big{(}\big{(}n^{k}\big{)}\big{)}|=\prod_{1\leq
i\leq k,\,1\leq j\leq n\atop j-i\leq n-k}\frac{N-i-j+1}{i+j-1}{\prod_{1\leq
i\leq k,\,1\leq j\leq n\atop j-i>n-k}\frac{N+i+j-1}{i+j-1}}.$

Moreover, the number $|{\cal{A}}_{N}((n^{k}))|$ 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)$.191919So 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].

  * •

There exists a bijection $\rho_{n}\colon{\cal
A}_{n}\longrightarrow\operatorname{ASM}(n)$ such that the image
$\operatorname{Im}\big{(}{\cal A}^{(0)}_{n}\big{)}$ contains the set of
$n\times n$ permutation matrices.

  * •

The number of row strict $($as well as column strict$)$ diagrams
$\lambda\subset\delta_{n+1}$ is equal to $2^{n}$.

Recall that a row-strict diagram202020Known also as a strict partition.
$\lambda$ is on such that $\lambda_{i}-\lambda_{i+1}\geq 1$, $\forall\,i$;
$\delta_{n}:=(n-1$, $n-2,\ldots,2,1)$.

######  Example 5.4.

Take $n=5$ so that $\operatorname{ASM}(5)=429$ and $\operatorname{Cat}(5)=42$.
One has

$\displaystyle\big{|}{\cal
A}^{(0)}_{5}\big{|}=\sum_{\lambda\subset\delta_{4}:=(4,3,2,1)\atop\lambda_{i}-\lambda_{i+1}\geq
1\,\forall\,i}\big{|}{\cal{A}}_{5}^{(0)}(\lambda)\big{|}=\big{|}{\cal
A}^{(0)}_{5}(\varnothing)\big{|}+\big{|}{\cal
A}^{(0)}_{5}((1))\big{|}+\big{|}{\cal A}^{(0)}_{5}((2))\big{|}+\big{|}{\cal
A}^{(0)}_{5}((3))\big{|}$ $\displaystyle\hphantom{\big{|}{\cal
A}^{(0)}_{5}\big{|}=}{}+\big{|}{\cal A}^{(0)}_{5}((2,1))\big{|}+\big{|}{\cal
A}^{(0)}_{5}((4))\big{|}+\big{|}{\cal A}^{(0)}_{5}((3,1))\big{|}+\big{|}{\cal
A}^{(0)}_{5}((3,2))\big{|}+\big{|}{\cal A}^{(0)}_{5}((4,1))\big{|}$
$\displaystyle\hphantom{\big{|}{\cal A}^{(0)}_{5}\big{|}=}{}+\big{|}{\cal
A}^{(0)}_{5}((4,2))\big{|}+\big{|}{\cal
A}^{(0)}_{5}((3,2,1))\big{|}+\big{|}{\cal
A}^{(0)}_{5}((4,3))\big{|}+\big{|}{\cal A}^{(0)}_{5}((4,2,1))\big{|}$
$\displaystyle\hphantom{\big{|}{\cal A}^{(0)}_{5}\big{|}=}{}+\big{|}{\cal
A}^{(0)}_{5}((4,3,1))\big{|}+\big{|}{\cal
A}^{(0)}_{5}((4,3,2))\big{|}+\big{|}{\cal A}^{(0)}_{5}((4,3,2,1))\big{|}$
$\displaystyle\hphantom{\big{|}{\cal
A}^{(0)}_{5}\big{|}}{}=1+4+9+14+6+14+16+4+21+14+4+1+9+2+1+1=121$
$\displaystyle\hphantom{\big{|}{\cal A}^{(0)}_{5}\big{|}=}{}\text{(sum of $16$
terms)},$ $\displaystyle\sum_{k=0}^{4}|{\cal A}_{5}((k))|=1+4+9+14+14=42.$

We expect that the image $\rho_{n}\big{(}\bigcup_{k=0}^{n-1}{\cal
A}_{n}((k))\big{)}$ coincides with the set of $n\times 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 ${\cal A}_{n}$.

######  Definition 5.5.

Let $\lambda$ be a partition, $\alpha$ be a composition of the same size. For
each tableau $T\in{\widetilde{\operatorname{STY}}}(\lambda,\alpha)\subset{\cal
A}_{n}(\lambda)$ define

$\displaystyle n(T)=\alpha_{n}=\\#|\\{(i,j)\in\lambda|T(i,j)=n\\}|.$

Clearly, $n(T)\leq\lambda_{1}$.

Define polynomials

$\displaystyle{\cal A}_{\lambda}(t):=\sum_{T\in{\cal
A}_{n}(\lambda)}t^{\lambda_{1}-n(T)}.$

It is instructive to display the numbers $\\{{\cal
A}_{n}(\lambda),\lambda\subset\delta_{n}\\}$ as a vector of the length equals
to the $n$-th Catalan number. For example,

$\displaystyle\begin{split}&{\cal
A}_{4}(\varnothing{,}(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))\\!\\\
&\qquad{}=(1,3,5,3,5,6,1,6,3,2,3,2,1,1).\end{split}$

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\times 2n\times 2n$
($\operatorname{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 $\\{{\cal A}_{n}(\lambda),\lambda\subset\delta_{n}\\}$ coincides
with the set of refined $\operatorname{TSSCPP}(n)$ numbers as defined in [12].
More precisely,

  * •

$|{\cal
A}_{n}(\lambda;N)|=\det\big{|}{N-i\choose\lambda^{\prime}_{j}-j+i}\big{|}_{1\leq
i,j\leq\ell(\lambda)}$,

  * •

we have

$\displaystyle{\cal
A}_{\lambda}(N;t):=\det\left|{N-i-1\choose\lambda^{\prime}_{j}-j+i-1}+t{N-i-1\choose\lambda^{\prime}_{j}-j+i}\right|_{1\leq
i,j\leq\ell(\lambda)},$

  * •

let $\lambda$ be a partition, $|\lambda|=n$, consider the column multi-Schur
polynomial and $t$-deformation thereof

$\displaystyle
s_{\lambda}^{*}(X_{N}):=\det|e_{\lambda^{\prime}_{j}-j+i}(X_{N-i})|_{1\leq
i,j\leq\ell(\lambda)},\qquad\text{cf. {\rm\cite[cite]{[\@@bibref{}{Ma}{}{},
Chapter~{}III]}, \cite[cite]{[\@@bibref{}{Wa}{}{}]}}},\quad\text{and}$
$\displaystyle
s_{\lambda}^{*}(X_{N};t):=\det|x_{N-i}e_{\lambda^{\prime}_{j}-j+i-1}(X_{N-i-1})+te_{\lambda^{\prime}_{j}-j+i}(X_{N-i-1})|_{1\leq
i,j\leq\ell(\lambda)},$

then, assuming that $\lambda\subset\delta_{n}$ and
$N\geq\lambda_{1}+\lambda^{\prime}_{\ell(\lambda)}$, the polynomial
$s_{\lambda}^{*}(X_{N})$ has nonnegative $($integer$)$ coefficients,

  * •

polynomial ${\cal A}_{\lambda}(t)$ is equal to a $t$-analog of refined
$\operatorname{TSSCPP}(n)$ numbers $P_{n}(\lambda^{\prime}_{n-1}+1,\dots$,
$\lambda^{\prime}_{n-i}+i,\dots,\lambda^{\prime}_{1}+n-1|t)$ introduced by
means of recurrence relations in [12, relation (3.5)],

  * •

one has

$\displaystyle
s_{((n^{k}))}^{*}(X_{n+k})=M_{n,k}(X_{n+k}){\mathfrak{S}}_{1^{k}\times
w_{0}^{(n)}}\big{(}x_{1}^{-1},\ldots,x_{k+n}^{-1}\big{)},$

where ${\mathfrak{S}}_{{1^{k}\times w_{0}^{(n)}}}(X_{n+k})$ denotes the
Schubert polynomial corresponding to the permutation

$\displaystyle 1^{k}\times w_{0}^{(n)}=[1,2,\ldots,k,n+k,n+k-1,\ldots,k+1],$

and
$M_{n,k}(X_{n+k})=\prod\limits_{a=1}^{k}x_{a}^{-1}\prod\limits_{a=1}^{n+k}~{}x_{a}^{\min(n+k-a+1,n)}$.

In particular, $\sum\limits_{\lambda\subset\delta_{n}}{\cal
A}_{\lambda}(t)=\sum\limits_{1\leq j\leq n-1}A_{n,j}t^{j-1}$, where $A_{n,j}$
stands for the number of alternating sign matrices ($\operatorname{ASM}_{n}$
for short) of size $n\times 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

$\displaystyle w_{0}:=\prod_{j=1}^{n-1}\left\\{\prod_{a=n-1}^{j}a\right\\}$

is equal to the number of alternating sign matrices of size $n\times n$, i.e.,

$\displaystyle|{\cal
A}_{n}|=|\operatorname{TSSCPP}(n)|=|\operatorname{ASM}_{n}|.$

It is well-known [6] that

$\displaystyle A_{n,j}={n+j-2\choose
j-1}{(2n-j-1)!\over(n-j)!}\prod_{i=0}^{n-2}{(3i+1)!\over(n+i)!},$

and the total number $A_{n}$ of $\operatorname{ASM}$ of size $n\times n$ is
equal to

$\displaystyle A_{n}\equiv
A_{n+1,1}=\sum_{j=1}^{n}A_{n,j}=\prod_{i=0}^{n-1}{(3i+1)!\over(n+i)!}.$

######  Theorem 5.8 (the case $\lambda=\delta_{n}:=(n-1,n-2,\ldots,2,1)$).

  * •

One has

$\displaystyle{\cal A}_{\delta_{n}}(n+1;t)=\prod_{j=2}^{n}~{}(1+jt).$

  * •

Gandhi–Dumont polynomials $($see [14] and [67, $A036970$]),

$\displaystyle{\cal A}_{\delta_{n}}(n+2;t)=\sum_{k=2}^{n}B_{n,k}t^{k},\qquad
B_{n,k}=\sum_{\\{k_{j}\\}}\prod_{j=2}^{n-1}{2j-k_{j-1}\choose 2j-k_{j}},$

where the sum runs over set of sequences $\\{1\leq
k_{1}<k_{2}<\cdots<k_{n-2}<k_{n-1}=2n-k\\}$.

  * •

In particular,

$\displaystyle{\cal A}_{\delta_{n}}(n+2;0)=G_{2n},\qquad{\cal
A}_{\delta_{n}}(n+2;1)=G_{2n+2},$

where $G_{2n}=2(2^{2n}-1)B_{2n}$ and $B_{2n}$ denotes the unsigned Genocchi
numbers212121Recall that the unsigned Genocchi numbers are defined through the
generting function  $\displaystyle\frac{2t}{e^{t}+1}=\sum_{n\geq
1}\frac{G_{2n}}{(2n)!}(-1)^{n}t^{2n},$ see, e.g., [14], or
https://en.wikipedia.org/wiki/Genocchi_number., and $B_{2n}$ denotes the
Bernoulli number, see, e.g., [67, $A027642$].

  * •

${\cal A}_{\delta_{n}}(n+2;-1)=(-1)^{n}$.

  * •

Let ${\cal A}_{\delta_{n}}(N;t,q)$ denote the principal specialization
$x_{i}:=q^{i-1}$, $i\geq 1$, of the polynomial $s_{\delta_{n}}^{*}(X_{N};t)$,
and write ${\cal
A}_{\delta_{n}}(n+2;t,q)=\sum\limits_{k=2}^{n-1}B_{n,k}(q)t^{k}$. Then
$B_{n,k}(q)\in\mathbb{N}[q]$.

For example, ${\cal
A}_{\delta_{6}}(8;t)=(2073,8146,12840,10248,4200,720)_{t}$, $2073=G_{12}$,
${\cal A}_{\delta_{6}}(8;1)=38227=G_{14}$, cf. [67, $A036970$]; ${\cal
A}_{(2,1)}(5;t,q)=q{4\brack 2}_{q}+t(q+q^{2})^{3}+t^{2}q^{5}{3\brack 1}_{q}$.
The last example shows that the polynomials ${\cal A}_{(\delta_{n})}(n+2;t,q)$
give rise to a $q$-deformation of the polynomials $p_{n+2}(t;\delta_{n})$
associated with refined ${\rm TSSCPP}(n)$ introduced in [12] which appeared to
be coincide $($A.K.$)$ with the Gandhi polynomials introduced, e.g., in [14].
However, the polynomials ${\cal A}_{(\delta_{n})}(n+2;t,q)$ are different from
a $q$-deformation of Gandhi polynomials defined in [22].

It is easy to see that
${\cal{A}}_{\delta_{n}}(X_{n+2};t)={\cal{A}}_{\delta_{n}}^{(1)}(X_{n};t)+x_{n+1}{\cal{A}}_{\delta_{n}}^{(2)}(X_{n};t)$
for some polynomials depending on the variables $\\{x_{1},\ldots,x_{n}\\}$
with nonnegative integer coefficients.

######  Theorem 5.9 (the Genocchi numbers of the second kind, [67,
$A005439$]).

  * •

${\cal{A}}_{\delta_{n}}^{(1)}(t;\,x_{i}=1,\,\forall\,i\in[1,n])$ is a
polynomial of the following form

$\displaystyle{\cal{A}}_{\delta_{n}}^{(1)}(t;\,x_{i}=1,\,\forall\,i\in[1,n])=t\/G_{n-2}^{(2)}+\cdots+(n-1)!t^{n-2},$
$\displaystyle{\cal{A}}_{\delta_{n}}^{(1)}(t=1;\,x_{i}=1,\,\forall\,i\in[1,n])=G_{n-2}^{(2)},$

where $G_{n}^{(2)}$ stands for the $n$-th Genocchi number of the second kind.
It is well known that $G_{n}^{(2)}=2^{n-1}G_{n}^{(m)}$, where $G_{n}^{(m)}$
denotes the so-called $n$-th median Genocchi number [67, $A000366$].

  * •

${\cal{A}}_{\delta_{n}}^{(2)}(t=0;\,x_{i}=1,\,\forall\,i\in[1,n])=G_{n-1}$,
where as before, $G_{n}$ denotes the $n$-th Genocchi number $($of the first
kind$)$ [67, $A036970$].

######  Example 5.10.

  1. (1)

Take $\lambda=\delta_{3}$ and $n=5$, then

$\displaystyle{\cal{A}}_{\delta_{3}}(X_{4};t)=t(x_{1}+x_{2})\big{(}x_{3}^{2}+t(x_{1}x_{2}+x_{1}x_{3}+x_{2}x_{3})\big{)}$
$\displaystyle\hphantom{{\cal{A}}_{\delta_{3}}(X_{4};t)=}{}+x_{4}(x_{1}x_{2}+x_{1}x_{3}+x_{3}x_{3}+t(x_{1}+x_{1})(x_{1}+x_{2}+x_{3})).$

Therefore,
${\cal{A}}_{\delta_{3}}(x_{i}=1,\,\forall\,i\in[1,3];t)=2t+6t^{2}+x_{4}(3+6t)$.

  2. (2)

Take $\lambda=\delta_{4}$ and $n=6$, then

$\displaystyle{\cal{A}}_{\delta_{4}}(x_{i}=1,\,\forall\,i\in[1,4];t)=8t\big{(}1+3t+3t^{2}\big{)}+x_{5}\big{(}17+46t+36t^{2}\big{)}.$

  3. (3)

Take $\lambda=\delta_{5}$ and $n=7$, then

$\displaystyle{\cal{A}}_{\delta_{5}}(x_{i}=1,\,\forall\,i\in[1,5];t)=t(56,192,240,120)_{t}+5x_{6}(31,100,114,48)_{t}.$

Therefore, the polynomials ${\cal{A}}_{\delta_{n}}(X_{n+1};t)$ and
${\cal{A}}_{\delta_{n}}^{(1)}(X_{n};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 ${\cal
A}_{p\delta_{n}}\\!(N{;}t{,}q)$ and ${\cal A}_{(n^{k})}\\!(N{;}t{,}q)$ for all
$N\geq pn-1$.

Let as before $\operatorname{STY}(\delta_{n}\leq n):={\cal ST}_{n}$ denotes
the set of all semistandard Young tableaux of the staircase shape
$\delta_{n}=(n-1,n-2,\ldots,2,1)$ filled by the numbers from the set
$\\{1,\ldots,n\\}$. Denote by ${\cal ST}_{n}^{(0)}$ the subset of “anti-
diagonally” increasing tableaux, i.e.,

$\displaystyle{\cal ST}_{n}^{(0)}=\\{T\in\operatorname{STY}(\delta_{n},\leq
n)\,|\,T_{i,j}\geq T_{i-1,j+1}\,\text{for all}\,2\leq i\leq n-1,\,1\leq j\leq
n-2\\}.$

One (A.K.) can construct bijections

$\displaystyle\iota_{n}\colon\ {\cal S}_{n}\sim{\cal
ST}_{n},\qquad\zeta_{n}\colon\ {\cal A}_{n}\sim{\cal ST}_{n}^{(0)}$

such that $\operatorname{Im}(\iota_{n})=\operatorname{Im}(\zeta_{n})$.

######  Proposition 5.12.

$\displaystyle\sum_{\lambda=(\lambda_{1},\ldots,\lambda_{n})\atop\rho_{n}\geq\lambda}K_{\rho_{n},\lambda}\begin{pmatrix}&n\\\
m_{0}(\lambda),&m_{1}(\lambda),&\ldots,&m_{n}(\lambda)\end{pmatrix}=2^{{n\choose
2}},$
$\displaystyle\sum_{\lambda=(\lambda_{1},\ldots,\lambda_{n})\atop\rho_{n}\geq\lambda}\begin{pmatrix}&n\\\
m_{0}(\lambda),&m_{1}(\lambda),&\ldots,&m_{n}(\lambda)\end{pmatrix}={\cal{F}}_{n},$

where ${\cal{F}}_{n}$ denotes the number of forests of trees on $n$ labeled
nodes; $K_{\rho_{n},\lambda}$ denotes the Kostka number, i.e., the number of
semistandard Young tableaux of the shape $\rho_{n}:=(n-1,n-2,$ $\ldots,1)$ and
content/weight $\lambda$; for any partition
$\lambda=(\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\geq 0)$ we set
$m_{i}(\lambda)=\\{j\,|\,\lambda_{j}=i\\}$.

Let $\alpha$ be a composition, we denote by $\alpha^{+}$ the partition
obtained from $\alpha$ by reordering of its parts. For example, if
$\alpha=(0,2,0,3,1,0)$ then $\alpha^{+}=(3,2,1)$. Note that $\ell(\alpha)=6$,
but $\ell(\alpha^{+})=3$.

Now let $\alpha$ be a composition such that $\rho_{n}\geq\alpha^{+}$,
$\ell(\alpha)\leq n$, that is $\alpha_{j}=0$, if $j>\ell(\alpha)$,
$|\alpha|={n\choose 2}$ and

$\displaystyle\sum_{k\leq j}{(\rho_{n})}_{k}\geq\sum_{k\leq
j}(\alpha^{+})_{k},\qquad\forall\,j.$

There is a unique semistandard Young tableau $T_{n}(\alpha)$ of shape
$\rho_{n}$ and content $\alpha$ which corresponds to the maximal configuration
of type $(\rho_{n};\alpha)$ and has all quantum numbers (riggings) equal to
zero. It follows from Proposition 5.12 that $\\#\\{\alpha\,|\,\ell(\alpha)\leq
n,\,\rho_{n}\geq\alpha^{+}\\}={\cal{F}}_{n}$. Therefore there is a natural
embedding of the set of forests on $n$ labeled nodes to the set of
semistandard Young tableaux of shape $\rho_{n}$ filled by the numbers from the
set $[1,\ldots,n]$. We denote by
${\cal{FT}}_{n}\subset\operatorname{STY}(\rho_{n},\leq n)$ the subset
$\\{T_{n}(\alpha)\,|\,\rho_{n}\geq\alpha^{+},\,\ell(\alpha)\leq n\\}$. Note
that the set
${\cal{K}}_{n}:=\\{\alpha\,|\,\ell(\alpha)=n,\,(\alpha)^{+}=\rho_{n}\\}$
contains $n!$ compositions, and under the rigged configuration bijection the
elements of the set ${\cal{K}}_{n}$ correspond to the key tableaux [52] of
shape $\rho_{n}$. See also [2] for connections of the Lascoux–Schützenberger
keys and $\operatorname{ASM}$.

Let us say a few words about the Kostka numbers $K_{\rho_{n},\alpha}$. First
of all, it’s clear that if $\alpha=(\alpha_{1},\alpha_{2},\dots)$ is a
composition such that $\alpha_{1}=n-1$, then
$K_{\rho_{n},\alpha}=K_{\rho_{n-1},\alpha[1]}$, where we set
$\alpha[1]:=(\alpha_{2},\ldots)$.

Now assume that $n=2k+1$ is an odd integer, and consider partitions
$\nu_{n}:=(k^{n})$ and $\mu_{n}:=((k+1)^{k},k^{k})$. Then

$\displaystyle K_{\rho_{n},\nu_{n}}=\operatorname{Coef\/f}_{(x_{1}x_{2}\cdots
x_{n})^{k}}\left(\prod_{1\leq i<j\leq n}(x_{i}+x_{j})\right),\qquad{2k\choose
k}K_{\rho_{n},\mu_{n}}=K_{\rho_{n},\nu_{n}}.$

It is well-known that the number $K_{\rho_{n},\nu_{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

$\displaystyle K_{\rho_{n},\nu_{n}}=K_{\rho_{n-1},{\nu_{n-1}}},\qquad
K_{\rho_{n},\mu_{n}}=K_{\rho_{n+1},{\mu_{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 $\operatorname{STY}(\rho_{n},\leq n)$, if $n$ is an odd integer,
and $\displaystyle\text{to the set $\operatorname{STY}(\rho_{n-1},\leq n-1)$,
if $n$ is even integer}.$

######  Theorem 5.13.

  1. $(1)$

In the plactic algebra ${\cal P}_{n}$ the Cauchy kernel has the following
decomposition

$\displaystyle{\cal C}_{n}(\mathfrak{P},U)=\sum_{T\in{\cal A}_{n}}{\cal
K}_{T}(\mathfrak{P})u_{w(T)}.$

  2. $(2)$

Let $T\in{\cal A}_{n}$, and $\alpha(T)$ be its bottom code. Then

$\displaystyle{\cal K}_{T}(\mathfrak{P})-\prod_{(i,j)\in
T}p_{\\{i,T(i,j)-j+1\\}}\geq 0,$

and equality holds if and only if the bottom code $\alpha(T)$ is a partition.

Note that the number of different shapes among the tableaux in the set ${\cal
A}_{n}$ is equal to the Catalan number $C_{n}:={1\over{n+1}}{2n\choose n}$.

######  Problem 5.14.

Construct a bijection between the set ${\cal A}_{n}$ and the set of
alternating sign matrices $\operatorname{ASM}_{n}$.

######  Example 5.15.

For $n=4$ one has

$\displaystyle{\cal
C}_{4}(X,U)=K[0]+K[1]u_{1}+K[01]u_{2}+K[001]u_{3}+K[11](u_{12}+u_{22})+K[2](u_{21}+u_{31})$
$\displaystyle\hphantom{{\cal
C}_{4}(X,U)=}{}+K[101]u_{13}+K[02]u_{32}+K[011](u_{23}+u_{33})+K[3]u_{321}+K[12](u_{312}+u_{322})$
$\displaystyle\hphantom{{\cal
C}_{4}(X,U)=}{}+K[21]u_{212}+K[111](u_{123}+u_{133}+u_{233}+u_{223}+u_{333})+K[021]u_{323}$
$\displaystyle\hphantom{{\cal
C}_{4}(X,U)=}{}+K[201](u_{313}+u_{213})+K[31]u_{3212}+K[301]u_{3213}$
$\displaystyle\hphantom{{\cal
C}_{4}(X,U)=}{}+K[22](u_{3132}+u_{2132}+u_{3232})+K[121](u_{3123}+u_{3233}+u_{3223})$
$\displaystyle\hphantom{{\cal
C}_{4}(X,U)=}{}+K[211](u_{2123}+u_{2133}+u_{3133})+K[32]u_{32132}+K[311](u_{32123}+u_{32133})$
$\displaystyle\hphantom{{\cal
C}_{4}(X,U)=}{}+K[221](u_{21323}+u_{31323}+u_{32323})+K[321]u_{321323}.$

Let $w\in\mathbb{S}_{n}$ be a permutation with the Lehmer code $\alpha(w)$.

######  Definition 5.16.

Define the plactic polynomial ${\cal{PL}}_{w}(U)$ to be

$\displaystyle{\cal{PL}}_{w}(U)=\biggl{\\{}\sum_{T\in{\cal
A}_{n},\,\alpha(T)=\alpha(w)}u_{w(T)}\biggr{\\}}.$

######  Comments 5.17.

It is easily seen from a definition of the Cauchy kernel that

$\displaystyle{\cal{C}}_{n}(X,U)=\sum_{\alpha\subset\delta_{n}}K[\alpha](X){\cal{PL}}_{w_{0}w_{\alpha}^{-1}}(U),$

where $w_{\alpha}$ denotes a unique permutation in $\mathbb{S}_{n}$ with the
Lehmer code equals $\alpha$; $K[\alpha](X)$ denotes the key polynomial
corresponding to composition $\alpha\subset\delta_{n}$. The polynomials
${\cal{PL}}_{w_{0}w_{\alpha}^{-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=\\{x_{1},\ldots,x_{n}\\}$ be a set of mutually commuting variables,
and

$\displaystyle
I_{0}^{(n)}:=\big{\\{}\underbrace{n-1,n-2,\ldots,2,1}_{n-1},\ldots,\underbrace{n-1,,n-2,\ldots,k+1,k}_{n-k},\ldots,\underbrace{n-1,n-2}_{2},n-1\big{\\}}$

be lexicographically maximal reduced expression for the longest element
$w_{0}\in\mathbb{S}_{n}$. Let $I$ be a tableau subword of the set
$I_{0}:=I_{0}^{(n)}$. One can show (A.K.) that under the specialization

$\displaystyle u_{i}=\begin{cases}x_{i},&\text{if}\ \ i\in
I_{0}{\setminus}I,\\\ 1,&\text{if}\ \ i\in I\end{cases}$

the polynomial ${\cal{PL}}_{w_{0}w_{\alpha}^{-1}}(U)$ turns into the Schubert
polynomial ${\mathfrak{S}}_{w_{\alpha}}(X)$. In a similar fashion, consider
the decomposition

$\displaystyle{\cal{C}}_{n}(X,U)=\sum_{\alpha\subset\delta_{n}}\operatorname{KG}[\alpha](X;-\beta){\cal{PL}}_{w_{0}w_{\alpha}^{-1}}(U;\beta).$

One can show (A.K.) that under the same specialization as has been listed
above, the polynomial ${\cal{PL}}_{w_{0}w_{\alpha}^{-1}}(U;\beta)$ turns into
the $\beta$-Grothendieck polynomial ${\cal{G}}_{w_{\alpha}}^{\beta}(X)$.

######  Definition 5.18.

Define algebra ${\cal{PC}}_{n}$ to be the quotient of the plactic algebra
${\cal{P}}_{n}$ by the two-sided ideal $J_{n}$ by the set of monomials

$\displaystyle\\{u_{i_{1}}u_{i_{2}}\cdots u_{i_{n}}\\},\qquad 1\leq i_{1}\leq
i_{2}\leq\cdots\leq i_{n}\leq n,\qquad\\#\\{a|i_{a}=j\\}\leq
j,\qquad\forall\,j=1,\ldots,n.$

######  Theorem 5.19.

  * •

The algebra ${\cal{PC}}_{n}$ has dimension equals to $\operatorname{ASM}(n)$,

  * •

$\operatorname{Hilb}({\cal{PC}}_{n},q)=\sum\limits_{\lambda\in\delta_{n-1}}|{\cal{A}}_{n}(\lambda)|q^{|\lambda|}$,

  * •

$\operatorname{Hilb}(({\cal{PC}}_{n+1})^{ab},q)=\sum\limits_{k=0}^{n}\frac{n-k+1}{n+1}{n+k\choose
n}q^{k}$, cf. [67, $A009766$].

######  Definition 5.20.

Denote by ${\cal{PC}}_{n}^{\sharp}$ the quotient of the algebra
${\cal{PC}}_{n}$ by the two-sided ideal generated by the elements
$\\{u_{i}u_{j}-u_{j}u_{i},\,|i-j|\geq 2\\}$.

######  Proposition 5.21.

Dimension $\dim{\cal{PC}}_{n}^{\sharp}$ of the algebra
${\cal{PC}}_{n}^{\sharp}$ is equal to the number of Dyck paths whose ascent
lengths are exactly $\\{1,2,\ldots,n+1\\}$.

See [67, $A107876$, $A107877$] where the first few of these numbers are
displayed.

######  Example 5.22.

$\displaystyle\operatorname{Hilb}\big{(}{\cal{PC}}_{5}^{\sharp},t\big{)}=(1,4,12,27,48,56,54,38,20,7,1)_{t},\qquad\dim{\cal{PC}}_{5}^{\sharp}=268,$
$\displaystyle\operatorname{Hilb}\big{(}{\cal{PC}}_{6}^{\sharp},t\big{)}=(1,5,18,50,116,221,321,398,414,368,275,175,89,35,9,1)_{t},$
$\displaystyle\dim{\cal{PC}}_{6}^{\sharp}=2496,\qquad\dim{\cal{PC}}_{7}^{\sharp}=28612.$

######  Example 5.23.

$\displaystyle\operatorname{Hilb}({\cal{PC}}_{3},q)=(1,2,3,1)_{q},\qquad\operatorname{Hilb}({\cal{PC}}_{4},q)=(1,3,8,12,11,6,1)_{q},$
$\displaystyle\operatorname{Hilb}({\cal{PC}}_{5},q)=(1,4,15,35,69,91,98,70,35,10,1)_{q},$
$\displaystyle\operatorname{Hilb}({\cal{PC}}_{6},q)=(1,5,24,74,204,435,783,1144,1379,1346,1037,628,275,85,15,1)_{q},$
$\displaystyle\operatorname{Hilb}({\cal{PC}}_{7},q)=(1,6,35,133,461,1281,3196,6686,12472,19804,27811,33271,34685,$
$\displaystyle\hphantom{\operatorname{Hilb}({\cal{PC}}_{7},q)=(}{}30527,22864,14124,7126,2828,840,175,21,1)_{q}.$

######  Problem 5.24.

Denote by ${\mathfrak{A}}_{n}$ the algebra generated by the curvature of
$2$-forms of the tautological Hermitian linear bundles $\xi_{i}$, $1\leq i\leq
n$, over the flag variety ${\cal{F}}l_{n}$ [66]. It is well-known [62] that
the Hilbert polynomial of the algebra ${\mathfrak{A}}_{n}$ is equal to

$\displaystyle\operatorname{Hilb}({\mathfrak{A}}_{n},t)=\sum_{F\in{\cal{F}}_{n}}t^{\operatorname{inv}(F)}=\sum_{F\in{\cal{F}}_{n}}t^{\operatorname{maj}(F)},$

where the sum runs over the set ${\cal{F}}_{n}$ of forests $F$ on the $n$
labeled vertices, and $\operatorname{inv}(F)$ $($resp.
$\operatorname{maj}(F))$ denotes the inversion index $($resp. the major
index$)$ of a forest $F$.222222For the readers convenience we recall
definitions of statistics $\operatorname{inv}(F)$ and $\operatorname{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 $\operatorname{inv}(F)$ is
equal to the number of pairs $(i,j)$ such that $1\leq i<j\leq 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 $\operatorname{maj}(F)$ is equal to
$\sum\limits_{x\in\operatorname{Des}(F)}h(x)$; here for any vertex $x\in F$,
$h(x)$ is the size of the subtree rooted at $x$; the descent set
$\operatorname{Des}(F)$ of $F$ consists of the vertices $x\in F$ which have
the labeling strictly greater than the labeling of its child.

Clearly that

$\displaystyle\dim({\mathfrak{A}}_{n})_{{n\choose
2}}=\dim({\cal{PC}}_{n})_{{n\choose
2}}=\dim(H^{\star}({\cal{F}}l_{n},\mathbb{Q}))_{{n\choose 2}}=1.$

For example,

$\displaystyle\operatorname{Hilb}({\cal{PC}}_{6},t)=(1,5,24,74,204,435,783,1144,1379,1346,1037,628,275,85,15,1)_{t},$
$\displaystyle\operatorname{Hilb}({\mathfrak{A}}_{6},t)=(1,5,15,35,70,126,204,300,405,490,511,424,245,85,15,1)_{t},$
$\displaystyle\operatorname{Hilb}(H^{\star}({\cal{F}}l_{n},\mathbb{Q}),t)=(1,5,14,29,49,71,90,101,101,90,71,49,29,14,5,1)_{t}.$

We expect that $\dim({\cal{PC}}_{n})_{{n\choose 2}-1}={n\choose 2}$ and
$\dim({\cal{PC}}_{n})_{{n\choose 2}-2}={\frac{3n+5}{4}}{n+2\choose
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. $(1)$

Is it true that
$\operatorname{Hilb}({\cal{PC}}_{n},t)-\operatorname{Hilb}({\mathfrak{A}}_{n},t)\in\mathbb{N}[t]$?
If so, as we expect, does there exist an embedding of sets
$\iota\colon{\cal{F}}(n)\hookrightarrow{\cal{A}}_{n}$ such that
$\operatorname{inv}(F)=n(\iota(F))$ for all $F\in{\cal{F}}_{n}$? See Section
5.1, Definition 5.5, for definitions of the set ${\cal{A}}_{n}$ and statistics
$n(T)$, $T\in{\cal{A}}_{n}$.

  2. $(2)$

Define a “natural” bijection $\kappa\colon\operatorname{STY}(\delta_{n},\leq
n)\longleftrightarrow 2^{\delta_{n}}$ such that the set
$\kappa(\operatorname{MT}(n))$ admits a “nice” combinatorial description.

Here $\operatorname{MT}(n)$ denotes the set of (increasing) monotone
triangles, namely, a subset of the set $\operatorname{STY}(\delta_{n},\leq n)$
consisting of tableaux $\\{T=(t_{i,j})\,|\,i+j\leq n+1,\,i\geq 1,j\geq 1\\}$
such that $t_{i,j}\geq t_{i-1,j+1}$, $2\leq i\leq n$, $1\leq j<n$, cf. [68];
$\delta_{n}=(n-1,n-2,\ldots,2,1)$; $\operatorname{STY}(\delta_{n},\leq n)$
denotes the set of semistandard Young tableaux of shape $\delta_{n}$ with
entries bounded by $n$; $2^{\delta_{n}}$ stands for the set of all subsets of
boxes of the staircase diagram $\delta_{n}$. It is well-known that
$\\#|\operatorname{STY}(\delta_{n},\leq n)|=2^{\delta_{n}}=2^{{n\choose 2}}$.

######  Comments 5.26.

One can ask a natural question: when do noncommutative elementary polynomials
$e_{1}(\mathbb{A}),\dots,e_{n}(\mathbb{A})$ form a $q$-commuting family, i.e.,
$e_{i}(\mathbb{A})e_{j}(\mathbb{A})=qe_{j}(\mathbb{A})e_{i}(\mathbb{A})$,
$1\leq i<j\leq n$?

Clearly in the case of two variables one needs to necessitate the following
relations

$\displaystyle
e_{i}e_{j}e_{i}+e_{j}e_{j}e_{i}=qe_{j}e_{i}e_{i}+qe_{j}e_{i}e_{j},\qquad i<j.$

Having in mind to construct a $q$-deformation of the plactic algebra
${\cal{P}}_{n}$ such that the wanted $q$-commutativity conditions are
fulfilled, one would be forced to add the following relations

$\displaystyle qe_{j}e_{i}e_{j}=e_{j}e_{j}e_{i}\qquad\text{and}\qquad
qe_{j}e_{i}e_{i}=e_{i}e_{i}e_{j}e_{i},\qquad i<j.$

It is easily seen that these two relations are compatible iff $q^{2}=1$.
Indeed,

$\displaystyle
e_{j}\underline{e_{j}e_{i}e_{j}}=qe_{j}\underline{e_{i}e_{j}e_{i}}=q^{2}e_{j}e_{j}e_{i}e_{i}\quad\Longrightarrow\quad
q^{2}=1.$

In the case $q=1$ one comes to the Knuth relations $({\rm PL1})$ and $({\rm
PL2})$. In the case $q=-1$ one comes to the “odd” analogue of the Knuth
relations, or “odd” plactic relations (${\rm OPL}_{n}$), i.e., $({\rm
OPL}_{n}):$

$\displaystyle u_{j}u_{i}u_{k}=-u_{j}u_{k}u_{i},\qquad\text{if}\quad i<j\leq
k\leq n,\qquad\text{and}$ $\displaystyle
u_{i}u_{k}u_{j}=-u_{k}u_{i}u_{j},\qquad\text{if}\quad i\leq j<k\leq n.$

######  Proposition 5.27 (A.K.).

Assume that the elements $\\{u_{1},\ldots,u_{n-1}\\}$ satisfy the odd plactic
relations $({\rm OPL}_{n})$. Then the noncommutative elementary polynomials
$e_{1}(U),\ldots,e_{n}(U)$ are mutually anticommute.

More generally, let ${\bf{\cal{Q}}_{n}}:=\\{q_{ij}\\}_{1\leq i<j\leq n-1}$ be
a set of parameters. Define generalized plactic algebra ${\cal{QP}}_{n}$ to be
(unital) associative algebra over the ring $\mathbb{Z}[\\{q_{ij}^{\pm
1}\\}_{1\leq i<j\leq n-1}]$ generated by elements $u_{1},\ldots,u_{n-1}$
subject to the set of relations

$\displaystyle q_{ik}u_{j}u_{i}u_{k}=u_{j}u_{k}u_{i},\qquad\text{if}\quad
i<j\leq k,\qquad\text{and}$ $\displaystyle
q_{ik}u_{i}u_{k}u_{j}=u_{k}u_{i}u_{j},\qquad\text{if}\quad i\leq j<k.$ (5.3)

######  Proposition 5.28.

Assume that $q_{ij}:=q_{j}$, $\forall\,1\leq i<j$ be a set of invertible
parameters. Then the reduced generalized plactic algebra ${\cal{QPC}}_{n}$ is
a free $\mathbb{Z}[q_{2}^{\pm 1},\ldots,q_{n-1}^{\pm 1}]$-module of rank
equals to the number of alternating sign matrices $\operatorname{ASM}(n)$.
Moreover,

$\displaystyle\operatorname{Hilb}({\cal{QPC}}_{n},t)=\operatorname{Hilb}({\cal{PC}}_{n},t),\operatorname{Hilb}({\cal{QP}}_{n},t)=\operatorname{Hilb}({\cal{P}}_{n},t).$

Recall that reduced generalized plactic algebra ${\cal{QPC}}_{n}$ is the
quotient of the generalized plactic algebra by the two-sided ideal $J_{n}$
introduced in Definition 5.18.

######  Example 5.29.

  1. (A)

Super plactic monoid [38, 56]. Assume that the set of generators
$U:=\\{u_{1},\ldots,u_{n-1}\\}$ is divided on two non-crossing subsets, say
$Y$ and $Z$, $Y\cup Z=U,Y\cap Z=\varnothing$. To each element $u\in U$ let us
assign the weight $wt(u)$ as follows: $wt(u)=0$ if $u\in Y$, and $wt(u)=1$ if
$u\in Z$. Finally, define parameters of the generalized plactic algebra
${\cal{QP}}_{n}$ to be $q_{ij}=(-1)^{wt(u_{i})wt(u_{j})}$. As a result we led
to conclude that the generalized plactic algebra ${\cal{QP}}_{n}$ in question
coincides with the super plactic algebra ${\cal{PS}}(V)$ introduced in [56].
We will denote this algebra by ${\cal{SP}}_{k,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.

  2. (B)

$q$-analogue of the plactic algebra. Now let $q\not=0,\pm 1$ be a parameter,
and assume that $q_{ij}=q$, $\forall\,1\leq i<j\leq 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 tropical/geometric RSK-correspondence