Classical Crystals
=================================================================

Tableaux and Representations of :math:`GL(n)`
---------------------------------------------

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

:math:`\def\lr#1#2#3{\multicolumn{1}{#1@{\hspace{.6ex}}c@{\hspace{.6ex}}#2}{\raisebox{-.3ex}{$#3$}}}\raisebox{-6ex}{\begin{array}[b]{cccc}\cline{1-3}\lr{|}{|}{\;}&\lr{|}{|}{\;}&\lr{|}{|}{\;}\\ \cline{1-3}\lr{|}{|}{}&\lr{|}{|}{}&&\\ \cline{1-2}\end{array}}`

A *semi-standard Young tableau* of shape :math:`\lambda` is a filling of the
box by integers in which the rows are weakly decreasing and the columns are
strictly decreasing. Thus

:math:`\def\lr#1#2#3{\multicolumn{1}{#1@{\hspace{.6ex}}c@{\hspace{.6ex}}#2}{\raisebox{-.3ex}{$#3$}}}\raisebox{-6ex}{\begin{array}[b]{cccc}\cline{1-3}\lr{|}{|}{3}&\lr{|}{|}{2}&\lr{|}{|}{2}\\ \cline{1-3}\lr{|}{|}{2}&\lr{|}{|}{1}&&\\ \cline{1-2}\end{array}}`

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

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

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

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

**Theorem** (Littlewood) If :math:`\lambda` is a partition, then the number of Semi-Standard Young
Tableaux with shape :math:`\lambda` and entries in :math:`{1,2,\cdots,r+1}` is the dimension
of :math:`\pi_\lambda`.

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

:math:`\begin{array}{ccccc}{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{1}&\lr{1}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{2}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{1}&\lr{2}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{2}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{1}&\lr{3}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{2}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{1}&\lr{3}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{2}&\lr{3}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}\\\\{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{1}&\lr{3}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{3}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{2}&\lr{3}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{3}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{2}&\lr{3}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{3}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{1}&\lr{1}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{1}&\lr{2}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}\\\\{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{2}&\lr{2}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{1}&\lr{1}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{3}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{1}&\lr{2}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{3}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{2}&\lr{2}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{3}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}&{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}&\lr{2}&\lr{2}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{3}&\lr{3}\\\cline{1-1}\cline{2-2}\end{array}$}}\end{array}`

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

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

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 :math:`T` is a tableaux, define the
*weight* of :math:`T` to be :math:`\hbox{wt}(T)=(k_1,\cdots,k_n)` where
:math:`k_i` is the number of :math:`i`'s in the tableaux. Then the
multiplicity of :math:`\mu` in the character :math:`\chi_\lambda` is the
number of tableaux of weight :math:`\lambda`. Thus if
:math:`\mathbf{z}=(z_1,\cdots,z_n)`, we have

:math:`\chi_\lambda(\mathbf{z})=\sum_T \mathbf{z}^{\hbox{wt}(T)}`

where the sum is over all semistandard Young tableaux of shape :math:`\lambda`
that have entries in :math:`{1,2,\cdots,r+1}`.

Tableaux and representations of :math:`S_k`
-------------------------------------------

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

:math:`\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 :math:`S_k` by partitions of :math:`k`.

Let us say that a Tableaux :math:`T` of shape :math:`\lambda\vdash k` is *standard*
if :math:`T` contains each entry :math:`1,2,\cdots,k` exactly once.

**Theorem** (Young, 1927) The degree of :math:`\pi_\lambda` is the number of standard
tableaux of shape :math:`\lambda`.

The Robinson-Schensted-Knuth correspondence
-------------------------------------------

References:

- Knuth, The Art of Computer Programming, Volume 3. Sorting and searching.
  Chapter on Tableaux and Involutions. (1973)

- Knuth, Permutations, matrices, and generalized Young tableaux. 
  Pacific J. Math. 34 1970 709--727.

- Fulton, Young Tableaux. (1997)

- Stanley, Enumerative Combinatorics, Volume 2 (1999).

The Robinson-Schensted-Knuth 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 :meth:`schensted_insertion`
of Tableau class in Sage.

Thus we have the following bijections:

- Pairs of standard tableaux of the same shape :math:`\lambda` 
  as :math:`\lambda` runs through the partitions of :math:`k` are in bijection
  with the :math:`k!` elements of :math:`S_k`.

- Pairs of tableaux :math:`T_1` and :math:`T_2` of shape :math:`\lambda` where
  :math:`\lambda` runs through the partitions of :math:`k` such that :math:`T_1`
  is a standard tableau and :math:`T_2` is a semistandard tableau in
  :math:`1,2,\cdots,n` are in bijection with the :math:`n^k` words of
  length :math:`k` in :math:`1,2,\cdots,n`.

- Pairs of tableaux :math:`T_1` and :math:`T_2` of the same shape :math:`\lambda` but
  arbitrary size in :math:`1,2,3,\cdots,n` are in bijection with :math:`n\times n`
  positive integer matrices.

- Pairs of tableaux :math:`T_1` and :math:`T_2` of conjugate shapes
  :math:`\lambda` and :math:`\lambda'` are in bijection with :math:`n\times n`
  matrices with entries :math:`0` or :math:`1`.

Analogies between representation theory and combinatorics
---------------------------------------------------------

The three bijections cited above have the following analogs
in representation theory.

- The group algebra :math:`\mathbb{C}` is an :math:`S_k\times S_k` bimodule
  with of dimension :math:`k!`. It decomposes as a direct sum of
  :math:`\pi_\lambda^{S_k}\otimes \pi_\lambda^{S_k}`.

- This is analogous to Frobenius-Schur duality, which decomposes
  the :math:`n^k`-dimensional vector space :math:`V^k` where :math:`V=\mathbb{C}`
  into the direct sum of :math:`\pi_\lambda^{GL(n)}\otimes\pi_\lambda^{S_k}`
  as a bimodule, where :math:`\lambda` runs through partitions of :math:`k`.

- This is analogous to the decomposition of the ring of polynomial
  functions on :math:`\hbox{Mat}(n,\mathbb{C})` on which :math:`GL(n,\mathbb{C})\times GL(n,\mathbb{C})`
  acts by :math:`(g_1,g_2)f(X)=f({^t g_1}X g_2)`. The polynomial ring
  decomposes into the direct sum of :math:`\pi^{GL(n)}_\lambda\otimes\pi^{GL(n)}_\lambda`.
  Taking traces gives the Cauchy identity.

- This is analogous to the decomposition of the exterior algebra
  over :math:`\hbox{Mat}(n,\mathbb{C})`. Taking traces gives the dual
  Cauchy identity.

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 :math:`\pi_\lambda^{GL(n)}`
is reinterpreted as a module for the quantized enveloping algebra
:math:`U_q(\mathfrak{gl}_n(\mathbb{C}))`, and the representation
:math:`\pi_\lambda^{S_k}` is reinterpreted as a module for the Iwahori
Hecke algebra. Then Frobenius-Schur duality persists. Reference:

- Jimbo, Michio A :math:`q`-analogue of :math:`U(\mathfrak{gl}(N+1))`, Hecke algebra,
  and the Yang-Baxter equation. Lett. Math. Phys. 11 (1986), no. 3, 247--252.

When :math:`q\to 1`, we recover the representation story. When :math:`q\to 0`,
we recover the combinatorial story.

Kashiwara Crystals
-------------------

References:

- Kashiwara, On crystal bases. Representations of groups (Banff, AB, 1994),
  155--197, CMS Conf. Proc., 16, Amer. Math. Soc., Providence, RI, 1995.

- Kashiwara and Nakashima, Crystal graphs for representations of the
  :math:`q`-analogue of classical Lie algebras.  J. Algebra 165 (1994), no. 2,
  295--345.

- Hong and Kang, Introduction to quantum groups and crystal bases. AMS Graduate
  Studies in Mathematics, 2002.

Kashiwara considered the highest weight modules of quantized enveloping
algebras :math:`U_q(\mathfrak{g})` in the limit when :math:`q\to 0`. The enveloping
algebra cannot be defined when :math:`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.

We will not make the most general definition of a crystal. See the references
for a more general definition. Let :math:`\Lambda` be the weight lattice of a classical
Cartan type.

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

:math:`\hbox{wt} (y) = \hbox{wt} (x) + \alpha_i, \qquad \varepsilon_i (x) =  \varepsilon_i (y) + 1, \qquad \phi_i (x) = \phi_i (y) - 1.`

Moreover, we assume that

:math:`\phi_i (x) - \varepsilon_i (x) = \left\langle \hbox{wt} (x), \alpha^{\vee}_i \right\rangle`

for all :math:`x \in \mathcal{B}`.

**Assumption** (Regularity) We will assume that :math:`\varepsilon_i(v)` is the
number of times that :math:`e_i` may applied to :math:`v`, and that :math:`\phi_i(v)` is the
number of times that :math:`f_i` may be applied. That is,
:math:`\phi_i (x) = \max \{k|f_i^k x \neq 0\}` and :math:`\varepsilon_i (x) = \max \{k|e_i^k (x) \neq 0\}.`

This regularity assumption is not made by Kashiwara, but it is satisfied by the
crystals that we are concerned with here. Kashiwara also allows :math:`\varepsilon_i`
and :math:`\phi_i` to take the value :math:`-\infty`.

Given the crystal :math:`\mathcal{B}`, the *character* :math:`\chi_{\mathcal{B}}` is:

:math:`\sum_{v\in\mathcal{B}} {\mathbf{z}}^{wt(v)}`.

Given any highest weight :math:`\lambda`, constructions of Kashiwara and Nakashima,
Littelmann and others produce a crystal :math:`\chi_{\mathcal{B}_\lambda}` such that
:math:`\chi_{\mathcal{B}_\lambda}=\chi_\lambda`, where :math:`\chi_\lambda` is the irreducible
character with highest weight :math:`\lambda`, as in :ref:`representations`.

The crystal :math:`\mathcal{B}_\lambda` is not uniquely characterized by the
properties that we have stated so far. For Cartan types A,D,E 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 :math:`\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.

You may download the following file:

http://sage.math.washington.edu/home/nthiery/dot2tex-2.8.7.spkg

Then run::

    sage -i dot2tex-2.8.7.spkg

to install the package.

Crystals of Tableaux in Sage
----------------------------

For type :math:`A_r`, Kashiwara and Nakashima put a crystal
structure on the set of tableaux with shape :math:`\lambda`
in :math:`1,2,\cdots,r+1`, and this is a realization of
:math:`\mathcal{B}_\lambda`. Moreover, this construction extends
to other Cartan types, as we will explain. At the moment, we will
consider how to draw pictures of these crystals.

Once you have dot2tex installed, you may make images pictures of crystals
as follows::

    sage: C=CrystalOfTableaux("A2",shape=[2,1])
    sage: C.latex_file("/tmp/a2rho.tex")

Here :math:`\lambda=(2,1)=(2,1,0)`. The crystal ``C`` is :math:`\mathcal{B}_{\lambda}`.
The character :math:`\chi_\lambda` will therefore be the eight-dimensional irreducible
character with this highest weight. The method :meth:`latex_file` produces

.. image:: a2rho.png

As you can see, the elements of this crystal are exactly the eight tableaux
of shape :math:`\lambda` with entries in :math:`\{1,2,3\}`. The convention is that if
:math:`x,y\in\mathcal{B}` and :math:`f_i(x)=y`, or equivalently :math:`e_i(y)=x`, then we
draw an arrow from :math:`x\to y`. Thus the highest weight tableau is the
one with no incoming arrows. Indeed, this is:

:math:`{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\lr{1}&\lr{1}\\\cline{1-1}\cline{2-2}\lr{2}\\\cline{1-1}\end{array}$}}`

We recall that the weight of the tableau is :math:`(k_1,k_2,k_3)` where :math:`k_i` is the number of
:math:`i`'s in the tableau, so this tableau has weight :math:`(2,1,0)`, which indeed equals :math:`\lambda`.

Once the crystal is created, you have access to the ambient space and its methods
through the method :meth:weight_lattice_realization()::

    sage: L = C.weight_lattice_realization(); L
    Ambient space of the Root system of type ['A', 2]
    sage: L.fundamental_weights()
    Finite family {1: (1, 0, 0), 2: (1, 1, 0)}

The highest weight vector is available as follows::

    sage: v = C.highest_weight_vector(); v
    [[1, 1], [2]]

or more simply::

    sage: C[0]
    [[1, 1], [2]]

Now we may apply the operators :math:`e_i` and :math:`f_i` to
move around in the crystal::

    sage: v.f(1)
    [[1, 2], [2]]
    sage: v.f(1).f(1)
    sage: v.f(1).f(1) == None
    True
    sage: v.f(1).f(2)
    [[1, 3], [2]]
    sage: v.f(1).f(2).f(2)
    [[1, 3], [3]]
    sage: v.f(1).f(2).f(2).f(1)
    [[2, 3], [3]]
    sage: v.f(1).f(2).f(2).f(1) == v.f(2).f(1).f(1).f(2)
    True

You can construct the character if you first make a Weyl character ring::

    sage: A2 = WeylCharacterRing("A2")
    sage: C.character(A2)
    A2(2,1,0)

Crystals of Letters
-------------------

For each of the classical Cartan types there is a *standard
crystal* :math:`\mathcal{B}_{\hbox{standard}}` from which other
crystals can be built up by taking tensor products and extracting
constituent irreducible crystals. This procedure is sufficient
for Cartan types :math:`A_r` and :math:`C_r`. For types :math:`B_r` and :math:`D_r`
the standard crystal must be supplemented with a *spin crystal*.

.. image:: standard1.png

The crystal of letters is a special case of the crystal of tableaux
in the sense that :math:`\mathcal{B}_{\hbox{standard}}` is isomorphic
the crystal of tableaux whose highest weight :math:`\lambda` is the
highest weight vector of the standard representation. Thus compare::

    sage: CrystalOfLetters("A3")
    The crystal of letters for type ['A', 3]
    sage: CrystalOfTableaux("A3",shape=[1])
    The crystal of tableaux of type ['A', 3] and shape(s) [[1]]

These two crystals are different in implementation, but they
are isomorphic, and in fact the second crystal is constructed
from the first. Crystals of letters have a special role in
the theory since they are particularly simple, yet as
Kashiwara and Nakashima showed, the crystals of tableaux can
be created from them.  We will review how this works.

Tensor Products of Crystals
---------------------------

Kashiwara defined the tensor product of crystals in a purely combinatorial
way. The beauty of this construction is that it exactly parallels the
tensor product of crystals of representations. That is, if 
:math:`\lambda` and :math:`\mu` are dominant weights, then 
:math:`\mathcal{B}_\lambda\otimes\mathcal{B}_\mu` is a (usually
disconnected) crystal which may contain multiple copies of
:math:`\mathcal{B}_\nu` (for another dominant weight :math:`\nu`) but the
number of copies of :math:`\mathcal{B}_\nu` is exactly the multiplicity
of :math:`\chi_\nu` in :math:`\chi_\lambda\chi_\mu`.

We will describe two conventions for the tensor product of
crystals. These conventions would have to be modified slightly
without the regularity assumption.

Kashiwara's definition
^^^^^^^^^^^^^^^^^^^^^^

As a set, the tensor product :math:`\mathcal{B} \otimes \mathcal{C}` of crystals
:math:`\mathcal{B}` and :math:`\mathcal{C}` is the Cartesian product, but we denote the
ordered pair :math:`(x, y)` with :math:`x \in \mathcal{B}` and :math:`y \in \mathcal{C}` by :math:`x
\otimes y`. We define :math:`\hbox{wt} (x \otimes y) = \hbox{wt} (x) + \hbox{wt}
(y)`. We define

:math:`f_i (x \otimes y) = \left\{ \begin{array}{ll} f_i (x) \otimes y & \text{if $\phi_i (x) > \varepsilon_i (y)$},\\ x \otimes f_i (y) & \text{if $\phi_i (x) \le \varepsilon_i (y)$}, \end{array} \right.`

and

:math:`e_i (x \otimes y) = \left\{ \begin{array}{ll} e_i (x) \otimes y & \text{if $\phi_i (x) \ge \varepsilon_i (y)$},\\ x \otimes e_i (y) & \text{if $\phi_i (x) < \varepsilon_i (y)$} . \end{array} \right.`

It is understood that :math:`x \otimes 0 = 0 \otimes x = 0`. We also define:

:math:`\phi_i (x \otimes y) = \max (\phi_i (y), \phi_i (x) + \phi_i (y) - \varepsilon_i (y)),`

:math:`\varepsilon_i (x \otimes y) = \max (\varepsilon_i (x), \varepsilon_i (x) + \varepsilon_i (y) - \phi_i (x)) .`


Alternative definition
^^^^^^^^^^^^^^^^^^^^^^

As a set, the tensor product :math:`\mathcal{B} \otimes \mathcal{C}` of crystals
:math:`\mathcal{B}` and :math:`\mathcal{C}` is the Cartesian product, but we denote the
ordered pair :math:`(y, x)` with :math:`y \in \mathcal{B}` and :math:`x \in \mathcal{C}` by :math:`x
\otimes y`. We define :math:`\hbox{wt} (x \otimes y) = \hbox{wt} (y) + \hbox{wt}
(x)`. We define

:math:`f_i (x \otimes y) = \left\{ \begin{array}{ll}  f_i (x) \otimes y & \text{if $\phi_i (y) \le \varepsilon_i (x)$},\\  x \otimes f_i (y) & \text{if $\phi_i (y) > \varepsilon_i (x)$},  \end{array} \right.`

and

:math:`e_i (x \otimes y) = \left\{ \begin{array}{ll}  e_i (x) \otimes y & \text{if $\phi_i (y) < \varepsilon_i (x)$} .\\  x \otimes e_i (y) & \text{if $\phi_i (y) \ge \varepsilon_i (x)$}, \end{array} \right.`

It is understood that :math:`y \otimes 0 = 0 \otimes y = 0`. We also define

:math:`\phi_i (x \otimes y)  =  \max (\phi_i (x), \phi_i (y) + \phi_i (x) - \varepsilon_i (x)),`

:math:`\varepsilon_i (x \otimes y)  =  \max (\varepsilon_i (y), \varepsilon_i (y) + \varepsilon_i (x) - \phi_i (y)) .`

The tensor product is associative: :math:`(x\otimes y)\otimes z\mapsto x\otimes(y\otimes z)` is
an isomorphism :math:`(\mathcal{B}\otimes\mathcal{C})\otimes\mathcal{D}\to\mathcal{B}\otimes(\mathcal{C}\otimes\mathcal{D})`,
and so we may consider tensor products of arbitrary numbers of crystals.

The relationship between the two definitions
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The relationship between the two definitions is simply that the
Kashiwara tensor product :math:`\mathcal{B}\otimes\mathcal{C}` is the
alternate tensor product :math:`\mathcal{C}\otimes\mathcal{B}` in
reverse order. Sage uses the alternative tensor product. Even
though the tensor product construction is *a priori* asymmetrical,
both constructions produce isomorphic crystals, and in particular Sage's
crystals of tableaux are identical to Kashiwara's.

Tensor products of crystals in Sage
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
You may construct the tensor product of several crystals in Sage using ``TensorProductOfCrystals``::

    sage: C = CrystalOfLetters("A2")
    sage: T = TensorProductOfCrystals(C,C,C); T
    Full tensor product of the crystals [The crystal of letters for type ['A', 2], 
    The crystal of letters for type ['A', 2], The crystal of letters for type ['A', 2]]
    sage: T.cardinality()
    27
    sage: T.highest_weight_vectors()
    [[1, 1, 1], [1, 2, 1], [2, 1, 1], [3, 2, 1]]

This crystal has four highest weight vectors. We may understand this as follows::

    sage: A2 = WeylCharacterRing("A2")
    sage: chi_C = C.character(A2)
    sage: chi_T = T.character(A2)
    sage: chi_C
    A2(1,0,0)
    sage: chi_T
    A2(1,1,1) + 2*A2(2,1,0) + A2(3,0,0)
    sage: chi_T == chi_C^3
    True

As expected, the character of ``T`` is the cube of the character of ``C``, and
representations with highest weight :math:`(1,1,1)`, :math:`(3,0,0)` and :math:`(2,1,0)`. This
decomposition is predicted by Frobenius-Schur duality: the multiplicity
of :math:`\pi_\lambda^{GL(n)}` in :math:`\otimes^3\mathbb{C}^3` is the degree of
of :math:`\pi_\lambda^{S_3}`.

It is useful to be able to select one irreducible constitutent of T.
If we only want one of the irreducible constituents of T, we can specify a
list of highest weight vectors by the option ``generators``. If the list
has only one element, then we get an irreducible crystal. We can make
four such crystals::

    sage: [T1,T2,T3,T4] = \
    [TensorProductOfCrystals(C,C,C,generators=[v]) for v in T.highest_weight_vectors()]
    sage: [B.cardinality() for B in [T1,T2,T3,T4]]
    [10, 8, 8, 1]
    sage: [B.character(A2) for B in [T1,T2,T3,T4]]
    [A2(3,0,0), A2(2,1,0), A2(2,1,0), A2(1,1,1)]

We see that two of these crystals are isomorphic, with character ``A2(2,1,0)``.
Try::

    sage: T1.plot(), T2.plot(), T3.plot(), T4.plot()

Elements of ``TensorProductOfCrystals(A,B,C, ...)`` are represented by
sequences ``[a,b,c, ...]`` with ``a`` in ``A``, ``b`` in ``B``, etc.
This of course represents :math:`a\otimes b\otimes c\otimes\cdots`.

Crystals of Tableaux as tensor products of crystals
---------------------------------------------------

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

    sage: T = CrystalOfTableaux("A3",shape=[3,1])
    sage: v = T.highest_weight_vector().f(1).f(2).f(3).f(1).f(2); v
    [[1, 3, 4], [2]]
    sage: v._list
    [2, 1, 3, 4]

We've looked at the internal representation of :math:`v`, where it is represented
as an element of the fourth tensor power of the CrystalOfLetters. We see that
the tableau:

:math:`{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}\raisebox{-.6ex}{$\begin{array}[b]{ccc}\cline{1-1}\cline{2-2}\cline{3-3}\lr{1}&\lr{3}&\lr{4}\\\cline{1-1}\cline{2-2}\cline{3-3}\lr{2}\\\cline{1-1}\end{array}$}}`

is interpreted as the tensor:

:math:`\begin{array}{|l|}\hline 2\\ \hline\end{array} \otimes \begin{array}{|l|} \hline 1\\ \hline\end{array} \otimes \begin{array}{|l|} \hline 4\\ \hline\end{array} \otimes \begin{array}{|l|} \hline 3\\ \hline\end{array}`

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.

Spin Crystals
-------------

For the Cartan types :math:`A_r`, :math:`C_r` or :math:`G_2`, CrystalOfTableaux are capable of making any
finite crystal. (For type :math:`A_r` it is necessary that the highest weight :math:`\lambda` be
a partition.)

For Cartan types :math:`B_r` and :math:`D_r`, CrystalOfTableaux fail to make :math:`\mathcal{B}_\lambda`
if :math:`\lambda` is half-integral. For type :math:`B_2` you can do this::

    sage: B = FastCrystal(['B',2],shape=[3/2,1/2]); B
    The fast crystal for B2 with shape [3/2,1/2]
    sage: v = B.highest_weight_vector(); v.weight()
    (3/2, 1/2)

However FastCrystals are only available for rank two Cartan types. We therefore
have to do something else to create crystals of half-integral weight.

For types :math:`B_r` and :math:`D_r` the solution to this problem involves the use of
*spin crystals*.

Type B spin crystal
^^^^^^^^^^^^^^^^^^^
The spin crystal has highest weight :math:`(1/2,\cdots,1/2)`. This is
the last fundamental weight. The irreducible representation with this weight
is the spin representation of degree :math:`2^r`. Its crystal is hand-coded in
Sage::

    sage: Cspin = CrystalOfSpins("B3"); Cspin
    The crystal of spins for type ['B', 3]
    sage: Cspin.cardinality()
    8

We can make use of this to construct an arbitrary crystal with
highest weight :math:`\lambda`, where :math:`\lambda` is a half-integral
weight. For example, suppose that :math:`\lambda=(3/2,3/2,1/2)`. The
corresponding irreducible character will have degree 112::

    sage: B3=WeylCharacterRing("B3")
    sage: B3(3/2,3/2,1/2).degree()
    112

So :math:`\mathcal{B}_\lambda` will have 112 elements. We can
find it as a subcrystal of ``Cspin``:math:`\otimes\mathcal{B}_\mu`,
where :math:`\mu=\lambda-(1/2,1/2,1/2)=(1,1,0)`::

    sage: B3(1,1,0)*B3(1/2,1/2,1/2)
    B3(1/2,1/2,1/2) + B3(3/2,1/2,1/2) + B3(3/2,3/2,1/2)

We see that just taking the tensor product of these two
crystals will produce a reducible crystal with three
constitutents, and we want to extract the one we want.
We do that as follows::

    sage: C1 = CrystalOfTableaux("B3",shape=[1,1])
    sage: C = TensorProductOfCrystals(C1,Cspin,generators=[[C1[0],Cspin[0]]])
    sage: C.cardinality()
    112

This is the desired crystal.

Type D spin crystals
^^^^^^^^^^^^^^^^^^^^
A similar situation pertains for type :math:`D_r`, but now there are two spin crystals,
both of degree :math:`2^{r-1}`. These are hand-coded in sage::

    sage: SpinPlus = CrystalOfSpinsPlus("D4")
    sage: SpinMinus = CrystalOfSpinsMinus("D4")
    sage: SpinPlus[0].weight()
    (1/2, 1/2, 1/2, 1/2)
    sage: SpinMinus[0].weight()
    (1/2, 1/2, 1/2, -1/2)
    sage: [C.cardinality() for C in [SpinPlus,SpinMinus]]
    [8, 8]

You can use them similarly to the type B crystal of spins in
order to construct any crystal of half-integral weight.

Levi Branching Rules for Crystals
---------------------------------

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

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

Affine Crystals
---------------

Sage contains support for affine crystals. These lie outside the scope
of this document.