An introduction to crystals¶
Informally, a crystal is an oriented graph with edges
colored in some set
such that, for each
, each node
has:
- at most one
-successor, denoted
;
- at most one
-predecessor, denoted
.
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 satisfies
appropriate conditions.
In combinatorial representation theory, crystals are used as combinatorial data to model representations of Lie algebra.
Axiomatic definition¶
Let be a Cartan type (
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
:
- for
, we have
if and only if
;
- if
, then:
,
,
;
- if
, then:
,
,
;
,
- if
for
, then
.
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, 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"}) #optional - dot2tex graphviz
sage: view(G, pdflatex=True, tightpage=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)¶ 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 each 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 follows: 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