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: $% $ 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 $% $, 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

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 $% 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,

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}}$!