# An introduction to crystals¶

Informally, a crystal $$\mathcal{B}$$ is an oriented graph with edges colored in some set $$I$$ such that, for each $$i\in I$$, each node $$x$$ has:

• at most one $$i$$-successor, denoted $$f_i x$$;
• at most one $$i$$-predecessor, denoted $$e_i x$$.

By convention, one writes $$f_i x=\emptyset$$ and $$e_i x=\emptyset$$ when $$x$$ has no successor resp. predecessor.

One may think of $$\mathcal{B}$$ as essentially a deterministic automaton whose dual is also deterministic; in this context, the $$f_i$$’s and $$e_i$$’s are respectively the transition functions of the automaton and of its dual, and $$\emptyset$$ is the sink.

A crystal comes further endowed with a weight function $$\operatorname{wt} : \mathcal{B} \to L$$ which satisfies appropriate conditions.

In combinatorial representation theory, crystals are used as combinatorial data to model representations of Lie algebra.

## Axiomatic definition¶

Let $$C$$ be a Cartan type (CartanType) with index set $$I$$, and $$L$$ be a realization of the weight lattice of the type $$C$$. Let $$\alpha_i$$ and $$\alpha^{\vee}_i$$ denote the simple roots and coroots respectively.

A type $$C$$ crystal is a non-empty set $$\mathcal{B}$$ endowed with maps $$\operatorname{wt} : \mathcal{B} \to L$$, $$e_i, f_i : \mathcal{B} \to \mathcal{B} \cup \{\emptyset\}$$, and $$\varepsilon_i, \varphi_i : \mathcal{B} \to \ZZ \cup \{-\infty\}$$ for $$i \in I$$ satisfying the following properties for all $$i \in I$$:

• for $$b, b^{\prime} \in \mathcal{B}$$, we have $$f_i b^{\prime} = b$$ if and only if $$e_i b = b^{\prime}$$;
• if $$e_i b \in \mathcal{B}$$, then:
• $$\operatorname{wt}(e_i b) = \operatorname{wt}(b) + \alpha_i$$,
• $$\varepsilon_i(e_i b) = \varepsilon_i(b) - 1$$,
• $$\varphi_i(e_i b) = \varphi_i(b) + 1$$;
• if $$f_i b \in \mathcal{B}$$, then:
• $$\operatorname{wt}(f_i b) = \operatorname{wt}(b) - \alpha_i$$,
• $$\varepsilon_i(f_i b) = \varepsilon_i(b) + 1$$,
• $$\varphi_i(f_i b) = \varphi_i(b) - 1$$;
• $$\varphi_i(b) = \varepsilon_i(b) + \langle \alpha^{\vee}_i, \operatorname{wt}(b) \rangle$$,
• if $$\varphi_i(b) = -\infty$$ for $$b \in \mathcal{B}$$, then $$e_i b = f_i b = \emptyset$$.

Some further conditions are required to guarantee that this data indeed models a representation of a Lie algebra. For finite simply laced types a complete characterization is given by Stembridge’s local axioms [Ste2003].

EXAMPLES:

We construct the type $$A_5$$ crystal on letters (or in representation theoretic terms, the highest weight crystal of type $$A_5$$ corresponding to the highest weight $$\Lambda_1$$):

sage: C = crystals.Letters(['A',5]); C
The crystal of letters for type ['A', 5]


It has a single highest weight element:

sage: C.highest_weight_vectors()
(1,)


A crystal is an enumerated set (see EnumeratedSets); and we can count and list its elements in the usual way:

sage: C.cardinality()
6
sage: C.list()
[1, 2, 3, 4, 5, 6]


as well as use it in for loops:

sage: [x for x in C]
[1, 2, 3, 4, 5, 6]


Here are some more elaborate crystals (see their respective documentations):

sage: Tens = crystals.TensorProduct(C, C)
sage: Spin = crystals.Spins(['B', 3])
sage: Tab  = crystals.Tableaux(['A', 3], shape = [2,1,1])
sage: Fast = crystals.FastRankTwo(['B', 2], shape = [3/2, 1/2])
sage: KR = crystals.KirillovReshetikhin(['A',2,1],1,1)


One can get (currently) crude plotting via:

sage: Tab.plot()
Graphics object consisting of 52 graphics primitives


If dot2tex is installed, one can obtain nice latex pictures via:

sage: K = crystals.KirillovReshetikhin(['A',3,1], 1,1)
sage: view(K, pdflatex=True) # optional - dot2tex graphviz, not tested (opens external window)


or with colored edges:

sage: K = crystals.KirillovReshetikhin(['A',3,1], 1,1)
sage: G = K.digraph()
sage: G.set_latex_options(color_by_label={0:"black", 1:"red", 2:"blue", 3:"green"})
sage: view(G, pdflatex=True) # optional - dot2tex graphviz, not tested (opens external window)


For rank two crystals, there is an alternative method of getting metapost pictures. For more information see C.metapost?.

Todo

• Vocabulary and conventions:
• For a classical crystal: connected / highest weight / irreducible
• Layout instructions for plot() for rank 2 types
• RestrictionOfCrystal

The crystals library in Sage grew up from an initial implementation in MuPAD-Combinat (see <MuPAD-Combinat>/lib/COMBINAT/crystals.mu).

class sage.combinat.crystals.crystals.CrystalBacktracker(crystal, index_set=None)

Time complexity: $$O(nF)$$ amortized for each produced element, where $$n$$ is the size of the index set, and $$F$$ is the cost of computing $$e$$ and $$f$$ operators.

Memory complexity: $$O(D)$$ where $$D$$ is the depth of the crystal.

Principle of the algorithm:

Let $$C$$ be a classical crystal. It’s an acyclic graph where each connected component has a unique element without predecessors (the highest weight element for this component). Let’s assume for simplicity that $$C$$ is irreducible (i.e. connected) with highest weight element $$u$$.

One can define a natural spanning tree of $$C$$ by taking $$u$$ as the root of the tree, and for any other element $$y$$ taking as ancestor the element $$x$$ such that there is an $$i$$-arrow from $$x$$ to $$y$$ with $$i$$ minimal. Then, a path from $$u$$ to $$y$$ describes the lexicographically smallest sequence $$i_1,\dots,i_k$$ such that $$(f_{i_k} \circ f_{i_1})(u)=y$$.

Morally, the iterator implemented below just does a depth first search walk through this spanning tree. In practice, this can be achieved recursively as follows: take an element $$x$$, and consider in turn each successor $$y = f_i(x)$$, ignoring those such that $$y = f_j(x^{\prime})$$ for some $$x^{\prime}$$ and $$j<i$$ (this can be tested by computing $$e_j(y)$$ for $$j<i$$).

EXAMPLES:

sage: from sage.combinat.crystals.crystals import CrystalBacktracker
sage: C = crystals.Tableaux(['B',3],shape=[3,2,1])
sage: CB = CrystalBacktracker(C)
sage: len(list(CB))
1617
sage: CB = CrystalBacktracker(C, [1,2])
sage: len(list(CB))
8