The symmetric functions catalog

An overview of symmetric functions and related topics

2022-06-07

Quasisymmetric functions

Quasisymmetric functions were formally introduced by I. Gessel in [Ges84]. Earlier work on P-partitions anticipated this development. For an introduction to quasisymmetric functions, see [LMvW13].

A function $f$ is quasisymmetric if for every composition $\alpha$ of length $\ell,$ the coefficient of $x_1^{\alpha_1} \dotsm x_\ell^{\alpha_\ell}$ is the same as the coefficient of $x_{i_1}^{\alpha_1} \dotsm x_{i_\ell}^{\alpha_\ell},$ for any $0 \lt i_1 \lt i_2 \lt \dotsb \lt i_{\ell}.$ The set of quasisymmetric functions form a graded ring, $\spaceQSym.$

Quasisymmetric functions of degree $n$ are usually indexed by either integer compositions of $n,$ or subsets of $[n-1].$ Given a composition $\alpha \vDash n$ with $\ell$ parts, define

$S_\alpha \coloneqq \{\alpha_1, \alpha_1+\alpha_2,\dotsc, \alpha_1+\alpha_2+\dotsb+\alpha_{\ell-1}\}.$

The bijection $\alpha \mapsto S_\alpha$ maps compositions of $n$ to subsets of $[n-1].$ The partial order $\alpha \leq \beta$ denotes refinement. That is, $\beta$ can be obtained from $\alpha$ by adding consecutive parts of $\alpha.$ When $\alpha \leq \beta,$ we illustrate this relationship with bars between parts of $\alpha,$ such that parts between bars add to parts of $\beta.$

Example (Refinement and bars).

Taken from [AS19b].

$112|341|21|34|2 \quad\text{corresponds to}\quad \alpha = 11234121342, \quad \beta = 48372.$

The most prevalent quasisymmetric function is perhaps the Gessel quasisymmetric functions.

Monomial quasisymmetric functions

Given a composition $\alpha$ with $\ell$ parts, we define the monomial quasisymmetric functions as

$\qmonom_\alpha(\xvec) \coloneqq \sum_{i_1 < i_2 < \dotsb < i_\ell} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \dotsm x_{i_\ell}^{\alpha_\ell}.$

The functions $\qmonom_\alpha$ constitute a basis for the space of homogeneous quasisymmetric functions of degree $n$ as $\alpha$ ranges over all compositions of $n.$

The monomial quasisymmetric functions refine the monomial symmetric functions,

$\monomial_{\lambda}(\xvec) = \sum_{\alpha \sim \lambda}\qmonom_{\alpha}(\xvec)$

where we sum over all compositions $\alpha$ that are a permutation of $\lambda.$

Powersum quasisymmetric functions (Psi)

There are two quasisymmetric refinements of the power-sum symmetric functions introduced in [BDHMN17], denoted $\qPsi_\alpha$ and $\qPhi_\alpha.$

Given a pair of compositions of $n,$ $\alpha \leq \beta,$ related by

\begin{equation*} \alpha_{11} \alpha_{12} \dotsc \alpha_{1,i_1}| \alpha_{21} \alpha_{22} \dotsc \alpha_{2,i_2} | \dotsb | \alpha_{k1} \alpha_{k2} \dotsc \alpha_{k,i_k} \end{equation*}

let

\begin{equation*} \pi(\alpha,\beta) \coloneqq \prod_{j=1}^k (\alpha_{j1})(\alpha_{j1}+\alpha_{j2})\dotsb (\alpha_{j1}+\alpha_{j2}+\dotsb +\alpha_{j,i_j}). \end{equation*}

The quasisymmetric power sum $\qPsi_\alpha$ is defined as

\begin{equation*} \qPsi_\alpha(\xvec) \coloneqq z_\alpha \sum_{\beta \geq \alpha } \frac{1}{\pi(\alpha,\beta)} \qmonom_\beta(\xvec). \end{equation*}

For example, $\Psi_{231} = \frac{1}{10}\qmonom_6 + \frac{1}{4}\qmonom_{24}+ \frac{3}{5}\qmonom_{51}+\qmonom_{231}.$ It was shown in [Thm. 3.11, BDHMN17] that quasisymmetric power sums refine the usual power sums as

$\powerSum_{\lambda}(\xvec) = \sum_{\alpha \sim \lambda}\qPsi_{\alpha}(\xvec).$

The $\qPsi_\alpha$ have a nice relationship with Gessel quasisymmetric functions.

Powersum quasisymmetric functions (p)

In [AWW21], the authors introduce a third quasisymmetric refinement of the power-sum basis, denoted $\qRho_\alpha.$ They refer to this basis as the combinatorial quasisymmetric power-sum basis.

Let $\alpha$ be a composition and let $\lambda$ be the partition obtained from $\alpha$ by rearranging the parts in decreasing order. The monomial expansion of $\qRho_\alpha$ is given by

$\qRho_\alpha(\xvec) = \sum_{\beta} R_{\alpha \beta} \qmonom_\beta(\xvec)$

where $R_{\alpha \beta}$ is the number of ordered set-partitions (see A000670)

$\gamma_1 | \gamma_2 | \dotsb | \gamma_k$

with the following two properties. The word

$\lambda_{\gamma_{11}}, \lambda_{\gamma_{12}},\dotsc,\; \lambda_{\gamma_{21}}, \lambda_{\gamma_{22}},\dotsc,\; \dotsc, \lambda_{\gamma_{k1}}, \lambda_{\gamma_{k2}},\dotsc,$

is equal to $\alpha,$ and $\lambda_{\gamma_{i1}}+ \lambda_{\gamma_{i2}}+\dotsb = \beta_i$ for all $i.$ For example, if $\lambda = 322211,$ then the set-partition $235|16|4$ contributes to $R_{\alpha \beta}$ where

$\alpha = (2,2,1,3,1,2), \qquad \beta = (5,4,2).$

The original article [AWW21] uses the enumeration of certain matrices to define the $R_{\alpha \beta},$ but the above definition is equivalent to theirs.

Example (Table of $\qRho_\alpha,$ for size $4$).

The following table shows the monomial expansion of $\qRho_\alpha.$

 $\alpha$ $\qRho_\alpha$ $4$ $\qmonom_4$ $13$ $\qmonom_{13}$ $22$ $\qmonom_4+2 \qmonom_{22}$ $31$ $\qmonom_4+\qmonom_{31}$ $112$ $\qmonom_{22}+2 \qmonom_{112}$ $121$ $2 \qmonom_{13}+2 \qmonom_{121}$ $211$ $\qmonom_4+\qmonom_{22}+2 \qmonom_{31}+2 \qmonom_{211}$ $1111$ $\qmonom_4+4 \qmonom_{13}+6 \qmonom_{22}+4 \qmonom_{31}+12 \qmonom_{112}+12 \qmonom_{121}+12 \qmonom_{211}+24 \qmonom_{1111}$

The authors also give formulas for computing product and coproduct.

Involution on symmetric functions

The standard involution on symmetric functions that sends $\schurS_\lambda$ to $\schurS_{\lambda'}$ can be extended to quasisymmetric functions in two ways, here defined via the Gessel quasisymmetric functions.

$\omega \gessel_{n,S}(x) = \gessel_{n,[n-1]\setminus (n-S)}(x) \qquad \text{ or } \qquad \psi \gessel_{n,S}(x) = \gessel_{n, [n-1]\setminus S}(x).$

Here, $n-S$ is the set $\{n-s : s \in S\}.$

In [BDHMN17], it is shown that $\omega\left( \qPsi_\alpha \right) = (-1)^{|\alpha|-\length(\alpha)}\qPsi_{\alpha^r},$ where $\alpha^r$ denotes the reverse of $\alpha.$ The same property holds for $\qRho_\alpha,$ see [Thm. 5.7, AWW21].