Poirier-Reutenauer Hopf algebra of standard tableaux¶
AUTHORS:
- Franco Saliola (2012): initial implementation
- Travis Scrimshaw (2018-04-11): added missing doctests and reorganization
-
sage.combinat.chas.fsym.
FSymBases
¶ The category of graded bases of \(FSym\) and \(FSym^*\) indexed by standard tableaux.
-
sage.combinat.chas.fsym.
FSymBasis_abstract
¶ Abstract base class for graded bases of \(FSym\) and of \(FSym^*\) indexed by standard tableaux.
This must define the following attributes:
_prefix
– the basis prefix
-
sage.combinat.chas.fsym.
FreeSymmetricFunctions
¶ The free symmetric functions.
The free symmetric functions is a combinatorial Hopf algebra defined using tableaux and denoted \(FSym\).
Consider the Hopf algebra \(FQSym\) (
FreeQuasisymmetricFunctions
) over a commutative ring \(R\), and its bases \((F_w)\) and \((G_w)\) (where \(w\), in both cases, ranges over all permutations in all symmetric groups \(S_0, S_1, S_2, \ldots\)). For each word \(w\), let \(P(w)\) be the P-tableau of \(w\) (that is, the first of the two tableaux obtained by applying the RSK algorithm to \(w\); seeRSK()
). If \(t\) is a standard tableau of size \(n\), then we define \(\mathcal{G}_t \in FQSym\) to be the sum of the \(F_w\) with \(w\) ranging over all permutations of \(\{1, 2, \ldots, n\}\) satisfying \(P(w) = t\). Equivalently, \(\mathcal{G}_t\) is the sum of the \(G_w\) with \(w\) ranging over all permutations of \(\{1, 2, \ldots, n\}\) satisfying \(Q(w) = t\) (where \(Q(w)\) denotes the Q-tableau of \(w\)).The \(R\)-linear span of the \(\mathcal{G}_t\) (for \(t\) ranging over all standard tableaux) is a Hopf subalgebra of \(FQSym\), denoted by \(FSym\) and known as the free symmetric functions or the Poirier-Reutenauer Hopf algebra of tableaux. It has been introduced in [PoiReu95], where it was denoted by \((\ZZ T, \ast, \delta)\). (What we call \(\mathcal{G}_t\) has just been called \(t\) in [PoiReu95].) The family \((\mathcal{G}_t)\) (with \(t\) ranging over all standard tableaux) is a basis of \(FSym\), called the Fundamental basis.
EXAMPLES:
As explained above, \(FSym\) is constructed as a Hopf subalgebra of \(FQSym\):
sage: G = algebras.FSym(QQ).G() sage: F = algebras.FQSym(QQ).F() sage: G[[1,3],[2]] G[13|2] sage: G[[1,3],[2]].to_fqsym() G[2, 1, 3] + G[3, 1, 2] sage: F(G[[1,3],[2]]) F[2, 1, 3] + F[2, 3, 1]
This embedding is a Hopf algebra morphism:
sage: all(F(G[t1] * G[t2]) == F(G[t1]) * F(G[t2]) ....: for t1 in StandardTableaux(2) ....: for t2 in StandardTableaux(3)) True sage: FF = F.tensor_square() sage: all(FF(G[t].coproduct()) == F(G[t]).coproduct() ....: for t in StandardTableaux(4)) True
There is a Hopf algebra map from \(FSym\) onto the Hopf algebra of symmetric functions, which maps a tableau \(t\) to the Schur function indexed by the shape of \(t\):
sage: TG = algebras.FSym(QQ).G() sage: t = StandardTableau([[1,3],[2,4],[5]]) sage: TG[t] G[13|24|5] sage: TG[t].to_symmetric_function() s[2, 2, 1]
-
sage.combinat.chas.fsym.
FreeSymmetricFunctions_Dual
¶ The Hopf dual \(FSym^*\) of the free symmetric functions \(FSym\).
See
FreeSymmetricFunctions
for the definition of the latter.Recall that the fundamental basis of \(FSym\) consists of the elements \(\mathcal{G}_t\) for \(t\) ranging over all standard tableaux. The dual basis of this is called the dual fundamental basis of \(FSym^*\), and is denoted by \((\mathcal{G}_t^*)\). The Hopf dual \(FSym^*\) is isomorphic to the Hopf algebra \((\ZZ T, \ast', \delta')\) from [PoiReu95]; the isomorphism sends a basis element \(\mathcal{G}_t^*\) to \(t\).
EXAMPLES:
sage: FSym = algebras.FSym(QQ) sage: TF = FSym.dual().F() sage: TF[1,2] * TF[[1],[2]] F[12|3|4] + F[123|4] + F[124|3] + F[13|2|4] + F[134|2] + F[14|2|3] sage: TF[[1,2],[3]].coproduct() F[] # F[12|3] + F[1] # F[1|2] + F[12] # F[1] + F[12|3] # F[]
The Hopf algebra \(FSym^*\) is a Hopf quotient of \(FQSym\); the canonical projection sends \(F_w\) (for a permutation \(w\)) to \(\mathcal{G}_{Q(w)}^*\), where \(Q(w)\) is the Q-tableau of \(w\). This projection is implemented as a coercion:
sage: FQSym = algebras.FQSym(QQ) sage: F = FQSym.F() sage: TF(F[[1, 3, 2]]) F[12|3] sage: TF(F[[5, 1, 4, 2, 3]]) F[135|2|4]
-
sage.combinat.chas.fsym.
ascent_set
(t)¶ Return the ascent set of a standard tableau
t
(encoded as a sorted list).The ascent set of a standard tableau \(t\) is defined as the set of all entries \(i\) of \(t\) such that the number \(i+1\) either appears to the right of \(i\) or appears in a row above \(i\) or does not appear in \(t\) at all.
EXAMPLES:
sage: from sage.combinat.chas.fsym import ascent_set sage: t = StandardTableau([[1,3,4,7],[2,5,6],[8]]) sage: ascent_set(t) [2, 3, 5, 6, 8] sage: ascent_set(StandardTableau([])) [] sage: ascent_set(StandardTableau([[1, 2, 3]])) [1, 2, 3] sage: ascent_set(StandardTableau([[1, 2, 4], [3]])) [1, 3, 4] sage: ascent_set([[1, 3, 5], [2, 4]]) [2, 4, 5]
-
sage.combinat.chas.fsym.
descent_composition
(t)¶ Return the descent composition of a standard tableau
t
.This is the composition of the size of \(t\) whose partial sums are the elements of the descent set of
t
(seedescent_set()
).EXAMPLES:
sage: from sage.combinat.chas.fsym import descent_composition sage: t = StandardTableau([[1,3,4,7],[2,5,6],[8]]) sage: descent_composition(t) [1, 3, 3, 1] sage: descent_composition([[1, 3, 5], [2, 4]]) [1, 2, 2]
-
sage.combinat.chas.fsym.
descent_set
(t)¶ Return the descent set of a standard tableau
t
(encoded as a sorted list).The descent set of a standard tableau \(t\) is defined as the set of all entries \(i\) of \(t\) such that the number \(i+1\) appears in a row below \(i\) in \(t\).
EXAMPLES:
sage: from sage.combinat.chas.fsym import descent_set sage: t = StandardTableau([[1,3,4,7],[2,5,6],[8]]) sage: descent_set(t) [1, 4, 7] sage: descent_set(StandardTableau([])) [] sage: descent_set(StandardTableau([[1, 2, 3]])) [] sage: descent_set(StandardTableau([[1, 2, 4], [3]])) [2] sage: descent_set([[1, 3, 5], [2, 4]]) [1, 3]
-
sage.combinat.chas.fsym.
standardize
(t)¶ Return the standard tableau corresponding to a given semistandard tableau
t
with no repeated entries.Note
This is an optimized version of
Tableau.standardization()
for computations in \(FSym\) by using the assumption of no repeated entries int
.EXAMPLES:
sage: from sage.combinat.chas.fsym import standardize sage: t = Tableau([[1,3,5,7],[2,4,8],[9]]) sage: standardize(t) [[1, 3, 5, 6], [2, 4, 7], [8]] sage: t = Tableau([[3,8,9,15],[5,10,12],[133]]) sage: standardize(t) [[1, 3, 4, 7], [2, 5, 6], [8]]
Returns an equal tableau if already standard:
sage: t = Tableau([[1,3,4,5],[2,6,7],[8]]) sage: standardize(t) [[1, 3, 4, 5], [2, 6, 7], [8]] sage: standardize(t) == t True