In algebra and in particular in algebraic combinatorics, a quasisymmetric function is any element in the ring of quasisymmetric functions which is in turn a subring of the formal power series ring with a countable number of variables. This ring generalizes the ring of symmetric functions. This ring can be realized as a specific limit of the rings of quasisymmetric polynomials in n variables, as n goes to infinity. This ring serves as universal structure in which relations between quasisymmetric polynomials can be expressed in a way independent of the number n of variables (but its elements are neither polynomials nor functions).

Definitions

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.^[2][3] 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}}}$

Important bases

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,^[4] the "type I" and "type II" quasisymmetric power sums,^[5] and bases related to enumeration in matroids.^[6][7]

Applications

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,^[8][9] permutations,^{[10][11][12][13]} tableaux,^[14] chains of posets,^[14][15] reduced decompositions in finite Coxeter groups (via Stanley symmetric functions),^[14] and parking functions.^[16] In symmetric function theory and representation theory, applications include the study of Schubert polynomials,^[17][18] Macdonald polynomials,^[19] Hecke algebras,^[20] and Kazhdan–Lusztig polynomials.^[21] Often quasisymmetric functions provide a powerful bridge between combinatorial structures and symmetric functions.

Related algebras

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.^[22] Hence any such Hopf algebra has a morphism to the ring of quasisymmetric functions.

One example of this is the peak algebra.^[23]

References

External links

• BIRS Workshop on Quasisymmetric Functions