Crystals

Let T be a CartanType with index set I, and W be a realization of the type T weight lattice.

A type T crystal C is a colored oriented graph equipped with a weight function from the nodes to some realization of the type T weight lattice such that:

  • Each edge is colored with a label in i \in I.

  • For each i\in I, each node x has:

    • at most one i-successor f_i(x);
    • at most one i-predecessor e_i(x).

    Furthermore, when they exist,

    • f_i(x).weight() = x.weight() - \alpha_i;
    • e_i(x).weight() = x.weight() + \alpha_i.

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 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 = 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:

  • Vocabulary and conventions:
    • elements or vectors of a crystal?
    • For a classical crystal: connected / highest weight / irreducible
    • ...
  • More introductory doc explaining the mathematical background
  • Layout instructions for plot() for rank 2 types
  • Streamlining the latex output
  • Littelmann paths and/or alcove paths (this would give us the exceptional types)
  • RestrictionOfCrystal / DirectSumOfCrystals
  • Crystal.crystal_morphism
  • Affine crystals
  • Kirillov-Reshetikhin crystals

Most of the above features (except Littelmann/alcove paths) are in MuPAD-Combinat (see lib/COMBINAT/crystals.mu), which could provide inspiration.

class sage.combinat.crystals.crystals.ClassicalCrystal

The abstract class of classical crystals

__iter__()

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
cardinality()

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
highest_weight_vector()

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
highest_weight_vectors()

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]]
list()

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]
class sage.combinat.crystals.crystals.Crystal

The abstract class of crystals

Derived subclasses should implement the following:

  • either a method cartan_type or an attribute _cartan_type
  • module_generators: a list (or container) of distinct elements which generate the crystal using f_i
Lambda()

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)}
cartan_type()

Returns the Cartan type of the associated crystal

EXAMPLES::
sage: C = CrystalOfLetters([‘A’,2]) sage: C.cartan_type() [‘A’, 2]
character(R)

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]
check()

Runs sanity checks on the crystal:

  • Checks that count, list, and __iter__ are consistent. For a ClassicalCrystal, this in particular checks that the number of elements returned by the brute force listing and the iterator __iter__ are consistent with the Weyl dimension formula.
  • Should check Stembridge’s rules, etc.

EXAMPLES:

sage: C = CrystalOfLetters(['A', 5])
sage: C.check()
True
digraph()

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
dot_tex()

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}'
index_set()

Returns the index set of the Dynkin diagram underlying the given crystal

EXAMPLES:
sage: C = CrystalOfLetters([‘A’, 5]) sage: C.index_set() [1, 2, 3, 4, 5]
latex()

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:

    • untaring in /usr/share/texmf/tex/generic
    • clean out remaining pgf files from older version
    • run texhash

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
...
latex_file(filename)

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
list()

Returns a list of the elements of self obtained by continually apply the f_i 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]
metapost(filename, thicklines=False, labels=True, scaling_factor=1.0, tallness=1.0)

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
plot(**options)

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
weight_lattice_realization()

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]
class sage.combinat.crystals.crystals.CrystalBacktracker(crystal)
__init__(crystal)

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(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 C by taking u as rot 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 follow: take an element x, and consider in turn each successor y = f_i(x), ignoring those such that y = f_j(x') for some x' 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 = CrystalOfTableaux(['B',3],shape=[3,2,1])
sage: CB = CrystalBacktracker(C)
sage: len(list(CB))
1617
_rec(x, state)

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)]
class sage.combinat.crystals.crystals.CrystalElement

The abstract class of crystal elements

Sub classes should implement at least:

  • x.e(i) (returning e_i(x))
  • x.f(i) (returning f_i(x))
  • x.weight()
Epsilon()

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)
Phi()

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)
__weakref__
list of weak references to the object (if defined)
cartan_type()

Returns the cartan type associated to self

EXAMPLES::
sage: C = CrystalOfLetters([‘A’, 5]) sage: C(1).cartan_type() [‘A’, 5]
e(i)

Returns e_i(x) 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
epsilon(i)

EXAMPLES:

sage: C = CrystalOfLetters(['A',5])
sage: C(1).epsilon(1)
0
sage: C(2).epsilon(1)
1
f(i)

Returns f_i(x) 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
index_set()

EXAMPLES:

sage: C = CrystalOfLetters(['A',5])
sage: C(1).index_set()
[1, 2, 3, 4, 5]
is_highest_weight()

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
phi(i)

EXAMPLES:

sage: C = CrystalOfLetters(['A',5])
sage: C(1).phi(1)
1
sage: C(2).phi(1)
0
s(i)

Returns the reflection of self along its i-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]]
weight()

EXAMPLES:

sage: C = CrystalOfLetters(['A',5])
sage: C(1).weight()
(1, 0, 0, 0, 0, 0)

Previous topic

Crystals

Next topic

Crystals of letters

This Page