Classical Crystals¶

A classical crystal is one coming from the finite (classical) types \(A_r, B_r, C_r, D_r, E_{6,7,8}, F_4\), and \(G_2\). Here we describe some background before going into the general theory of crystals and the type dependent combinatorics.

Tableaux and representations of \(GL(n)\)¶

Let \(\lambda\) be a partition. The Young diagram of \(\lambda\) is the array of boxes having \(\lambda_i\) boxes in the \(i\)-th row, left adjusted. Thus if \(\lambda = (3, 2)\) the diagram is:

A semi-standard Young tableau of shape \(\lambda\) is a filling of the box by integers in which the rows are weakly increasing and the columns are strictly increasing. Thus

is a semistandard Young tableau. Sage has a Tableau class, and you may create this tableau as follows:

Sage

sage: T = Tableau([[1,2,2], [2,3]]); T
[[1, 2, 2], [2, 3]]

Python

>>> from sage.all import *
>>> T = Tableau([[Integer(1),Integer(2),Integer(2)], [Integer(2),Integer(3)]]); T
[[1, 2, 2], [2, 3]]

Sage Live

T = Tableau([[1,2,2], [2,3]]); T

A partition of length \(\le r+1\) is a dominant weight for \(GL(r+1, \mathbf{C})\) according to the description of the ambient space in Standard realizations of the ambient spaces. Therefore it corresponds to an irreducible representation \(\pi_\lambda = \pi_\lambda^{GL(r+1)}\) of \(GL(r+1, \mathbf{C})\).

It is true that not every dominant weight \(\lambda\) is a partition, since a dominant weight might have some values \(\lambda_i\) negative. The dominant weight \(\lambda\) is a partition if and only if the character of \(\lambda\) is a polynomial as a function on the space \(\hbox{Mat}_n(\mathbf{C})\). Thus for example \(\det^{-1} = \pi_\lambda\) with \(\lambda = (-1, \dots, -1)\), which is a dominant weight but not a partition, and the character is not a polynomial function on \(\hbox{Mat}_n(\mathbf{C})\).

Theorem [Littlewood] If \(\lambda\) is a partition, then the number of semi-standard Young tableaux with shape \(\lambda\) and entries in \(\{1,2,\ldots,r+1\}\) is the dimension of \(\pi_\lambda\).

For example, if \(\lambda = (3,2)\) and \(r = 2\), then we find 15 tableaux with shape \(\lambda\) and entries in \(\{1,2,3\}\):

This is consistent with the theorem since the dimension of the irreducible representation of \(GL(3)\) with highest weight \((3,2,0)\) has dimension 15:

Sage

sage: A2 = WeylCharacterRing("A2")
sage: A2(3,2,0).degree()
15

Python

>>> from sage.all import *
>>> A2 = WeylCharacterRing("A2")
>>> A2(Integer(3),Integer(2),Integer(0)).degree()
15

Sage Live

A2 = WeylCharacterRing("A2")
A2(3,2,0).degree()

In fact we may obtain the character of the representation from the set of tableaux. Indeed, one of the definitions of the Schur polynomial (due to Littlewood) is the following combinatorial one. If \(T\) is a tableaux, define the weight of \(T\) to be \(\hbox{wt}(T) = (k_1,\dots,k_n)\) where \(k_i\) is the number of \(i\)’s in the tableaux. Then the multiplicity of \(\mu\) in the character \(\chi_\lambda\) is the number of tableaux of weight \(\lambda\). Thus if \(\mathbf{z} = (z_1,\dots,z_n)\), we have

\[\chi_\lambda(\mathbf{z}) = \sum_T \mathbf{z}^{\hbox{wt}(T)}\]

where the sum is over all semi-standard Young tableaux of shape \(\lambda\) that have entries in \(\{1, 2, \ldots, r+1\}\).

Frobenius-Schur Duality¶

Frobenius-Schur duality is a relationship between the representation theories of the symmetric group and general linear group. We will relate this to tableaux in the next section.

Representations of the symmetric group \(S_k\) are parametrized by partitions \(\lambda\) of \(k\). The parametrization may be characterized as follows. Let \(n\) be any integer \(\ge k\). Then both \(GL(n,\mathbf{C})\) and \(S_k\) act on \(\otimes^k V\) where \(V = \mathbf{C}^n\). Indeed, \(GL(n)\) acts on each \(V\) and \(S_k\) permutes them. Then if \(\pi_\lambda^{GL(n)}\) is the representation of \(GL(n,\mathbf{C})\) with highest weight vector \(\lambda\) and \(\pi_\lambda^{S_k}\) is the irreducible representation of \(S_k\) parametrized by \(\lambda\) then

\[\otimes^k V \cong \bigoplus_{\lambda\vdash k}\pi^{GL(n)}_\lambda\otimes\pi^{S_k}_\lambda\]

as bimodules for the two groups. This is Frobenius-Schur duality and it serves to characterize the parametrization of the irreducible representations of \(S_k\) by partitions of \(k\).

Counting pairs of tableaux¶

In both the representation theory of \(GL(n)\) and the representation theory of \(S_k\), the degrees of irreducible representations can be expressed in terms of the number of tableaux of the appropriate type. We have already stated the theorem for \(GL(n)\). For \(S_k\), it goes as follows.

Let us say that a semistandard Young tableau \(T\) of shape \(\lambda\vdash k\) is standard if \(T\) contains each entry \(1,2,\dots,k\) exactly once. Thus both rows and columns are strictly increasing.

Theorem [Young, 1927] The degree of \(\pi_\lambda\) is the number of standard tableaux of shape \(\lambda\).

Now let us consider the implications of Frobenius-Schur duality. The dimension of \(\otimes^k V\) is \(n^k\). Therefore \(n^k\) is equal to the number of pairs \((T1,T2)\) of tableaux of the same shape \(\lambda\vdash k\), where the first tableaux is standard (in the alphabet \(1,2,\ldots,k\)), and the second the second semistandard (in the alphabet \(1,2,\ldots,n\)).

The Robinson-Schensted-Knuth correspondence¶

The last purely combinatorial statement has a combinatorial proof, based on the Robinson-Schensted-Knuth (RSK) correspondence.

References:

[Knuth1998], section “Tableaux and Involutions”.
[Knuth1970]
[Fulton1997]
[Stanley1999]

The RSK correspondence gives bijections between pairs of tableaux of various types and combinatorial objects of different types. We will not review the correspondence in detail here, but see the references. We note that Schensted insertion is implemented as the method schensted_insertion of Tableau class in Sage.

Thus we have the following bijections:

Pairs of tableaux \(T_1\) and \(T_2\) of shape \(\lambda\) where \(\lambda\) runs through the partitions of \(k\) such that \(T_1\) is a standard tableau and \(T_2\) is a semistandard tableau in \(1,2,\dots,n\) are in bijection with the \(n^k\) words of length \(k\) in \(1,2,\dots,n\).
Pairs of standard tableaux of the same shape \(\lambda\) as \(\lambda\) runs through the partitions of \(k\) are in bijection with the \(k!\) elements of \(S_k\).
Pairs of tableaux \(T_1\) and \(T_2\) of the same shape \(\lambda\) but arbitrary size in \(1,2,3,\dots,n\) are in bijection with \(n \times n\) positive integer matrices.
Pairs of tableaux \(T_1\) and \(T_2\) of conjugate shapes \(\lambda\) and \(\lambda'\) are in bijection with \(n \times n\) matrices with entries \(0\) or \(1\).

The second of these four bijection gives a combinatorial proof of the fact explained above, that the number of pairs \((T1,T2)\) of tableaux of the same shape \(\lambda\vdash k\), where the first tableaux is standard (in the alphabet \(1,2,\cdots,k\)), and the second the second semistandard (in the alphabet \(1,2,\cdots,n\)). So this second bijection is a combinatorial analog of Frobenius-Schur duality.

Analogies between representation theory and combinatorics¶

The four combinatorial bijections (variants of RSK) cited above have the following analogs in representation theory.

The first combinatorial fact corresponds to Frobenius-Schur duality, as we have already explained.
The second combinatorial fact also has an analog in representation theory. The group algebra \(\mathbf{C}[S_k]\) is an \(S_k \times S_k\) bimodule with of dimension \(k!\). It decomposes as a direct sum of \(\pi_\lambda^{S_k} \otimes \pi_\lambda^{S_k}\).

Both the combinatorial fact and the decomposition of \(\mathbf{C}[S_k]\) show that the number of pairs of standard tableaux of size \(k\) and the same shape equals \(k!\).

The third combinatorial fact is analogous to the decomposition of the ring of polynomial functions on \(\hbox{Mat}(n, \mathbf{C})\) on which \(GL(n, \mathbf{C}) \times GL(n, \mathbf{C})\) acts by \((g_1, g_2)f(X) = f({^t g_1}X g_2)\). The polynomial ring decomposes into the direct sum of \(\pi^{GL(n)}_\lambda \otimes \pi^{GL(n)}_\lambda\).

Taking traces gives the Cauchy identity:

\[\sum_\lambda s_\lambda(x_1,\cdots,x_n) s_\lambda(y_1,\cdots,y_n) =\prod_{i,j}(1-x_i y_j)^{-1}\]

where \(x_i\) are the eigenvalues of \(g_1\) and \(y_j\) are the eigenvalues of \(g_2\). The sum is over all partitions \(\lambda\).

The last combinatorial fact is analogous to the decomposition of the exterior algebra over \(\hbox{Mat}(n, \mathbf{C})\).

Taking traces gives the dual Cauchy identity:

\[\sum_\lambda s_\lambda(x_1,\cdots,x_n) s_{\lambda'}(y_1,\cdots,y_n) =\prod_{i,j}(1+x_i y_j).\]

Again the sum is over partitions \(\lambda\) and here \(\lambda'\) is the conjugate partition.

Interpolating between representation theory and combinatorics¶

The theory of quantum groups interpolates between the representation theoretic picture and the combinatorial picture, and thereby explains these analogies. The representation \(\pi_\lambda^{GL(n)}\) is reinterpreted as a module for the quantized enveloping algebra \(U_q(\mathfrak{gl}_n(\mathbf{C}))\), and the representation \(\pi_\lambda^{S_k}\) is reinterpreted as a module for the Iwahori Hecke algebra. Then Frobenius-Schur duality persists. See [Jimbo1986]. When \(q \to 1\), we recover the representation story. When \(q \to 0\), we recover the combinatorial story.

Kashiwara crystals¶

References:

Kashiwara considered the highest weight modules of quantized enveloping algebras \(U_q(\mathfrak{g})\) in the limit when \(q \to 0\). The enveloping algebra cannot be defined when \(q = 0\), but a limiting structure can still be detected. This is the crystal basis of the module.

Kashiwara’s crystal bases have a combinatorial structure that sheds light even on purely combinatorial constructions on tableaux that predated quantum groups. It gives a good generalization to other Cartan types (or more generally to Kac-Moody algebras).

Let \(\Lambda\) be the weight lattice of a Cartan type with root system \(\Phi\). We now define a crystal of type \(\Phi\). Let \(\mathcal{B}\) be a set, and let \(0 \notin \mathcal{B}\) be an auxiliary element. For each index \(1 \le i \le r\) we assume there given maps \(e_i, f_i : \mathcal{B} \longrightarrow \mathcal{B} \cup \{0\}\), maps \(\varepsilon_i, \varphi_i : \mathcal{B} \longrightarrow \mathbf{Z}\) and a map \(\hbox{wt} : \mathcal{B} \longrightarrow \Lambda\) satisfying certain assumptions, which we now describe. It is assumed that if \(x, y \in \mathcal{B}\) then \(e_i (x) = y\) if and only if \(f_i (y) = x\). In this case, it is assumed that

\[\hbox{wt} (y) = \hbox{wt} (x) + \alpha_i, \qquad \varepsilon_i (x) = \varepsilon_i (y) + 1, \qquad \varphi_i (x) = \varphi_i (y) - 1.\]

Moreover, we assume that

\[\varphi_i (x) - \varepsilon_i (x) = \left\langle \hbox{wt} (x), \alpha^{\vee}_i \right\rangle\]

for all \(x \in \mathcal{B}\).

We call a crystal regular if it satisfies the additional assumption that \(\varepsilon_i(v)\) is the number of times that \(e_i\) may be applied to \(v\), and that \(\phi_i(v)\) is the number of times that \(f_i\) may be applied. That is, \(\varphi_i (x) = \max \{k | f_i^k x \neq 0\}\) and \(\varepsilon_i (x) = \max \{k | e_i^k (x) \neq 0\}\). Kashiwara also allows \(\varepsilon_i\) and \(\varphi_i\) to take the value \(-\infty\).

Note

Most of the crystals that we are concerned with here are regular.

Given the crystal \(\mathcal{B}\), the character \(\chi_{\mathcal{B}}\) is:

\[\sum_{v\in\mathcal{B}} {\mathbf{z}}^{wt(v)}.\]

Given any highest weight \(\lambda\), constructions of Kashiwara and Nakashima, Littelmann and others produce a crystal \(\chi_{\mathcal{B}_\lambda}\) such that \(\chi_{\mathcal{B}_\lambda} = \chi_\lambda\), where \(\chi_\lambda\) is the irreducible character with highest weight \(\lambda\), as in Representations and characters.

The crystal \(\mathcal{B}_\lambda\) is not uniquely characterized by the properties that we have stated so far. For Cartan types \(A, D, E\) (more generally, any simply-laced type) it may be characterized by these properties together with certain other Stembridge axioms. We will take it for granted that there is a unique “correct” crystal \(\mathcal{B}_\lambda\) and discuss how these are constructed in Sage.

Installing dot2tex¶

Before giving examples of crystals, we digress to help you install dot2tex, which you will need in order to make latex images of crystals.

dot2tex is an optional package of sage and the latest version can be installed via:

$ sage -i dot2tex

This also requires various LaTeX packages. The following command checks whether those are available:

Sage

sage: from sage.graphs.graph_latex import check_tkz_graph
sage: check_tkz_graph() # random

Python

>>> from sage.all import *
>>> from sage.graphs.graph_latex import check_tkz_graph
>>> check_tkz_graph() # random

Sage Live

from sage.graphs.graph_latex import check_tkz_graph
check_tkz_graph() # random

Crystals of tableaux as tensor products of crystals¶

Sage implements the CrystalOfTableaux as a subcrystal of a tensor product of the ClassicalCrystalOfLetters. You can see how its done as follows:

Sage

sage: T = crystals.Tableaux("A4",shape=[3,2])
sage: v = T.highest_weight_vector().f(1).f(2).f(3).f(2).f(1).f(4).f(2).f(3); v
[[1, 2, 5], [3, 4]]
sage: list(v)
[3, 1, 4, 2, 5]

Python

>>> from sage.all import *
>>> T = crystals.Tableaux("A4",shape=[Integer(3),Integer(2)])
>>> v = T.highest_weight_vector().f(Integer(1)).f(Integer(2)).f(Integer(3)).f(Integer(2)).f(Integer(1)).f(Integer(4)).f(Integer(2)).f(Integer(3)); v
[[1, 2, 5], [3, 4]]
>>> list(v)
[3, 1, 4, 2, 5]

Sage Live

T = crystals.Tableaux("A4",shape=[3,2])
v = T.highest_weight_vector().f(1).f(2).f(3).f(2).f(1).f(4).f(2).f(3); v
list(v)

We’ve looked at the internal representation of \(v\), where it is represented as an element of the fourth tensor power of the ClassicalCrystalOfLetters. We see that the tableau:

\[\]

is interpreted as the tensor:

\[\]

The elements of the tableau are read from bottom to top and from left to right. This is the inverse middle-Eastern reading of the tableau. See Hong and Kang, loc. cit. for discussion of the readings of a tableau.

Levi branching rules for crystals¶

Let \(G\) be a Lie group and \(H\) a Levi subgroup. We have already seen that the Dynkin diagram of \(H\) is obtained from that of \(G\) by erasing one or more nodes.

If \(\mathcal{C}\) is a crystal for \(G\), then we may obtain the corresponding crystal for \(H\) by a similar process. For example if the Dynkin diagram for \(H\) is obtained from the Dynkin diagram for \(G\) by erasing the \(i\)-th node, then if we erase all the edges in the crystal \(\mathcal{C}\) that are labeled with \(i\), we obtain a crystal for \(H\).

In Sage this is achieved by specifying the index set used in the digraph method:

Sage

sage: T = crystals.Tableaux(['D',4],shape=[1])
sage: G = T.digraph(index_set=[1,2,3])

Python

>>> from sage.all import *
>>> T = crystals.Tableaux(['D',Integer(4)],shape=[Integer(1)])
>>> G = T.digraph(index_set=[Integer(1),Integer(2),Integer(3)])

Sage Live

T = crystals.Tableaux(['D',4],shape=[1])
G = T.digraph(index_set=[1,2,3])

We see that the type \(D_4\) crystal indeed decomposes into two type \(A_3\) components.

For more on branching rules, see Maximal Subgroups and Branching Rules or Levi subgroups for specifics on the Levi subgroups.

Subcrystals¶

Sometimes it might be desirable to work with a subcrystal of a crystal. For example, one might want to look at all \(\{2,3,\ldots,n\}\) highest elements of a crystal and look at a particular such component:

Sage

sage: T = crystals.Tableaux(['D',4],shape=[2,1])
sage: hw = [ t for t in T if t.is_highest_weight(index_set = [2,3,4]) ]; hw
[[[1, 1], [2]],
 [[1, 2], [2]],
 [[2, -1], [-2]],
 [[2, -1], [-1]],
 [[1, -1], [2]],
 [[2, -1], [3]],
 [[1, 2], [3]],
 [[2, 2], [3]],
 [[1, 2], [-2]],
 [[2, 2], [-2]],
 [[2, 2], [-1]]]
sage: C = T.subcrystal(generators = [T(rows=[[2,-1],[3]])], index_set = [2,3,4])
sage: G = T.digraph(subset = C, index_set=[2,3,4])

Python

>>> from sage.all import *
>>> T = crystals.Tableaux(['D',Integer(4)],shape=[Integer(2),Integer(1)])
>>> hw = [ t for t in T if t.is_highest_weight(index_set = [Integer(2),Integer(3),Integer(4)]) ]; hw
[[[1, 1], [2]],
 [[1, 2], [2]],
 [[2, -1], [-2]],
 [[2, -1], [-1]],
 [[1, -1], [2]],
 [[2, -1], [3]],
 [[1, 2], [3]],
 [[2, 2], [3]],
 [[1, 2], [-2]],
 [[2, 2], [-2]],
 [[2, 2], [-1]]]
>>> C = T.subcrystal(generators = [T(rows=[[Integer(2),-Integer(1)],[Integer(3)]])], index_set = [Integer(2),Integer(3),Integer(4)])
>>> G = T.digraph(subset = C, index_set=[Integer(2),Integer(3),Integer(4)])

Sage Live

T = crystals.Tableaux(['D',4],shape=[2,1])
hw = [ t for t in T if t.is_highest_weight(index_set = [2,3,4]) ]; hw
C = T.subcrystal(generators = [T(rows=[[2,-1],[3]])], index_set = [2,3,4])
G = T.digraph(subset = C, index_set=[2,3,4])

Classical Crystals¶

Tableaux and representations of \(GL(n)\)¶

Frobenius-Schur Duality¶

Counting pairs of tableaux¶

The Robinson-Schensted-Knuth correspondence¶

Analogies between representation theory and combinatorics¶

Interpolating between representation theory and combinatorics¶

Kashiwara crystals¶

Installing dot2tex¶

Crystals of tableaux in Sage¶

Crystals of letters¶

Tensor products of crystals¶

Kashiwara’s definition¶

Alternative definition¶

The relationship between the two definitions¶

Tensor products of crystals in Sage¶

Crystals of tableaux as tensor products of crystals¶

Spin crystals¶

Type B spin crystal¶

Type D spin crystals¶

Lusztig involution¶

Levi branching rules for crystals¶

Subcrystals¶