The symmetric functions catalog

An overview of symmetric functions and related topics

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.

Example (Taken from [AA19a]).

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].

Theorem (See [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.

Conjecture (Alexandersson–Alhajjar (2018)).

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.

Definition.

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.pdf

Products 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.

Example (Key polynomials into atoms).

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.

Theorem (See [Thm. 6, Las03]).

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.

Example (Personal communication, Vasu Tewari 2019).

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