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:
$$\left(\begin{array}{ccccc} 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.

Can you prove it?

As this ingenious post over at Math With Bad Drawings explained so clearly recently, there is a big difference between finding the answer to a math problem and being able to explain, beyond all reasonable doubt, why your answer is correct. It is the difference between solving it and proving it!

While mathematical proof is a huge part of math and science, it is unfortunately somewhat overlooked in the standard US curriculum. Partly for this reason, my family and I started a new math summer camp called Prove it! Math Academy. This year’s program will be a two-week crash course in proofs, using challenging problems and advanced mathematical concepts as examples.

Consider the following diagram which appears on our program website:

No explanation, no words, no proof. Just the picture. Enticing!

The first step in proving a fact is to state exactly what it is you are trying to prove. In this case, one might generalize/interpret this diagram as follows. Suppose you have a circle $O$ (the big white one) containing three circles $A$, $B$, and $C$ inside of it that are mutually externally tangent to each other and internally tangent to $O$. (These three circles $A$, $B$, and $C$ would be the large green, large yellow, and small red circle in the diagram above.) Now let $X$, $Y$, and $Z$ be the remaining green, yellow, and red circles respectively: for instance, $X$ is the circle tangent internally to $O$ and externally to $B$ and $C$. Then the lines $AX$, $BY$, and $CZ$ connecting the centers of these circles all meet at one point – they are concurrent.

You can construct this in Geogebra or Asymptote. You can vary the sizes of the circles and test that indeed, these lines always seem to be concurrent. But unlike in science, lots of evidence to support a fact is not good enough in mathematics. We want to prove beyond all reasonable doubt that this is always true, no matter what the sizes of the circles are. In other words, you can solve it, but can you prove it?

A very elegant solution to this problem, which appears on the next page of this post, is due to Michael Kural, one of my former students at MOP. He was intrigued by the image on our program flyer at a recent math tournament, and came up with a proof using only Desargues’ theorem, Monge’s theorem, homothety, and inversion. Read on!

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:
$$gug^{-1}=\left(\begin{array}{ccccccc} \lambda_1 & 1 & & & & & \\ & \lambda_1 & 1 & & & & \\ & & \lambda_1 & & & & \\ & & & \lambda_2 & 1 & & \\ & & & & \lambda_2 & & \\ & & & & & \ddots & \\ & & & & & & \lambda_k \end{array}\right)$$

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
$$F_t(R_\mu)=\sum_{i=0}^{d(\mu)}F((R_{\mu})_i)t^i$$
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.


$$\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
$$\left(\begin{array}{ccccc} 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:
$$\mathbb{C}[\mathbf{x}]=\Lambda_{\mathbb{C}}(\mathbf{x})\otimes_{\mathbb{C}[S_n]}\mathbb{C}[\mathbf{x}]/I$$

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.

Writing polynomials in terms of invariants and coinvariants

There is a fun little fact regarding polynomials in two variables $x$ and $y$:

Any two-variable polynomial $f(x,y)$ can be uniquely written as a sum of a symmetric polynomial and an antisymmetric polynomial.

(To be more precise, this is true for polynomials over any field of characteristic not equal to $2$. For simplicity, in what follows we will assume that our polynomials have coefficients in $\mathbb{C}$.)

Recall that a polynomial $g$ is symmetric if it does not change upon permuting its variables. In this case, with two variables, $g(x,y)=g(y,x)$. It is antisymmetric if swapping any two of the variables negates it, in this case $g(x,y)=-g(y,x)$.

It is not hard to prove the fact above. To show existence of the decomposition, set $g(x,y)=\frac{f(x,y)+f(y,x)}{2}$ and $h(x,y)=\frac{f(x,y)-f(y,x)}{2}$. Then $$f(x,y)=g(x,y)+h(x,y),$$ and $g$ is symmetric while $h$ is antisymmetric. For instance, if $f(x,y)=x^2$, then we can write $$x^2=\frac{x^2+y^2}{2}+\frac{x^2-y^2}{2}.$$

For uniqueness, suppose $f(x,y)=g_0(x,y)+h_0(x,y)$ where $g_0$ is symmetric and $h_0$ is antisymmetric. Then $g_0+h_0=g+h$, and so $$g_0-g=h-h_0.$$ The left hand side of this equation is symmetric and the right hand side is antisymmetric, and so both sides must be identically zero. This implies that $g_0=g$ and $h_0=h$, so the unique decomposition is $f=g+h$. QED.

This got me thinking…

Is there an analogous decomposition for polynomials in three variables? Or any number of variables?

The above decomposition doesn’t make sense in three variables, but perhaps every polynomial in $x$, $y$, and $z$ can be written uniquely as a sum of a symmetric, antisymmetric, and… some other particular type(s) of polynomials.

Indeed, it can be generalized in the following sense. Notice that any antisymmetric polynomial in two variables is divisible by $x-y$, since setting $x=y$ gives us $f(x,x)=-f(x,x)=0$. Moreover, dividing by $x-y$ gives a symmetric polynomial: if $$h(x,y)=p(x,y)\cdot(x-y)$$ is antisymmetric, then $p(x,y)\cdot (x-y)=-p(y,x)\cdot(y-x)$, and so $p(x,y)=p(y,x)$.

Thus any antisymmetric polynomial $h$ is equal to $x-y$ times a symmetric polynomial, and so we can restate our fact above in the following way:

Any two variable polynomial $f(x,y)$ can be written uniquely as a linear combination of $1$ and $x-y$, using symmetric polynomials as the coefficients.

For instance, $f(x,y)=x^2$ can be written as $$x^2=\left(\frac{x^2+y^2}{2}\right)\cdot 1+\left(\frac{x+y}{2}\right)\cdot (x-y).$$

Now, to generalize this to three variables, in place of $x-y$, we consider the polynomial $$\Delta=(x-y)(x-z)(y-z).$$ Also consider the five polynomials:

• $x^2-z^2+2yz-2xy$,
• $z^2-y^2+2xy-2xz$,
• $x-y$,
• $y-z$, and
• $1$,

each of which is obtained by taking certain partial derivatives starting with $\Delta$. It turns out that every polynomial in three variables can be decomposed uniquely as a linear combination of these six polynomials, using symmetric polynomials as the coefficients!

Where do these six polynomials come from? Turn to the next page to find out…

Expii: Learning, connected

It’s been several months since I posted a gemstone, and the main reason is that much of my free-time mathematics energy recently became channeled into a new project: Expii.

Expii (currently beta) is a new online crowdsourced learning site that aims to fill the gaps in users’ understanding of topics, with the goal of making math, science, and other topics easy for everyone in the universe. Its motto? Learning, connected.

With an addictive, game-like format (hence the XP pun) in which users are awarded “fame points” for writing good explanations and “experience points” for successfully making it through tutorials, Expii is more interactive and community oriented than other online learning resources like Wikipedia. It is also more structured than question-and-answer sites like Quora or Stack Exchange, in that the primary “graph structure” for the topics is organized by our team, and users fill in the content in the nodes.

The first thing you see when you go to www.expii.com is the highest-level Universe graph:

This currently has two disjoint subgraphs: Expii Guide and Calculus. One can scroll or click to zoom in on Calculus:

And magically, other smaller subgraphs appear! Keep zooming in and eventually you get to the lowest level of detail, which has Topic nodes that you can click on:

Let’s click on Lines and Slopes. This brings us to a user-written explanation of lines and slopes!

It is easy for an explainer to write interactive questions, for the student to answer before moving on to the next part of the explanation. For instance, if you answer the first question correctly here, it gives you a green light and reveals the next part of the explanation:

But if you get it wrong, red light!

When you’re done with a topic or simply feel like browsing, you can scroll down for a seamless transition to a related topic:

And this is just the beginning. Expii was founded by Po-Shen Loh and Ray Li only a handful of months ago. They quickly drew in a fantastic team of mathematicians of scientists (including me) that care about education, outreach, and spreading the love of learning in a way that is fun and engaging. It will be exciting to see what Expii becomes over the next few years.

If you’d like to experiment with Expii yourself, write some explanations, or contribute to the project, contact me and I can get you a referral code so that you can log in. It’s the newest and shiniest gemstone in mathematics education!

PEMDAS is broken (and how we can fix it)

In the first week of teaching my Calculus 1 discussion section this term, I decided to give the students a Precalc Review Worksheet. Its purpose was to refresh their memories of the basics of arithmetic, algebra, and trigonometry, and see what they had remembered from high school.

Surprisingly, it was the arithmetic part that they had the most trouble with. Not things like multiplication and long division of large numbers – those things are taught well in our grade schools – but when they encountered a complicated multi-step arithmetic problem such as the first problem on the worksheet, they were stumped:

Simplify: $1+2-3\cdot 4/5+4/3\cdot 2-1$

Gradually, some of the groups began to solve the problem. But some claimed it was $-16/15$, others guessed that it was $34/15$, and yet others insisted that it was $-46/15$. Who was correct? And why were they all getting different answers despite carefully checking over their work?

The answer is that the arithmetic simplification procedure that one learns in grade school is ambiguous and sometimes incorrect. In American public schools, students are taught the acronym “PEMDAS”, which stands for Parentheses, Exponents, Multiplication, Division, Addition, Subtraction. This is called the order of operations, which tells you which arithmetic operations to perform first by convention, so that we all agree on what the expression above should mean.

But PEMDAS doesn’t work properly in all cases. (This has already been wonderfully demonstrated in several YouTube videos such as this one, but I feel it is good to re-iterate the explanation in as many places as possible.) To illustrate the problem, consider the computation $6-2+3$. Here we’re starting with $6$, taking away $2$, and adding back $3$, so we should end up with $7$. This is what any modern calculator will tell you as well (try typing it into Google!) But if you follow PEMDAS to the letter, it tells you that addition comes before subtraction, and so we would add $2+3$ first to get $5$, and then end up with $6-5=1$.

Even worse, what happens if we try to do $6-3-2$? We should end up with $1$ since we are taking away $2$ and $3$ from $6$, and yet if we choose another order in which to do a subtraction first, say $6-(3-2)=6-1$, we get $5$. So, subtraction can’t even properly be done before itself, and the PEMDAS rule does not deal with that ambiguity.

Mathematicians have a better convention that fixes all of this. What we’re really doing when we’re subtracting is adding a negative number: $6-2+3$ is just $6+(-2)+3$. This eliminates the ambiguity; addition is commutative and associative, meaning no matter what order we choose to add several things together, the answer will always be the same. In this case, we could either do $6+(-2)=4$ and $4+3=7$ to get the answer of $7$, or we could do $(-2)+3$ first to get $1$ and then add that to $6$ to get $7$. We could even add the $6$ and the $3$ first to get $9$, and then add $-2$, and we’d once again end up with $7$. So now we always get the same answer!

There’s a similar problem with division. Is $4/3/2$ equal to $4/(3/2)=8/3$, or is it equal to $(4/3)/2=2/3$? PEMDAS doesn’t give us a definite answer here, and has the further problem of making $4/3\cdot 2$ come out to $4/(3\cdot 2)=2/3$, which again disagrees with Google Calculator. As in the case of subtraction, the fix is to turn all division problems into multiplication problems: we should think of division as multiplying by a reciprocal. So in the exercise I gave my students, we’d have $4/3\cdot 2=4\cdot \frac{1}{3}\cdot 2=\frac{8}{3}$, and all the confusion is removed.

To finish the problem, then, we would write
$$\begin{eqnarray*} 1+2-3\cdot 4/5+4/3\cdot 2-1&=&1+2+(-\frac{12}{5})+\frac{8}{3}+(-1) \\ &=&2+\frac{-36+40}{15} \\ &=&\frac{34}{15}. \end{eqnarray*}$$

The only thing we need to do now is come up with a new acronym. We still follow the convention that Parentheses, Exponents, Multiplication, and Addition come in that order, but we no longer have division and subtraction since we replaced them with better operators. So that would be simply PEMA. But that’s not quite as catchy, so perhaps we could add in the “reciprocal” and “negation” rules to call it PERMNA instead. If you have something even more catchy, post it in the comments below!

A proof of the existence of finite fields of every possible order

This is our first contributed gemstone! Submitted by user Anon1.

In the following, $p$ denotes a prime. We wish to prove that, for all positive integers $n$, there is a finite field of order $p^{n}$.

Step 1. Restating the problem.

Claim: It suffices to show that, for some power of $p$ (call it $q$), there exists a finite field of order $q^{n}$.

Proof. Suppose there is a field $F$ such that $|F| = q^{n}$. The claim is that the solution set to $x^{p^{n}} = x$ in $F$ is a subfield of order $p^{n}$.

Since $q$ is a power of $p$, we have $$p^{n}-1 | q^{n}-1.$$ Since $q^{n}-1$ is the order of the cyclic group $F^{ \times }$, we know that $F^{ \times }$ has a unique cyclic subgroup of order $p^{n}-1$. This contributes $p^{n}-1$ solutions to $x^{p^{n}} = x$ in $F$. But $0$ is another solution, since it is not an element of $F^{ \times }$. This gives $p^{n}$ solutions, so this gives all solutions.

It remains to show that these solutions form a subfield of $F$. Since they form a finite set, it suffices to show that they are closed under addition and, since they include 0, it suffices to show they are closed under multiplication.

Closure under multiplication is immediate: $x^{p^{n}} = x$ and $y^{p^{n}} = y$ implies $$(xy)^{p^{n}} = x^{p^{n}}y^{p^{n}} = xy.$$

Closure under addition is similarly easy: Since $|F| = q$ and $q$ is a power of $p$, the field $F$ has characteristic $p$. This means that, for all $x,y \in F$, $$(x+y)^{p} = x^{p} + y^{p}.$$ Applying this $n$ times yields $(x+y)^{p^{n}} = x^{p^{n}} + y^{p^{n}}$. If $x^{p^{n}} = x$ and $y^{p^{n}} = y$, then it follows that $(x+y)^{p^{n}} = x + y$. We are done with Step 1. $\square$

Step 2. Reducing to an asymptotic problem.

Claim: There are arbitrarily large $k$ such that there is a finite field of order $q = p^{k}$.

Proof. If $f \in \mathbb{F}_{p}[x]$ is irreducible and of degree $k$, then $\mathbb{F}_{p}[x]/(f)$ is a field of order $p^{k}$. So we need to prove that the degrees of irreducible polynomials in $\mathbb{F}_{p}[x]$ get arbitrarily high. Since $\mathbb{F}_{p}[x]$ has only $(p-1)p^{k}$ polynomials of degree $k$, it suffices to prove that $\mathbb{F}_{p}[x]$ has infinitely many irreducible polynomials.

At this point we use Euclid’s argument: if $f_{1}, \ldots , f_{N}$ are all the irreducibles in $\mathbb{F}_{p}[x]$, then $1 + f_{1} \cdot \ldots \cdot f_{N}$ cannot be factored into irreducibles (and isn’t constant), contradicting the fact that $\mathbb{F}_{p}[x]$ is a unique factorization domain. Therefore $\mathbb{F}_{p}[x]$ has infinitely many irreducibles and we are done. $\square$

Step 3. Counting the irreducible polynomials of degree $d$ over various $\mathbb{F}_q$.

Claim: If $q$ is a power of $p$ for which there is a finite field of order $q$ (here denoted $\mathbb{F}_{q}$), then the number of irreducible monic polynomials of degree $d$ over $\mathbb{F}_{q}$ is a polynomial (call it $I_{d}(q)$) depending only on $d$, evaluated at $q$.

Proof. This proceeds by strong induction on $d$. The base case is $d = 1$: any linear polynomial is irreducible, and there are $q$ monic linear polynomials over $\mathbb{F}_{q}$.

Now suppose $d > 1$. There are $q^{d}$ monic degree $d$ polynomials over $\mathbb{F}_{q}$. To count how many are irreducible, we remove the ones which are reducible: If a monic polynomial is reducible, it can be written uniquely as a product of monic irreducibles of lower degree. These degrees add up to $d$, so they give a partition $\lambda$ of $d$ which can be any partition except $(d)$ itself.

Specifically, for each such partition $\lambda$ suppose $a_{i}$ is the number of parts of size $i$. Then
$$I_{d}(q) = q^{d} – \sum_{ \lambda \vdash d, \lambda \neq (d)}{ \prod_{i=1}^{d} \binom{I_{i}(q) + a_{i} – 1}{a_{i}} },$$ which is a polynomial in $q$ by the strong induction hypothesis. $\square$

Now, it suffices to show that for any given $n$, $I_n(q)>0$ for sufficiently large $q$. For, by step 2, this will give us a power of $p$ called $q$ for which $\mathbb{F}_q$ exists and such that there is a monic irreducible polynomial over $\mathbb{F}_q$ of degree $n$. By step 1 we are then done.

Since $I_{n}$ is a polynomial, this amounts to showing that $I_{n}$ has a positive leading coefficient for all $n$. This we do now:

Step 4. Showing that the counting polynomial $I_n$ has positive leading coefficient.

Claim: For all $n$, $I_{n}$ has degree $n$ and leading coefficient $1/n$.

Proof. Again we proceed by strong induction on $n$. When $n = 1$, we have $I_{n}(q) = q$ and we are done. So suppose $n>1$. Then as in step 3, we have
$$I_{n}(q) = q^{n} – \sum_{ \lambda \vdash n, \lambda \neq (n) }{ \Pi_{i=1}^{n} \binom{I_{i}(q) + a_{i} – 1}{a_{i}} }.$$
Since $a_{n} = 0$, we can restrict the products to only $i \lt n$. Then the degree of each of these products is $\sum_{i=1}^{n} i\cdot a_i=n$ by the induction hypothesis, and so $I_n(q)$ has degree at most $n$. Moreover, assuming by the induction hypothesis that the coefficient of $q^i$ in $I_i(q)$ is $1/i$, we have that the coefficient of $q^{i\cdot a_i}$ in $\binom{I_i(q)+a_i-1}{a_i}$ is $$\frac{1}{a_i!\cdot i^{a_i}}.$$

Finally, it follows that the coefficient of $q^n$ in $I_n(q)$ is $$1-\sum_{ \lambda \vdash n, \lambda \neq (n) }{ \Pi_{i=1}^{n}{ \frac{1}{a_{i}!i^{a_{i}}}}}.$$ Now, notice that for a given $\lambda$, the product $$z_\lambda=a_1!\cdot 1^{a_1}\cdot a_2!\cdot 2^{a_2}\cdot\cdots\cdot a_n!\cdot n^{a_n}$$ is the well-known demoninator of the formula $$n!/z_\lambda$$ for the size of the conjugacy class of elements of shape $\lambda$ in the symmetric group $S_n$. Thus we have $$\sum_{\lambda\vdash n} \frac{n!}{z_\lambda}=n!,$$ and so $$\sum_{\lambda\vdash n}\frac{1}{z_\lambda}=1.$$ It follows from this and the formula for our coefficient above that the coefficient is simply $$\sum_{\lambda=(n)}\frac{1}{z_\lambda}=1/n,$$ and the claim is proven. $\square$

FindStat and combinatorial statistics

Last semester, I attended Sage Days 54 at UC Davis. In addition to learning about Sage development (perhaps a topic for a later blog post), I was introduced to FindStat, a new online database of combinatorial statistics.

You may be familiar with the Online Encyclopedia of Integer Sequences; the idea of FindStat is similar, and somewhat more general. The Online Encyclopedia of Integer Sequences is a database of mathematically significant sequences, and to search the database you can simply enter a list of numbers. It will return all the sequences containing your list as a consecutive subsequence, along with the mathematical significance of each such sequence and any other relevant information.

FindStat does the same thing, but with combinatorial statistics instead of sequences. A combinatorial statistic is any integer-valued function defined on a set of combinatorial objects (such as graphs, permutations, posets, and so on). Some common examples of combinatorial statistics are:

• The number of edges of a finite simple graph,
• The length of a permutation, that is, the smallest length of a decomposition of the permutation into transpositions,
• The number of parts of a partition,
• The diameter of a tree.

The FindStat database has a number of combinatorial objects programmed in, with various statistics assigned to them, which can all be viewed in the Statistics Database tab. The search functionality is under Statistic Finder, in which you can choose a combinatorial object, say graphs, and enter some values for some of the graphs. It will then tell you what statistics, if any, on graphs match the values you have entered.

So this is strictly more general than OEIS: we can think of integer sequences as combinatorial statistics on some collection of combinatorial objects represented by the nonnegative integers, such as finite collections of indistinguishable balls. Not that FindStat should be used for integer sequences – OEIS already does a splendid job of that – but FindStat provides something that OEIS cannot: an organized database of mathematical data that doesn’t necessarily have a natural linear ordering.

The last, and most interesting, feature of FindStat is its “maps” functionality. There are many known natural maps of combinatorial objects, such as the map $\phi:P\to B$ sending a permutation to its corresponding binary search tree, where $P$ denotes the set of all permutations and $B$ the set of all binary search trees. (See here for all the maps currently implemented on the Permutations class in FindStat.) Now, given a statistic $s:B\to \mathbb{Z}$ on $B$, we automatically get a statistic $$s\circ \phi:P\to \mathbb{Z}.$$ FindStat uses this fact to give the user more information: it will give you not only the matching statistics on the combinatorial object that you chose, but the matching statistics on all other possible combinatorial objects linked by any relevant map in the database! This can help the working combinatorialist discover new ways of thinking about their statistics.