2023-02-07
Key polynomials
The key polynomials, also known as Demazure characters, is a family of non-symmetric polynomials, indexed by weak compositions, or alternatively, an integer partition and a permutation. The set $\{ \key_\alpha(x_1,\dotsc,x_n) \}_\alpha$ where $\alpha$ ranges over all compositions of length $n,$ is a basis for $\setC[x_1,\dotsc,x_n].$
The key polynomials generalize the Schur polynomials.
Demazure characters were introduced in [Dem74bDem74a]. Later, a combinatorial formula using so called key tableaux was discovered in [LS90a]. Key polynomials are also given as a specialization of non-symmetric Macdonald polynomials, see [HHL08], and this gives several combinatorial models for the key polynomials, see the works of S. Mason [Mas09], and also [Kur16AS19a].
Key polynomials are closely related to Demazure atoms.
The K-theoretic version of key polynomials are the Lascoux polynomials.
Definition (Operators)
Define the divided difference operator $\partial_i$ as
\[ \partial_i(f) = \frac{f - s_i(f)}{z_i - z_{i+1}}, \]and let $\pi_i(f) \coloneqq \partial_i(z_i f)$ for $i=1,\dotsc,n-1$ whenever $f \in \setC[z_1,\dotsc,z_n].$ One can show that $\pi_i^2 = \pi_i$ and that they satisfiy the braid relations.
Let $\sigma = s_{i_1} s_{i_2} \dotsc s_{i_\ell}$ be a reduced word of a permutation $\sigma \in \symS_n,$ and let
\[ \pi_\sigma \coloneqq \pi_{i_1} \circ \pi_{i_2} \circ \dotsb \circ \pi_{i_\ell}. \]This is well-defined, as the action of $\pi_\sigma$ is independent of the choice of reduced word.
Let $\lambda$ be a partition with at most $n$ parts, and let $\sigma \in \symS_n.$ In fact, we can choose $\sigma$ to be the minimal coset representation for the parabolic subgroup $W_J \subseteq \symS_n$ that fixes $\lambda.$ The key polynomial $\key_{\lambda,\sigma}(z)$ is defined as
\begin{equation*} \key_{\lambda,\sigma}(z) \coloneqq \pi_\sigma\left( z_1^{\lambda_1} \dotsm z_n^{\lambda_n} \right). \end{equation*}Note that if $\sigma^1(\lambda)=\sigma^2(\lambda),$ then $\key_{\lambda,\sigma^1}(z) = \key_{\lambda,\sigma^2}(z).$
This definition shows the close connection between Schubert polynomials and key polynomials. Notice that if we take $w_0$ to be the longest permutation in $\symS_n,$ then
\[ \schurS_\lambda(z_1,\dotsc,z_n) = \key_{\lambda,w_0}(z_1,\dotsc,z_n), \]so the key polynomials are a superfamily of the Schur polynomials.
Let $\lambda = (2,1,0,0)$ and $\sigma = [2,4,3,1] \in \symS_4$ in one-line notation. The permutation can be expressed as a reduced word as $\sigma = s_2 s_3 s_2 s_1.$ We compute the key polynomial as follows:
\begin{align*} \key_{\lambda,\sigma}(z) &= \pi_2 \pi_3 \pi_2 \pi_1 (z_1^2 z_2) = \pi_2 \pi_3 \pi_2 \partial_1 (z_1^3 z_2 ) = \pi_2 \pi_3 \pi_2 \left( \frac{z_1^3z_2 - z_1 z^3_2}{z_1-z_2}\right) \\ &= \pi_2 \pi_3 \pi_2 (z_1^2z_2 + z_1 z_2^2). \end{align*}We continue the calculation by applying $\pi_2$ and get
\begin{align*} \key_{\lambda,\sigma}(z) &= \pi_2 \pi_3 (z_2 z_1^2+z_3 z_1^2+z_2^2 z_1+z_3^2 z_1+z_2 z_3 z_1). \end{align*}Applying $\pi_2 \pi_3$ then finally gives
\begin{equation*}\label{eq:keyExample} \begin{split} \key_{\lambda,\sigma}(z) &= z_1^2 z_2 + z_1^2 z_3 + z_1^2 z_4 + z_1 z_2^2 + z_1 z_3^2 \\ &\phantom{=}+ z_1 z_4^2 + z_1 z_2 z_3 + z_1 z_2 z_4 + z_1 z_3 z_4 . \end{split} \end{equation*}In general, some monomials may appear multiple times.
Alternatively, key polynomials are also commonly indexed by weak compositions. If $\alpha = (\alpha_1,\dotsc,\alpha_n)$ is a weak composition, we let $\key_{\alpha}(z)$ be the key polynomial $\key_{\lambda,\sigma}(z),$ where $\lambda$ is the partition obtained from $\alpha$ by sorting the elements in decreasing order, and $\sigma \in \symS_n$ is a permutation with the property that it sorts $\alpha$ into a partition; $\lambda = (\alpha_{\sigma(1)},\alpha_{\sigma(2)},\dotsc,\alpha_{\sigma(n)}).$
For example, $\alpha = (1,0,3,2)$ corresponds to $\lambda = (3,2,1,0)$ and $\sigma = [3, 4, 1, 2].$ With these conventions, $\key_{\lambda}(z)=\schurS_{\lambda}(z).$
Note: This indexing convention is not uniform in the literature; in some places, one needs to reverse the indexing composition $\alpha.$
Definition (GT-patterns)
A formula for the key polynomials as a sum over lattice points in a union of faces of Gelfand–Tsetlin polytopes was proved in [KST12].
Let $\GT(\lambda,\sigma)$ be defined as the polytopal complex
\[ \GT(\lambda,\sigma) \coloneqq \bigcup_{\substack{\mathcal{F} \in \GT(\lambda) \\ \type(\mathcal{F}) = w_0\sigma}} \mathcal{F}. \]That is, $\GT(\lambda,\sigma)$ is the union of all reduced Kogan faces of type $w_0\sigma$ in the polytope $\GT(\lambda).$
The key polynomial $\key_{\lambda,\sigma}(z)$ can be computed as
\begin{align}\label{eq:keyGTFormula} \key_{\lambda,\sigma}(z_1,\dotsc,z_n) = \sum_{G \in \GT(\lambda,\sigma) \cap \setZ^{\tfrac{n(n+1)}{2}} } z_1^{w_1(G)} \dotsm z_n^{w_n(G)} \end{align}Fix $\lambda,$ $\sigma \in \symS_n.$ With the above theorem, it follows that for the map
\[ k \mapsto \key_{k \lambda,\sigma}(1^n) \]is a polynomial in $k.$ This is in fact an Ehrhart polynomial of a union of faces in a GT-polytope. Let $P_{\sigma}(\lambda_1,\dotsc,\lambda_n;k)$ denote this polynomial. From the definition via divided difference operators, one can see that $P_{\sigma}(\lambda_1,\dotsc,\lambda_n;k)$ is a polynomial in $\setQ[\lambda_1,\dotsc,\lambda_n,k].$
See [AA19a] for the following conjecture.
The polynomial $P_{\sigma}(\lambda_1,\dotsc,\lambda_n;k)$ has non-negative coefficients.
Moreover, after setting $a_j = \lambda_1+\lambda_2+\dotsb+\lambda_j,$ the function $P_{\sigma}(a_1,\dotsc,a_n;k)$ is a polynomial in $\setQ[a_1,\dotsc,a_n,k]$ with non-negative coefficients.
See also my conjecture regarding the corresponding $h^*$-polynomial.
Definition (Skyline fillings)
In [HHL08], the authors presented a combinatorial model for the non-symmetric Macdonald polynomials. It is relatively straightforward to see that setting $q=t=0$ in a non-symmetric Macdonald polynomial $\macdonaldE_{\alpha}(\xvec,q,t),$ we recover the key polynomial $\key_\alpha(\xvec).$
From the work of S. Mason [Mas09], we in fact get two combinatorial models for key polynomials as special cases of the permuted basement Macdonald polynomials. In the below definition, we assume that the reader is familiar with the combinatorial model for the permuted basement Macdonald polynomials.
A semi-standard augmented filling of shape $\alpha = (\alpha_1,\dotsc,\alpha_n)$ is a non-attacking filling of the diagram with shape $\alpha,$ basement $\sigma = [n,n-1,\dotsc,2,1]$ such that all rows (including the basement) are weakly decreasing, and there are no coinversion triples. Let $\mathrm{SSAF}(\alpha)$ be the set of semi-standard augmented fillings of shape $\alpha.$
The key polynomial $\key_\alpha(\xvec)$ is defined as
\[ \key_\alpha(\xvec) = \sum_{T \in \mathrm{SSAF}(\alpha)} \xvec^T. \]Note that when $\alpha$ is a partition, we sum over fillings with weakly decreasing rows, and strictly decreasing columns. It is then easy to see that this sum is the Schur polynomial $\schurS_{\lambda}(x_1,\dotsc,x_n).$
Alternatively, by choosing a different basement, we can realize $\key_\alpha(\xvec)$ as a sum over augmented fillings with partition shape. Let $\mathrm{SSAF}_{\sigma}(\lambda)$ be the set of semi-standard augmented fillings with basement $\sigma$ and shape $\lambda.$ Then
\[ \key_\alpha(\xvec) = \sum_{T \in \mathrm{SSAF}_{\sigma}(\lambda)} \xvec^T, \quad \text{where} \quad \alpha = (\lambda_{\sigma^{-1}(n)}, \lambda_{\sigma^{-1}(n-1)},\dotsc,\lambda_{\sigma^{-1}(1)}). \]In fact, one can find a series of bijections proving the equivalence of the two above formulas, see [Prop. 5.5, AS19a] (with $t=0$). It amounts to prove that interchanging two adjacent rows (including the basement) in an augmented diagram in such a way that a longer row is moved upwards, preserves the weighted sum of SSAF's with corresponding shape and basement.
Definition (SSYT)
Representation theory of GLn
See introduction in e.g. https://arxiv.org/pdf/1911.07650.pdfProducts of key polynomials
A product of key polynomials is not in general key positive. However, in some instances such a product is key positive, see [Kou18].
Pieri rule for key polynomials
A Pieri rule for key polynomials is described via an Robinson–Schensted–Knuth-type algorithm is given by S. Assaf and D. Quijada in https://arxiv.org/pdf/1908.08502.pdf.
Skew key polynomials
In AssafvanWilligenburg2019, the authors introduce skew key polynomials, and show that these are positive in the key basis. They use weak dual equivalence to obtain their result. This generalizes an earlier result by Reiner and Shimozono, [RS95].
Demazure atoms
The Demazure atoms (originally called standard bases) may be defined in a manner similar to key polynomials using operators. They were introduced by Lascoux and Schützenberger in [LS90a]. Using the notation for divided difference operators, let $\theta_i \coloneqq \pi_i -1.$ These satisfy the braid relations and we have $\theta_i \theta_j = \theta_j \theta_i$ whenever $|i-j| \geq 2.$ However, note that $\theta_i^2 = 0,$ so we must now pay extra attention to choices of permutations.
Let $\lambda$ be a partition with at most $n$ parts, and let $\sigma \in \symS_n$ be a minimal coset representatative in $\symS_n / Stab_n(\lambda).$ The Demazure atom $\atom_{\lambda,\sigma}(z)$ is defined as
\begin{equation*} \atom_{\lambda,\sigma}(z) \coloneqq \theta_\sigma\left( z_1^{\lambda_1} \dotsm z_n^{\lambda_n} \right). \end{equation*}Again, instead of using $(\lambda,\sigma)$ as index, we simply use $\sigma(\lambda)$ as index. Here, we must must choose $\sigma$ to be the shortest permutation $\sigma$ which sends $\lambda$ to $\alpha = \sigma(\lambda).$
For example, if $\alpha = 1113,$ then $\lambda=3111,$ and we must pick $\sigma = 4123,$ and
\[ \atom_{1113}(z) = \atom_{3111,4123}(z) = z_1 z_2 z_3 z_4^3 + z_1 z_2 z_3^2 z_4^2 + z_1 z_2^2 z_3z_4^2 + z_1^2 z_2 z_3 z_4^2. \]Similarly,
\[ \atom_{103}(z) = = \atom_{310,312}(z) z_1^3 z_2 + z_1^3 z_3 + z_1^2 z_2^2 + z_1^2 z_3^2 + z_1^2 z_2 z_3 + z_1 z_2^3 + z_1 z_3^3 + z_1 z_2 z_3^2 + z_1 z_2^2 z_3. \]Since $\pi_i = \theta_i+1,$ one can easily show that key polynomials are positive in the Demazure atom basis. In fact we have that (see [Thm. 2.8, Pun16])
\[ \key_{\alpha}(z) = \sum_{\beta \leq \alpha} \atom_{\beta}(z), \]where we have $\beta \leq \alpha$ if one can obtain $\beta$ from $\rev(\alpha)$ by successively permuting entries which are in increasing order. For example,
\[ \key_{301} = \atom_{103} + \atom_{130}+\atom_{301}+\atom_{310} \]since $103,$ $130,$ $301$ and $310$ can be obtained from $\rev(301)=103$ by successive swaps of elements (see also Bruhat order). Similarly,
\[ \key_{002} = \atom_{200} + \atom_{020} + \atom_{002}. \]Again, note that the notation used here might differ from yours.
We have that
\[ \key_{202} = \atom_{202}+\atom_{220} \]and
\[ \key_{301} = \atom_{103} + \atom_{130}+\atom_{301}+\atom_{310} \]See Anna Pun's thesis for a good overview of Demazure atoms, key polynomials and recent results [Pun16].
Cauchy kernel
A bijective proof of the Cauchy-type identity below is given in [Thm. 6, Las03]. The proof uses the Robinson–Schensted–Knuth correspondence.
We have that
\[ \prod_{i+j \leq n+1} (1-x_iy_j)^{-1} = \sum_{\alpha \in \setN^n} \atom_{w_0\alpha}(\xvec) \key_{\alpha}(\yvec). \]In [FL09], the authors prove this formula and several other Cauchy-type identities involving key polynomials and Demazure atoms in other types.
A generalization to truncated staircase shapes is provided by O. Azenhas and A. Emami in [AE15]. They use a version of RSK introduced by S. Mason in [Mas08].
An alternative proof also appear in [CK17] where the authors use $U_q(\mathfrak{g})$ crystals.
See also [AGL22] for the connection between the Cauchy kernel, RSK, crystals and last passage percolation.
Recall the Cauchy identity for Schubert polynomials (see e.g. [p. 30, PS08]).
\[ \sum_{w \in \symS_n} \schubert_w(\xvec) \schubert_{w w_0}(\yvec) = \prod_{i+j \leq n} (1 + x_iy_j) = \prod_{k=1}^{n-1}\sum_{j=0}^k y_{n-k}^{k-j} \elementaryE_{j}(x_1,\dotsc,x_k). \]Since the Schubert polynomials are positive in the key basis, it follows that the standard elementary monomials are key-positive.
Demazure keys and Demazure atoms in type $B,$ $C$ and $D$
In [FL09], A. Fu and A. Lascoux define divided difference operators that allow us to define key polynomials and Demazure atoms in types $B,$ $C$ and $D.$
See these slides for a nice overview. In particular, the type $C$ key polynomials contain the symplectic Schur functions. There is an operator definition, crystal graph definition and a key-tableau definition of these.
They end with an open question about how to characterize type $B$ Demazure atoms as a sum over fillings. This question is perhaps answered in the recent preprint https://arxiv.org/pdf/1910.14115.pdf.
See also [RY11], as key polynomials are specializations of non-symmetric Macdonald polynomials.
Type $B/C$ key polynomials
In [San21], J. M. Santos gives combinatorial formulas for the type $C$ key polynomials and Demazure atom polynomials. The type $C$ key polynomials expand positively into type $C$ Demazure atoms, by summing over an ideal in the Bruhat poset, see [Prop. 53, San21]. This is analogous to the type $A$ setting. A crystal characterization is also given, as well as analogs of key tableaux.
Type $B/C$ Demazure atoms
See [FL09] for definitions of key polynomials in other types. These are related to the orthogonal and symplectic Schur functions.
References
- [AA19a] Per Alexandersson and Elie Alhajjar. Ehrhart positivity and Demazure characters. Algebraic and Geometric Combinatorics on Lattice Polytopes. World Scientific, June 2019.
- [AE15] Olga Azenhas and Aram Emami. An analogue of the robinson–schensted–knuth correspondence and non-symmetric Cauchy kernels for truncated staircases. European Journal of Combinatorics, 46:16–44, May 2015.
- [AGL22] Olga Azenhas, Thomas Gobet and Cédric Lecouvey. Non symmetric Cauchy kernel, crystals and last passage percolation. arXiv e-prints, 2022.
- [AS19a] Per Alexandersson and Mehtaab Sawhney. Properties of non-symmetric Macdonald polynomials at $q=1$ and $q=0$. Annals of Combinatorics, 23(2):219–239, May 2019.
- [CK17] Seung-Il Choi and Jae-Hoon Kwon. Lakshmibai–Seshadri paths and non-symmetric Cauchy identity. Algebras and Representation Theory, 21(6):1381–1394, December 2017.
- [Dem74a] Michel Demazure. Désingularisation des variétés de schubert généralisées. Annales scientifiques de l'École normale supérieure, 7(1):53–88, 1974.
- [Dem74b] Michel Demazure. Une nouvelle formule des caractères. Bulletin des Sciences Mathématiques, 98(3):163–172, 1974.
- [FL09] Amy M. Fu and Alain Lascoux. Non-symmetric Cauchy kernels for the classical groups. Journal of Combinatorial Theory, Series A, 116(4):903–917, May 2009.
- [HHL08] James Haglund, Mark D. Haiman and Nicholas A. Loehr. A combinatorial formula for nonsymmetric Macdonald polynomials. American Journal of Mathematics, 130(2):359–383, 2008.
- [Kou18] Takafumi Kouno. Decomposition of tensor products of Demazure crystals. arXiv e-prints, 2018.
- [KST12] Valentina A. Kiritchenko, Evgeny Yu Smirnov and Vladlen A. Timorin. Schubert calculus and Gelfand–Zetlin polytopes. Russian Mathematical Surveys, 67(4):685, 2012.
- [Kur16] Daniel Kurland. An exploration of key polynomials. 2016.
- [Las03] Alain Lascoux. Double crystal graphs. In Studies in Memory of Issai Schur. Birkhäuser Boston, 2003.
- [LS90a] Alain Lascoux and Marcel-Paul Schützenberger. Keys & standard bases. In Invariant theory and tableaux (Minneapolis, MN, 1988). Springer, New York, 1990.
- [Mas08] Sarah K. Mason. A decomposition of Schur functions and an analogue of the Robinson–Schensted–Knuth algorithm. Séminaire Lotharingien de Combinatoire, 57(B57e), 2008.
- [Mas09] Sarah K. Mason. An explicit construction of type A Demazure atoms. Journal of Algebraic Combinatorics, 29(3):295–313, 2009.
- [PS08] Alexander Postnikov and Richard P. Stanley. Chains in the Bruhat order. Journal of Algebraic Combinatorics, 29(2):133–174, March 2008.
- [Pun16] Anna Pun. On decomposition of the product of Demazure atoms and Demazure characters. University of Pennsylvania. November 2016.
- [RS95] Victor Reiner and Mark Shimozono. Key polynomials and a flagged Littlewood–Richardson rule. J. Combin. Theory Ser. A, 70(1):107–143, 1995.
- [RY11] Arun Ram and Martha Yip. A combinatorial formula for Macdonald polynomials. Advances in Mathematics, 226(1):309–331, 2011.
- [San21] João Miguel Santos. Symplectic keys and Demazure atoms in type C. The Electronic Journal of Combinatorics, 28(2), June 2021.