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\); see RSK()). 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 (see descent_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 in t.

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