The structure of the Garsia-Procesi modules $R_\mu$

Somehow, in all the time I’ve posted here, I’ve not yet described the structure of my favorite graded $S_n$-modules. I mentioned them briefly at the end of the Springer Correspondence series, and talked in depth about a particular one of them – the ring of coinvariants – in this post, but it’s about time for…

The Garsia-Procesi modules!

Also known as the cohomology rings of the Springer fibers in type $A$, or as the coordinate ring of the intersection of the closure of a nilpotent conjugacy class of $n\times n$ matrices with a torus, with a link between these two interpretations given in a paper of DeConcini and Procesi. But the work of Tanisaki, and Garsia and Procesi, allows us to work with these modules in an entirely elementary way.

Using Tanisaki’s approach, we can define $$R_{\mu}=\mathbb{C}[x_1,\ldots,x_n]/I_{\mu},$$ where $I_{\mu}$ is the ideal generated by the partial elementary symmetric functions defined as follows. Recall that the elementary symmetric function $e_d(z_1,\ldots,z_k)$ is the sum of all square-free monomials of degree $d$ in the set of variables $z_i$. Let $S\subset\{x_1,\ldots,x_n\}$ with $|S|=k$. Then the elementary symmetric function $e_r(S)$ in this subset of the variables is called a partial elementary symmetric function, and we have $$I_{\mu}=(e_r(S) : k-d_k(\mu) \lt r \le k, |S|=k).$$ Here, $d_k(\mu)=\mu’_n+\mu’_{n-1}+\cdots+ \mu’_{n-k+1}$ is the number of boxes in the last $k$ columns of $\mu$, where we pad the transpose partition $\mu’$ with $0$’s so that it has $n$ parts.

This ring $R_\mu$ inherits the natural action of $S_n$ on $\mathbb{C}[x_1,\ldots,x_n]$ by permuting the variables, since $I_\mu$ is fixed under this action. Since $I_\mu$ is also a homogeneous ideal, $R_\mu$ is a graded $S_n$-module, graded by degree.

To illustrate the construction, suppose $n=4$ and $\mu=(3,1)$. Then to compute $I_{\mu}$, first consider subsets $S$ of $\{x_1,\ldots,x_4\}$ of size $k=1$. We have $d_1(\mu)=0$ since the fourth column of the Young diagram of $\mu$ is empty (see image below), and so in order for $e_r(S)$ to be in $I_\mu$ we must have $1-0\lt r \le 1$, which is impossible. So there are no partial elementary symmetric functions in $1$ variable in $I_\mu$.


For subsets $S$ of size $k=2$, we have $d_2(\mu)=1$ since there is one box among the last two columns (columns $3$ and $4$) of $\mu$, and we must have $2-1\lt r\le 2$. So $r$ can only be $2$, and we have the partial elementary symmetric functions $e_2(S)$ for all subsets $S$ of size $2$. This gives us the six polynomials $$x_1x_2,\hspace{0.3cm} x_1x_3,\hspace{0.3cm} x_1x_4,\hspace{0.3cm} x_2x_3,\hspace{0.3cm} x_2x_4,\hspace{0.3cm} x_3x_4.$$

For subsets $S$ of size $k=3$, we have $d_3(\mu)=2$, and so $3-2 \lt r\le 3$. We therefore have $e_2(S)$ and $e_3(S)$ for each such subset $S$ in $I_\mu$, and this gives us the eight additional polynomials $$x_1x_2+x_1x_3+x_2x_3, \hspace{0.5cm}x_1x_2+x_1x_4+x_2x_4,$$ $$x_1x_3+x_1x_4+x_3x_4,\hspace{0.5cm} x_2x_3+x_2x_4+x_3x_4,$$ $$x_1x_2x_3, \hspace{0.4cm} x_1x_2x_4, \hspace{0.4cm} x_1x_3x_4,\hspace{0.4cm} x_2x_3x_4$$

Finally, for $S=\{x_1,x_2,x_3,x_4\}$, we have $d_4(\mu)=4$ and so $4-4\lt r\le 4$. Thus all of the full elementary symmetric functions $e_1,\ldots,e_4$ in the four variables are also relations in $I_{\mu}$. All in all we have
I_{(3,1)}= &(e_2(x_1,x_2), e_2(x_1,x_3),\ldots, e_2(x_3,x_4), \\
& e_2(x_1,x_2,x_3), \ldots, e_2(x_2,x_3,x_4), \\
& e_3(x_1,x_2,x_3), \ldots, e_3(x_2,x_3,x_4), \\
& e_1(x_1,\ldots,x_4), e_2(x_1,\ldots,x_4), e_3(x_1,\ldots,x_4), e_4(x_1,\ldots,x_4))

As two more examples, it’s clear that $R_{(1^n)}=\mathbb{C}[x_1,\ldots,x_n]/(e_1,\ldots,e_n)$ is the ring of coninvariants under the $S_n$ action, and $R_{(n)}=\mathbb{C}$ is the trivial representation. So $R_\mu$ is a generalization of the coinvariant ring, and in fact the graded Frobenius characteristic of $R_\mu$ is the Hall-Littlewood polynomial $\widetilde{H}_\mu(x;q)$.

Where do these relations come from? The rings $R_\mu$ were originally defined as follows. Let $A$ be a nilpotent $n\times n$ matrix over $\mathbb{C}$. Then $A$ has all $0$ eigenvalues, and so it is conjugate to a matrix in Jordan normal form whose Jordan blocks have all $0$’s on the diagonal. The sizes of the Jordan blocks, written in nonincreasing order form a partition $\mu’$, and this partition uniquely determines the conjugacy class of $A$. In other words:

There is exactly one nilpotent conjugacy class $C_{\mu’}$ in the space of $n\times n$ matrices for each partition $\mu’$ of $n$.

The closures of these conjugacy classes $\overline{C_{\mu’}}$ form closed matrix varieties, and their coordinate rings were studied here. However, they are easier to get a handle on after intersecting with the set $T$ of diagonal matrices, leading to an interesting natural question: what is the subvariety of diagonal matrices in the closure of the nilpotent conjugacy class $C_{\mu’}$? Defining $R_\mu=\mathcal{O}(\overline{C_{\mu’}}\cap T)$, we obtain the same modules as above.

Tanisaki found the presentation for $R_\mu$ given above using roughly the following argument. Consider the matrix $A-tI$, where $A\in C_{\mu’}$. Then one can show (see, for instance, the discussion of invariant factors and elementary divisors in the article on Smith normal form on Wikipedia) that the largest power of $t$ dividing all of the $k\times k$ minors of $A-tI$, say $t^{d_k}$, is fixed under conjugation, so we can assume $A$ is in Jordan normal form. Then it’s not hard to see, by analyzing the Jordan blocks, that this power of $t$ is $t^{d_k(\mu)}$ where $\mu$ is the transpose partition of $\mu’$ and $d_k(\mu)$ is defined as above – the sums of the ending columns of $\mu$.

It follows that any element of the closure of $C_\mu$ must also have this property, and so if $X=\mathrm{diag}(x_1,\ldots,x_n)\in \overline{C_\mu}\cap T$ then we have $$t^{d_k(\mu)} | (x_{i_1}-t)(x_{i_2}-t)\cdots (x_{i_k}-t)$$ for any subset $S=\{x_{i_1},\ldots,x_{i_k}\}$ of $\{x_1,\ldots,x_n\}$. Expanding the right hand side as a polynomial in $t$ using Vieta’s formulas, we see that the elementary symmetric functions $e_r(S)$ vanish on $X$ as soon as $r \gt k-d_k(\mu)$, which is exactly the relations that describe $I_\mu$ above.

It takes somewhat more work to prove that these relations generate the entire ideal, but this can be shown by showing that $R_\mu$ has the right dimension, namely the multinomial coefficient $\binom{n}{\mu}$. And for that, we’ll discuss on page 2 the monomial basis of Garsia and Procesi.


Sometimes it’s the missteps in life that lead to the greatest adventures down the road.

For me, my pursuit of a Ph.D. in mathematics, specifically in algebraic combinatorics, might be traced back to my freshman year as an undergraduate at MIT. Coming off of a series of successes in high school math competitions and other science-related endeavors (thanks to my loving and very mathematical family!), I was a confident and excited 18-year old whose dream was to become a physicist and use my mathematical skills to, I don’t know, come up with a unified field theory or something.

Me at the age of 18-ish.

Me at the age of 18-ish.

But I loved pure math too, and a number of my friends were signed up for the undergraduate Algebraic Combinatorics class in the spring, so my young ambitious self added it to my already packed course load. I had no idea what “Algebraic Combinatorics” even meant, but I did hear that it was being taught by Richard Stanley, a world expert in the area. How could I pass up that chance? What if he didn’t teach it again before I left MIT?

On the first day of the class, Stanley started with a simple combinatorial question. It was something like the following: In a complete graph with $n$ vertices, how many walks of length $k$ starting at vertex $v$ end up back at vertex $v$ on the last step? For instance, if $n=5$ and $k=2$, the graph looks like: graph5-noblue and there are four closed walks of length two, from $v$ to any other vertex and back again:


There is an elementary (though messy) way to solve this, but Stanley went forth with an algebraic proof. He considered the adjacency matrix $A$ of the complete graph, and showed that the total number of loops of length $k$ starting from any vertex is the trace of $A^k$. One can then compute this trace using eigenvalues and divide by $n$ to get the number of loops starting at $v$. Beautiful!

I remember sitting in my seat, wide-eyed, watching Richard Stanley quietly but authoritatively discuss the technique. It was incredible to me that advanced tools from linear algebra could be used to so elegantly solve such a simple, concrete problem. To use a term from another area of algebraic combinatorics, I was hooked.

But I was also a freshman, and didn’t yet have a strong grasp of some of the other algebraic concepts being used in the course. I studied hard but wound up with a B+ in the class. Me, get a B+ in a math class? I was horrified, my 18-year-old Little-Miss-Perfect confidence shattered. Now, not only was I fascinated with the subject, I gained respect for it. It was a worthy challenge, and I couldn’t help but come back for more.

In the years that followed, I took more courses on similar subjects and wrote several undergraduate research papers. I dabbled in other areas as well, but was always drawn back to the interplay between combinatorics and algebra. I now find myself, as of Friday, May 20, 2016, having completed my Ph.D. at UC Berkeley on a topic in algebraic combinatorics…

Maria Grad - Web - 19

…and I often wonder how much that silly little B+ motivated me throughout the years.

(See page 2 for a summary of my thesis. My full thesis can be found here.)

What do Schubert curves, Young tableaux, and K-theory have in common? (Part III)

This is the third and final post in our expository series of posts (see Part I and Part II) on the recent paper coauthored by Jake Levinson and myself.

Last time, we discussed the fact that the operator $\omega$ on certain Young tableaux is actually the monodromy operator of a certain covering map from the real locus of the Schubert curve $S$ to $\mathbb{RP}^1$. Now, we’ll show how our improved algorithm for computing $\omega$ can be used to approach some natural questions about the geometry of the curve $S$. For instance, how many (complex) connected components does $S$ have? What is its genus? Is $S$ a smooth (complex) curve?

The genus of $S$

The arithmetic genus of a connected curve $S$ can be defined as $g=1-\chi(\mathcal{O}_S)$ where $$\chi(\mathcal{O}_S)=\dim H^0(\mathcal{O}_S)-\dim H^1(\mathcal{O}_S)$$ is the Euler characteristic and $\mathcal{O}_S$ is the structure sheaf. So, to compute the genus it suffices to compute the Euler characteristic, which can alternatively be defined in terms of the $K$-theory of the Grassmannian.

The $K$-theory ring $K(\mathrm{Gr}(n,k))$

The $K$-theory ring $K(X)$ of a scheme $X$ is defined as follows. First, consider the free abelian group $G$ generated by isomorphism classes of locally free coherent sheaves (a.k.a. vector bundles) on $X$. Then define $K(X)$, as a group, to be the quotient of $G$ by “short exact sequences”, that is, the quotient $G/H$ where $H$ is the subgroup generated by expressions of the form $[\mathcal{E}_1]+[\mathcal{E}_2]-[\mathcal{E}]$ where $0\to \mathcal{E}_1 \to \mathcal{E} \to \mathcal{E}_2 \to 0$ is a short exact sequence of vector bundles on $X$. This gives the additive structure on $K(X)$, and the tensor product operation on vector bundles makes it into a ring. It turns out that, in the case that $X$ is smooth (such as a Grassmannian!) then we get the exact same ring if we remove the “locally free” restriction and consider coherent sheaves modulo short exact sequences.

Where does this construction come from? Well, a simpler example of $K$-theory is the construction of the Grothendieck group of an abelian monoid. Consider an abelian monoid M (recall that a monoid is a set with an associative binary operation and an identity element, like a group without inverses). We can construct an associated group $K(M)$ by taking the quotient free abelian group generated by elements $[m]$ for $m\in M$ by the subgroup generated by expressions of the form $[m]+[n]-[m+n]$. So, for instance, $K(\mathbb{N})=\mathbb{Z}$. In a sense we are groupifying monoids. The natural monoidal operation on vector spaces is $\oplus$, so if $X$ is a point, then all short exact sequences split and the $K$-theory ring $K(X)$ is the Grothendieck ring of this monoid.

A good exposition on the basics of $K$-theory can be found here, and for the $K$-theory of Grassmannians, see Buch’s paper. For now, we’ll just give a brief description of how the $K$-theory of the Grassmannian works, and how it gives us a handle on the Euler characteristic of Schubert curves.

Recall from this post that the CW complex structure given by the Schubert varieties shows that the classes $[\Omega_\lambda]$, where $\lambda$ is a partition fitting inside a $k\times (n-k)$ rectangle, generate the cohomology ring $H^\ast(\mathrm{Gr}(n,k))$. Similarly, the $K$-theory ring is a filtered ring generated by the classes of the coherent sheaves $[\mathcal{O}_{\lambda}]$ where if $\iota$ is the inclusion map $\iota:\Omega_\lambda\to \mathrm{Gr}(n,k)$, then $\mathcal{O}_\lambda=\iota_\ast \mathcal{O}_{\Omega_\lambda}$. Multiplication of these basic classes is given by a variant of the Littlewood-Richardson rule: $$[\mathcal{O}_\lambda]\cdot [\mathcal{O}_\nu]=\sum_\nu (-1)^{|\nu|-|\lambda|-|\mu|}c^\nu_{\lambda\mu}[\mathcal{O}_\nu]$$ where if $|\nu|=|\lambda|+|\mu|$ then $c^{\nu}_{\lambda\mu}$ is the usual Littlewood-Richardson coefficient. If $|\nu|<|\lambda|+|\mu|$ then the coefficient is zero, and if it $|\nu|>|\lambda|+|\mu|$ then $c^{\nu}_{\lambda\mu}$ is a nonnegative integer. We will refer to these nonnegative values as $K$-theory coefficients.

$K$-theory and the Euler characteristic

The $K$-theory ring is especially useful in computing Euler characteristics. It turns out that the Euler characteristic gives an (additive) group homomorphism $\chi:K(X)\to \mathbb{Z}$. To show this, it suffices to show that if $0\to \mathcal{A}\to \mathcal{B}\to \mathcal{C}\to 0$ is a short exact sequence of coherent sheaves on $X$, then $\chi(\mathcal{A})+\chi(\mathcal{C})-\chi(\mathcal{B})=0$. Indeed, such a short exact sequence gives rise to a long exact sequence in cohomology:

& H^0(\mathcal{A}) & \to & H^0(\mathcal{B}) & \to & H^0(\mathcal{C}) \\
\to &H^1(\mathcal{A}) & \to & H^1(\mathcal{B}) & \to & H^1(\mathcal{C}) \\
\to &H^2(\mathcal{A}) & \to & H^2(\mathcal{B}) & \to & H^2(\mathcal{C}) \\
\cdots & & & & &

and the alternating sum of the dimensions of any exact sequence must be zero. Thus we have $$\begin{eqnarray*}0&=&\sum_i (-1)^i\dim H^i(\mathcal{A})-\sum_i (-1)^i\dim H^i(\mathcal{b})+\sum_i (-1)^i\dim H^i(\mathcal{C}) \\ &=&\chi(\mathcal{A})+\chi(\mathcal{C})-\chi(\mathcal{B})\end{eqnarray*}$$ as desired.

Therefore, it makes sense to talk about the Euler characteristic of a class of coherent sheaves in $K(X)$. In fact, in our situation, we have a closed subset $S$ of $X=\mathrm{Gr}(n,k)$, say with inclusion map $j:S\to X$, and so the Euler characteristic of the pushforward $j_\ast\mathcal{O}_S$ is equal to $\chi(\mathcal{O}_S)$ itself. We can now compute the Euler characteristic $\chi(j_\ast\mathcal{O}_S)$ using the structure of the $K$-theory ring of the Grassmannian. Indeed, $S$ is the intersection of Schubert varieties indexed by the three partitions $\alpha$, $\beta$, and $\gamma$ (see Part I). So in the $K$-theory ring, if we identify structure sheaves of closed subvarieties with their pushforwards under inclusion maps, we have $$[\mathcal{O}_S]=[\mathcal{O}_\alpha]\cdot [\mathcal{O}_\beta]\cdot [\mathcal{O}_\gamma].$$ By the $K$-theoretic Littlewood-Richardson rule described above, this product expands as a sum of integer multiples of classes $[\mathcal{O}_\nu]$ where $|\nu|\ge |\alpha|+|\beta|+|\gamma|$. But in our setup we have $|\alpha|+|\beta|+|\gamma|=k(n-k)-1$, so $\nu$ is either the entire $k\times (n-k)$ rectangle (call this $\rho$) or it is the rectangle minus a single box (call this $\rho’$). In other words, we have:

$$[\mathcal{O}_S]=c^{\rho’}_{\alpha,\beta,\gamma}[\mathcal{O}_{\rho’}]-k[\mathcal{O}_{\rho}]$$ where $k$ is an integer determined by the $K$-theory coefficients. Notice that $c^{\rho’}_{\alpha,\beta,\gamma}$ is the usual Littlewood-Richardson coefficient, and counts exactly the size of the fibers (the set $\omega$ acts on) in our map from Part II. Let’s call this number $N$.

Finally, notice that $\Omega_\rho$ and $\Omega_{\rho’}$ are a point and a copy of $\mathbb{P}^1$ respectively, and so both have Euler characteristic $1$. It follows that $$\chi(\mathcal{O}_S)=N-k.$$
Going back to the genus, we see that if $S$ is connected, we have $g=1-\chi(\mathcal{O}_S)=k-(N-1)$.

Computing $k$ in terms of $\omega$

The fascinating thing about our algorithm for $\omega$ is that certain steps of the algorithm combinatorially correspond to certain tableaux that enumerate the $K$-theory coefficients, giving us information about the genus of $S$. These tableaux are called “genomic tableaux”, and were first introduced by Pechenik and Yong.

In our case, the genomic tableaux that enumerate $k$ can be defined as follows. The data of a tableau $T$ and two marked squares $\square_1$ and $\square_2$ in $T$ is a genomic tableau if:

  1. The marked squares are non-adjacent and contain the same entry $i$,
  2. There are no $i$’s between $\square_1$ and $\square_2$ in the reading word of $T$,
  3. If we delete either $\square_1$ or $\square_2$, every suffix of the resulting reading word is ballot (has more $j$’s than $j+1$’s for all $j$).

For instance, consider the following tableaux with two marked (shaded) squares:


Property 1 means that the fourth tableau is not genomic: the marked squares, while they do contain the same entry, are adjacent squares. The first tableau above violates Property 2, because there is a $2$ between the two marked $2$’s in reading order. Finally, the second tableau above violates Property 3, because if we delete the top marked $1$ then the suffix $221$ is not ballot. The third tableau above satisfies all three properties, and so it is genomic.

Finally, consider the algorithm for $\omega$ described in Part I. Jake and I discovered that the steps in Phase 1 in which the special box does not move to an adjacent square are in bijective correspondence with the $K$-theory tableau of the total skew shape $\gamma^c/\alpha$ and content $\beta$ (where the marked squares only add $1$ to the total number of $i$’s). The correspondence is formed by simply filling the starting and ending positions of the special box with the entry $i$ that it moved past, and making these the marked squares of a genomic tableau. In other words:

The $K$-theory coefficient $k$ is equal to the number of non-adjacent moves in all Phase 1’s of the local algorithm for $\omega$.

Geometric consequences

This connection allows us to get a handle on the geometry of the Schubert curves $S$ using our new algorithm. As one illuminating example, let’s consider the case when $\omega$ is the identity permutation.

It turns out that the only way for $\omega$ to map a tableau back to itself is if Phase 1 consists of all vertical slides and Phase 2 is all horizontal slides; then the final shuffle step simply reverses these moves. This means that we have no non-adjacent moves, and so $k=0$ in this case. Since $\omega$, the monodromy operator on the real locus, is the identity, we also know that the number of real connected components is equal to $N$, which is an upper bound on the number of complex connected components (see here), which in turn is an upper bound on the Euler characteristic $\chi(\mathcal{O}_S)=\dim H^0(\mathcal{O}_S)-\dim H^1(\mathcal{O}_S)$. But the Euler characteristic is equal to $N$ in this case, and so there must be $N$ complex connected components, one for each of the real connected components. It follows that $\dim H^1(\mathcal{O}_S)=0$, so the arithmetic genus of each of these components is zero.

We also know each of these components is integral, and so they must each be isomorphic to $\mathbb{CP}^1$ (see Hartshorne, section 4.1 exercise 1.8). We have therefore determined the entire structure of the complex Schubert curve $S$ in the case that $\omega$ is the identity map, using the connection with $K$-theory described above.

Similar analyses lead to other geometric results: we have also shown that the Schubert curves $S$ can have arbitrarily high genus, and can arbitrarily many complex connected components, for various values of $\alpha$, $\beta$, and $\gamma$.

So, what do Schubert curves, Young tableaux, and $K$-theory have in common? A little monodromy operator called $\omega$.

What do Schubert curves, Young tableaux, and K-theory have in common? (Part II)

In the last post, we discussed an operation $\newcommand{\box}{\square}
\omega$ on skew Littlewood-Richardson Young tableaux with one marked inner corner, defined as a commutator of rectification and shuffling. As a continuation, we’ll now discuss where this operator arises in geometry.

Schubert curves: Relaxing a Restriction

Recall from our post on Schubert calculus that we can use Schubert varieties to answer the question:

Given four lines $\ell_1,\ell_2,\ell_3,\ell_4\in \mathbb{C}\mathbb{P}^3$, how many lines intersect all four of these lines in a point?

In particular, given a complete flag, i.e. a chain of subspaces $$0=F_0\subset F_1\subset\cdots \subset F_m=\mathbb{C}^m$$ where each $F_i$ has dimension $i$, the Schubert variety of a partition $\lambda$ with respect to this flag is a subvariety of the Grassmannian $\mathrm{Gr}^n(\mathbb{C}^m)$ defined as
$$\Omega_{\lambda}(F_\bullet)=\{V\in \mathrm{Gr}^n(\mathbb{C}^m)\mid \dim V\cap F_{n+i-\lambda_i}\ge i.\}$$

Here $\lambda$ must fit in a $k\times (n-k)$ box in order for the Schubert variety to be nonempty. In the case of the question above, we can translate the question into an intersection problem in $\mathrm{Gr}^2(\mathbb{C}^4)$ with four general two-dimensional subspaces $P_1,P_2,P_3,P_4\subset \mathbb{C}^4$, and construct complete flags $F_\bullet^{(1)},F_\bullet^{(2)},F_\bullet^{(3)},F_\bullet^{(4)}$ such that their second subspace $F^{(i)}_2$ is $P_i$ for each $i=1,2,3,4$. Then the intersection condition is the problem of finding a plane that intersects all $P_i$’s in a line. The variety of all planes intersecting $P_i$ in a line is $\Omega_\box(F_\bullet^{(i)})$ for each $i$, and so the set of all solutions is the intersection $$\Omega_\box(F_\bullet^{(1)})\cap \Omega_\box(F_\bullet^{(2)})\cap \Omega_\box(F_\bullet^{(3)})\cap \Omega_\box(F_\bullet^{(4)}).$$ And, as discussed in our post on Schubert calculus, since the $k\times(n-k)$ box has size $4$ in $\mathrm{Gr}^2(\mathbb{C}^4)$ and the four partitions involved have sizes summing to $4$, this intersection has dimension $0$. The Littlewood-Richardson rule then tells us that the number of points in this zero-dimensional intersection is the Littlewood-Richardson coefficient $c_{\box,\box,\box,\box}^{(2,2)}$.

What happens if we relax one of the conditions in the problem, so that we are only intersecting three of the Schubert varieties above? In this case we get a one-parameter family of solutions, which we call a Schubert curve.

To define a Schubert curve in general, we require a sufficiently “generic” choice of $r$ flags $F_\bullet^{(1)},\ldots, F_\bullet^{(r)}$ and a list of $r$ partitions $\lambda^{(1)},\ldots,\lambda^{(r)}$ (fitting inside the $k\times (n-k)$ box) whose sizes sum to $k(n-k)-1$. It turns out that one can choose any flags $F_\bullet$ defined by the iterated derivatives at chosen points on the rational normal curve, defined by the locus of points of the form $$(1:t:t^2:t^3:\cdots:t^{n-1})\in \mathbb{CP}^n$$ (along with the limiting point $(0:0:\cdots:1)$.) In particular, consider the flag whose $k$th subspace $F_k$ is the span of the first $k$ rows of the matrix of iterated derivatives at the point on this curve parameterized by $t$:
1 & t & t^2 & t^3 & \cdots & t^{n-1} \\
0 & 1 & 2t & 3t^2 & \cdots & (n-1) t^{n-2} \\
0 & 0 & 2 & 6t & \cdots & \frac{(n-1)!}{(n-3)!} t^{n-3} \\
0 & 0 & 0 & 6 & \cdots & \frac{(n-1)!}{(n-4)!} t^{n-3} \\
\vdots & \vdots & \vdots & \vdots &\ddots & \vdots \\
0 & 0 & 0 & 0 & \cdots & (n-1)!

This is called the osculating flag at the point $t$, and if we pick a number of points on the curve and choose their osculating flag, it turns out that they are in sufficiently general position in order for the Schubert intersections to have the expected dimension. So, we pick some number $r$ of these osculating flags, and choose exactly $r$ partitions $\lambda^{(1)},\ldots,\lambda^{(r)}$ with sizes summing to $k(n-k)-1$. Intersecting the resulting Schubert varieties defines a Schubert curve $S$.

A covering map

In order to get a handle on these curves, we consider the intersection of $S$ with another Schubert variety of a single box, $\Omega_\box(F_\bullet)$. In particular, after choosing our $r$ osculating flags, choose an $(r+1)$st point $t$ on the rational normal curve and choose the single-box partition $\lambda=(1)$. Intersecting the resulting Schubert variety $\Omega_\box(F_\bullet)$ with our Schubert curve $S$ gives us a zero-dimensional intersection, with the number of points given by the Littlewood-Richardson coefficient $c:=c^{B}_{\lambda^{(1)},\ldots,\lambda^{(r)},\box}$ where $B=((n-k)^k)$ is the $k\times (n-k)$ box partition.

By varying the choice of $t$, we obtain a partition of an open subset of the Schubert curve into sets of $c$ points. We can then define a map from this open subset of $S$ to the points of $\mathbb{CP}^1$ for which the preimage of $(1:t)$ consists of the $c$ points in the intersection given by choosing the $(r+1)$st point to be $(1:t:t^2:t^3:\cdots:t^{n-1})$.

In this paper written by my coauthor Jake Levinson, it is shown that if we choose all $r+1$ points to be real, then this can be extended to a map $S\to \mathbb{CP}^1$ for which the real locus $S(\mathbb{R})$ is a smooth, finite covering of $\mathbb{RP}^1$. The fibers of this map have size $c=c^{B}_{\lambda^{(1)},\ldots,\lambda^{(r)},\box}$. Note that this Littlewood-Richardson coefficient counts the number of ways of filling the box $B$ with skew Littlewood-Richardson tableaux with contents $\lambda^{(1)},\ldots,\lambda^{(r)},\box$ such that each skew shape extends the previous shape outwards. In addition, by the symmetry of Littlewood-Richardson coefficients, it doesn’t matter what order in which we use the partitions. It turns out that there is a canonical way of labeling the fibers by these chains of tableaux, for which the monodromy of the covering is described by shuffling operators.

Let’s be more precise, and consider the simplest interesting case, $r=3$. We have three partitions $\alpha$, $\beta$, and $\gamma$ such that $$|\alpha|+|\beta|+|\gamma|=k(n-k)-1=|B|-1.$$ Let’s choose, for simplicity, the three points $0$, $1$, and $\infty$ to define the respective osculating flags. Then we can label the points in the fiber $f^{-1}(0)$ of the map $f:S\to \mathbb{RP}^1$ by the fillings of the box with a chain of Littlewood-Richardson tableaux of contents $\alpha$, $\box$, $\beta$, and $\gamma$ in that order. Note that there is only one Littlewood-Richardson tableau of straight shape and content $\alpha$, and similarly for the anti-straight shape $\gamma$, so the data here consists of a skew Littlewood-Richardson tableau of content $\beta$ with an inner corner chosen to be the marked box. This is the same object that we were considering in Part I.

Now, we can also label the fiber $f^{-1}(1)$ by the chains of contents $\box$, $\alpha$, $\beta$, and $\gamma$ in that order, and finally label the fiber $f^{-1}(\infty)$ by the chains of contents $\alpha$, $\beta$, $\box$, and $\gamma$ in that order, in such a way that if we follow the curve $S$ along an arc from a point in $f^{-1}(0)$ to $f^{-1}(1)$ or similarly from $1$ to $\infty$ or $\infty$ to $0$, then then the map between the fibers is given by the shuffling operations described in the last post! In particular if we follow the arc from $0$ to $\infty$ that passes through $1$, the corresponding operation on the fibers is given by the “evacuation-shuffle”, or the first three steps of the operator $\omega$ described in the previous post. The arc from $\infty$ back to $0$ on the other side is given by the “shuffle” of the $\box$ past $\beta$, which is the last step of $\omega$. All in all, $\omega$ gives us the monodromy operator on the zero fiber $f^{-1}(0)$.

The following picture sums this up:


So, the real geometry of the Schubert curve boils down to an understanding of the permutation $\omega$. Our local algorithm allows us to get a better handle on the orbits of $\omega$, and hence tell us things about the number of real connected components, the lengths of these orbits, and even in some cases the geometry of the complex curve $S$.

Next time, I’ll discuss some of these consequences, as well as some fascinating connections to the $K$-theory of the Grassmannian. Stay tuned!

The Springer Correspondence, Part III: Hall-Littlewood Polynomials

This is the third post in a series on the Springer correspondence. See Part I and Part II for background.

In this post, we’ll restrict ourselves to the type A setting, in which $\DeclareMathOperator{\GL}{GL}\DeclareMathOperator{\inv}{inv} G=\GL_n(\mathbb{C})$, the Borel $B$ is the subgroup of invertible upper triangular matrices, and $U\subset G$ is the unipotent subvariety. In this setting, the flag variety is isomorphic to $G/B$ or $\mathcal{B}$ where $\mathcal{B}$ is the set of all subgroups conjugate to $B$.

The Hall-Littlewood polynomials

For a given partition $\mu$, the Springer fiber $\mathcal{B}_\mu$ can be thought of as the set of all flags $F$ which are fixed by left multiplication by a unipotent element $u$ of Jordan type $\mu$. In other words, it is the set of complete flags $$F:0=F_0\subset F_1 \subset F_2 \subset \cdots \subset F_n=\mathbb{C}^n$$ where $\dim F_i=i$ and $uF_i=F_i$ for all $i$.

In the last post we saw that there is an action of the Weyl group, in this case the symmetric group $S_n$, on the cohomology rings $H^\ast(\mathcal{B}_\mu)$ of the Springer fibers. We let $R_\mu=H^\ast(\mathcal{B}_\mu)$ denote this ring, and we note that its graded Frobenius characteristic $$\DeclareMathOperator{\Frob}{Frob}\widetilde{H}_\mu(X;t):=\Frob_t(H^\ast(\mathcal{B}_\mu))=\sum_{d\ge 0}t^d \Frob(H^{2d}(\mathcal{B}_\mu))$$ encodes all of the data determining this ring as a graded $S_n$-module. The symmetric functions $\widetilde{H}_\mu(X,t)\in \Lambda_{\mathbb{Q}(t)}(x_1,x_2,\ldots)$ are called the Hall-Littlewood polynomials.

The first thing we might ask about a Hall-Littlewood polynomial $H_\mu$ is: what is its degree as a polynomial in $t$? In other words…

What is the dimension of $\mathcal{B}_\mu$?

The dimension of $\mathcal{B}_\mu$ will tell us the highest possible degree of its cohomology ring, giving us at least an upper bound on the degree of $H_\mu$. To compute the dimension, we will decompose $\mathcal{B}_\mu$ into a disjoint union of subvarieties whose dimensions are easier to compute.

Let’s start with a simple example. If $\mu=(1,1,1,\ldots,1)$ is a single-column shape of size $n$, then $\mathcal{B}_\mu$ is the full flag variety $\mathcal{B}$, since here the unipotent element $1$ is in the conjugacy class of shape $\mu$, and we can interpret $\mathcal{B}_\mu$ as the set of flags fixed by the identity matrix (all flags). As described in Part I, the flag variety can be decomposed into Schubert cells $X_w$ where $w$ ranges over all permutations in $S_n$ and $\dim(X_w)=\inv(w)$. For instance, $X_{45132}$ is the set of flags defined by the initial row spans of a matrix of the form:
0 & 1 & \ast & \ast & \ast \\
1 & 0 & \ast & \ast & \ast \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & \ast & 0 \\
0 & 0 & 0 & 1 & 0 \end{array}\right)$$
because this matrix has its leftmost $1$’s in positions $4,5,1,3,2$ from the right in that order.

Thus the dimension of the flag variety is the maximum of the dimensions of these cells. The number of inversions in $w$ is maximized when $w=w_0=n(n-1)\cdots 2 1$, and so $$\dim(\mathcal{B})=\inv(w_0)=\binom{n}{2}.$$

We claim that in general, $\dim(\mathcal{B}_\mu)=n(\mu)$ where if $\mu^\ast$ denotes the conjugate partition, $n(\mu)=\sum \binom{\mu^\ast_i}{2}$. Another way of defining $n(\mu)$ is as the sum of the entries of the superstandard tableau formed by filling the bottom row of $\mu$ with $0$’s, the next row with $1$’s, and so on:


To show this, notice that since $\mathcal{B}_\mu$ is a subvariety of the full flag variety $\mathcal{B}$, and so $$\mathcal{B}_\mu=\mathcal{B}_\mu\cap \mathcal{B}=\bigsqcup \mathcal{B}_\mu\cap X_{w}.$$ It thus suffices to find the largest possible dimension of the varieties $\mathcal{B}_\mu\cap X_{w}$.

Let $u$ be the standard unipotent element of Jordan type $\mu$. For instance, the matrix below is the standard unipotent matrix of shape $(3,2,2)$.
Then the set $\mathcal{B}_\mu\cap X_{w}$ can be defined as the subset of $n\times n$ matrices defining flags in $X_w$ whose partial row spans are fixed by the action of $u$. Note that since the first vector is fixed by $u$, it must be equal to a linear combination of the unit vectors $e_{\mu_1}, e_{\mu_1+\mu_2},\ldots$. So we instantly see that the dimension of $\mathcal{B}_\mu\cap X_w$ is in general less than that of $X_w$.

Now, consider the permutation $$\hat{w}=n,n-\mu_1,n-\mu_1-\mu_2,\ldots,n-1,n-1-\mu_1,n-1-\mu_1-\mu_2,\ldots,\ldots.$$ Then it is not hard to see that the matrices in $X_{\hat{w}}$ whose flags are fixed by $u$ are those with $1$’s in positions according to $\hat{w}$, and with $0$’s in all other positions besides those in row $i$ from the top and column $k-\mu_1-\cdots-\mu_j$ from the right for some $i,j,k$ satisfying $i\le j$ and $\mu^\ast_1+\cdots+\mu^\ast_k< i \le \mu^\ast_1+\cdots+\mu^\ast_{k+1}$. This is a mouthful which is probably better expressed via an example. If $\mu=(3,2,2)$ as above, then $\hat{w}=7426315$, and $\mathcal{B}_\mu\cap X_{7426315}$ is the set of flags determined by the rows of matrices of the form $$\left(\begin{array}{ccccccc} 1 & 0 & 0 & \ast & 0 & \ast & 0 \\ 0 & 0 & 0 & 1 & 0 & \ast & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & \ast & 0 & \ast \\ 0 & 0 & 0 & 0 & 1 & 0 & \ast \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ \end{array}\right)$$ The first three rows above correspond to the first column of $\mu$, the next three rows to the second column, and the final row to the last column. Notice that the stars in each such block of rows form a triangular pattern similar to that for $X_{w_0}$, and therefore there are $n(\mu)=\binom{\mu^\ast_1}{2}+\binom{\mu^\ast_2}{2}+\cdots$ stars in the diagram. Thus $\mathcal{B}_\mu\cap X_{\hat{w}}$ an open affine set of dimension $n(\mu)$, and so $\mathcal{B}_\mu$ has dimension at least $n(\mu)$. A bit more fiddling with linear algebra and multiplication by $u$ (try it!) shows that, in fact, for any permutation $w$, the row with a $1$ in the $i$th position contributes at most as many stars in $\mathcal{B}_\mu\cap X_{w}$ as it does in $\mathcal{B}_\mu\cap X_{\hat{w}}$. In other words, all other components $\mathcal{B}_\mu\cap X_{w}$ have dimension at most $n(\mu)$, and so $$\dim\mathcal{B}_\mu=n(\mu).$$

The orthogonality relations

In Lusztig’s survey on character sheaves, he shows that the Hall-Littlewood polynomials (and similar functions for other Lie types) satisfy certain orthogonality and triangularity conditions that determine them completely. To state them in the type A case, we first define $\widetilde{H}_\mu[(1-t)X;t]$ to be the result of plugging in the monomials $x_1,-tx_1,x_2,-tx_2,\ldots$ for $x_1,x_2,\ldots$ in the Hall-Littlewood polynomials. (This is a special kind of plethystic substitution.) Then Lusztig’s work shows that:

  • $\left\langle \widetilde{H}_\mu(X;t),s_\lambda\right\rangle=0$ for any $\lambda<\mu$ in dominance order, and $\langle\widetilde{H}_\mu,s_\mu\rangle=1$
  • $\left\langle \widetilde{H}_\mu[(1-t)X;t],s_\lambda\right\rangle=0$ for any $\lambda>\mu$ in dominance order
  • $\left\langle \widetilde{H}_\mu(X;t),\widetilde{H}_{\lambda}[(1-t)X;t]\right\rangle=0$ whenever $\lambda\neq \mu$.

In all three of the above, the inner product $\langle,\rangle$ is the Hall inner product, which can be defined as the unique inner product for which $$\langle s_\lambda,s_\mu\rangle = \delta_{\lambda\mu}$$ for all $\lambda$ and $\mu$.

Since the Schur functions $s_\lambda$ correspond to the irreducible representations $V_\lambda$ of $S_n$, we can therefore interpret these orthogonality conditions in a representation theoretic manner. The inner product $\left \langle \widetilde{H}_\mu(X;t),s_\lambda \right\rangle$ is the coefficient of $s_\lambda$ in the Schur expansion of $\widetilde{H}_\mu$, and is therefore the Hilbert series of the isotypic component of type $V_\lambda$ in the cohomology ring $R_\mu=H^\ast(\mathcal{B}_\mu)$. Moreover, the seemingly arbitrary substitution $X\mapsto (1-t)X$ actually corresponds to taking tensor products with the exterior powers of the permutation representation $V$ of $S_n$. To be precise: $$\widetilde{H}_\mu[(1-t)X;t]=\sum_{i\ge 0} (-1)^i t^i \Frob_t(R_\mu\otimes \Lambda^i(V)).$$

It turns out that any two of the three conditions above uniquely determine the Hall-Littlewood polynomials, and in fact can be used to calculate them explicitly. On the next page, we will work out an example using the first and third conditions above.

The Springer Correspondence, Part II: The Resolution

This is a continuation of The Springer Correspondence, Part I. Here we will work with unipotent matrices to construct the Springer resolution and the cohomology of its fibers.

Unipotent Matrices and Partitions

A unipotent element of a linear algebraic group $G$ is any element $u\in G$ such that $1-u$ is nilpotent. That is, $u=1+n$ where $n^k=0$ for some $k$.

To get a sense of what unipotent matrices look like, consider the type A situation in which $\DeclareMathOperator{\GL}{GL}\newcommand{\CC}{\mathbb{C}} G=\GL_n(\CC)$. Given a unipotent element $u$, we can conjugate it by some matrix to put it in Jordan normal form. It will look something like this:
\lambda_1 & 1 & & & & & \\
& \lambda_1 & 1 & & & & \\
& & \lambda_1 & & & & \\
& & & \lambda_2 & 1 & & \\
& & & & \lambda_2 & & \\
& & & & & \ddots & \\
& & & & & & \lambda_k

It turns out that the matrix above is particularly simple in this case:

The eigenvalues $\lambda_i$ of a unipotent matrix are all $1$.

To see this, suppose $\lambda$ is an eigenvalue of $u$. We have $uv=\lambda v$ for some vector $v$, and so $$(1-u)v=(1-\lambda)v.$$ Since $1-u=n$ is nilpotent, say with $n^k=0$, we have $$(1-u)^kv=(1-\lambda)^kv=0,$$ so $(1-\lambda)^k=0$. Since $\lambda\in\CC$ and $\CC$ is a field, it follows that $\lambda=1$, as claimed.

Therefore, every unipotent matrix is conjugate to a matrix havnig all $1$’s on the diagonal, $0$’s or $1$’s on the off-diagonal, and $0$’s everywhere else. The blocks of $1$’s on the off-diagonal split the matrix into Jordan blocks, which we can order by size from greatest to least. Let the sizes of the Jordan blocks be $\mu_1,\mu_2,\ldots,\mu_k$. Then $\mu=(\mu_1,\ldots,\mu_k)$ is a partition of $n$, and determines the conjugacy class of a given unipotent matrix.

For instance, the partition $\mu=(3,2,2)$ corresponds to the conjugacy class of unipotent matrices with the Jordan canonical form below.


This can all be summed up in the following fact:

The unipotent conjugacy classes in $\GL_n$ are in one-to-one correspondence with the partitions of $n$.

Now, I know what you are thinking:

“Maria, if the unipotent conjugacy classes of $\GL_n$ and the irreducible representations of $S_n$ are both indexed by the partitions of $n$, shouldn’t there be some nice geometric construction that relates them directly?”

Indeed there is! The Springer correspondence gives just that – and furthermore relates the unipotent conjgacy classes of any Lie group $G$ to the representations of its Weyl group.

The Springer Resolution

In what follows, let $G$ be a Lie group, and let $U$ be the subvariety of $G$ consisting of all unipotent elements. The variety $U$ is not smooth in general, and to resolve the singularities we construct the variety $\widetilde{U}\subset U\times \mathcal{B}$ by $$\widetilde{U}=\{(u,B):u\in B\}.$$ Recall from the previous post that $\mathcal{B}$ is the variety of all Borel subgroups of $G$ and is isomorphic to the Flag variety $G/B$ for any Borel $B$. If we interpret $\mathcal{B}$ as the Flag variety in the case $G=\GL_n$, we can alternatively define $\widetilde{U}$ as the set of all pairs $(u,F)$ where $F$ is a flag and $u$ fixes $F$, that is, $uF_i=F_i$ for each $i$.

It turns out that $\widetilde{U}$ is smooth and the projection map $$\pi:\widetilde{U}\to U$$ is proper, so it resolves the singularities in $U$. This map is known as the Springer resolution.

The theory gets rather deep at this point, so in what follows I will state the main facts without proof. For full details I refer the interested reader to the exposition in Chapter 3 of Representation Theory and Complex Geometry by Chriss and Ginzburg.

Springer Fibers and Weyl Group Action

For any $x\in U$, define the Springer fiber $\mathcal{B}_x$ to be the fiber $\pi^{-1}(x)$ of the Springer resolution over $x$, that is, the set of all Borel subgroups of $G$ that contain $x$. Now, consider the cohomology ring $H^\ast(\mathcal{B}_x)$ over $\CC$. It turns out that there is an action of the Weyl group $W$ on this cohomology ring, called the Springer action.

There is unfortunately no direct way of defining this action. To get some intuition for where the action comes from, notice that the Springer resolution above can be lifted to the entire group: one can define $\widetilde{G}$ to be the subvariety of $G\times \mathcal{B}$ consisting of all pairs $(g,B)$ such that $g\in B$. Now, let $x$ be a regular semisimple element of $G$.

In the case $G=\GL_n$, a regular semisimple element is simply a diagonalizable element $x$ with $n$ distinct nonzero eigenvalues. If $x$ is of this form, any subspace of $\CC^n$ fixed by $x$ is a direct sum of its (linear) eigenspaces. So, if $V_1,\ldots,V_n$ are the eigenspaces corresponding to the distinct eigenvalues of $x$, any flag fixed by $x$ is of the form $$V_{\sigma(1)}\subset V_{\sigma(1)}\oplus V_{\sigma(2)}\subset \cdots \subset V_{\sigma(1)}\oplus \cdots \oplus V_{\sigma(n)}$$ for some permutation $\sigma$ of $\{1,2,\ldots,n\}$. It follows that $\mathcal{B}_x$ consists of exactly $n!$ flags, and has a natural action of $S_n$ via permuting the eigenspaces $V_i$. Therefore, $S_n$ acts on $\mathcal{B}_x$ and therefore on $H^\ast(\mathcal{B}_x)$.

In general, if $x$ is regular and semisimple, the fiber $\mathcal{B}_x$ is a finite set of size $|W|$ where $W$ is the Weyl group of $G$. The regular semisimple elements form a dense subset of $G$, and one can use this to extend the action to all cohomology rings $H^\ast(\mathcal{B}_x)$ for any $x\in G$. This is the tricky part, and involves many more constructions than fit in a reasonable-length blog post, so again I refer the reader to this awesome book.

The Springer Correspondence

We’re finally ready to state the Springer correspodence. For $x\in G$, let $d(x)$ be the dimension of the Springer fiber $\mathcal{B}_x$.

In the case $G=\GL_n$, the top cohomology groups $H^{d(x)}(\mathcal{B}_x)$ are $S_n$-modules due to the Springer action described above. Notice also that $\mathcal{B}_x$ depends only on the conjugacy class of $x$, so for $x$ in the unipotent conjugacy class with shape $\mu$, we write $\mathcal{B}_\mu$ to denote this Springer fiber, with $d(\mu)$ its dimension. It turns out that these $S_n$-modules are precisely the irreducible representations of $S_n$.

The $S_n$-module $H^{d(\mu)}(\mathcal{B}_\mu)$ is isomoprhic to the irreducible representation $V_\mu$ of $S_n$ corresponding to $\mu$.

And there you have it.

For general Lie groups $G$, the Springer correspondence is not quite as nice; the top cohomology groups $H^d(\mathcal{B}_u)$ (where $u$ is a unipotent conjugacy class) are not in general irreducible $W$-modules. However, all of the irreducible $W$-modules occur exactly once as a summand among the modules $H^d(\mathcal{B}_u)$, and there is a correspondence between the irreducible representations of $W$ and pairs $(u,\xi)$ where $u$ is a unipotent conjugacy class in $G$ and $\xi$ is an irreducible $G$-equivariant local system on $u$.

Hall-Littlewood Polynomials

The fact that the top cohomology groups $H^{d(\mu)}(\mathcal{B}_\mu)$ are so nice naturally raises the question: what about the other cohomology groups? What $S_n$-modules do we get in each degree?

In particular, let $R_\mu=H^\ast(\mathcal{B}_\mu)$. Then $R_\mu$ is a graded $S_n$-module with grading $$R_\mu=\bigoplus (R_\mu)_i=\bigoplus H^i(\mathcal{B}_\mu),$$ and so we can construct the Frobenius series
where $F$ is the Frobenius map that sends $S_n$-modules to symmetric functions.

The Hall-Littlewood polynomials $\widetilde{H}_\mu(\mathbf{x};t)$ are defined to be the Frobenius characteristics $F_t(R_\mu)$, and are therefore a class of symmetric polynomials in the variables $\mathbf{x}=x_1,x_2,\ldots$ with coefficients in $\mathbb{Q}[t]$. They have incredibly rich combinatorial structure which reveals the decomposition of $R_\mu$ into irreducible $S_n$-modules… structure that I will save for a later post. Stay tuned!

The Springer Correspondence, Part I: The Flag Variety

In prior posts, we’ve seen that the irreducible representations of the symmetric group $S_n$ are in one-to-one correspondence with the partitions of $n$, and the Schur functions give an elegant encoding of their characters as symmetric polynomials. Now we can dive a bit deeper: a geometric construction known as the Springer resolution allows us to obtain all the irreducible representations of $S_n$ geometrically, and as a side bonus give natural graded representations that will allow us to define a $q$-analog of the Schur functions known as the Hall-Littlewood polynomials.

Quite a mouthful of terminology. Let’s start at the beginning.

The Classical Flag Variety

When you think of a flag, you might imagine something like this:


Roughly speaking, a flag on a flagpole consists of:

  • a point (the bulbous part at the top of the pole),
  • a line passing through that point (the pole),
  • a plane passing through that line (the plane containing the flag), and
  • space to put it in.

Mathematically, this is the data of a complete flag in three dimensions. However, higher-dimensional beings would require more complicated flags. So in general, a complete flag in $n$-dimensional space $\mathbb{C}^n$ is a chain of vector spaces of each dimension from $0$ to $n$, each containing the previous:

$$0=V_0\subset V_1 \subset V_2 \subset \cdots \subset V_n=\mathbb{C}^n$$

with $\dim V_i=i$ for all $i$.

(Our higher-dimensional flag-waving imaginary friends are living in a world of complex numbers because $\mathbb{C}$ is algebraically closed and therefore easier to work with. However, one could define the flag variety similarly over any field $k$.)

Variety Structure

Now that we’ve defined our flags, let’s see what happens when we wave them around continuously in space. It turns out we get a smooth algebraic variety!

Indeed, the set of all possible flags in $\mathbb{C}^n$ forms an algebraic variety of dimension $n(n-1)$ (over $\mathbb{R}$), covered by open sets similar to the Schubert cells of the Grassmannian. In particular, given a flag $\{V_i\}_{i=1}^n$, we can choose $n$ vectors $v_1,\ldots,v_n$ such that the span of $v_1,\ldots,v_i$ is $V_i$ for each $i$, and list the vectors $v_i$ as row vectors of an $n\times n$ matrix. We can then perform certain row reduction operations to form a different basis $v_1^\prime,\ldots,v_n^\prime$ that also span the subspaces of the flag, but whose matrix is in the following canonical form: it has $1$’s in a permutation matrix shape, $0$’s to the left and below each $1$, and arbitrary complex numbers in all other entries.

For instance, say we start with the flag in three dimensions generated by the vectors $\langle 0,2,3\rangle$, $\langle 1, 1, 4\rangle$, and $\langle 1, 2, -3\rangle$. The corresponding matrix is $$\left(\begin{array}{ccc} 0 & 2 & 3 \\ 1 & 1 & 4 \\ 1 & 2 & -3\end{array}\right).$$ We start by finding the leftmost nonzero element in the first row and scale that row so that this element is $\newcommand{\PP}{\mathbb{P}}
\DeclareMathOperator{\inv}{inv}1$. Then subtract multiples of this row from the rows below it so that all the entries below that $1$ are $0$. Continue the process on all further rows:

$$\left(\begin{array}{ccc} 0 & 2 & 3 \\ 1 & 1 & 4 \\ 1 & 2 & -3\end{array}\right) \to \left(\begin{array}{ccc} 0 & 1 & 1.5 \\ 1 & 0 & 2.5 \\ 1 & 0 & -6\end{array}\right)\to \left(\begin{array}{ccc} 0 & 1 & 1.5 \\ 1 & 0 & 2.5 \\ 0 & 0 & 1\end{array}\right)$$

It is easy to see that this process does not change the flag formed by the partial row spans, and that any two matrices in canonical form define different flags. So, the flag variety is covered by $n!$ open sets given by choosing a permutation and forming the corresponding canonical form. For instance, one such open set in the $5$-dimensional flag variety is the open set given by all matrices of the form
0 & 1 & \ast & \ast & \ast \\
1 & 0 & \ast & \ast & \ast \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & \ast & 0 \\
0 & 0 & 0 & 1 & 0 \end{array}\right)$$

We call this open set $X_{45132}$ because it corresponds to the permutation matrix formed by placing a $1$ in the $4$th column from the right in the first row, in the $5$th from the right in the second row, and so on. The maximum number of $\ast$’s we can have in such a matrix is when the permutation is $w_0=n(n-1)\cdots 3 2 1$, in which case the dimension of the open set $X_{12\cdots n}$ is $n(n-1)/2$ over $\CC$ — or $n(n-1)$ over $\RR$, since $\CC$ is two-dimensional over $\RR$. In general, the number of $\ast$’s in the set $X_w$ is the inversion number $\inv(w)$, the number of pairs of entries of $w$ which are out of order.

Finally, in order to paste these disjoint open sets together to form a smooth manifold, we consider the closures of the sets $X_w$ as a disjoint union of other $X_w$’s. The partial ordering in which $\overline{X_w}=\sqcup_{v\le w} X_v$ is called the Bruhat order, a famous partial ordering on permutations. (For a nice introduction to Bruhat order, one place to start is Yufei Zhao’s expository paper on the subject.)

Intersection Cohomology

Now suppose we wish to answer incidence questions about our flags: which flags satisfy certain given constraints? As in the case of the Grassmannians, this boils down to understanding how the Schubert cells $X_w$ intersect. This question is equaivalent to studying the cohomology ring of the flag variety $\Fl_n$ over $\mathbb{Z}$, where we consider the Schubert cells as forming a cell complex structure on the flag variety.

The cohomology ring $H^\ast(\Fl_n)$, as it turns out, is the coinvariant ring that we discussed in the last post! For full details I will refer the interested reader to Fulton’s book on Young tableaux. To give the reader the general idea here, the Schubert cell $X_w$ can be thought of as a cohomology class in $H^{2i}(\Fl_n)$ where $i=\inv(w)$. We call this cohomology class $\sigma_w$, and note that for the transpositions $s_i$ formed by swapping $i$ and $i+1$, we have $\sigma_{s_i}\in H^2(\Fl_n)$. It turns out that setting $x_i=\sigma_i-\sigma_{i+1}$ for $i\le n-1$ and $x_n=-\sigma_{s_{n-1}}$ gives a set of generators for the cohomology ring, and in fact $$H^\ast(\Fl_n)=\mathbb{Z}[x_1,\ldots,x_n]/(e_1,\ldots,e_n)$$ where $e_1,\ldots,e_n$ are the elementary symmetric polynomials in $x_1,\ldots,x_n$.

Digging deeper: The isotypic components

In last week’s post, we made use of the coinvariant ring $$\mathbb{C}[x_1,\ldots,x_n]/I$$ where $I=(p_1,\ldots,p_n)$ is the ideal generated by the positive-degree homogeneous $S_n$-invariants (symmetric polynomials). We saw that this was an $S_n$-module with Hilbert series $(n)_q!$, and claimed that it was the regular representation.

Let’s see why that is, and see if we can understand where the irreducible components occur.

More precisely, our goal is to understand the series $$\sum_{d} H_{\chi^\mu}(d)q^d$$ where $H_{\chi^\mu}(d)$ is the number of copies of the $\mu$th irreducible representation of $S_n$ occurring in the $d$th degree component of $\mathbb{C}[x_1,\ldots,x_n]/I$. In Stanley’s paper on invariants of finite groups, he states without proof the answer as the following “unpublished result of Lusztig”:

Let $G$ be the group of all $m \times m$ permutation matrices, and let $\chi$ be the irreducible character of $G$ corresponding to the partition $\mu$ of $m$. Then $H_{\chi}(n)$ is equal to the number of standard Young tableaux $T$ of shape $\mu$ such that $n$ is equal to the sum of those entries $i$ of $T$ for which $i$ appears in a column to the left of $i+1$.

To prove this, let’s start with the identity we showed last time, using boldface $\mathbf{x}$ to denote $x_1,\ldots,x_n$ as a shorthand:

Since $\Lambda_{\mathbb{C}}(\mathbf{x})$, the ring of symmetric functions, consists entirely of copies of the trivial representation of $S_n$, we see that the irreducible components of type $\chi^\mu$ in degree $d$ on the right hand side come from those of that type in $\mathbb{C}[\mathbf{x}]/I$ of degree $d-k$, tensored with the trivial representations in degree $k$ in $\Lambda$, for some $k$. Moreover, there are $p_n(d)$ copies of the trivial representation in the $d$th degree in $\Lambda$ for all $d$, where $p_n(d)$ is the number of partitions of $d$ into parts of size at most $n$. (One can use the elementary or power sum symmetric function bases to see this.) From this we obtain the following series identity:

$$\left(\sum \left\langle (\mathbb{C}[\mathbf{x}])_d,\chi^\mu \right\rangle q^d\right)= \left(\sum p_n(d)q^d\right)\cdot \left(\sum H_{\chi^\mu}(d) q^d\right)$$

To simplify the left hand side, we can use the generalized version of Molien’s theorem for isotypic components (see here.) This gives us
$$\sum \left\langle (\mathbb{C}[\mathbf{x}])_d,\chi^\mu \right\rangle q^d=\frac{1}{n!}\sum_{\pi\in S_n}\frac{\overline{\chi^\mu}(\pi)}{\prod (1-q^{c_i(\pi)})}$$ where the $c_i(\pi)$’s are the cycle lengths of $\pi$.

(See this post for details on the above simplification in the case of the trivial character. The case of a general $\chi^\mu$ is analogous.)

If we group the permutations $\pi$ in the sum above according to cycle type (i.e. by conjugacy class), and use the fact that characters of $S_n$ are integers and hence $\overline{\chi^\mu}=\chi^\mu$, we have $$\sum \left\langle (\mathbb{C}[\mathbf{x}])_d,\chi^\mu \right\rangle q^d=\frac{1}{n!}\sum_{\lambda\vdash n} \frac{n!}{z_\lambda}\frac{\chi^\mu(\lambda)}{\prod_i (1-q^{\lambda_i})}.$$ Here $z_\lambda$ are the numbers such that $n!/z_\lambda$ is the size of the conjugacy class corresponding to the partition $\lambda$. It is not hard to see that this simplifies to a specialization of the power sum symmetric functions: $$\sum \frac{\chi^\mu(\lambda)}{z_\lambda} p_\lambda(1,q,q^2,\ldots)$$

Finally, by the representation-theoretic definition of the Schur functions, we see that this is simply $$s_\mu(1,q,q^2,\ldots).$$

Substituting for the left hand side of our original equation, we now have $$s_\lambda(1,q,q^2,\ldots)=\left(\sum p_n(d) q^d\right)\cdot \left(\sum H_{\chi^\mu}(d) q^d\right).$$ We can simplify this further by using the series identity $$\sum p_n(d) q^d=\frac{1}{(1-q)(1-q^2)\cdots(1-q^n)}.$$ In addition, there is a well-known identity (see also Enumerative Combinatorics vol. 2, Proposition 7.19.11) $$s_\mu(1,q,q^2,\ldots)=\frac{\sum_T q^{\operatorname{maj} T}}{(1-q)(1-q^2)\cdots (1-q^n)}$$ where the sum ranges over all standard Young tableaux $T$ of shape $\mu$, and where $\operatorname{maj} T$ denotes the sum of all entries $i$ of $T$ that occur in a higher row than $i+1$ (written in English notation).

This does it: putting everything together and solving for $\sum H_{\chi^\mu}(d) q^d$, we obtain $$\sum H_{\chi^\mu}(d) q^d=\sum_{T}q^{\operatorname{maj} T},$$ which is just about equivalent to Lusztig’s claim. (The only difference is whether we are looking at the rows or the columns that $i$ and $i+1$ are in. There must have been a typo, because the two are not the same $q$-series for the shape $(3,1)$. Replacing “column to the left of” by “row above” or replacing $\mu$ by its conjugate would fix the theorem statement above.)

One final consequence of the formulas above is that it is easy to deduce that the ring of coinvariants, $\mathbb{C}[\mathbf{x}]/I$, is isomorphic to the regular representation of $S_n$. Indeed, setting $q=1$ we see that the total number of copies of the irreducible representation corresponding to $\mu$ is equal to the number of standard Young tableaux of shape $\mu$, giving us the regular representation.

Acknowledgments: The above techniques were shown to me by Vic Reiner at a recent conference. Thanks also to Federico Castillo for many discussions about the ring of coinvariants.

Molien’s Theorem and symmetric functions

My colleague David Harden recently pointed me to Molien’s theorem, a neat little fact about the invariant polynomials under the action by a finite group. It turns out that this has a nice interpretation in the case of the symmetric group $S_n$ that brings in some nice combinatorial and group-theoretic arguments.

The general version of Molien’s theorem can be stated thus: Suppose we have a finite subgroup $G$ of the general linear group $GL_n(\mathbb{C})$. Then $G$ acts on the polynomial ring $R=\mathbb{C}[x_1,\ldots,x_n]$ in the natural way, that is, by replacing the column vector of variables $(x_1,\ldots,x_n)$ with their image under left matrix multiplication by $G$.

Let $R^G$ be the invariant space under this action. Then $R$ is graded by degree; that is, for each nonnegative integer $k$, the space $R_k^G$ of $G$-invariant homogeneous polynomials of degree $k$ are a finite dimensional subspace of $R^G$, and $R^G$ is the direct sum of these homogeneous components. What is the size (dimension) of these homogeneous components?

If $d_k$ denotes the dimension of the $k$th piece, then Molien’s theorem states that the generating function for the $d_k$’s is given by
$$\sum_{k\ge 0} d_k t^k=\frac{1}{|G|}\sum_{M\in G} \frac{1}{\det(I-tM)}$$ where $I$ is the $n\times n$ identity matrix.

There is a nice exposition of the proof (in slightly more generality) in this paper of Richard Stanley, which makes use of some basic facts from representation theory. Rather than go into the proof, let’s look at the special case $G=S_n$, namely the set of all permutation matrices in $GL_n$.

Specialization at $G=S_n$

In this case, the invariant space $R^{S_n}$ is simply the space of symmetric polynomials in $x_1,\ldots,x_n$, and the $k$th graded piece consists of the degree-$k$ homogeneous symmetric polynomials. But we know exactly how many linearly independent homogeneous symmetric polynomials of degree $k$ there can be – as shown in my previous post, the monomial symmetric polynomials $m_\lambda$, where $\lambda$ is any partition of $k$, form a basis of this space in the case that we have infinitely many variables. Since we only have $n$ variables, however, some of these are now zero, namely those for which $\lambda$ has more than $n$ parts. The nonzero $m_\lambda$’s are still linearly independent, so the dimension of the $k$th graded piece in this case is $p(k,n)$, the number of partitions of $k$ into at most $n$ parts.

Notice that by considering the conjugate of each partition, we see that the number of partitions of $k$ into at most $n$ parts is equal to the number of partitions of $k$ that use parts of size at most $n$. It is not hard to see that the generating function for $p(k,n)$ is therefore
$$\sum_{k\ge 0}p(k,n)t^k=\frac{1}{(1-t)(1-t^2)\cdots (1-t^n)}.$$

Molien’s theorem says that this generating function should also be equal to $$\frac{1}{n!}\sum_{M\in S_n}\frac{1}{\det(I-tM)}$$ where we use the somewhat sloppy notation $M\in S_n$ to indicate that $M$ is an $n\times n$ permutation matrix. What are these determinants? Well, suppose $M$ corresponds to a permutation with cycle type $\lambda$, that is, when we decompose the permutation into cycles the lengths of the cycles are $\lambda_1,\ldots,\lambda_r$ in nonincreasing order. Then notice that, up to simultaneous reordering of the rows and columns, $I-tM$ is a block matrix with blocks of sizes $\lambda_1,\ldots,\lambda_r$. The determinant of a block of size $\lambda_i$ is easily seen to be $1-t^{\lambda_i}$. For instance
$$\det \left(\begin{array}{ccc} 1 & -t & 0 \\ 0& 1 & -t \\ -t & 0 & 1\end{array}\right)=1-t^3,$$ and in general, the determinant of such a block will have contributions only from the product of the 1’s down the diagonal and from the product of the off-diagonal $-t$’s; all other permutations have a $0$ among the corresponding matrix entries. The sign on the product of $t$’s is always negative since either $\lambda_i$ is odd, in which case the cyclic permutation of length $\lambda_i$ is even, or $\lambda_i$ is even, in which case the permutation is odd. Hence, the determinant of each block is $1-t^{\lambda_i}$, and the entire determinant is
$$\det (I-tM)=\prod_i (1-t^{\lambda_i}).$$

So, our summation becomes
$$\frac{1}{n!}\sum_{\pi\in S_n} \frac{1}{\prod_{\lambda_i\in c(\pi)} (1-t^{\lambda_i})}$$ where $c(\pi)$ denotes the cycle type of a permutation $\pi$. Already we have an interesting identity; we now know this series is equal to
$$\frac{1}{(1-t)(1-t^2)\cdots (1-t^n)}.$$ But can we prove it directly?

It turns out that the equality of these two series can be viewed as a consequence of Burnside’s Lemma. In particular, consider the action of the symmetric group on the set $X$ of weak compositions of $k$ having $n$ parts, that is, an ordered $n$-tuple of nonnegative integers (possibly $0$) that add up to $k$. Then Burnside’s lemma states that the number of orbits under this action, which correspond to the partitions of $k$ having at most $n$ parts, is equal to
$$\frac{1}{n!}\sum_{\pi \in S_n} |X^\pi|$$ where $X^\pi$ is the collection of weak compositions which are fixed under permuting the entries by $\pi$. We claim that this is the coefficient of $t^k$ in
$$\frac{1}{n!}\sum_{\pi\in S_n} \frac{1}{\prod_{\lambda_i\in c(\pi)} (1-t^{\lambda_i})}$$ hence showing that the two generating functions are equal.

To see this, note that if $\pi\in S_n$ has cycle type $\lambda$, then $X^\pi$ consists of the weak compositions which have $\lambda_1$ of their parts equal to each other, $\lambda_2$ other parts equal to each other, and so on. Say WLOG that the first $\lambda_1$ parts are all equal, and the second $\lambda_2$ are equal, and so on. Then the first $\lambda_1$ parts total to some multiple of $\lambda_1$, and the next $\lambda_2$ total to some multiple of $\lambda_2$, and so on, and so the total number of such compositions of $k$ is the coefficient of $t^k$ in the product $$\frac{1}{\prod_{\lambda_i\in c(\pi)} (1-t^{\lambda_i})}.$$ Averaging over all $\pi\in S_n$ yields the result.

A q-analog of the decomposition of the regular representation of the symmetric group

It is a well-known fact of representation theory that, if the irreducible representations of a finite group $\DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\sh}{sh} G$ are $V_1,\ldots,V_m$, and $R$ is the regular representation formed by $G$ acting on itself by left multiplication, then
$$R=\bigoplus_{i=1}^{m} (\dim V_i) \cdot V_i$$ is its decomposition into irreducibles.

I’ve recently discovered a $q$-analog of this fact for $G=S_n$ that is a simple consequence of some known results in symmetric function theory.

In Enumerative Combinatorics, Stanley defines a generalization of the major index on permutations to standard tableaux. For a permutation $$w=w_1,\ldots,w_n$$ of $1,\ldots,n$, a descent is a position $i$ such that $w_i>w_{i+1}$. For instance, $52413$ has two descents, in positions $1$ and $3$. The major index of $w$, denoted $\maj(w)$, is the sum of the positions of the descents, in this case $$\maj(52413)=1+3=4.$$

To generalize this to standard Young tableaux, notice that $i$ is a descent of $w$ if and only if the location of $i$ occurs after $i+1$ in the inverse permutation $w^{-1}$. With this as an alternative notion of descent, we define a descent of a tableau $T$ to be a number $i$ for which $i+1$ occurs in a lower row than $i$. In fact, this is precisely a descent of the inverse of the reading word of $T$, the word formed by reading the rows of $T$ from left to right, starting from the bottom row.

As an example, the tableau $T$ below has two descents, $2$ and $4$, since $3$ and $5$ occur in lower rows than $2$ and $4$ respectively:


So $\maj(T)=2+4=6$. Note that its reading word $5367124$, and the inverse permutation is $5627134$, which correspondingly has descents in positions $2$ and $4$.

(This is a slightly different approach to the major index than taken by Stanley, who used a reading word that read the columns from bottom to top, starting at the leftmost column. The descents remain the same in either case, since both reading words Schensted insert to give the same standard Young tableau.)

Now, the major index for tableaux gives a remarkable specialization of the Schur functions $s_\lambda$. As shown in Stanley’s book, we have $$s_\lambda(1,q,q^2,q^3,\ldots)=\frac{\sum_{T} q^{\maj(T)}}{(1-q)(1-q^2)\cdots(1-q^n)}$$ where the sum is over all standard Young tableaux $T$ of shape $\lambda$. When I came across this fact, I was reminded of a similar specialization of the power sum symmetric functions. It is easy to see that
$$p_\lambda(1,q,q^2,q^3,\ldots)=\prod_{i}\frac{1}{1-q^{\lambda_i}},$$ an identity that comes up in defining a $q$-analog of the Hall inner product in the theory of Hall-Littlewood symmetric functions. In any case, the power sum symmetric functions are related to the Schur functions via the irreducible characters $\chi_\mu$ of the symmetric group $S_n$, and so we get

p_\lambda(1,q,q^2,\ldots) &=& \sum_{|\mu|=n} \chi_{\mu}(\lambda) s_{\mu}(1,q,q^2,\ldots) \\
\prod_{i} \frac{1}{1-q^{\lambda_i}} &=& \sum_{\mu} \chi_{\mu}(\lambda) \frac{\sum_{T\text{ shape }\mu} q^{\maj(T)}}{(1-q)(1-q^2)\cdots(1-q^n)} \\

This can be simplified to the equation: \begin{equation}
\sum_{|T|=n} \chi_{\sh(T)}(\lambda)q^{\maj(T)} = \frac{(1-q)(1-q^2)\cdots (1-q^n)}{(1-q^{\lambda_1})(1-q^{\lambda_2})\cdots(1-q^{\lambda_k})}
\end{equation} where $\sh(T)$ denotes the shape of the tableau $T$.

Notice that when we take $q\to 1$ above, the right hand side is $0$ unless $\lambda=(1^n)$ is the partition of $n$ into all $1$’s. If $\lambda$ is not this partition, setting $q=1$ yields $$\sum \chi_\mu(\lambda)\cdot f^{\mu}=0$$ where $f^\mu$ is the number of standard Young tableaux of shape $\mu$. Otherwise if $\lambda=(1^n)$, we obtain $$\sum \chi_\mu(\lambda)\cdot f^{\mu}=n!.$$ Recall also that $f^\mu$ (see e.g. Stanley or Sagan) is equal to the dimension of the irreducible representation $V_\mu$ of $S_n$. Thus, these two equations together are equivalent to the fact that, if $R$ is the regular representation,
$$\chi_R=\sum_\mu (\dim V_\mu) \cdot \chi_{\mu}$$ which is in turn equivalent to the decomposition of $R$ into irreducibles.

Therefore, Equation (1) is a $q$-analog of the decomposition of the regular representation. I’m not sure this is known, and I find it’s a rather pretty consequence of the Schur function specialization at powers of $q$.

EDIT: It is known, as Steven Sam pointed out in the comments below, and it gives a formula for a graded character of a graded version of the regular representation.