The symmetric functions catalog

An overview of symmetric functions and related topics

2023-09-20

Schubert polynomials

Schubert polynomials were introduced by A. Lascoux and M.-P. Schützenberger in [LS82a]. The Schubert polynomials generalize the Schur polynomials and represent Schubert cycles in flag varieties. The Schubert polynomials are generalized by the Grothendieck polynomials.

The Schubert polynomials are indexed by permutations. The set

\[ \{ \schubert_\omega(x_1,\dotsc,x_n) \}_{\omega \in \symS_n} \]

is then a basis for the space $\setZ[x_1,\dotsc,x_n]/I_n$ where $I_n = \langle \elementaryE_1, \elementaryE_2,\dotsc, \elementaryE_n \rangle,$ i.e., the ideal generated by non-constant symmetric functions. The Schubert polynomials $\schubert_\omega$ with $\omega \in \symS_\infty$ form an integral basis for $\setZ[x_1,x_2,\dotsc].$

Operator definition

Consider the ring $\setR[x_1,\dotsc,x_n]$ and let $s_i$ act by permuting $x_i$ and $x_{i+1}.$ Define $\partial_i(f)$ as $\frac{f-s_i(f)}{x_i - x_{i+1}}$ for $i=1,\dotsc,n-1.$ These divided difference operators satisfy the braid relations, and we let $\partial_\omega = \partial_{a_1} \partial_{a_2} \dotsm \partial_{a_k}$ where $(a_1,a_2,\dotsc,a_k)$ is a reduced word for $\omega.$

The Schubert polynomials are then defined as

\begin{equation*} \schubert_\omega(x_1,\dotsc,x_n) \coloneqq \partial_{\omega^{-1}\omega_0}(x_1^{n-1}x_2^{n-2}\dotsm x_{n-1}). \end{equation*}

Reduced word formula

Let $RW(\omega)$ be the set of reduced words of $\omega.$

We say that a $k$-tuple $\alpha_1,\dotsc,\alpha_k$ is $a$-compatible if

  • $\alpha_1 \leq \alpha_2 \leq \dotsb \leq \alpha_k$
  • $\alpha_j \leq a_j$ for $1 \leq j \leq k$
  • $\alpha_j \lt \alpha_{j+1}$ whenever $a_j \lt a_{j+1}.$

Let $C(a)$ denote the set of $a$-compatible sequences. Then

\begin{equation*} \schubert_\omega(x_1,\dotsc,x_n) = \sum_{a \in RW(\omega)} \sum_{\alpha \in C(a)} x^\alpha \end{equation*}

Pipe dream formula

The set of reduced words and compatible sequences can be described in a more combinatorial manner using rc-graphs. Suppose $(\alpha_1,\dotsc,\alpha_k)$ is an $a$-compatible sequence, for $a\in RW(\omega).$ Let

\[ D(a,\alpha) = \{ (\alpha_j, a_j - \alpha_j + 1) \text{ for } j=1,\dotsc,k \}. \]

This set of points is illustrated in an rc-graph, also known as pipe-dreams.

Example.

Let $\omega = 314652.$ Then $a = 521345$ is in $RW(\omega),$ and $\alpha = 111235$ is $a$-compatible. We mark the corresponding entries in $D(a,\alpha)$ with a cross, $+,$ in the rc-graph:

$ \;$$ 1$$ 2$$ 3$$ 4$$ 5$$ 6$
$ 1$$+$$+$$\cdot$$\cdot$$+$$\cdot$
$ 2$$\cdot$$+$$\cdot$$\cdot$$\cdot$ 
$ 3$$\cdot$$+$$\cdot$$\cdot$  
$ 4$$\cdot$$\cdot$$\cdot$   
$ 5$$+$$\cdot$    
$ 6$$\cdot$     

Let $RC(\omega)$ denote the set of all such diagrams. Let $\xvec_D = \prod_{(i,j) \in D} x_i$ then the Schubert polynomial is given as

\begin{equation*} \schubert_\omega(x_1,\dotsc,x_n) = \sum_{D \in RC(\omega)} \xvec_D. \end{equation*}

Bumpless pipe dreams

The notion of bumpless pipe dreams was introduced by Lam, Lee and Shimozono in [LLS18]. They prove the following formula for the double Schubert polynomials:

\[ \schubert_\omega(\xvec,\yvec) = \sum_{P \in RBPD(\omega)} \prod_{(i,j)\in D(P)} (x_i - y_j ) \]

where the sum runs over reduced bumpless pipe dreams. This formula can be lifted to a formula for the doubble Grothendieck polynomials.

Representation theory

This subsection follows the introduction in [FG19].

Let $D=(D_1,\dotsc,D_n)$ be an $n$-tuple of subsets of $[n].$ Then $D$ encodes a subset of $[n]\times [n],$ where $D_j$ is considered as a set of row indices (seen as a strictly increasing list). For example, the following diagram encodes $(23,14,\emptyset,124)$

$\;$ $\;$$ \;$
  $\;$$ \;$
 $\;$$\;$$\;$
$\;$ $\;$$ \;$

We define a partial order on such diagrams, where $C \leq D$ if for every $j \in [n],$ we have $|C_j| = |D_j|$ and $C_{jk} \leq D_{jk}$ for all $k.$

Let $B \subset GL_n(\setC)$ be the set of invertible upper-triangular $n\times n$-matrices. Let $Y$ denote the upper-triangular matrix with indeterminate entries $\{y_{ij}\}_{i\leq j},$ and let $\setC[Y]$ be the polynomial ring with these indeterminates. We have that a matrix $M \in GL_n(\setC)$ act on $f \in \setC[Y]$ on the right by $f \cdot M \coloneqq f(M^{-1} Y).$

Given a diagram $D,$ the flagged Weyl module $\mathcal{M}_D$ is a $B$-module, defined as

\[ \mathcal{M}_D \coloneqq \mathrm{Span} \left\{ \prod_{j=1}^n \det( Y_{D_j}^{C_j} ) : C \leq D \right\} \subseteq \setC[Y], \]

where $ Y_{D_j}^{C_j}$ denotes the submatrix of $Y$ with row-indices from $C_j$ and colum-indices from $D_j.$

The character, $char(M_D)(x_1,\dotsc,x_n)$ of $\mathcal{M}_D$ is defined as the trace of the map $X : \mathcal{M}_D \to \mathcal{M}_D,$ where $X = (x_1,\dotsc,x_n)$ is a diagonal matrix acting on $\setC[Y].$ Note that for $C \leq D,$

\[ \left( \prod_{j=1}^n \det( Y_{D_j}^{C_j} ) \right) \cdot X = \prod_{j=1}^n \prod_{i \in C_j} x_i^{-1} \det( Y_{D_j}^{C_j} ) \]

so we see that all polynomials $\det( Y_{D_j}^{C_j} )$ with $C \leq D$ are eigenvectors, and do in fact span $\mathcal{M}_D.$ It was shown in [KP87KP04] that the Schubert polynomial indexed by $\omega$ is related to the character of $\mathcal{M}_{D(\omega)},$ via

\[ \schubert_\omega(x_1,\dotsc,x_n) = char(M_{D(\omega)})(x^{-1}_1,\dotsc,x^{-1}_n). \]

Gelfand–Tsetlin polytopes

In [LMD19b], the authors express the Schubert polynomials as a projection of a Minkowski sum of Gelfand–Tsetlin polytopes. This generalizes the way Schur polynomials are expressible as an integer point transform of a single Gelfand–Tsetlin polytope.

See also a similar result in [FMD18], using the integer point transforms of generalized permutahedra.

Block decomposition formula

If $\sigma \in \symS_j$ and $\tau \in \symS_{k},$ we can compute the skew sum $\sigma \times \tau \in \symS_{j+k}.$ We then have the factorization (see [BJS93])

\[ \schubert_{\sigma \times \tau} = (x_1 \dotsm x_j)^k \schubert_{\sigma} \; \uparrow^j \! \schubert_{\tau} \]

where $\uparrow^k x_i \coloneqq x_{j+k}$ is the operator which increases the variable index by $j$ on all variables.

Grassmanian permutations

A permutation $\omega \in \symS_n$ is called Grassmanian (of descent $k$) if $\omega_i \lt \omega_{i+1}$ for all $i\neq k.$ All Grassmanian permutations are vexillary, which means it is 2143-avoiding.

A Grassmanian permutation determines a partition:

\[ \lambda(\omega) = (\omega_k - k, \omega_{k-1} - k + 1, \dotsc, \omega_1 - 1 ). \]

We then have the identity

\begin{equation*} \schurS_{\lambda(\omega)}(x_1,\dotsc,x_k) = \schubert_{\omega}(\xvec). \end{equation*}

Furthermore, the Stanley symmetric functions are obtained as a stable limit of the Schubert polynomial.

Murnaghan–Nakaygama rule

In [MS18] a Murnaghan–Nakaygama rule is proved:

\begin{equation*} \powerSum_r(x_1,\dotsc,x_k) \schubert_\omega(\xvec) = \sum (-1)^{\epsilon_k(\sigma)} \schubert_{\omega \cdot \sigma}(\xvec) \end{equation*}

Monks rule

The geometric version of this result was given by D. Monk in [Mon59]. (David Monk is a prolific IMO problem constructor.)

Let $s_r$ be a simple transposition. Then

\[ \schubert_{s_r}(\xvec) \schubert_\omega(\xvec) = \sum \schubert_{\omega t_{ij}}(\xvec) \]

where the sum is over all transpositions $t_{ij}$ such that $i\leq r \lt j$ and $\length(\omega t_{ij}) = \length(\omega)+1.$ Notice that

\[ \schubert_{s_r}(\xvec) = x_1+x_2+\dotsb + x_r. \]

A combinatorial proof is given in [CT18], and a bijective proof using bumpless pipe dreams can be found in [Hua20a]. Huang also proves Monk's rule for the double Schubert polynomials with this model.

Pieri rule

F. Sotille [Sot96] provides the following Pieri-type formulas for Schubert polynomials. Let $\omega \in \symS_n,$ then

\[ \completeH_{m}(x_1,\dotsc,x_k) \schubert_\omega(\xvec) = \sum_{\omega'} \schubert_{\omega'}(\xvec) \]

where the sum run over all $w = w't_{a_1b_1}\dotsm t_{a_mb_m}$ such that $a_i \leq k \leq b_i,$ $\length(w't_{a_1b_1}\dotsm t_{a_ib_i}) = \length(w')+i$ and all $b_i$ distinct.

Similarly,

\[ \elementaryE_{m}(x_1,\dotsc,x_k) \schubert_\omega(\xvec) = \sum_{\omega'} \schubert_{\omega'}(\xvec) \]

with the same sum as above, but now the $a_i$ are distinct.

Sotille rule

There is a rule for multiplying $\schubert_\omega(\xvec)$ with a Schur polynomial indexed by a hook.

Cauchy identity

By letting $w=\omega_0,$ in the Giambelli formula for double Schubert polynomials, one can prove the following Cauchy identity for Schubert polynomials:

\[ \prod_{i+j \leq n} (x_i - y_j) = \sum_{\omega} \schubert_{\omega}(\xvec) \schubert_{\omega_0 \omega}(-\yvec). \]

Littlewood–Richardson rule

Problem.

Give a combinatorial interpretation of the coefficients in the product

\[ \schubert_u(\xvec) \schubert_v(\xvec) = \sum_{w} c^w_{uv} \schubert_w(\xvec). \]

Due to the geometric interpretation of Schubert polynomials, it is known that the coefficients $c^w_{uv}$ are non-negative integers.

Note that the coefficients $c^w_{uv}$ generalize the classical Littlewood–Richardson coefficients in the Littlewood–Richardson rule for Schur polynomials. This is a major open problem in Schubert calculus and algebraic combinatorics.

This problem is closely related to the Fomin–Kirillov conjecture, see [Conjecture 8.1 and Problem 8.3, FK99]. It concerns the evaluation of Schubert polynomials at Dunkl elements.

There are many special cases proved for this problem, one particular case is treated in [Hua22], regarding products of two permutations with separated descents.

Matthew J. Samuel has a python package for computing products of Schubert polynomials.

Expansion in key polynomials

There are several proofs of the fact that Schubert polynomials expand positively into key polynomials, the first proof appearing in [LS90b].

One recent proof is by using crystal bases, [AS18b].

Sum of elementary

Let $\omega \in \symS_{n+1},$ and let $\elementaryE_{j}(m) = \elementaryE_{j}(x_1,\dotsc,x_m)$ denote the elementary symmetric functions of degree $j$ in $m$ variables. Then there is a unique way to express $\schubert_\omega(\xvec)$ as

\[ \schubert_\omega(\xvec) = \sum a_{k_1 \dotsc k_n} \elementaryE_{k_1}(1) \elementaryE_{k_2}(2) \dotsm \elementaryE_{k_n}(n) \]

where the sum ranges over integers such that $0 \leq k_i \leq i$ and $k_1+\dotsb + k_n = \length(\omega).$ This expansion is the starting point for defining the quantum Schubert polynomials. The coefficients $a_{k_1 \dotsc k_n}$ are in general not always positive. These coefficients are studied in [Win98] but many questions are left unanswered.

Problem (See [MS15b]).

For each $n,$ find a permutation $w\in\symS_n$ which maximizes $\schubert_w(1,1,\dotsc,1)$ and find the maximal value.

The sequence is given as A284661. See also Richard Stanley's Some Schubert Shenanigans.

Type B/C/D Schubert polynomials

In type $B,$ there are combinatorial analogues of Schubert polynomials introduced in [FK96a]. They also introduce type $B$ Stanely symmetric functions.

Divided difference formulas for Schubert polynomials in types $B,$ $C$ and $D$ were introduced by Billey and Haiman [BH95]. See also S. Billey's PhD thesis on Schubert polynomials for classical groups.

Type $B,$ $C$ and $D$ double Schubert polynomials are defined in [IMN11].

Skew Schubert polynomials

In [LS03], a skew version of Schubert polynomials are defined. They expand positively into Schubert polynomials, and a formula in the monomial basis is given.

Double Schubert polynomials

The double Schubert polynomials were introduced by I. G. Macdonald [Mac91]

They are defined as

\begin{equation*} \schubert_\omega(x_1,\dotsc,x_n,y_1,\dotsc,y_n) = \partial_{\omega^{-1}\omega_0} \prod_{i + j \leq n} (x_i-y_j). \end{equation*}

where the divided difference operator act on the $\xvec$-variables. By letting $y_i=0,$ we get the usual Schubert polynomials. The double Schubert polynomials generalize the double Schur polynomials.

There is a pipe-dream formula, expressing $\schubert_\omega(\xvec,\yvec) $ as a sum over pipe dreams:

\[ \begin{equation*} \schubert_\omega(\xvec,\yvec) = \sum_{D \in RC(\omega) } \prod_{(i,j) \in D} \left(x_{i} - y_{j} \right). \end{equation*} \]

See also the survey by N. Bergeron and S. Billey [BB93].

In a recent paper, A. Knutson [Knu19] provides new proofs that several combinatorial formulas for the double Schubert polynomials.

Giambelli formula

The Giambelli formula for double Schubert polynomials state that

\begin{equation*} \schubert_w(\xvec;\yvec) = \sum_{\substack{ v^{-1}u=w \\ \length(u)+\length(v) = \length(w) }} (-1)^{\length(v)}\schubert_u(\xvec) \schubert_v(\yvec). \end{equation*}

Affine Schubert polynomials

In [Lee15], an affine extension of Schubert polynomials (indexed by affine permutations) is defined via divided difference operators after being introduced by T. Lam in [Lam06b].

In the Youtube video, Seungjin Lee introduces the affine Schubert polynomials. See 47:16 for the definition.

In [Thm. 6.1, LLS19], the authors prove that the affine Schubert polynomials expand positively in the monomial basis.

Involution Schubert polynomials

The involution Schubert polynomials were introduced in [WY16]. Additional properties are proved in [HMP18], where the authors introduce the name of the family of polynomials. The following definition is from that paper.

Let $y \in I_n,$ the set of involutions in $\symS_n,$ and let $A(y)$ denote the set of minimal-length permutations $w$ such that $y = w^{-1} \circ w.$ That is, we consider all minimal factorizations of $y$ into simple transpositions of the form $(s_{i_1}\dotsc s_{i_k})\circ (s_{i_k}\dotsc s_{i_1}).$ Then let

\[ \ischubert_y(x_1,\dotsc,x_n) \coloneqq \sum_{w \in A(y)} \schubert_w(x_1,\dotsc,x_n) \]

There is also a recursive way to produce these polynomials via divided difference operators.

The stable limit of these yield the involution Stanley symmetric functions.

A combinatorial model using involution pipe dreams for these polynomials is given by Hamaker, Marberg and Pawlowski in [HMP19].

Quantum Schubert polynomials

The quantum Schubert polynomials $\schubert^q_\omega(\xvec)$ is a deformation of the Schubert polynomials by a vector $q=(q_1,\dotsc,q_{n-1}).$ These were introduced in [FGP97].

Recall the formula that expresses the Schubert polynomials as sums of products of elementary symmetric functions:

\[ \schubert_\omega(\xvec) = \sum a_{k_1 \dotsc k_n} \elementaryE_{k_1}(1) \elementaryE_{k_2}(2) \dotsm \elementaryE_{k_n}(n) \]

The quantum Schubert polynomials are then defined as

\[ \schubert_\omega(\xvec) = \sum a_{k_1 \dotsc k_n} \elementaryE^{q}_{k_1}(1) \elementaryE^{q}_{k_2}(2) \dotsm \elementaryE^{q}_{k_n}(n) \]

where

\[ \sum_{i=0}^k \elementaryE^{q}_{k}(i)t^i = \det(1+tG_k) \text{ and } G_k= \begin{vmatrix} x_1 & q_1 & 0 & \ldots & 0 \\ -1 & x_2 & q_2 & \ldots & 0 \\ 0 & -1 & x_3 & \ldots & 0 \\ \vdots & \vdots & & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & x_k \\ \end{vmatrix} \]

By letting $q_i=0,$ one recovers the classical Schubert polynomials.

Quantum Monks rule

The following refinement of Monk's rule is given in [Theorem 7.1, FGP97]. Let $s_r$ be a simple transposition. Then

\[ \schubert^q_{s_r}(\xvec) \schubert^q_\omega(\xvec) = (x_1+x_2+\dotsb + x_r) \schubert^q_\omega(\xvec) = \sum \schubert^q_{\omega t_{ab}}(\xvec) + \sum q_{cd} \schubert^q_{\omega t_{cd}}(\xvec) \]

where the first sum is over all transpositions $t_{ab}$ such that $a\leq r \lt b$ and $\length(\omega t_{ab}) = \length(\omega)+1,$ and the second sum runs over all transpositions $t_{cd}$ such that $c\leq r \lt d$ and $\length(\omega t_{cd}) = \length(\omega)-\length(t_{cd}) = \length(\omega)-2(d-c)+1.$

Here, $q_{cd} = q_c q_{c+1} \dotsm q_d.$

Quantum Pieri rule

Quantum Sotille rule

Quantum Murnaghan–Nakaygama

This is work in progress (2018), by authors BBCSS.

Quantum Double Schubert polynomials

The double quantum Schubert polynomials were introduced by A. Kirillov and T. Maeno [KM00].

Cauchy identity

In [KM00], the following Cauchy identity for quantum double Schubert polynomials is given:

\[ \sum_{\omega \in \symS_n} \schubert^q_\omega(\xvec) \schubert^q_{\omega \omega_0}(\yvec) = \schubert^q_{\omega_0}(\xvec;\yvec) \]

Universal Schubert polynomials

The universal Schubert polynomials were introduced by W. Fulton, [Ful99] and generalize the (double) quantum Schubert polynomials.

The double universal Schubert polynomials are defined via

\begin{equation*} \schubert_w(c;d) = \sum_{u,v} (-1)^{\length(v)}\schubert_u(c) \schubert_v(d) \end{equation*}

as for double Schubert polynomials.

Twisted Schubert polynomials

The twisted Schubert polynomials are defined via $\tilde{\schubert}_{\omega_0}=x_1^{n-1} x_2^{n-2}\dotsm x_{n-1},$ and the recursion $\tilde{\schubert}_{\omega s_i}= (s_i + \partial_i)\tilde{\schubert}_{\omega}.$

It was recently proved in [Liu19] that these are positive in the monomial basis. This is the earliest reference that I could find that explicitly define these polynomials. They are implicitly studied in earlier works, and are related to the Chern–Schwartz–MacPherson classes of Schubert cells in flag varieties.

References