Quasisymmetric function

The ring of quasisymmetric functions, denoted QSym, can be defined over any commutative ring R such as the integers. Quasisymmetric functions are power series of bounded degree in variables ${\displaystyle x_{1},x_{2},x_{3},\dots }$ with coefficients in R, which are shift invariant in the sense that the coefficient of the monomial ${\displaystyle x_{1}^{\alpha _{1}}x_{2}^{\alpha _{2}}\cdots x_{k}^{\alpha _{k}}}$ is equal to the coefficient of the monomial ${\displaystyle x_{i_{1}}^{\alpha _{1}}x_{i_{2}}^{\alpha _{2}}\cdots x_{i_{k}}^{\alpha _{k}}}$ for any strictly increasing sequence of positive integers ${\displaystyle i_{1}<i_{2}<\cdots <i_{k}}$ indexing the variables and any positive integer sequence ${\displaystyle (\alpha _{1},\alpha _{2},\ldots ,\alpha _{k})}$ of exponents.[1] Much of the study of quasisymmetric functions is based on that of symmetric functions.

A quasisymmetric function in finitely many variables is a quasisymmetric polynomial. Both symmetric and quasisymmetric polynomials may be characterized in terms of actions of the symmetric group ${\displaystyle S_{n}}$ on a polynomial ring in ${\displaystyle n}$ variables ${\displaystyle x_{1},\dots ,x_{n}}$. One such action of ${\displaystyle S_{n}}$ permutes variables, changing a polynomial ${\displaystyle p(x_{1},\dots ,x_{n})}$ by iteratively swapping pairs ${\displaystyle (x_{i},x_{i+1})}$ of variables having consecutive indices. Those polynomials unchanged by all such swaps form the subring of symmetric polynomials. A second action of ${\displaystyle S_{n}}$ conditionally permutes variables, changing a polynomial ${\displaystyle p(x_{1},\ldots ,x_{n})}$ by swapping pairs ${\displaystyle (x_{i},x_{i+1})}$ of variables except in monomials containing both variables. Those polynomials unchanged by all such conditional swaps form the subring of quasisymmetric polynomials. One quasisymmetric function in four variables ${\displaystyle x_{1},x_{2},x_{3},x_{4}}$ is the polynomial

${\displaystyle x_{1}^{2}x_{2}x_{3}+x_{1}^{2}x_{2}x_{4}+x_{1}^{2}x_{3}x_{4}+x_{2}^{2}x_{3}x_{4}.\,}$

The simplest symmetric function containing these monomials is

${\displaystyle {\begin{aligned}x_{1}^{2}x_{2}x_{3}+x_{1}^{2}x_{2}x_{4}+x_{1}^{2}x_{3}x_{4}+x_{2}^{2}x_{3}x_{4}+x_{1}x_{2}^{2}x_{3}+x_{1}x_{2}^{2}x_{4}+x_{1}x_{3}^{2}x_{4}+x_{2}x_{3}^{2}x_{4}\\{}+x_{1}x_{2}x_{3}^{2}+x_{1}x_{2}x_{4}^{2}+x_{1}x_{3}x_{4}^{2}+x_{2}x_{3}x_{4}^{2}.\,\end{aligned}}}$

QSym is a graded R-algebra, decomposing as

${\displaystyle \operatorname {QSym} =\bigoplus _{n\geq 0}\operatorname {QSym} _{n},\,}$

where ${\displaystyle \operatorname {QSym} _{n}}$ is the ${\displaystyle R}$-span of all quasisymmetric functions that are homogeneous of degree ${\displaystyle n}$. Two natural bases for ${\displaystyle \operatorname {QSym} _{n}}$ are the monomial basis ${\displaystyle \{M_{\alpha }\}}$ and the fundamental basis ${\displaystyle \{F_{\alpha }\}}$ indexed by compositions ${\displaystyle \alpha =(\alpha _{1},\alpha _{2},\ldots ,\alpha _{k})}$ of ${\displaystyle n}$, denoted ${\displaystyle \alpha \vDash n}$. The monomial basis consists of ${\displaystyle M_{0}=1}$ and all formal power series

${\displaystyle M_{\alpha }=\sum _{i_{1}<i_{2}<\cdots <i_{k}}x_{i_{1}}^{\alpha _{1}}x_{i_{2}}^{\alpha _{2}}\cdots x_{i_{k}}^{\alpha _{k}}.\,}$

The fundamental basis consists ${\displaystyle F_{0}=1}$ and all formal power series

${\displaystyle F_{\alpha }=\sum _{\alpha \succeq \beta }M_{\beta },\,}$

where ${\displaystyle \alpha \succeq \beta }$ means we can obtain ${\displaystyle \alpha }$ by adding together adjacent parts of ${\displaystyle \beta }$, for example, (3,2,4,2) ${\displaystyle \succeq }$ (3,1,1,1,2,1,2). Thus, when the ring ${\displaystyle R}$ is the ring of rational numbers, one has

${\displaystyle \operatorname {QSym} _{n}=\operatorname {span} _{\mathbb {Q} }\{M_{\alpha }\mid \alpha \vDash n\}=\operatorname {span} _{\mathbb {Q} }\{F_{\alpha }\mid \alpha \vDash n\}.\,}$

Then one can define the algebra of symmetric functions ${\displaystyle \Lambda =\Lambda _{0}\oplus \Lambda _{1}\oplus \cdots }$ as the subalgebra of QSym spanned by the monomial symmetric functions ${\displaystyle m_{0}=1}$ and all formal power series ${\displaystyle m_{\lambda }=\sum M_{\alpha },}$ where the sum is over all compositions ${\displaystyle \alpha }$ which rearrange to the partition ${\displaystyle \lambda }$. Moreover, we have ${\displaystyle \Lambda _{n}=\Lambda \cap \operatorname {QSym} _{n}}$. For example, ${\displaystyle F_{(1,2)}=M_{(1,2)}+M_{(1,1,1)}}$ and ${\displaystyle m_{(2,1)}=M_{(2,1)}+M_{(1,2)}.}$

Other important bases for quasisymmetric functions include the basis of quasisymmetric Schur functions,[2] the "type I" and "type II" quasisymmetric power sums,[3] and bases related to enumeration in matroids.[4][5]

Quasisymmetric functions have been applied in enumerative combinatorics, symmetric function theory, representation theory, and number theory. Applications of quasisymmetric functions include enumeration of P-partitions,[6][7] permutations,[8][9][10][11] tableaux,[12] chains of posets,[12][13] reduced decompositions in finite Coxeter groups (via Stanley symmetric functions),[12] and parking functions.[14] In symmetric function theory and representation theory, applications include the study of Schubert polynomials,[15][16] Macdonald polynomials,[17] Hecke algebras,[18] and Kazhdan–Lusztig polynomials.[19] Often quasisymmetric functions provide a powerful bridge between combinatorial structures and symmetric functions.

As a graded Hopf algebra, the dual of the ring of quasisymmetric functions is the ring of noncommutative symmetric functions. Every symmetric function is also a quasisymmetric function, and hence the ring of symmetric functions is a subalgebra of the ring of quasisymmetric functions.

The ring of quasisymmetric functions is the terminal object in category of graded Hopf algebras with a single character.[20] Hence any such Hopf algebra has a morphism to the ring of quasisymmetric functions.

One example of this is the peak algebra.[21]

• BIRS Workshop on Quasisymmetric Functions