Let be a CartanType with index set
, and
be a realization of the type
weight
lattice.
A type crystal
is a colored oriented graph
equipped with a weight function from the nodes to some realization
of the type
weight lattice such that:
Each edge is colored with a label in .
For each , each node
has:
Furthermore, when they exist,
This crystal actually models a representation of a Lie algebra if it satisfies some further local conditions due to Stembridge, see 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 = CrystalOfLetters(['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 a CombinatorialClass; 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 = TensorProductOfCrystals(C, C)
sage: Spin = CrystalOfSpins(['B', 3])
sage: Tab = CrystalOfTableaux(['A', 3], shape = [2,1,1])
sage: Fast = FastCrystal(['B', 2], shape = [3/2, 1/2])
One can get (currently) crude plotting via:
sage: Tab.plot()
For rank two crystals, there is an alternative method of getting metapost pictures. For more information see C.metapost?
Caveat: this crystal library, although relatively featureful for classical crystals, is still in an early development stage, and the syntax details may be subject to changes.
TODO:
Most of the above features (except Littelmann/alcove paths) are in MuPAD-Combinat (see lib/COMBINAT/crystals.mu), which could provide inspiration.
The abstract class of classical crystals
Returns an iterator over the elements of the crystal.
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: [x for x in C]
[1, 2, 3, 4, 5, 6]
TESTS:
sage: C = CrystalOfLetters(['D',4])
sage: D = CrystalOfSpinsPlus(['D',4])
sage: E = CrystalOfSpinsMinus(['D',4])
sage: T=TensorProductOfCrystals(D,E,generators=[[D.list()[0],E.list()[0]]])
sage: U=TensorProductOfCrystals(C,E,generators=[[C(1),E.list()[0]]])
sage: T.cardinality()
56
sage: T.check()
True
sage: U.check()
True
Bump’s systematic tests:
sage: fa3 = lambda a,b,c: CrystalOfTableaux(['A',3],shape=[a+b+c,b+c,c])
sage: fb3 = lambda a,b,c: CrystalOfTableaux(['B',3],shape=[a+b+c,b+c,c])
sage: fc3 = lambda a,b,c: CrystalOfTableaux(['C',3],shape=[a+b+c,b+c,c])
sage: fb4 = lambda a,b,c,d: CrystalOfTableaux(['B',4],shape=[a+b+c+d,b+c+d,c+d,d])
sage: fd4 = lambda a,b,c,d: CrystalOfTableaux(['D',4],shape=[a+b+c+d,b+c+d,c+d,d])
sage: fd5 = lambda a,b,c,d,e: CrystalOfTableaux(['D',5],shape=[a+b+c+d+e,b+c+d+e,c+d+e,d+e,e])
sage: def fd4spinplus(a,b,c,d):\
C = CrystalOfTableaux(['D',4],shape=[a+b+c+d,b+c+d,c+d,d]);\
D = CrystalOfSpinsPlus(['D',4]);\
return TensorProductOfCrystals(C,D,generators=[[C[0],D[0]]])
sage: def fb3spin(a,b,c):\
C = CrystalOfTableaux(['B',3],shape=[a+b+c,b+c,c]);\
D = CrystalOfSpins(['B',3]);\
return TensorProductOfCrystals(C,D,generators=[[C[0],D[0]]])
TODO: choose a good panel of values for a,b,c ... both for basic systematic tests and for conditionally run more computationally involved tests
sage: fb4(1,0,1,0).check()
True
#sage: fb4(1,1,1,1).check() # expensive: the crystal is of size 297297
#True
Returns the number of elements of the crystal, using Weyl’s dimension formula on each connected component
EXAMPLES:
sage: from sage.combinat.crystals.crystals import ClassicalCrystal
sage: C = CrystalOfLetters(['A', 5])
sage: ClassicalCrystal.cardinality(C)
6
Returns the highest weight vector if there is a single one; otherwise, raises an error.
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: C.highest_weight_vector()
1
Returns a list of the highest weight vectors of self.
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: C.highest_weight_vectors()
[1]
sage: C = CrystalOfLetters(['A',2])
sage: T = TensorProductOfCrystals(C,C,C,generators=[[C(2),C(1),C(1)],[C(1),C(2),C(1)]])
sage: T.highest_weight_vectors()
[[2, 1, 1], [1, 2, 1]]
The default implementation of list which builds the list from the iterator.
EXAMPLES:
sage: class C(CombinatorialClass):
... def __iter__(self):
... return iter([1,2,3])
...
sage: C().list() #indirect doctest
[1, 2, 3]
The abstract class of crystals
Derived subclasses should implement the following:
Returns the fundamentals weights in the weight lattice realization for the root system associated to self.
EXAMPLES:
sage: C = CrystalOfLetters(['A', 5])
sage: C.Lambda()
Finite family {1: (1, 0, 0, 0, 0, 0), 2: (1, 1, 0, 0, 0, 0), 3: (1, 1, 1, 0, 0, 0), 4: (1, 1, 1, 1, 0, 0), 5: (1, 1, 1, 1, 1, 0)}
Returns the Cartan type of the associated crystal
INPUT: R, a WeylCharacterRing. Produces the character of the crystal.
EXAMPLES:
sage: C = CrystalOfLetters(['A',2])
sage: T = TensorProductOfCrystals(C, C)
sage: A2 = WeylCharacterRing(C.cartan_type()); A2
The Weyl Character Ring of Type [A,2] with Integer Ring coefficients
sage: chi = T.character(A2); chi
A2(1,1,0) + A2(2,0,0)
sage: chi.check(verbose = true)
[9, 9]
Runs sanity checks on the crystal:
EXAMPLES:
sage: C = CrystalOfLetters(['A', 5])
sage: C.check()
True
Returns the DiGraph associated to self.
EXAMPLES:
sage: from sage.combinat.crystals.crystals import Crystal
sage: C = CrystalOfLetters(['A', 5])
sage: Crystal.digraph(C)
Digraph on 6 vertices
Returns a dot_tex version of self.
EXAMPLES:
sage: C = CrystalOfLetters(['A',2])
sage: C.dot_tex()
'digraph G { \n node [ shape=plaintext ];\n N_0 [ label = " ", texlbl = "$\\text{1}$" ];\n N_1 [ label = " ", texlbl = "$\\text{2}$" ];\n N_2 [ label = " ", texlbl = "$\\text{3}$" ];\n N_0 -> N_1 [ label = " ", texlbl = "1" ];\n N_1 -> N_2 [ label = " ", texlbl = "2" ];\n}'
Returns the index set of the Dynkin diagram underlying the given crystal
Returns the crystal graph as a bit of latex. This can be exported to a file with self.latex_file(‘filename’).
This requires dot2tex to be installed in sage-python.
Here some tips for installation:
Install graphviz = 2.14
Download pyparsing-1.4.11.tar.gz pydot-0.9.10.tar.gz dot2tex-2.7.0.tar.gz (see the dot2tex web page for download links) (note that the most recent version of pydot may not work. Be sure to install the 0.9.10 version.) Install each of them using the standard python install, but using sage-python:
# FIX ACCORDING TO YOUR Sage INSTALL
export sagedir=/opt/sage/
export sagepython=$sagedir/local/bin/sage-python
# Use downloaded version nums
for package in pyparsing-1.4.11 pydot-0.9.10 dot2tex-2.7.0; do\
tar zxvf $package.tar.gz;\
cd $package;\
sudo $sagepython setup.py install;\
cd ..;\
done
Install pgf-2.00 inside your latex tree In short:
You should be done! To test, go to the dot2tex-2.7.0/examples directory, and type:
$sagedir//local/bin/dot2tex balls.dot > balls.tex
pdflatex balls.tex
open balls.pdf \#your favorite viewer here
EXAMPLES:
sage: C = CrystalOfLetters(['A', 5])
sage: C.latex() #optional requires dot2tex
...
Exports a file, suitable for pdflatex, to ‘filename’. This requires a proper installation of dot2tex in sage-python. For more information see the documentation for self.latex().
EXAMPLES:
sage: C = CrystalOfLetters(['A', 5])
sage: C.latex_file('/tmp/test.tex') #optional requires dot2tex
Returns a list of the elements of self obtained by continually
apply the operators to the module generators of
self.
EXAMPLES:
sage: from sage.combinat.crystals.crystals import Crystal
sage: C = CrystalOfLetters(['A', 5])
sage: l = Crystal.list(C)
sage: l.sort(); l
[1, 2, 3, 4, 5, 6]
Use C.metapost(“filename.mp”,[options]) where options can be:
thicklines = True (for thicker edges) labels = False (to suppress labeling of the vertices) scaling_factor=value, where value is a floating point number, 1.0 by default. Increasing or decreasing the scaling factor changes the size of the image. tallness=1.0. Increasing makes the image taller without increasing the width.
Root operators e(1) or f(1) move along red lines, e(2) or f(2) along green. The highest weight is in the lower left. Vertices with the same weight are kept close together. The concise labels on the nodes are strings introduced by Berenstein and Zelevinsky and Littelmann; see Littelmann’s paper Cones, Crystals, Patterns, sections 5 and 6.
For Cartan types B2 or C2, the pattern has the form
a2 a3 a4 a1
where c*a2 = a3 = 2*a4 =0 and a1=0, with c=2 for B2, c=1 for C2. Applying e(2) a1 times, e(1) a2 times, e(2) a3 times, e(1) a4 times returns to the highest weight. (Observe that Littelmann writes the roots in opposite of the usual order, so our e(1) is his e(2) for these Cartan types.) For type A2, the pattern has the form
a3 a2 a1
where applying e(1) a1 times, e(2) a2 times then e(3) a1 times returns to the highest weight. These data determine the vertex and may be translated into a Gelfand-Tsetlin pattern or tableau.
EXAMPLES:
sage: C = CrystalOfLetters(['A', 2])
sage: C.metapost('/tmp/test.mp') #optional
sage: C = CrystalOfLetters(['A', 5])
sage: C.metapost('/tmp/test.mp')
...
NotImplementedError
Returns the plot of self as a directed graph.
EXAMPLES:
sage: C = CrystalOfLetters(['A', 5])
sage: show_default(False) #do not show the plot by default
sage: C.plot()
Graphics object consisting of 17 graphics primitives
Returns the weight lattice realization for the root system associated to self. This default implementation uses the ambient space of the root system.
EXAMPLES:
sage: C = CrystalOfLetters(['A', 5])
sage: C.weight_lattice_realization()
Ambient space of the Root system of type ['A', 5]
Time complexity: amortized for each produced
element, where
is the size of the index set, and f is
the cost of computing
and
operators.
Memory complexity: O(depth of the crystal)
Principle of the algorithm:
Let C 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 C is irreducible (i.e. connected) with highest weight element u.
One can define a natural spanning tree of by taking
as rot 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 = CrystalOfTableaux(['B',3],shape=[3,2,1])
sage: CB = CrystalBacktracker(C)
sage: len(list(CB))
1617
Returns an iterator for the (immediate) children of x in the search tree.
EXAMPLES:
sage: from sage.combinat.crystals.crystals import CrystalBacktracker
sage: C = CrystalOfLetters(['A', 5])
sage: CB = CrystalBacktracker(C)
sage: list(CB._rec(C(1), 'n/a'))
[(2, 'n/a', True)]
The abstract class of crystal elements
Sub classes should implement at least:
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: C(0).Epsilon()
(0, 0, 0, 0, 0, 0)
sage: C(1).Epsilon()
(0, 0, 0, 0, 0, 0)
sage: C(2).Epsilon()
(1, 0, 0, 0, 0, 0)
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: C(0).Phi()
(0, 0, 0, 0, 0, 0)
sage: C(1).Phi()
(1, 0, 0, 0, 0, 0)
sage: C(2).Phi()
(1, 1, 0, 0, 0, 0)
Returns the cartan type associated to self
Returns if it exists or None otherwise. This is
to be implemented by subclasses of CrystalElement.
TESTS:
sage: from sage.combinat.crystals.crystals import CrystalElement
sage: C = CrystalOfLetters(['A',5])
sage: CrystalElement.e(C(1), 1)
...
NotImplementedError
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: C(1).epsilon(1)
0
sage: C(2).epsilon(1)
1
Returns if it exists or None otherwise. This is
to be implemented by subclasses of CrystalElement.
TESTS:
sage: from sage.combinat.crystals.crystals import CrystalElement
sage: C = CrystalOfLetters(['A',5])
sage: CrystalElement.f(C(1), 1)
...
NotImplementedError
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: C(1).index_set()
[1, 2, 3, 4, 5]
Returns True if self is a highest weight.
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: C(1).is_highest_weight()
True
sage: C(2).is_highest_weight()
False
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: C(1).phi(1)
1
sage: C(2).phi(1)
0
Returns the reflection of self along its -string
EXAMPLES:
sage: C = CrystalOfTableaux(['A',2], shape=[2,1])
sage: b=C(rows=[[1,1],[3]])
sage: b.s(1)
[[2, 2], [3]]
sage: b=C(rows=[[1,2],[3]])
sage: b.s(2)
[[1, 2], [3]]
sage: T=CrystalOfTableaux(['A',2],shape=[4])
sage: t=T(rows=[[1,2,2,2]])
sage: t.s(1)
[[1, 1, 1, 2]]
EXAMPLES:
sage: C = CrystalOfLetters(['A',5])
sage: C(1).weight()
(1, 0, 0, 0, 0, 0)