# 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)

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 – (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: 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


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: 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]])


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

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()
Multi-digraph on 24 vertices


We construct an example without a specified inverse map:

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

class Element

An element of an induced crystal.

e(i)

Return $$e_i$$ of self.

EXAMPLES:

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)

epsilon(i)

Return $$\varepsilon_i$$ of self.

EXAMPLES:

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]

f(i)

Return $$f_i$$ of self.

EXAMPLES:

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]]

phi(i)

Return $$\varphi_i$$ of self.

EXAMPLES:

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]

weight()

Return the weight of self.

EXAMPLES:

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)

cardinality()

Return the cardinality of self.

EXAMPLES:

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

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

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.

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

class Element

An element of an induced crystal.

e(i)

Return $$e_i$$ of self.

EXAMPLES:

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)

epsilon(i)

Return $$\varepsilon_i$$ of self.

EXAMPLES:

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]

f(i)

Return $$f_i$$ of self.

EXAMPLES:

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]]

phi(i)

Return $$\varphi_i$$ of self.

EXAMPLES:

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]

weight()

Return the weight of self.

EXAMPLES:

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)

cardinality()

Return the cardinality of self.

EXAMPLES:

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