Induced Crystals

We construct a crystal structure on a set induced by a bijection \(\Phi\).

AUTHORS:

• Travis Scrimshaw (2014-05-15): Initial implementation

class sage.combinat.crystals.induced_structure.InducedCrystal(X, phi, inverse)

Bases: UniqueRepresentation, Parent

A crystal induced from an injection.

Let \(X\) be a set and let \(C\) be crystal and consider any injection \(\Phi : X \to C\). We induce a crystal structure on \(X\) by considering \(\Phi\) to be a crystal morphism.

Alternatively we can induce a crystal structure on some (sub)set of \(X\) by considering an injection \(\Phi : C \to X\) considered as a crystal morphism. This form is also useful when the set \(X\) is not explicitly known.

INPUT:

• X – the base set

• phi – the map \(\Phi\)

• inverse – (optional) the inverse map \(\Phi^{-1}\)

• from_crystal – boolean (default: False); if the induced structure is of the second type \(\Phi : C \to X\)

EXAMPLES:

We construct a crystal structure of Gelfand-Tsetlin patterns by going through their bijection with semistandard tableaux:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,3))
sage: G = GelfandTsetlinPatterns(4, 3)
sage: phi = lambda x: D(x.to_tableau())
sage: phi_inv = lambda x: G(x.to_tableau())
sage: I = crystals.Induced(G, phi, phi_inv)
sage: I.digraph().is_isomorphic(D.digraph(), edge_labels=True)
True

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(3)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(3))
>>> phi = lambda x: D(x.to_tableau())
>>> phi_inv = lambda x: G(x.to_tableau())
>>> I = crystals.Induced(G, phi, phi_inv)
>>> I.digraph().is_isomorphic(D.digraph(), edge_labels=True)
True

Now we construct the above example but inducing the structure going the other way (from tableaux to Gelfand-Tsetlin patterns). This can also give us more information coming from the crystal.

Sage

sage: D2 = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,1))
sage: G2 = GelfandTsetlinPatterns(4, 1)
sage: phi2 = lambda x: D2(x.to_tableau())
sage: phi2_inv = lambda x: G2(x.to_tableau())
sage: I2 = crystals.Induced(D2, phi2_inv, phi2, from_crystal=True)
sage: I2.module_generators
([[0, 0, 0, 0], [0, 0, 0], [0, 0], [0]],
 [[1, 0, 0, 0], [1, 0, 0], [1, 0], [1]],
 [[1, 1, 0, 0], [1, 1, 0], [1, 1], [1]],
 [[1, 1, 1, 0], [1, 1, 1], [1, 1], [1]],
 [[1, 1, 1, 1], [1, 1, 1], [1, 1], [1]])

Python

>>> from sage.all import *
>>> D2 = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(1)))
>>> G2 = GelfandTsetlinPatterns(Integer(4), Integer(1))
>>> phi2 = lambda x: D2(x.to_tableau())
>>> phi2_inv = lambda x: G2(x.to_tableau())
>>> I2 = crystals.Induced(D2, phi2_inv, phi2, from_crystal=True)
>>> I2.module_generators
([[0, 0, 0, 0], [0, 0, 0], [0, 0], [0]],
 [[1, 0, 0, 0], [1, 0, 0], [1, 0], [1]],
 [[1, 1, 0, 0], [1, 1, 0], [1, 1], [1]],
 [[1, 1, 1, 0], [1, 1, 1], [1, 1], [1]],
 [[1, 1, 1, 1], [1, 1, 1], [1, 1], [1]])

We check an example when the codomain is larger than the domain (although here the crystal structure is trivial):

Sage

sage: P = Permutations(4)
sage: D = crystals.Tableaux(['A',3], shapes=Partitions(4))
sage: T = crystals.TensorProduct(D, D)
sage: phi = lambda p: T(D(RSK(p)[0]), D(RSK(p)[1]))
sage: phi_inv = lambda d: RSK_inverse(d[0].to_tableau(), d[1].to_tableau(), output='permutation')
sage: all(phi_inv(phi(p)) == p for p in P) # Check it really is the inverse
True
sage: I = crystals.Induced(P, phi, phi_inv)
sage: I.digraph()
Digraph on 24 vertices

Python

>>> from sage.all import *
>>> P = Permutations(Integer(4))
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=Partitions(Integer(4)))
>>> T = crystals.TensorProduct(D, D)
>>> phi = lambda p: T(D(RSK(p)[Integer(0)]), D(RSK(p)[Integer(1)]))
>>> phi_inv = lambda d: RSK_inverse(d[Integer(0)].to_tableau(), d[Integer(1)].to_tableau(), output='permutation')
>>> all(phi_inv(phi(p)) == p for p in P) # Check it really is the inverse
True
>>> I = crystals.Induced(P, phi, phi_inv)
>>> I.digraph()
Digraph on 24 vertices

We construct an example without a specified inverse map:

Sage

sage: X = Words(2,4)
sage: L = crystals.Letters(['A',1])
sage: T = crystals.TensorProduct(*[L]*4)
sage: Phi = lambda x : T(*[L(i) for i in x])
sage: I = crystals.Induced(X, Phi)
sage: I.digraph()
Digraph on 16 vertices

Python

>>> from sage.all import *
>>> X = Words(Integer(2),Integer(4))
>>> L = crystals.Letters(['A',Integer(1)])
>>> T = crystals.TensorProduct(*[L]*Integer(4))
>>> Phi = lambda x : T(*[L(i) for i in x])
>>> I = crystals.Induced(X, Phi)
>>> I.digraph()
Digraph on 16 vertices

class Element

Bases: ElementWrapper

An element of an induced crystal.

e(i)

Return \(e_i\) of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,3))
sage: G = GelfandTsetlinPatterns(4, 3)
sage: phi = lambda x: D(x.to_tableau())
sage: phi_inv = lambda x: G(x.to_tableau())
sage: I = crystals.Induced(G, phi, phi_inv)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: elt.e(1)
sage: elt.e(2)
[[1, 1, 0, 0], [1, 1, 0], [1, 1], [1]]
sage: elt.e(3)

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(3)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(3))
>>> phi = lambda x: D(x.to_tableau())
>>> phi_inv = lambda x: G(x.to_tableau())
>>> I = crystals.Induced(G, phi, phi_inv)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> elt.e(Integer(1))
>>> elt.e(Integer(2))
[[1, 1, 0, 0], [1, 1, 0], [1, 1], [1]]
>>> elt.e(Integer(3))

epsilon(i)

Return \(\varepsilon_i\) of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,3))
sage: G = GelfandTsetlinPatterns(4, 3)
sage: phi = lambda x: D(x.to_tableau())
sage: phi_inv = lambda x: G(x.to_tableau())
sage: I = crystals.Induced(G, phi, phi_inv)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: [elt.epsilon(i) for i in I.index_set()]
[0, 1, 0]

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(3)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(3))
>>> phi = lambda x: D(x.to_tableau())
>>> phi_inv = lambda x: G(x.to_tableau())
>>> I = crystals.Induced(G, phi, phi_inv)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> [elt.epsilon(i) for i in I.index_set()]
[0, 1, 0]

f(i)

Return \(f_i\) of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,3))
sage: G = GelfandTsetlinPatterns(4, 3)
sage: phi = lambda x: D(x.to_tableau())
sage: phi_inv = lambda x: G(x.to_tableau())
sage: I = crystals.Induced(G, phi, phi_inv)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: elt.f(1)
[[1, 1, 0, 0], [1, 1, 0], [1, 0], [0]]
sage: elt.f(2)
sage: elt.f(3)
[[1, 1, 0, 0], [1, 0, 0], [1, 0], [1]]

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(3)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(3))
>>> phi = lambda x: D(x.to_tableau())
>>> phi_inv = lambda x: G(x.to_tableau())
>>> I = crystals.Induced(G, phi, phi_inv)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> elt.f(Integer(1))
[[1, 1, 0, 0], [1, 1, 0], [1, 0], [0]]
>>> elt.f(Integer(2))
>>> elt.f(Integer(3))
[[1, 1, 0, 0], [1, 0, 0], [1, 0], [1]]

phi(i)

Return \(\varphi_i\) of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,3))
sage: G = GelfandTsetlinPatterns(4, 3)
sage: phi = lambda x: D(x.to_tableau())
sage: phi_inv = lambda x: G(x.to_tableau())
sage: I = crystals.Induced(G, phi, phi_inv)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: [elt.phi(i) for i in I.index_set()]
[1, 0, 1]

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(3)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(3))
>>> phi = lambda x: D(x.to_tableau())
>>> phi_inv = lambda x: G(x.to_tableau())
>>> I = crystals.Induced(G, phi, phi_inv)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> [elt.phi(i) for i in I.index_set()]
[1, 0, 1]

weight()

Return the weight of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,3))
sage: G = GelfandTsetlinPatterns(4, 3)
sage: phi = lambda x: D(x.to_tableau())
sage: phi_inv = lambda x: G(x.to_tableau())
sage: I = crystals.Induced(G, phi, phi_inv)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: elt.weight()
(1, 0, 1, 0)

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(3)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(3))
>>> phi = lambda x: D(x.to_tableau())
>>> phi_inv = lambda x: G(x.to_tableau())
>>> I = crystals.Induced(G, phi, phi_inv)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> elt.weight()
(1, 0, 1, 0)

cardinality()

Return the cardinality of self.

EXAMPLES:

Sage

sage: P = Permutations(4)
sage: D = crystals.Tableaux(['A',3], shapes=Partitions(4))
sage: T = crystals.TensorProduct(D, D)
sage: phi = lambda p: T(D(RSK(p)[0]), D(RSK(p)[1]))
sage: phi_inv = lambda d: RSK_inverse(d[0].to_tableau(), d[1].to_tableau(), output='permutation')
sage: I = crystals.Induced(P, phi, phi_inv)
sage: I.cardinality() == factorial(4)
True

Python

>>> from sage.all import *
>>> P = Permutations(Integer(4))
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=Partitions(Integer(4)))
>>> T = crystals.TensorProduct(D, D)
>>> phi = lambda p: T(D(RSK(p)[Integer(0)]), D(RSK(p)[Integer(1)]))
>>> phi_inv = lambda d: RSK_inverse(d[Integer(0)].to_tableau(), d[Integer(1)].to_tableau(), output='permutation')
>>> I = crystals.Induced(P, phi, phi_inv)
>>> I.cardinality() == factorial(Integer(4))
True

class sage.combinat.crystals.induced_structure.InducedFromCrystal(X, phi, inverse)

Bases: UniqueRepresentation, Parent

A crystal induced from an injection.

Alternatively we can induce a crystal structure on some (sub)set of \(X\) by considering an injection \(\Phi : C \to X\) considered as a crystal morphism.

See also

InducedCrystal

INPUT:

• X – the base set

• phi – the map \(\Phi\)

• inverse – (optional) the inverse map \(\Phi^{-1}\)

EXAMPLES:

We construct a crystal structure on generalized permutations with a fixed first row by using RSK:

Sage

sage: C = crystals.Tableaux(['A',3], shape=[2,1])
sage: def psi(x):
....:     ret = RSK_inverse(x.to_tableau(), Tableau([[1,1],[2]]))
....:     return (tuple(ret[0]), tuple(ret[1]))
sage: psi_inv = lambda x: C(RSK(*x)[0])
sage: I = crystals.Induced(C, psi, psi_inv, from_crystal=True)

Python

>>> from sage.all import *
>>> C = crystals.Tableaux(['A',Integer(3)], shape=[Integer(2),Integer(1)])
>>> def psi(x):
...     ret = RSK_inverse(x.to_tableau(), Tableau([[Integer(1),Integer(1)],[Integer(2)]]))
...     return (tuple(ret[Integer(0)]), tuple(ret[Integer(1)]))
>>> psi_inv = lambda x: C(RSK(*x)[Integer(0)])
>>> I = crystals.Induced(C, psi, psi_inv, from_crystal=True)

class Element

Bases: ElementWrapper

An element of an induced crystal.

e(i)

Return \(e_i\) of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,1))
sage: G = GelfandTsetlinPatterns(4, 1)
sage: def phi(x): return G(x.to_tableau())
sage: def phi_inv(x): return D(G(x).to_tableau())
sage: I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: elt.e(1)
sage: elt.e(2)
[[1, 1, 0, 0], [1, 1, 0], [1, 1], [1]]
sage: elt.e(3)

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(1)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(1))
>>> def phi(x): return G(x.to_tableau())
>>> def phi_inv(x): return D(G(x).to_tableau())
>>> I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> elt.e(Integer(1))
>>> elt.e(Integer(2))
[[1, 1, 0, 0], [1, 1, 0], [1, 1], [1]]
>>> elt.e(Integer(3))

epsilon(i)

Return \(\varepsilon_i\) of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,1))
sage: G = GelfandTsetlinPatterns(4, 1)
sage: def phi(x): return G(x.to_tableau())
sage: def phi_inv(x): return D(G(x).to_tableau())
sage: I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: [elt.epsilon(i) for i in I.index_set()]
[0, 1, 0]

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(1)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(1))
>>> def phi(x): return G(x.to_tableau())
>>> def phi_inv(x): return D(G(x).to_tableau())
>>> I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> [elt.epsilon(i) for i in I.index_set()]
[0, 1, 0]

f(i)

Return \(f_i\) of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,1))
sage: G = GelfandTsetlinPatterns(4, 1)
sage: def phi(x): return G(x.to_tableau())
sage: def phi_inv(x): return D(G(x).to_tableau())
sage: I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: elt.f(1)
[[1, 1, 0, 0], [1, 1, 0], [1, 0], [0]]
sage: elt.f(2)
sage: elt.f(3)
[[1, 1, 0, 0], [1, 0, 0], [1, 0], [1]]

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(1)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(1))
>>> def phi(x): return G(x.to_tableau())
>>> def phi_inv(x): return D(G(x).to_tableau())
>>> I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> elt.f(Integer(1))
[[1, 1, 0, 0], [1, 1, 0], [1, 0], [0]]
>>> elt.f(Integer(2))
>>> elt.f(Integer(3))
[[1, 1, 0, 0], [1, 0, 0], [1, 0], [1]]

phi(i)

Return \(\varphi_i\) of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,1))
sage: G = GelfandTsetlinPatterns(4, 1)
sage: def phi(x): return G(x.to_tableau())
sage: def phi_inv(x): return D(G(x).to_tableau())
sage: I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: [elt.epsilon(i) for i in I.index_set()]
[0, 1, 0]

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(1)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(1))
>>> def phi(x): return G(x.to_tableau())
>>> def phi_inv(x): return D(G(x).to_tableau())
>>> I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> [elt.epsilon(i) for i in I.index_set()]
[0, 1, 0]

weight()

Return the weight of self.

EXAMPLES:

Sage

sage: D = crystals.Tableaux(['A',3], shapes=PartitionsInBox(4,1))
sage: G = GelfandTsetlinPatterns(4, 1)
sage: def phi(x): return G(x.to_tableau())
sage: def phi_inv(x): return D(G(x).to_tableau())
sage: I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
sage: elt = I([[1, 1, 0, 0], [1, 1, 0], [1, 0], [1]])
sage: elt.weight()
(1, 0, 1, 0)

Python

>>> from sage.all import *
>>> D = crystals.Tableaux(['A',Integer(3)], shapes=PartitionsInBox(Integer(4),Integer(1)))
>>> G = GelfandTsetlinPatterns(Integer(4), Integer(1))
>>> def phi(x): return G(x.to_tableau())
>>> def phi_inv(x): return D(G(x).to_tableau())
>>> I = crystals.Induced(D, phi, phi_inv, from_crystal=True)
>>> elt = I([[Integer(1), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(1), Integer(0)], [Integer(1), Integer(0)], [Integer(1)]])
>>> elt.weight()
(1, 0, 1, 0)

cardinality()

Return the cardinality of self.

EXAMPLES:

Sage

sage: C = crystals.Tableaux(['A',3], shape=[2,1])
sage: def psi(x):
....:     ret = RSK_inverse(x.to_tableau(), Tableau([[1,1],[2]]))
....:     return (tuple(ret[0]), tuple(ret[1]))
sage: psi_inv = lambda x: C(RSK(*x)[0])
sage: I = crystals.Induced(C, psi, psi_inv, from_crystal=True)
sage: I.cardinality() == C.cardinality()
True

Python

>>> from sage.all import *
>>> C = crystals.Tableaux(['A',Integer(3)], shape=[Integer(2),Integer(1)])
>>> def psi(x):
...     ret = RSK_inverse(x.to_tableau(), Tableau([[Integer(1),Integer(1)],[Integer(2)]]))
...     return (tuple(ret[Integer(0)]), tuple(ret[Integer(1)]))
>>> psi_inv = lambda x: C(RSK(*x)[Integer(0)])
>>> I = crystals.Induced(C, psi, psi_inv, from_crystal=True)
>>> I.cardinality() == C.cardinality()
True