Addicted to Crystal Math

Some of my recent research has centered on crystals, so here’s an introductory post, from a combinatorial point of view, on what crystals are and where they come up.

First, a clarification: the crystals I have in mind are not the chemical kind that you find in nature, nor are they any of these other uses of the word crystal on the Wikipedia disambiguation page. There is yet another use of the word, sometimes referred to as a crystal base, introduced by Kashiwara in the mid-90’s. Kashiwara developed crystal base theory as a way of understanding the $q\to 0$ limit of the representation theory of quantum groups $U_q(\mathfrak{g})$ where $\mathfrak{g}$ is a Lie algebra and $U_q(\mathfrak{g})$ is a $q$-analog of the universal enveloping algebra $U(\mathfrak{g})$. In the quantized statistical mechanics models in which quantum groups come up, the parameter $q$ is a measure of temperature, so the $q\to 0$ limit is exploring what happens in the situation of absolute zero temperature. Hence the word ``crystal’’, referring to what happens to many forms of matter when frozen.

Although the original motivation for crystals came from quantum groups, the combinatorial structure is also very useful in symmetric function theory. One example of a crystal is a certain weighted, edge-labeled directed graph structure on the summands that comprise a Schur polynomial. Recall that the Schur function $s_{\lambda/\mu}(x_1,\ldots,x_n)$ is given by the sum \[s_{\lambda/\mu}=\sum_{T\in \mathrm{SSYT}(\lambda/\mu)} x^T\] where $\mathrm{SSYT}(T)$ is the set of semistandard Young tableaux of skew shape $\lambda/\mu$, and $x^T=x_1^{m_1}x_2^{m_2}\cdots$ where $m_i$ is the number of $i$’s in $T$. For instance, we have \[s_{(2,1)}(x_1,x_2,x_3)=x_1^2x_2+x_1x_2^2+x_1^2x_3+2x_1x_2x_3+x_1x_3^2+x_2^2x_3+x_2x_3^2,\] since the eight semistandard Young tableaux of straight shape $(2,1)$ are:

We can organize these tableaux by weight in a 2-dimensional grid, since each weight is a tuple $(m_1,m_2,m_3)$ where $m_1+m_2+m_3=3$. We angle the grid so that either changing the weight by $(-1,1,0)$ or by $(0,-1,1)$ is ``lowering’’ the weight, going downwards at a 45 degree angle to the right or left. We will then connect some of the tableaux along the edges of the grid with edges labeled by weight-lowering operators $F_1$ and $F_2$ (with inverses $E_1$ and $E_2$), shown in red and blue below:

In general $F_i$ changes the weight by $(0,0,\ldots,-1,1,0,\ldots,0)$ with the $-1$ in the $i$-th position, and we think of $F_i$ as an operator on tableaux that changes an $i$ into an $i+1$. To define $F_i(T)$, we consider the reading word $w$ of the tableau $T$, formed by concatenating the rows from bottom to top, and consider just the $i$ and $i+1$ entries of $w$. Replace each $i$ with a closed bracket ‘)’, and each $i+1$ with an open bracket ‘(‘, and cancel the brackets in matching pairs until only a word of the form \[)))\cdots ))(((\cdots ((\] (or alternatively, of the form $ii\cdots ii(i+1)(i+1)\cdots(i+1)$) remains. Then $F_i$ changes the last $i$ in this subsequence to $i+1$. For example, if $T$ looks like:

then to apply $F_1$ to $T$, we consider the reading word of $1$s and $2$s and cancel matching pairs as follows:

\begin{array}{ccccccccccc} 2 & 2 & 1 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ ( & ( & ) & ) & ) & ) & ( & ) & ( & ( & ) \\ ( & & & ) & ) & ) & & & ( & & \\ & & & & ) & ) & & & ( & & \end{array}

Then $F_1$ changes the rightmost $)$ that was not cancelled to $($, changing that $1$ to $2$. The word becomes:

\begin{array}{ccccccccccc} 2 & 2 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 1. \end{array}

Note that $F_i$ may not be defined, if there is no closed bracket that is not cancelled. If no $F_i$ operator may be applied to a tableau $T$, we say that $T$ is lowest weight. The bottom tableau on the crystal diagram above is lowest weight for the operators $F_1,F_2$. Similarly, we can define raising operators $E_i$ as the natural partial inverses of the $F_i$ operators (simply by reversing the arrows in the crystal graph), and we define highest weight elements as those for which all $E_i$ operators are undefined.

Now here’s the interesting thing: highest weight tableaux or words are precisely the Littlewood-Richardson tableaux that we have encountered in several previous posts. Recall that a tableau is Littlewood-Richardson if its reading word $w=w_1\cdots w_n$ is ballot, meaning that every tail of the word (of the form $w_k\cdots w_n$ for some $k$) has at least as many $1$’s as $2$’s, at least as many $2$’s as $3$’s, and so on. In other words, when reading the word from right to left, the smaller letters always occur more frequently than larger letters. For instance, the word \[12122111\] is ballot, and it is not hard to see that ballotness in a word with just $1$’s and $2$’s is equivalent to the condition that every $2$ is bracketed with a $1$, so that $E_1$ is undefined.

The key fact about tableau crystals is as follows:

Every connected component of a crystal graph has a unique highest weight element.

For instance, here is the crystal graph for the skew shape $(3,1)/(1)$:

Note that each connected component has a Littlewood-Richardson tableau at the top, and no other elements are killed by all raising operators. Notice also that the first graph above has the same structure as that of the shape $(2,1)$ crystal drawn above. This is no coincidence: another key fact about the operators $F_i$ and $E_i$ is that they commute with Jeu de Taquin rectification, which is easily proven using Knuth equivalence. The tableaux in the shape $(2,1)$ crystal are simply the Jeu de Taquin rectifications of those in the corresponding component of the $(3,1)/(1)$ graph. Similarly, the tableaux in the second component rectify to form the tableau crystal for shape $(3)$. It follows that, if we sum the monomial weights in the graph, we obtain the equation \[s_{(3,1)/(1)}=s_{(2,1)}+s_{(3)},\] which is an instance of the famous Littlewood-Richardson rule.

In general, let $c^{\lambda}_{\mu\nu}$ be the number of Littlewood-Richardson tableaux of shape $\lambda/\mu$ and content $\nu$. Then recall that the Littlewood-Richardson rule for multiplying Schur functions states:

\[s_\mu s_\nu = \sum_{\lambda} c^{\lambda}_{\mu\nu} s_\lambda,\]

or equivalently, after a bit of symmetric function theory manipulation,

\[s_{\lambda/\mu}=\sum_{\nu} c^{\lambda}_{\mu\nu} s_\nu.\]

The latter equation now follows immediately from the facts about crystals listed above, as we saw for the shape $(3,1)/(1)$. We can also prove the product version directly using crystals, by introducing a tensor product. There is a natural tensor product on crystals coming from their correspondence with Lie algebra representations, which we will define in general on the next page. In combinatorial terms, we can define the tensor product of crystals of tableaux by defining the concatenation of two tableaux $T$ and $S$ to be the tableau $T\cdot S$ formed by drawing $S$ above and to the right of $T$, with the lower left corner of $S$ matching the upper right corner of $T$. For instance, tableaux of skew shape $(3,1)/(1)$ can be formed by concatenating a tableau of shape $(1)$ with a tableau of shape $(2)$. (Note that this concatenates the reading words of $T$ and $S$ as well, and induces the plactic monoid structure on Knuth equivalence classes of words.)

Then the tensor product $\mathcal{B}_\mu \otimes \mathcal{B}_\nu$ of two tableaux crystals on shapes $\mu$ and $\nu$ is the crystal on all words of the form $T\cdot S$ for $T\in \mathcal{B}_\mu$ and $S\in \mathcal{B}_\lambda$, with operators $F_i$ connecting the nodes appropriately. It turns out that every connected component in the resulting crystal are again full crystals of tableaux, with Schur functions as their weight generating functions. We thus obtain a crystal-theoretic interpretation of the multiplicative Littlewood-Richardson rule. Namely, we have \[\mathcal{B}_\mu \otimes \mathcal{B}_\nu=\bigcup c^\lambda_{\mu\nu} \mathcal{B}_{\lambda}.\]

For instance, $\mathcal{B}_{(1)}\otimes \mathcal{B}_{(2)}$ is the crystal whose graph is precisely the diagram of $\mathcal{B}_{(3,1)/(1)}$ shown above, so \[\mathcal{B}_{(1)}\otimes \mathcal{B}_{(2)}=\mathcal{B}_{(2,1)}\cup \mathcal{B}_{(3)},\] matching the Schur expansion $s_{(1)}s_{(2)}=s_{(2,1)}+s_{(3)}.$

With these examples in mind, on the next page we will define the tensor category of crystals over any semisimple Lie algebra.

Let $\mathfrak{g}$ be a semisimple Lie algebra. One example to keep in mind is $\mathfrak{sl}_n$, the Lie algebra of trace-zero $n\times n$ matrices. Let $\Lambda$ be the weight lattice of $\mathfrak{g}$, the lattice of generalized eigenvalues of the Cartan subalgebra of $\mathfrak{g}$. Let $I$ be the index set of the simple roots $\{\alpha_i\}_{i\in I}$ of $\mathfrak{g}$. For instance, in the case of $\mathfrak{sl}_n$ (referred to as `type A’), we have that $\Lambda$ is the quotient of $\mathbb{Z}^n$ by the subspace generated by the vector $(1,1,\ldots,1)$, and $I=\{1,\ldots, n-1\}$ with simple roots \[\alpha_i=(0,0,\ldots,0,1,-1,0\ldots,0)=v_i-v_{i+1}\] where $v_i=(0,0,\ldots,0,1,0,0,\ldots,0)$ is the standard basis vector with a $1$ in the $i$-th position.

In the simplest nontrivial case, $\mathfrak{sl}_2$, the Lie algebra is generated by the matrices \[e_1=\left(\begin{array}{cc} 0 & 1 \\ 0 & 0\end{array}\right),\hspace{0.5cm} f_1=\left(\begin{array}{cc} 0 & 0 \\ 1 & 0\end{array}\right), \hspace{0.5cm}h_1=\left(\begin{array}{cc} 1 & 0 \\ 0 & -1\end{array}\right).\] In general there are generators $e_i,f_i,h_i$ for $i\in I$ that generate $\mathfrak{g}$, and hence $U_q(\mathfrak{g})$. The $e_i$ and $f_i$ elements, and their actions on weight spaces in $U_q(\mathfrak{g})$-representations, give rise to the corresponding crystal operators $E_i$ and $F_i$ in Kashiwara’s construction.

We now come to the main definition: a combinatorial crystal (sometimes referred to as a Kashiwara crystal) is a nonempty set $\mathcal{B}$ along with:

Raising and lowering operators \[e_i,f_i:\mathcal{B}\to \mathcal{B}\sqcup \{\emptyset\},\]
`String length’ operators \[\varepsilon_i,\varphi_i:\mathcal{B}\to \mathbb{Z}\sqcup \{-\infty\},\]
A weight function \[\mathrm{wt}:\mathcal{B}\to \Lambda,\]

satisfying the following properties:

The operators $e_i$ and $f_i$ are partial inverses: if $x,y\in \mathcal{B}$ then \[e_i(x)=y\text{ iff }f_i(y)=x.\] Moreover, in this case we have: \[\begin{eqnarray*} \mathrm{wt}(y)&=&\mathrm{wt}(x)+\alpha_i \\ \varepsilon_i(y)&=&\varepsilon_i(x)-1 \\ \varphi_i(y)&=&\varphi_i(x)+1. \end{eqnarray*} \]
For any $x\in \mathcal{B}$ and $i\in I$, we have \[\varphi_i(x)-\varepsilon_i(x)=\langle \mathrm{wt}(x),\alpha_i^\vee \rangle\] where $\alpha_i^\vee = 2\alpha_i/\langle \alpha_i,\alpha_i\rangle$ is the corresponding simple coroot. In particular if $\varphi_i(x)=-\infty$, then $\epsilon_i=-\infty$ as well, and in this case $e_i(x)=f_i(x)=0$.

The string lengths $\varphi_i(x)$ and $\varepsilon_i(x)$ often measure actual lengths to the end of the $i$-string through $x$ in the crystal graph, and such a crystal is called seminormal. More precisely, a crystal is seminormal if $\varphi_i(x)$ is the largest $k$ for which $f_i^k(x)\neq \emptyset$, and $\varepsilon_i(x)$ is the largest $k$ for which $e_i^k(x)\neq \emptyset$, for all $x$ and $i$.

One can now define the category of Kashiwara crystals by defining a crystal morphism from $\mathcal{B}$ to $\mathcal{C}$ to be a map $\psi:\mathcal{B}\to \mathcal{C}\cup \{\emptyset\}$ that preserves the string length, weight, and raising and lowering operators. In fact, it is a tensor category under the following tensor product. If $\mathcal{B}$ and $\mathcal{C}$ are two crystals of the same type, their tensor product $\mathcal{B}\otimes \mathcal{C}$ is the crystal having:

Ground set $\mathcal{B}\times \mathcal{C}$, the Cartesian product of the sets.
Weight function $\mathrm{wt}(x\otimes y)=\mathrm{wt}(x)+\mathrm{wt}(y)$.
Raising operators \[e_i(x\otimes y)=\begin{cases} e_i(x)\otimes y & \varphi_i(y) \lt \varepsilon_i(x) \\ x\otimes e_i(y) & \varphi_i(y)\ge \varepsilon_i(x) \end{cases}\] and lowering operators \[f_i(x\otimes y)=\begin{cases} f_i(x)\otimes y & \varphi_i(y) \le \varepsilon_i(x) \\ x\otimes f_i(y) & \varphi_i(y)\gt \varepsilon_i(x) \end{cases}.\]
String lengths \[\begin{eqnarray*}\varphi_i(x\otimes y)&=&\mathrm{max}(\varphi_i(x),\varphi_i(y)+\langle\mathrm{wt}(x),\alpha_i^\vee\rangle) \\ \varepsilon_i(x\otimes y)&=&\mathrm{max}(\varepsilon_i(y),\varepsilon_i(x)+\langle\mathrm{wt}(y),\alpha_i^\vee\rangle) \end{eqnarray*}\]

While this abstract category has many nice properties, it is in some sense too large. In particular, not every crystal in this category comes from a representation of $U_q(\mathfrak{g})$. In this paper, Stembridge introduced a set of local axioms that identify which objects in the category of crystals correspond to actual representations, for any simply-laced Lie type. (He restricts to the case of integrable representations, meaning that the operators $e_\alpha$ and $f_\alpha$ that generate $\mathfrak{g}$ act locally nilpotently). Such crystals, called Stembridge crystals, have unique highest weight elements, and the highest weight element uniquely determines its Stembridge crystal.

It’s not hard to check that the tableau crystals, and their tensor products, satisfy these axioms for the type A root system, using string lengths for the operators $\varphi_i$ and $\varepsilon_i$. They satisfy Stembridge’s axioms as well, and there is one tableau crystal for every possible highest weight, so in fact:

The tableau crystals are precisely the Stembridge crystals in type A, corresponding to the integrable representations of $U_q(\mathfrak{sl}_n)$.

In future posts, we’ll discuss some new developments in crystal base theory and their applications to symmetric function theory. An excellent reference for more crystal essentials is the book Crystal Bases by Dan Bump and Anne Schilling.