Informally, a crystal is an oriented graph with edges
colored in some set
such that, for each
, each node
has:
By convention, one writes and
when
has no successor resp. predecessor.
One may think of as essentially a deterministic
automaton whose dual is also deterministic; in this context, the
‘s and
‘s are respectively the transition functions of the
automaton and of its dual, and
is the sink.
A crystal comes further endowed with a weight function
which shall satisfies
appropriate conditions.
In combinatorial representation theory, Crystals are used as combinatorial data to model representations of Lie algebra.
Let be a CartanType with index set
, and
be a realization
of the weight lattice of the type
. Let
and
denote the simple roots and coroots
respectively.
A type crystal is a non-empty set
endowed with maps
,
, and
for
satisfying the following properties for all
:
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 [St2003].
REFERENCES:
[St2003] | J. Stembridge, A local characterization of simply-laced crystals, Trans. Amer. Math. Soc. 355 (2003), no. 12, 4807-4823. |
EXAMPLES:
We construct the type crystal on letters (or in representation
theoretic terms, the highest weight crystal of type
corresponding to the highest weight
):
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, tightpage=True) #optional - dot2tex graphviz
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"}) #optional - dot2tex graphviz
sage: view(G, pdflatex=True, tightpage=True) #optional - dot2tex graphviz
For rank two crystals, there is an alternative method of getting metapost pictures. For more information see C.metapost?.
Todo
The crystals library in Sage grew up from an initial implementation in MuPAD-Combinat (see <MuPAD-Combinat>/lib/COMBINAT/crystals.mu).
Bases: sage.combinat.backtrack.GenericBacktracker
Time complexity: amortized for each produced
element, where
is the size of the index set, and
is
the cost of computing
and
operators.
Memory complexity: where
is the depth of the crystal.
Principle of the algorithm:
Let be a classical crystal. It’s an acyclic graph where all
connected component has a unique element without predecessors (the
highest weight element for this component). Let’s assume for
simplicity that
is irreducible (i.e. connected) with highest
weight element
.
One can define a natural spanning tree of by taking
as the root of the tree, and for any other element
taking as ancestor the element
such that
there is an
-arrow from
to
with
minimal. Then, a path from
to
describes the lexicographically smallest sequence
such that
.
Morally, the iterator implemented below just does a depth first
search walk through this spanning tree. In practice, this can be
achieved recursively as follow: take an element , and
consider in turn each successor
, ignoring
those such that
for some
and
(this can be tested by computing
for
).
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