Quasisymmetric functions

REFERENCES:

[Ges]I. Gessel, Multipartite P-partitions and inner products of skew Schur functions, Contemp. Math. 34 (1984), 289-301. http://people.brandeis.edu/~gessel/homepage/papers/multipartite.pdf
[MR]C. Malvenuto and C. Reutenauer, Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra 177 (1995), no. 3, 967-982. http://www.mat.uniroma1.it/people/malvenuto/Duality.pdf
[Mal1993]Claudia Malvenuto, Produits et coproduits des fonctions quasi-symetriques et de l’algebre des descentes, thesis, November 1993. http://www1.mat.uniroma1.it/people/malvenuto/Thesis.pdf
[Haz2004]Michiel Hazewinkel, Explicit polynomial generators for the ring of quasisymmetric functions over the integers. Arxiv math/0410366v1
[Rad1979]David E. Radford, A natural ring basis for the shuffle algebra and an application to group schemes, J. Algebra 58 (1979), 432-454.
[NCSF1]Israel Gelfand, D. Krob, Alain Lascoux, B. Leclerc, V. S. Retakh, J.-Y. Thibon, Noncommutative symmetric functions. Arxiv hep-th/9407124v1
[NCSF2]D. Krob, B. Leclerc, J.-Y. Thibon, Noncommutative symmetric functions II: Transformations of alphabets. http://www-igm.univ-mlv.fr/~jyt/ARTICLES/NCSF2.ps
[HLNT09]F. Hivert, J.-G. Luque, J.-C. Novelli, J.-Y. Thibon, The (1-E)-transform in combinatorial Hopf algebras. Arxiv math/0912.0184v2
[LMvW13]Kurt Luoto, Stefan Mykytiuk and Stephanie van Willigenburg, An introduction to quasisymmetric Schur functions – Hopf algebras, quasisymmetric functions, and Young composition tableaux, May 23, 2013, Springer. http://www.math.ubc.ca/%7Esteph/papers/QuasiSchurBook.pdf
[BBSSZ2012]Chris Berg, Nantel Bergeron, Franco Saliola, Luis Serrano, Mike Zabrocki, A lift of the Schur and Hall-Littlewood bases to non-commutative symmetric functions, Arxiv 1208.5191v3.
[Hoff2015]Michael Hoffman. Quasi-symmetric functions and mod \(p\) multiple harmonic sums. Kyushu J. Math. 69 (2015), pp. 345-366. doi:10.2206/kyushujm.69.345, Arxiv math/0401319v3.
[BDHMN2017]Cristina Ballantine, Zajj Daugherty, Angela Hicks, Sarah Mason, Elizabeth Niese. Quasisymmetric power sums. Arxiv 1710.11613.
[AHM2018]Edward Allen, Joshua Hallam, Sarah Mason, Dual Immaculate Quasisymmetric Functions Expand Positively into Young Quasisymmetric Schur Functions. Arxiv 1606.03519

AUTHOR:

  • Jason Bandlow
  • Franco Saliola
  • Chris Berg
  • Darij Grinberg
sage.combinat.ncsf_qsym.qsym.QuasiSymmetricFunctions

The Hopf algebra of quasisymmetric functions.

Let \(R\) be a commutative ring with unity. The \(R\)-algebra of quasi-symmetric functions may be realized as an \(R\)-subalgebra of the ring of power series in countably many variables \(R[[x_1, x_2, x_3, \ldots]]\). It consists of those formal power series \(p\) which are degree-bounded (i. e., the degrees of all monomials occuring with nonzero coefficient in \(p\) are bounded from above, although the bound can depend on \(p\)) and satisfy the following condition: For every tuple \((a_1, a_2, \ldots, a_m)\) of positive integers, the coefficient of the monomial \(x_{i_1}^{a_1} x_{i_2}^{a_2} \cdots x_{i_m}^{a_m}\) in \(p\) is the same for all strictly increasing sequences \((i_1 < i_2 < \cdots < i_m)\) of positive integers. (In other words, the coefficient of a monomial in \(p\) depends only on the sequence of nonzero exponents in the monomial. If “sequence” were to be replaced by “multiset” here, we would obtain the definition of a symmetric function.)

The \(R\)-algebra of quasi-symmetric functions is commonly called \(\mathrm{QSym}_R\) or occasionally just \(\mathrm{QSym}\) (when \(R\) is clear from the context or \(\ZZ\) or \(\QQ\)). It is graded by the total degree of the power series. Its homogeneous elements of degree \(k\) form a free \(R\)-submodule of rank equal to the number of compositions of \(k\) (that is, \(2^{k-1}\) if \(k \geq 1\), else \(1\)).

The two classical bases of \(\mathrm{QSym}\), the monomial basis \((M_I)_I\) and the fundamental basis \((F_I)_I\), are indexed by compositions \(I = (I_1, I_2, \cdots, I_\ell )\) and defined by the formulas:

\[M_I = \sum_{1 \leq i_1 < i_2 < \cdots < i_\ell} x_{i_1}^{I_1} x_{i_2}^{I_2} \cdots x_{i_\ell}^{I_\ell}\]

and

\[F_I = \sum_{(j_1, j_2, \ldots, j_n)} x_{j_1} x_{j_2} \cdots x_{j_n}\]

where in the second equation the sum runs over all weakly increasing \(n\)-tuples \((j_1, j_2, \ldots, j_n)\) of positive integers (where \(n\) is the size of \(I\)) which increase strictly from \(j_r\) to \(j_{r+1}\) if \(r\) is a descent of the composition \(I\).

These bases are related by the formula

\(F_I = \sum_{J \leq I} M_J\)

where the inequality \(J \leq I\) indicates that \(J\) is finer than \(I\).

The \(R\)-algebra of quasi-symmetric functions is a Hopf algebra, with the coproduct satisfying

\[\Delta M_I = \sum_{k=0}^{\ell} M_{(I_1, I_2, \cdots, I_k)} \otimes M_{(I_{k+1}, I_{k+2}, \cdots , I_{\ell})}\]

for every composition \(I = (I_1, I_2, \cdots , I_\ell )\).

It is possible to define an \(R\)-algebra of quasi-symmetric functions in a finite number of variables as well (but it is not a bialgebra). These quasi-symmetric functions are actual polynomials then, not just power series.

Chapter 5 of [GriRei18] and Section 11 of [HazWitt1] are devoted to quasi-symmetric functions, as are Malvenuto’s thesis [Mal1993] and part of Chapter 7 of [Sta-EC2].

The implementation of the quasi-symmetric function Hopf algebra

We realize the \(R\)-algebra of quasi-symmetric functions in Sage as a graded Hopf algebra with basis elements indexed by compositions:

sage: QSym = QuasiSymmetricFunctions(QQ)
sage: QSym.category()
Join of Category of hopf algebras over Rational Field
    and Category of graded algebras over Rational Field
    and Category of monoids with realizations
    and Category of coalgebras over Rational Field with realizations

The most standard two bases for this \(R\)-algebra are the monomial and fundamental bases, and are accessible by the M() and F() methods:

sage: M = QSym.M()
sage: F = QSym.F()
sage: M(F[2,1,2])
M[1, 1, 1, 1, 1] + M[1, 1, 1, 2] + M[2, 1, 1, 1] + M[2, 1, 2]
sage: F(M[2,1,2])
F[1, 1, 1, 1, 1] - F[1, 1, 1, 2] - F[2, 1, 1, 1] + F[2, 1, 2]

The product on this space is commutative and is inherited from the product on the realization within the ring of power series:

sage: M[3]*M[1,1] == M[1,1]*M[3]
True
sage: M[3]*M[1,1]
M[1, 1, 3] + M[1, 3, 1] + M[1, 4] + M[3, 1, 1] + M[4, 1]
sage: F[3]*F[1,1]
F[1, 1, 3] + F[1, 2, 2] + F[1, 3, 1] + F[1, 4] + F[2, 1, 2]
 + F[2, 2, 1] + F[2, 3] + F[3, 1, 1] + F[3, 2] + F[4, 1]
sage: M[3]*F[2]
M[1, 1, 3] + M[1, 3, 1] + M[1, 4] + M[2, 3] + M[3, 1, 1] + M[3, 2]
 + M[4, 1] + M[5]
sage: F[2]*M[3]
F[1, 1, 1, 2] - F[1, 2, 2] + F[2, 1, 1, 1] - F[2, 1, 2] - F[2, 2, 1]
 + F[5]

There is a coproduct on \(\mathrm{QSym}\) as well, which in the Monomial basis acts by cutting the composition into a left half and a right half. The coproduct is not co-commutative:

sage: M[1,3,1].coproduct()
M[] # M[1, 3, 1] + M[1] # M[3, 1] + M[1, 3] # M[1] + M[1, 3, 1] # M[]
sage: F[1,3,1].coproduct()
F[] # F[1, 3, 1] + F[1] # F[3, 1] + F[1, 1] # F[2, 1]
 + F[1, 2] # F[1, 1] + F[1, 3] # F[1] + F[1, 3, 1] # F[]

The duality pairing with non-commutative symmetric functions

These two operations endow the quasi-symmetric functions \(\mathrm{QSym}\) with the structure of a Hopf algebra. It is the graded dual Hopf algebra of the non-commutative symmetric functions \(NCSF\). Under this duality, the Monomial basis of \(\mathrm{QSym}\) is dual to the Complete basis of \(NCSF\), and the Fundamental basis of \(\mathrm{QSym}\) is dual to the Ribbon basis of \(NCSF\) (see [MR]).

sage: S = M.dual(); S
Non-Commutative Symmetric Functions over the Rational Field in the Complete basis
sage: M[1,3,1].duality_pairing( S[1,3,1] )
1
sage: M.duality_pairing_matrix( S, degree=4 )
[1 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 1]
sage: F.duality_pairing_matrix( S, degree=4 )
[1 0 0 0 0 0 0 0]
[1 1 0 0 0 0 0 0]
[1 0 1 0 0 0 0 0]
[1 1 1 1 0 0 0 0]
[1 0 0 0 1 0 0 0]
[1 1 0 0 1 1 0 0]
[1 0 1 0 1 0 1 0]
[1 1 1 1 1 1 1 1]
sage: NCSF = M.realization_of().dual()
sage: R = NCSF.Ribbon()
sage: F.duality_pairing_matrix( R, degree=4 )
[1 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 1]
sage: M.duality_pairing_matrix( R, degree=4 )
[ 1  0  0  0  0  0  0  0]
[-1  1  0  0  0  0  0  0]
[-1  0  1  0  0  0  0  0]
[ 1 -1 -1  1  0  0  0  0]
[-1  0  0  0  1  0  0  0]
[ 1 -1  0  0 -1  1  0  0]
[ 1  0 -1  0 -1  0  1  0]
[-1  1  1 -1  1 -1 -1  1]

Let \(H\) and \(G\) be elements of \(\mathrm{QSym}\), and \(h\) an element of \(NCSF\). Then, if we represent the duality pairing with the mathematical notation \([ \cdot, \cdot ]\),

\([H G, h] = [H \otimes G, \Delta(h)]~.\)

For example, the coefficient of M[2,1,4,1] in M[1,3]*M[2,1,1] may be computed with the duality pairing:

sage: I, J = Composition([1,3]), Composition([2,1,1])
sage: (M[I]*M[J]).duality_pairing(S[2,1,4,1])
1

And the coefficient of S[1,3] # S[2,1,1] in S[2,1,4,1].coproduct() is equal to this result:

sage: S[2,1,4,1].coproduct()
S[] # S[2, 1, 4, 1] + ... + S[1, 3] # S[2, 1, 1] + ... + S[4, 1] # S[2, 1]

The duality pairing on the tensor space is another way of getting this coefficient, but currently the method duality_pairing is not defined on the tensor squared space. However, we can extend this functionality by applying a linear morphism to the terms in the coproduct, as follows:

sage: X = S[2,1,4,1].coproduct()
sage: def linear_morphism(x, y):
....:   return x.duality_pairing(M[1,3]) * y.duality_pairing(M[2,1,1])
sage: X.apply_multilinear_morphism(linear_morphism, codomain=ZZ)
1

Similarly, if \(H\) is an element of \(\mathrm{QSym}\) and \(g\) and \(h\) are elements of \(NCSF\), then

\[[ H, g h ] = [ \Delta(H), g \otimes h ].\]

For example, the coefficient of R[2,3,1] in R[2,1]*R[2,1] is computed with the duality pairing by the following command:

sage: (R[2,1]*R[2,1]).duality_pairing(F[2,3,1])
1
sage: R[2,1]*R[2,1]
R[2, 1, 2, 1] + R[2, 3, 1]

This coefficient should then be equal to the coefficient of F[2,1] # F[2,1] in F[2,3,1].coproduct():

sage: F[2,3,1].coproduct()
F[] # F[2, 3, 1] + ... + F[2, 1] # F[2, 1]  + ... + F[2, 3, 1] # F[]

This can also be computed by the duality pairing on the tensor space, as above:

sage: X = F[2,3,1].coproduct()
sage: def linear_morphism(x, y):
....:   return x.duality_pairing(R[2,1]) * y.duality_pairing(R[2,1])
sage: X.apply_multilinear_morphism(linear_morphism, codomain=ZZ)
1

The operation dual to multiplication by a non-commutative symmetric function

Let \(g \in NCSF\) and consider the linear endomorphism of \(NCSF\) defined by left (respectively, right) multiplication by \(g\). Since there is a duality between \(\mathrm{QSym}\) and \(NCSF\), this linear transformation induces an operator \(g^{\perp}\) on \(\mathrm{QSym}\) satisfying

\[[ g^{\perp}(H), h ] = [ H, gh ].\]

for any non-commutative symmetric function \(h\).

This is implemented by the method skew_by(). Explicitly, if H is a quasi-symmetric function and g a non-commutative symmetric function, then H.skew_by(g) and H.skew_by(g, side='right') are expressions that satisfy, for any non-commutative symmetric function h, the following equalities:

H.skew_by(g).duality_pairing(h) == H.duality_pairing(g*h)
H.skew_by(g, side='right').duality_pairing(h) == H.duality_pairing(h*g)

For example, M[J].skew_by(S[I]) is \(0\) unless the composition J begins with I and M(J).skew_by(S(I), side='right') is \(0\) unless the composition J ends with I. For example:

sage: M[3,2,2].skew_by(S[3])
M[2, 2]
sage: M[3,2,2].skew_by(S[2])
0
sage: M[3,2,2].coproduct().apply_multilinear_morphism( lambda x,y: x.duality_pairing(S[3])*y )
M[2, 2]
sage: M[3,2,2].skew_by(S[3], side='right')
0
sage: M[3,2,2].skew_by(S[2], side='right')
M[3, 2]

The counit

The counit is defined by sending all elements of positive degree to zero:

sage: M[3].degree(), M[3,1,2].degree(), M.one().degree()
(3, 6, 0)
sage: M[3].counit()
0
sage: M[3,1,2].counit()
0
sage: M.one().counit()
1
sage: (M[3] - 2*M[3,1,2] + 7).counit()
7
sage: (F[3] - 2*F[3,1,2] + 7).counit()
7

The antipode

The antipode sends the Fundamental basis element indexed by the composition \(I\) to \((-1)^{|I|}\) times the Fundamental basis element indexed by the conjugate composition to \(I\) (where \(|I|\) stands for the size of \(I\), that is, the sum of all entries of \(I\)).

sage: F[3,2,2].antipode()
-F[1, 2, 2, 1, 1]
sage: Composition([3,2,2]).conjugate()
[1, 2, 2, 1, 1]

The antipodes of the Monomial quasisymmetric functions can also be computed easily: Every composition \(I\) satisfies

\[\omega(M_I) = (-1)^{\ell(I)} \sum M_J,\]

where the sum ranges over all compositions \(J\) of \(|I|\) which are coarser than the reversed composition \(I^r\) of \(I\). Here, \(\ell(I)\) denotes the length of the composition \(I\) (that is, the number of its parts).

sage: M[3,2,1].antipode()
-M[1, 2, 3] - M[1, 5] - M[3, 3] - M[6]
sage: M[3,2,2].antipode()
-M[2, 2, 3] - M[2, 5] - M[4, 3] - M[7]

We demonstrate here the defining relation of the antipode:

sage: X = F[3,2,2].coproduct()
sage: X.apply_multilinear_morphism(lambda x,y: x*y.antipode())
0
sage: X.apply_multilinear_morphism(lambda x,y: x.antipode()*y)
0

The relation with symmetric functions

The quasi-symmetric functions are a ring which contain the symmetric functions as a subring. The Monomial quasi-symmetric functions are related to the monomial symmetric functions by

\[m_\lambda = \sum_{\operatorname{sort}(I) = \lambda} M_I\]

(where \(\operatorname{sort}(I)\) denotes the result of sorting the entries of \(I\) in decreasing order).

There are methods to test if an expression in the quasi-symmetric functions is a symmetric function and, if it is, send it to an expression in the symmetric functions:

sage: f = M[1,1,2] + M[1,2,1]
sage: f.is_symmetric()
False
sage: g = M[3,1] + M[1,3]
sage: g.is_symmetric()
True
sage: g.to_symmetric_function()
m[3, 1]

The expansion of the Schur function in terms of the Fundamental quasi-symmetric functions is due to [Ges]. There is one term in the expansion for each standard tableau of shape equal to the partition indexing the Schur function.

sage: f = F[3,2] + F[2,2,1] + F[2,3] + F[1,3,1] + F[1,2,2]
sage: f.is_symmetric()
True
sage: f.to_symmetric_function()
5*m[1, 1, 1, 1, 1] + 3*m[2, 1, 1, 1] + 2*m[2, 2, 1] + m[3, 1, 1] + m[3, 2]
sage: s = SymmetricFunctions(QQ).s()
sage: s(f.to_symmetric_function())
s[3, 2]

It is also possible to convert a symmetric function to a quasi-symmetric function:

sage: m = SymmetricFunctions(QQ).m()
sage: M( m[3,1,1] )
M[1, 1, 3] + M[1, 3, 1] + M[3, 1, 1]
sage: F( s[2,2,1] )
F[1, 1, 2, 1] + F[1, 2, 1, 1] + F[1, 2, 2] + F[2, 1, 2] + F[2, 2, 1]

It is possible to experiment with the quasi-symmetric function expansion of other bases, but it is important that the base ring be the same for both algebras.

sage: R = QQ['t']
sage: Qp = SymmetricFunctions(R).hall_littlewood().Qp()
sage: QSymt = QuasiSymmetricFunctions(R)
sage: Ft = QSymt.F()
sage: Ft( Qp[2,2] )
F[1, 2, 1] + t*F[1, 3] + (t+1)*F[2, 2] + t*F[3, 1] + t^2*F[4]
sage: K = QQ['q','t'].fraction_field()
sage: Ht = SymmetricFunctions(K).macdonald().Ht()
sage: Fqt = QuasiSymmetricFunctions(Ht.base_ring()).F()
sage: Fqt(Ht[2,1])
q*t*F[1, 1, 1] + (q+t)*F[1, 2] + (q+t)*F[2, 1] + F[3]

The following will raise an error because the base ring of F is not equal to the base ring of Ht:

sage: F(Ht[2,1])
Traceback (most recent call last):
...
TypeError: do not know how to make x (= McdHt[2, 1]) an element of self (=Quasisymmetric functions over the Rational Field in the Fundamental basis)

The map to the ring of polynomials

The quasi-symmetric functions can be seen as an inverse limit of a subring of a polynomial ring as the number of variables increases. Indeed, there exists a projection from the quasi-symmetric functions onto the polynomial ring \(R[x_1, x_2, \ldots, x_n]\). This projection is defined by sending the variables \(x_{n+1}, x_{n+2}, \cdots\) to \(0\), while the remaining \(n\) variables remain fixed. Note that this projection sends \(M_I\) to \(0\) if the length of the composition \(I\) is higher than \(n\).

sage: M[1,3,1].expand(4)
x0*x1^3*x2 + x0*x1^3*x3 + x0*x2^3*x3 + x1*x2^3*x3
sage: F[1,3,1].expand(4)
x0*x1^3*x2 + x0*x1^3*x3 + x0*x1^2*x2*x3 + x0*x1*x2^2*x3 + x0*x2^3*x3 + x1*x2^3*x3
sage: M[1,3,1].expand(2)
0