Alcove paths¶
AUTHORS:
- Brant Jones (2008): initial version
- Arthur Lubovsky (2013-03-07): rewritten to implement affine type
- Travis Scrimshaw (2016-06-23): implemented \(\mathcal{B}(\infty)\)
Special thanks to: Nicolas Borie, Anne Schilling, Travis Scrimshaw, and Nicolas Thiery.
-
sage.combinat.crystals.alcove_path.
CrystalOfAlcovePaths
¶ Crystal of alcove paths generated from a “straight-line” path to the negative of a given dominant weight.
INPUT:
cartan_type
– Cartan type of a finite or affine untwisted root system.weight
– Dominant weight as a list of (integral) coefficients of the fundamental weights.highest_weight_crystal
– (Default:True
) IfTrue
returns the highest weight crystal. IfFalse
returns an object which is close to being isomorphic to the tensor product of Kirillov-Reshetikhin crystals of column shape in the following sense: We get all the vertices, but only some of the edges. We’ll call the included edges pseudo-Demazure. They are all non-zero edges and the 0-edges not at the end of a 0-string of edges, i.e. not those with \(f_{0}(b) = b'\) with \(\varphi_0(b) =1\). (Whereas Demazure 0-edges are those that are not at the beginning of a zero string.) In this case the weight \([c_1, c_2, \ldots, c_k]\) represents \(\sum_{i=1}^k c_i \omega_i\).Note
If
highest_weight_crystal
=False
, since we do not get the full crystal,TestSuite
will fail on the Stembridge axioms.
See also
Crystals
EXAMPLES:
The following example appears in Figure 2 of [LP2008]:
sage: C = crystals.AlcovePaths(['G',2],[0,1]) sage: G = C.digraph() sage: GG = DiGraph({ ....: () : {(0) : 2 }, ....: (0) : {(0,8) : 1 }, ....: (0,1) : {(0,1,7) : 2 }, ....: (0,1,2) : {(0,1,2,9) : 1 }, ....: (0,1,2,3) : {(0,1,2,3,4) : 2 }, ....: (0,1,2,6) : {(0,1,2,3) : 1 }, ....: (0,1,2,9) : {(0,1,2,6) : 1 }, ....: (0,1,7) : {(0,1,2) : 2 }, ....: (0,1,7,9) : {(0,1,2,9) : 2 }, ....: (0,5) : {(0,1) : 1, (0,5,7) : 2 }, ....: (0,5,7) : {(0,5,7,9) : 1 }, ....: (0,5,7,9) : {(0,1,7,9) : 1 }, ....: (0,8) : {(0,5) : 1 }, ....: }) sage: G.is_isomorphic(GG) True sage: for (u,v,i) in G.edges(): ....: print((u.integer_sequence() , v.integer_sequence(), i)) ([], [0], 2) ([0], [0, 8], 1) ([0, 1], [0, 1, 7], 2) ([0, 1, 2], [0, 1, 2, 9], 1) ([0, 1, 2, 3], [0, 1, 2, 3, 4], 2) ([0, 1, 2, 6], [0, 1, 2, 3], 1) ([0, 1, 2, 9], [0, 1, 2, 6], 1) ([0, 1, 7], [0, 1, 2], 2) ([0, 1, 7, 9], [0, 1, 2, 9], 2) ([0, 5], [0, 1], 1) ([0, 5], [0, 5, 7], 2) ([0, 5, 7], [0, 5, 7, 9], 1) ([0, 5, 7, 9], [0, 1, 7, 9], 1) ([0, 8], [0, 5], 1)
Alcove path crystals are a discrete version of Littelmann paths. We verify that the alcove path crystal is isomorphic to the LS path crystal:
sage: C1 = crystals.AlcovePaths(['C',3],[2,1,0]) sage: g1 = C1.digraph() #long time sage: C2 = crystals.LSPaths(['C',3],[2,1,0]) sage: g2 = C2.digraph() #long time sage: g1.is_isomorphic(g2, edge_labels=True) #long time True
The preferred initialization method is via explicit weights rather than a Cartan type and the coefficients of the fundamental weights:
sage: R = RootSystem(['C',3]) sage: P = R.weight_lattice() sage: La = P.fundamental_weights() sage: C = crystals.AlcovePaths(2*La[1]+La[2]); C Highest weight crystal of alcove paths of type ['C', 3] and weight 2*Lambda[1] + Lambda[2] sage: C1==C True
We now explain the data structure:
sage: C = crystals.AlcovePaths(['A',2],[2,0]) ; C Highest weight crystal of alcove paths of type ['A', 2] and weight 2*Lambda[1] sage: C._R.lambda_chain() [(alpha[1], 0), (alpha[1] + alpha[2], 0), (alpha[1], 1), (alpha[1] + alpha[2], 1)]
The previous list gives the initial “straight line” path from the fundamental alcove \(A_o\) to its translation \(A_o - \lambda\) where \(\lambda = 2\omega_1\) in this example. The initial path for weight \(\lambda\) is called the \(\lambda\)-chain. This path is constructed from the ordered pairs \((\beta, k)\), by crossing the hyperplane orthogonal to \(\beta\) at height \(-k\). We can view a plot of this path as follows:
sage: x=C( () ) sage: x.plot() # not tested - outputs a pdf
An element of the crystal is given by a subset of the \(\lambda\)-chain. This subset indicates the hyperplanes where the initial path should be folded. The highest weight element is given by the empty subset.
sage: x () sage: x.f(1).f(2) ((alpha[1], 1), (alpha[1] + alpha[2], 1)) sage: x.f(1).f(2).integer_sequence() [2, 3] sage: C([2,3]) ((alpha[1], 1), (alpha[1] + alpha[2], 1)) sage: C([2,3]).is_admissible() #check if a valid vertex True sage: C([1,3]).is_admissible() #check if a valid vertex False
Alcove path crystals now works in affine type (trac ticket #14143):
sage: C = crystals.AlcovePaths(['A',2,1],[1,0,0]) ; C Highest weight crystal of alcove paths of type ['A', 2, 1] and weight Lambda[0] sage: x=C( () ) sage: x.f(0) ((alpha[0], 0),) sage: C.R Root system of type ['A', 2, 1] sage: C.weight Lambda[0]
Test that the tensor products of Kirillov-Reshetikhin crystals minus non-pseudo-Demazure arrows is in bijection with alcove path construction:
sage: K = crystals.KirillovReshetikhin(['B',3,1],2,1) sage: T = crystals.TensorProduct(K,K) sage: g = T.digraph() #long time sage: for e in g.edges(): #long time ....: if e[0].phi(0) == 1 and e[2] == 0: #long time ....: g.delete_edge(e) #long time sage: C = crystals.AlcovePaths(['B',3,1],[0,2,0], highest_weight_crystal=False) sage: g2 = C.digraph() #long time sage: g.is_isomorphic(g2, edge_labels = True) #long time True
Note
In type \(C_n^{(1)}\), the Kirillov-Reshetikhin crystal is not connected when restricted to pseudo-Demazure arrows, hence the previous example will fail for type \(C_n^{(1)}\) crystals.
sage: R = RootSystem(['B',3]) sage: P = R.weight_lattice() sage: La = P.fundamental_weights() sage: D = crystals.AlcovePaths(2*La[2], highest_weight_crystal=False) sage: C == D True
Warning
Weights from finite root systems index non-highest weight crystals.
-
class
sage.combinat.crystals.alcove_path.
CrystalOfAlcovePathsElement
¶ Bases:
sage.structure.element_wrapper.ElementWrapper
Crystal of alcove paths element.
INPUT:
data
– a list of folding positions in the lambda chain (indexing starts at 0) or a tuple ofRootsWithHeight
giving folding positions in the lambda chain.
EXAMPLES:
sage: C = crystals.AlcovePaths(['A',2],[3,2]) sage: x = C ( () ) sage: x.f(1).f(2) ((alpha[1], 2), (alpha[1] + alpha[2], 4)) sage: x.f(1).f(2).integer_sequence() [8, 9] sage: C([8,9]) ((alpha[1], 2), (alpha[1] + alpha[2], 4))
-
e
(i)¶ Return the \(i\)-th crystal raising operator on
self
.INPUT:
i
– element of the index set of the underlying root system.
EXAMPLES:
sage: C = crystals.AlcovePaths(['A',2],[2,0]); C Highest weight crystal of alcove paths of type ['A', 2] and weight 2*Lambda[1] sage: x = C( () ) sage: x.e(1) sage: x.f(1) == x.f(1).f(2).e(2) True
-
epsilon
(i)¶ Return the distance to the start of the \(i\)-string.
EXAMPLES:
sage: C = crystals.AlcovePaths(['A',2],[1,1]) sage: [c.epsilon(1) for c in C] [0, 1, 0, 0, 1, 0, 1, 2] sage: [c.epsilon(2) for c in C] [0, 0, 1, 2, 1, 1, 0, 0]
-
f
(i)¶ Returns the \(i\)-th crystal lowering operator on
self
.INPUT:
i
– element of the index_set of the underlying root_system.
EXAMPLES:
sage: C=crystals.AlcovePaths(['B',2],[1,1]) sage: x=C( () ) sage: x.f(1) ((alpha[1], 0),) sage: x.f(1).f(2) ((alpha[1], 0), (alpha[1] + alpha[2], 2))
-
integer_sequence
()¶ Return a list of integers corresponding to positions in the \(\lambda\)-chain where it is folded.
Todo
Incorporate this method into the
_repr_
for finite Cartan type.Note
Only works for finite Cartan types and indexing starts at 0.
EXAMPLES:
sage: C = crystals.AlcovePaths(['A',2],[3,2]) sage: x = C( () ) sage: x.f(1).f(2).integer_sequence() [8, 9]
-
is_admissible
()¶ Diagnostic test to check if
self
is a valid element of the crystal.If
self.value
is given by\[(\beta_1, i_1), (\beta_2, i_2), \ldots, (\beta_k, i_k),\]for highest weight crystals this checks if the sequence
\[1 \rightarrow s_{\beta_1} \rightarrow s_{\beta_1}s_{\beta_2} \rightarrow \cdots \rightarrow s_{\beta_1}s_{\beta_2} \ldots s_{\beta_k}\]is a path in the Bruhat graph. If
highest_weight_crystal=False
, then the method checks if the above sequence is a path in the quantum Bruhat graph.EXAMPLES:
sage: C = crystals.AlcovePaths(['A',2],[1,1]); C Highest weight crystal of alcove paths of type ['A', 2] and weight Lambda[1] + Lambda[2] sage: roots = sorted(list(C._R._root_lattice.positive_roots())); roots [alpha[1], alpha[1] + alpha[2], alpha[2]] sage: r1 = C._R(roots[0],0); r1 (alpha[1], 0) sage: r2 = C._R(roots[2],0); r2 (alpha[2], 0) sage: r3 = C._R(roots[1],1); r3 (alpha[1] + alpha[2], 1) sage: x = C( ( r1,r2) ) sage: x.is_admissible() True sage: x = C( (r3,) ); x ((alpha[1] + alpha[2], 1),) sage: x.is_admissible() False sage: C = crystals.AlcovePaths(['C',2,1],[2,1],False) sage: C([7,8]).is_admissible() True sage: C = crystals.AlcovePaths(['A',2],[3,2]) sage: C([2,3]).is_admissible() True
Todo
Better doctest
-
path
()¶ Return the path in the (quantum) Bruhat graph corresponding to
self
.EXAMPLES:
sage: C = crystals.AlcovePaths(['B', 3], [3,1,2]) sage: b = C.highest_weight_vector().f_string([1,3,2,1,3,1]) sage: b.path() [1, s1, s3*s1, s2*s3*s1, s3*s2*s3*s1] sage: b = C.highest_weight_vector().f_string([2,3,3,2]) sage: b.path() [1, s2, s3*s2, s2*s3*s2] sage: b = C.highest_weight_vector().f_string([2,3,3,2,1]) sage: b.path() [1, s2, s3*s2, s2*s3*s2, s1*s2*s3*s2]
-
phi
(i)¶ Return the distance to the end of the \(i\)-string.
This method overrides the generic implementation in the category of crystals since this computation is more efficient.
EXAMPLES:
sage: C = crystals.AlcovePaths(['A',2],[1,1]) sage: [c.phi(1) for c in C] [1, 0, 0, 1, 0, 2, 1, 0] sage: [c.phi(2) for c in C] [1, 2, 1, 0, 0, 0, 0, 1]
-
plot
()¶ Return a plot
self
.Note
Currently only implemented for types \(A_2\), \(B_2\), and \(C_2\).
EXAMPLES:
sage: C = crystals.AlcovePaths(['A',2],[2,0]) sage: x = C( () ).f(1).f(2) sage: x.plot() # Not tested - creates a pdf
-
weight
()¶ Return the weight of
self
.EXAMPLES:
sage: C = crystals.AlcovePaths(['A',2],[2,0]) sage: for i in C: i.weight() (2, 0, 0) (1, 1, 0) (0, 2, 0) (0, -1, 0) (-1, 0, 0) (-2, -2, 0) sage: B = crystals.AlcovePaths(['A',2,1],[1,0,0]) sage: p = B.module_generators[0].f_string([0,1,2]) sage: p.weight() Lambda[0] - delta
-
sage.combinat.crystals.alcove_path.
InfinityCrystalOfAlcovePaths
¶ \(\mathcal{B}(\infty)\) crystal of alcove paths.
-
sage.combinat.crystals.alcove_path.
RootsWithHeight
¶ Data structure of the ordered pairs \((\beta,k)\), where \(\beta\) is a positive root and \(k\) is a non-negative integer. A total order is implemented on this set, and depends on the weight.
INPUT:
cartan_type
– Cartan type of a finite or affine untwisted root systemweight
– dominant weight as a list of (integral) coefficients of the fundamental weights
EXAMPLES:
sage: from sage.combinat.crystals.alcove_path import RootsWithHeight sage: R = RootsWithHeight(['A',2],[1,1]); R Roots with height of Cartan type ['A', 2] and dominant weight Lambda[1] + Lambda[2] sage: r1 = R._root_lattice.from_vector(vector([1,0])); r1 alpha[1] sage: r2 = R._root_lattice.from_vector(vector([1,1])); r2 alpha[1] + alpha[2] sage: x = R(r1,0); x (alpha[1], 0) sage: y = R(r2,1); y (alpha[1] + alpha[2], 1) sage: x < y True
-
class
sage.combinat.crystals.alcove_path.
RootsWithHeightElement
(parent, root, height)¶ Bases:
sage.structure.element.Element
Element of
RootsWithHeight
.INPUT:
root
– A positive root \(\beta\) in our root systemheight
– Is an integer, such that \(0 \leq l \leq \langle \lambda, \beta^{\vee} \rangle\)
EXAMPLES:
sage: from sage.combinat.crystals.alcove_path import RootsWithHeight sage: rl = RootSystem(['A',2]).root_lattice() sage: x = rl.from_vector(vector([1,1])); x alpha[1] + alpha[2] sage: R = RootsWithHeight(['A',2],[1,1]); R Roots with height of Cartan type ['A', 2] and dominant weight Lambda[1] + Lambda[2] sage: y = R(x, 1); y (alpha[1] + alpha[2], 1)
-
sage.combinat.crystals.alcove_path.
compare_graphs
(g1, g2, node1, node2)¶ Compare two edge-labeled
graphs
obtained fromCrystal.digraph()
, starting from the root nodes of each graph.Traverse
g1
starting atnode1
and compare this graph with the one obtained by traversingg2
starting withnode2
. If the graphs match (including labels) then returnTrue
. ReturnFalse
otherwise.EXAMPLES:
sage: from sage.combinat.crystals.alcove_path import compare_graphs sage: G1 = crystals.Tableaux(['A',3], shape=[1,1]).digraph() sage: C = crystals.AlcovePaths(['A',3],[0,1,0]) sage: G2 = C.digraph() sage: compare_graphs(G1, G2, C( () ), G2.vertices()[0]) True