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 Thiéry.

class sage.combinat.crystals.alcove_path.CrystalOfAlcovePaths(starting_weight, highest_weight_crystal)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

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) If True returns the highest weight crystal. If False 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(sort=True):
....:     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(sort=False): #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.

Element

alias of CrystalOfAlcovePathsElement

vertices()

Return a list of all the vertices of the crystal.

The vertices are represented as lists of integers recording the folding positions.

One can compute all vertices of the crystal by finding all the admissible subsets of the \(\lambda\)-chain (see method is_admissible, for definition). We use the breadth first search algorithm.

Warning

This method is (currently) only useful for the case when highest_weight_crystal = False, where you cannot always reach all vertices of the crystal using crystal operators, starting from the highest weight vertex. This method is typically slower than generating the crystal graph using crystal operators.

EXAMPLES:

sage: C = crystals.AlcovePaths(['C',2],[1,0])
sage: C.vertices()
[[], [0], [0, 1], [0, 1, 2]]
sage: C = crystals.AlcovePaths(['C',2,1],[2,1],False)
sage: len(C.vertices())
80

The number of elements reachable using the crystal operators from the module generator:

sage: len(list(C))
55

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 of RootsWithHeight 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(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

class sage.combinat.crystals.alcove_path.InfinityCrystalOfAlcovePaths(cartan_type)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

\(\mathcal{B}(\infty)\) crystal of alcove paths.

class Element(parent, elt, shift)

Bases: sage.structure.element_wrapper.ElementWrapper

Initialize self.

EXAMPLES:

sage: A = crystals.infinity.AlcovePaths(['F',4])
sage: mg = A.highest_weight_vector()
sage: x = mg.f_string([2,3,1,4,4,2,3,1])
sage: TestSuite(x).run()

e(i)

Return the action of \(e_i\) on self.

INPUT:

• i – an element of the index set

EXAMPLES:

sage: A = crystals.infinity.AlcovePaths(['D',5,1])
sage: mg = A.highest_weight_vector()
sage: x = mg.f_string([1,3,4,2,5,4,5,5])
sage: x.f(4).e(5) == x.e(5).f(4)
True

epsilon(i)

Return \(\varepsilon_i\) of self.

INPUT:

• i – an element of the index set

EXAMPLES:

sage: A = crystals.infinity.AlcovePaths(['A',7,2])
sage: mg = A.highest_weight_vector()
sage: x = mg.f_string([1,0,2,3,4,4,4,2,3,3,3])
sage: [x.epsilon(i) for i in A.index_set()]
[0, 0, 0, 3, 0]
sage: x = mg.f_string([2,2,1,1,0,1,0,2,3,3,3,4])
sage: [x.epsilon(i) for i in A.index_set()]
[1, 2, 0, 1, 1]

f(i)

Return the action of \(f_i\) on self.

INPUT:

• i – an element of the index set

EXAMPLES:

sage: A = crystals.infinity.AlcovePaths(['E',7,1])
sage: mg = A.highest_weight_vector()
sage: mg.f_string([1,3,5,6,4,2,0,2,1,0,2,4,7,4,2])
((alpha[2], -3), (alpha[5], -1), (alpha[1], -1),
 (alpha[0] + alpha[1], -2),
 (alpha[2] + alpha[4] + alpha[5], -2),
 (alpha[5] + alpha[6], -1), (alpha[1] + alpha[3], -1),
 (alpha[5] + alpha[6] + alpha[7], -1),
 (alpha[0] + alpha[1] + alpha[3], -1),
 (alpha[1] + alpha[3] + alpha[4] + alpha[5], -1))

phi(i)

Return \(\varphi_i\) of self.

Let \(A \in \mathcal{B}(\infty)\) Define \(\varphi_i(A) := \varepsilon_i(A) + \langle h_i, \mathrm{wt}(A) \rangle\), where \(h_i\) is the \(i\)-th simple coroot and \(\mathrm{wt}(A)\) is the weight() of \(A\).

INPUT:

• i – an element of the index set

EXAMPLES:

sage: A = crystals.infinity.AlcovePaths(['A',8,2])
sage: mg = A.highest_weight_vector()
sage: x = mg.f_string([1,0,2,3,4,4,4,2,3,3,3])
sage: [x.phi(i) for i in A.index_set()]
[1, 1, 1, 3, -2]
sage: x = mg.f_string([2,2,1,1,0,1,0,2,3,3,3,4])
sage: [x.phi(i) for i in A.index_set()]
[4, -1, 0, 0, 2]

projection(k=None)

Return the projection self onto \(B(k \rho)\).

INPUT:

• k – (optional) if not given, defaults to the smallest value such that self is not None under the projection

EXAMPLES:

sage: A = crystals.infinity.AlcovePaths(['G',2])
sage: mg = A.highest_weight_vector()
sage: x = mg.f_string([2,1,1,2,2,2,1,1]); x
((alpha[2], -3), (alpha[1] + alpha[2], -3),
 (3*alpha[1] + 2*alpha[2], -1), (2*alpha[1] + alpha[2], -1))
sage: x.projection()
((alpha[2], 0), (alpha[1] + alpha[2], 9),
 (3*alpha[1] + 2*alpha[2], 8), (2*alpha[1] + alpha[2], 14))
sage: x.projection().parent()
Highest weight crystal of alcove paths of type ['G', 2]
 and weight 3*Lambda[1] + 3*Lambda[2]

sage: mg.projection().parent()
Highest weight crystal of alcove paths of type ['G', 2]
 and weight 0
sage: mg.f(1).projection().parent()
Highest weight crystal of alcove paths of type ['G', 2]
 and weight Lambda[1] + Lambda[2]
sage: mg.f(1).f(2).projection().parent()
Highest weight crystal of alcove paths of type ['G', 2]
 and weight Lambda[1] + Lambda[2]
sage: b = mg.f_string([1,2,2,1,2])
sage: b.projection().parent()
Highest weight crystal of alcove paths of type ['G', 2]
 and weight 2*Lambda[1] + 2*Lambda[2]
sage: b.projection(3).parent()
Highest weight crystal of alcove paths of type ['G', 2]
 and weight 3*Lambda[1] + 3*Lambda[2]
sage: b.projection(1)

weight()

Return the weight of self.

EXAMPLES:

sage: A = crystals.infinity.AlcovePaths(['E',6])
sage: mg = A.highest_weight_vector()
sage: fstr = [1,3,4,2,1,2,3,6,5,3,2,6,2]
sage: x = mg.f_string(fstr)
sage: al = A.weight_lattice_realization().simple_roots()
sage: x.weight() == -sum(al[i]*fstr.count(i) for i in A.index_set())
True

class sage.combinat.crystals.alcove_path.RootsWithHeight(weight)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

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 system

• weight – 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

Element

alias of RootsWithHeightElement

lambda_chain()

Return the unfolded \(\lambda\)-chain.

Note

Only works in root systems of finite type.

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: R.lambda_chain()
[(alpha[2], 0), (alpha[1] + alpha[2], 0), (alpha[1], 0), (alpha[1] + alpha[2], 1)]

word()

Gives the initial alcove path (\(\lambda\)-chain) in terms of simple roots. Used for plotting the path.

Note

Currently only implemented for finite Cartan types.

EXAMPLES:

sage: from sage.combinat.crystals.alcove_path import RootsWithHeight
sage: R = RootsWithHeight(['A',2],[3,2])
sage: R.word()
[2, 1, 2, 0, 1, 2, 1, 0, 1, 2]

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 system

• height – 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 from Crystal.digraph(), starting from the root nodes of each graph.

• g1 – graphs, first digraph

• g2 – graphs, second digraph

• node1 – element of g1

• node2 – element of g2

Traverse g1 starting at node1 and compare this graph with the one obtained by traversing g2 starting with node2. If the graphs match (including labels) then return True. Return False 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(sort=True)[0])
True