Chromotopy

Stanley symmetric functions

Besides the original definition in terms of reduced words, the Stanley symmetric functions $F_w$ can be computed in at least three ways, which seem mysteriously different enough to me that it’s worth talking about all of them.

Combinatorics

It turns out that in the Schur expansion $F_w = \sum_{\lambda} a_{\lambda w} s_{\lambda}$, the coefficients $a_{\lambda w}$ are nonnegative integers, so it’s natural to ask for a combinatorial interpretation for them. Edelman and Greene gave a nice answer to this question. The column word of a semistandard tableau $T$ is the word gotten by reading up the first column, then the second column, and so on. Say $EG(w)$ is the set of semistandard tableaux whose column words are reduced words for $w$. Then $a_{\lambda w}$ is the number of tableaux in $EG(w)$ with shape $\lambda$.

For example, $Red(2143) = \{13, 31\}$, and each of these is the column word of exactly one tableau: $\begin{array}{cc} 1 & 3 \end{array}$ and $\begin{array}{c} 1\\ 3 \end{array}$ respectively, so $F_{2143} = s_{11} + s_{2}$. $Red(321) = \{121, 212\}$, but only the second of these can be the column word of a semistandard tableau, namely $\begin{array}{cc} 1 & 2\\ 2 & \end{array}$, so $F_{321} = s_{21}$.

In fact Edelman-Greene do better than this. Previously I mentioned that the equality $\mid Red(w)\mid = \sum_{\lambda} a_{w\lambda} f^{\lambda}$ falls out of the definition of $F_w$, where $f^{\lambda}$ is the number of standard tableaux of shape $\lambda$. Given the interpretation of $a_{w\lambda}$, this  suggests there should be a bijection

$$Red(w) \leftrightarrow \{(P, Q) : P \in EG(w), \text{shape}(P) = \text{shape}(Q), Q \text{ standard} \}.$$

Edelman-Greene provide just such a bijection. If you know the Robinson-Schensted(-Knuth) correspondence, this should look familiar—Edelman-Greene’s bijection is very similar, and includes Robinson-Schensted as the special case $w = 2143\cdots (2n)(2n-1)$.

This also solves the problem of sampling uniformly from $Red(w)$, as long as we can compute $EG(w)$. For example, take the special case $w = n(n-1)\cdots 1$, where $EG(w)$ has just one element $P_0$ (because $F_w = s_{(n-1, n-2, \ldots, 1)}$). It turns out to be easy to uniformly choose a standard tableau $Q$ of a particular shape (using the “hook walk” algorithm), so choose $Q$ with the same shape as $P_0$ and apply the Edelman-Greene bijection to the pair $(P_0, Q)$ to obtain a reduced word.

Representation theory

The Edelman-Greene bijection shows that the coefficients $a_{w\lambda}$ are nonnegative integers. Since the Schur functions $s_{\lambda}$ are irreducible characters for $GL(E)$ (if $\text{dim}(E)$ is large enough), this means $F_w$ is the character of a $GL(E)$-module. This module turns out to have a nice description not relying on knowing its decomposition into irreducibles.

Here’s how to get the module $E^{\lambda}$ whose character is $s_{\lambda}$ (called a Schur module). Start with the left $GL(E)$-module $E^{\otimes n}$, where $n = \mid\lambda\mid$. This is also a right $S_n$-module, permutations acting by permuting tensor factors. Construct the Young symmetrizer $c_{\lambda}$, a member of the group algebra $\mathbb{C}[S_n]$. Then the Schur module $E^{\lambda}$ is $E^{\otimes n}c_{\lambda}$.

The construction of the Young symmetrizer $c_{\lambda}$ uses the Ferrers diagram of $\lambda$, but only actually relies on having a set of boxes to put numbers in, not that the boxes are arranged in any particular way. That is, any finite set $D \subset \mathbb{N}^2$ has a Young symmetrizer $c_D$ using the same definition, and so there’s a $GL(E)$-module $E^D = E^{\otimes n}c_D$.

The Stanley symmetric function $F_w$ turns out to be the character of one of these guys. The inversion set of a permutation $w$ is $I(w) = \{(i,j) : i < j, w(i) > w(j)\}$. Then $F_w$ is the character of $E^{I(w^{-1})}$. [I’m not sure who to credit this to… Kraśkiewicz and Pragacz? Let’s say yes, Poles unite!!]

For example,

$$I(321) = \{(1,2),(1,3),(2,3)\} = \begin{array}{ccc} \cdot & \square & \square \\ & \cdot & \square \\ & & \cdot \end{array}$$

is more or less the Ferrers diagram of $(2,1)$, so we recover again that $F_{321} = s_{21}$. The equality $F_{2143} = s_{11} + s_{2}$ from this point of view ends up being the classic decomposition of 2-tensors into symmetric and antisymmetric parts, $E \otimes E \simeq Sym^2(E) \oplus \bigwedge^2(E)$.

Geometry

Schubert calculus, in modern terms, amounts to doing calculations in the cohomology ring of Grassmannians or flag varieties (or more generally, a semisimple algebraic group mod a parabolic subgroup). Take $B^+, B^-$ the subgroups of upper and lower triangular matrices, respectively, in $GL_n$. A (complete) flag in $\mathbb{C}^n$ is a sequence of subspaces $0 = V_0 \subseteq V_1 \subseteq \cdots \subseteq V_n = \mathbb{C}^{n}$ with $\text{dim}(V_i) = i$. The collection of flags in $\mathbb{C}^n$ is naturally in bijection with the flag variety $Fl(n) = GL_n / B^+$, a projective variety.

The LU decomposition (or LPU) gives the Bruhat decomposition of $GL_n$: the disjoint union $GL_n = \bigcup_{w \in S_n} B^- w B^+$, interpreting $w$ as a permutation matrix. This descends to a decomposition $Fl(n) = \bigcup_{w \in S_n} B^- w B^+ / B^+$. Each $B^- w B^+ / B^+$ is a Schubert cell $X_w^o$, homeomorphic to some $\mathbb{C}^k$; the Schubert variety $X_w$ is the closure of $X_w^o$. The Schubert cells form a CW decomposition of $Fl(n)$, and have even real dimensions, so the classes $[X_w]$ Poincaré dual to the Schubert varieties form a $\mathbb{Z}$-basis of $H^*(Fl(n), \mathbb{Z})$.

As for the ring structure, by realizing $Fl(n)$ as the total space of the top of a tower of projective bundles over $\mathbb{P}^1$, one can compute that $H^*(Fl(n))$ is a certain quotient of $\mathbb{Z}[x_1, \ldots, x_n]$. Lots of classical enumerative geometry questions can be phrased in terms of counting intersection points between various Schubert varieties, so one should try to find polynomials representing the Schubert classes $[X_w]$ in this picture of $H^*(Fl(n))$.

Lascoux and Schützenberger found a nice set of such polynomials, the Schubert polynomials $\mathfrak{S}_w$. They have the nice property of being stable under the inclusions $Fl(n) \to Fl(n+1)$, meaning that for $w \in S_n$, $\mathfrak{S}_w$ represents $[X_w]$ in $H^*(Fl(N))$ whenever $N \geq n$, if we view $w$ as a permutation of $[N]$ fixing $n+1, \ldots, N$.

Schubert polynomials enjoy another kind of stability. Write $1^m \times w$ for the permutation $1\cdots m (w(1)+m)(w(2)+m) \cdots$. It turns out that as $m \to \infty$, $\mathfrak{S}_{1^m \times w}$ converges to a power series in $x_1, x_2, \ldots$. This power series is exactly $F_{w^{-1}}$!

A Serif blog | View archive of 36 posts