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 $x\_1,x\_2,x\_3,\; \backslash dots$ with coefficients in R, which are shift invariant in the sense that the coefficient of the monomial $x\_1^\{\backslash alpha\_1\}x\_2^\{\backslash alpha\_2\}\; \backslash cdots\; x\_k^\{\backslash alpha\_k\}$ is equal to the coefficient of the monomial $x\_\{i\_1\}^\{\backslash alpha\_1\}\; x\_\{i\_2\}^\{\backslash alpha\_2\}\backslash cdots\; x\_\{i\_k\}^\{\backslash alpha\_k\}$ for any strictly increasing sequence of positive integers

indexing the variables and any positive integer sequence $(\backslash alpha\_1,\; \backslash alpha\_2,\backslash ldots,\backslash alpha\_k)$ of exponents.

Stanley, Richard P. Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999. {{ISBN|0-521-56069-1}} (hardback) {{ISBN|0-521-78987-7}} (paperback).

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 $S\_n$

on a polynomial ring in $n$ variables $x\_1,\backslash dots,\; x\_n$.

One such action of $S\_n$ permutes variables,

changing a polynomial $p(x\_1,\backslash dots,x\_n)$ by iteratively swapping pairs $(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 $S\_n$ conditionally permutes variables,

changing a polynomial $p(x\_1,\backslash ldots,x\_n)$

by swapping pairs $(x\_i,\; x\_\{i+1\})$ of variables

except in monomials containing both variables.{{citation|last1=Hivert|first1=Florent|title=Hecke Algebras, Difference Operators, and Quasi-Symmetric Functions|journal= Advances in Mathematics |volume=155 |year=2000 |pages=181–238 |issue= 2|doi=10.1006/aima.1999.1901|doi-access=free}}

Those polynomials unchanged by all such conditional swaps form

the subring of quasisymmetric polynomials. One quasisymmetric polynomial in four variables $x\_1,x\_2,x\_3,x\_4$ is the polynomial

: $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.\; \backslash ,$

The simplest symmetric polynomial containing these monomials is

: $$

\begin{align}

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{align}

QSym is a graded R-algebra, decomposing as

: $\backslash operatorname\{QSym\}\; =\; \backslash bigoplus\_\{n\; \backslash ge\; 0\}\; \backslash operatorname\{QSym\}\_n,\; \backslash ,$

where $\backslash operatorname\{QSym\}\_n$ is the $R$-span of all quasisymmetric functions that are homogeneous of degree $n$. Two natural bases for $\backslash operatorname\{QSym\}\_n$ are the monomial basis $\backslash \{M\_\{\backslash alpha\}\; \backslash \}$ and the fundamental basis $\backslash \{F\_\{\backslash alpha\}\; \backslash \}$ indexed by compositions $\backslash alpha\; =\; (\backslash alpha\_1,\; \backslash alpha\_2,\; \backslash ldots\; ,\; \backslash alpha\_k)$ of $n$, denoted $\backslash alpha\; \backslash vDash\; n$. The monomial basis consists of $M\_0=1$ and all formal power series

:

The fundamental basis consists $F\_0=1$ and all formal power series

: $F\_\backslash alpha\; =\; \backslash sum\_\{\backslash alpha\; \backslash succeq\; \backslash beta\}\; M\_\backslash beta,\; \backslash ,$

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

: $\backslash operatorname\{QSym\}\_n\; =\; \backslash operatorname\{span\}\_\{\backslash mathbb\{Q\}\}\; \backslash \{\; M\_\backslash alpha\; \backslash mid\; \backslash alpha\; \backslash vDash\; n\; \backslash \}\; =\; \backslash operatorname\{span\}\_\{\backslash mathbb\{Q\}\}\; \backslash \{\; F\_\backslash alpha\; \backslash mid\; \backslash alpha\; \backslash vDash\; n\; \backslash \}.\; \backslash ,$

Then one can define the algebra of symmetric functions $\backslash Lambda\; =\; \backslash Lambda\; \_0\; \backslash oplus\; \backslash Lambda\; \_1\; \backslash oplus\; \backslash cdots$ as the subalgebra of QSym spanned by the monomial symmetric functions $m\_0=1$ and all formal power series $m\_\backslash lambda\; =\; \backslash sum\; M\_\backslash alpha,$ where the sum is over all compositions $\backslash alpha$ which rearrange to the integer partition $\backslash lambda$. Moreover, we have $\backslash Lambda\_n\; =\; \backslash Lambda\; \backslash cap\; \backslash operatorname\{QSym\}\_n$. For example, $F\_\{(1,2)\}=M\_\{(1,2)\}+M\_\{(1,1,1)\}$ and $m\_\{(2,1)\}=M\_\{(2,1)\}+M\_\{(1,2)\}.$

Other important bases for quasisymmetric functions include the basis of quasisymmetric Schur functions,{{citation|first1=J. |last1=Haglund|first2= K. |last2=Luoto|first3=S. |last3=Mason |first4= S. |last4=van Willigenburg | author4-link=Stephanie van Willigenburg |title= Quasisymmetric Schur functions|journal=Journal of Combinatorial Theory | series=Series A|volume= 118 |year=2011|pages= 463–490|doi=10.1016/j.jcta.2009.11.002|issue=2|arxiv=0810.2489|doi-access=free}} the "type I" and "type II" quasisymmetric power sums,{{citation|first1=Christina |last1=Ballantine|first2=Zajj |last2=Daughtery|first3=Angela |last3=Hicks |first4=Sarah |last4=Mason |first5=Elizabeth |last5=Niese |title=On Quasisymmetric Power Sums|journal=Journal of Combinatorial Theory | series=Series A|volume= 175 |year=2020|page=105273 |arxiv=1710.11613|doi=10.1016/j.jcta.2020.105273|s2cid=51775423 }} and bases related to enumeration in matroids.{{citation|first=K. |last=Luoto|title=A matroid-friendly basis for the quasisymmetric functions|journal=Journal of Combinatorial Theory | series=Series A|volume= 115 |year=2008|pages= 777–798|bibcode=2007arXiv0704.0836L|arxiv=0704.0836|doi=10.1016/j.jcta.2007.10.003|issue=5|doi-access=free}}{{citation|first1=L. |last1=Billera| authorlink1=Louis Billera | first2=N. |last2=Jia |first3= V. |last3=Reiner|title= A quasisymmetric function for matroids|journal= European Journal of Combinatorics|volume= 30 |year=2009|pages= 1727–1757|bibcode=2006math......6646B|arxiv=math/0606646|doi=10.1016/j.ejc.2008.12.007|doi-access=free|issue=8}}

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,

Stanley, Richard P. Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, 1972.

Gessel, Ira. Multipartite P-partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983), 289–317, Contemp. Math., 34, Amer. Math. Soc., Providence, RI, 1984.

permutations,{{citation|

last1=Gessel|first1=Ira|author1-link=Ira Gessel|last2= Reutenauer|first2= Christophe|title=Counting permutations with given cycle structure and descent set |journal=Journal of Combinatorial Theory |series=Series A |volume=64 |year=1993|pages= 189–215|issue= 2|

doi=10.1016/0097-3165(93)90095-P|doi-access=free}}{{citation|last1= Shareshian|first1= John|last2= Wachs|first2= Michelle L.|author2-link= Michelle L. Wachs |title=$q$-Eulerian polynomials: excedance number and major index|journal= Electron. Res. Announc. Amer. Math. Soc. |volume=13 |year=2007|pages= 33–45|doi= 10.1090/S1079-6762-07-00172-2|issue= 4|arxiv= math/0608274|s2cid= 15394306}}{{citation|last1= Shareshian|first1= John|last2= Wachs|first2= Michelle L.|author2-link= Michelle L. Wachs |title= Eulerian quasisymmetric functions|journal=Advances in Mathematics |volume=225 |issue=6 |year= 2010 |pages=2921–2966|doi= 10.1016/j.aim.2010.05.009|doi-access=free|arxiv= 0812.0764}}

{{citation|last=Hyatt|first= Matthew|title=Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups|arxiv=1007.0459|bibcode=2010arXiv1007.0459H|journal=Advances in Applied Mathematics |volume=48 |year=2012 |issue= 3|pages=465–505 |doi=10.1016/j.aam.2011.11.005|s2cid= 119118644}}

tableaux,{{citation|last=Stanley|first=Richard P.|authorlink=Richard P. Stanley|title=On the number of reduced decompositions of elements of Coxeter groups|journal= European Journal of Combinatorics |volume= 5 |year=1984 |pages= 359–372 |issue= 4 |doi=10.1016/s0195-6698(84)80039-6|doi-access=free}} chains of posets,{{citation|last=Ehrenborg|first= Richard|author-link=Richard Ehrenborg |title=On posets and Hopf algebras|journal= Advances in Mathematics |volume= 119

|year=1996|pages= 1–25|issue= 1|doi=10.1006/aima.1996.0026|doi-access=free}} reduced decompositions in finite Coxeter groups (via Stanley symmetric functions), and parking functions.Haglund, James; The q,t-Catalan numbers and the space of diagonal harmonics.

University Lecture Series, 41. American Mathematical Society, Providence, RI, 2008. viii+167 pp. {{ISBN|978-0-8218-4411-3}}; 0-8218-4411-3 In symmetric function theory and representation theory, applications include the study of Schubert polynomials,{{citation|last1=Billey|first1= Sara C.|last2=Jockusch|first2=William|last3= Stanley|first3= Richard P.|author3-link=Richard P. Stanley|title=Some combinatorial properties of Schubert polynomials|journal=Journal of Algebraic Combinatorics |volume=2 |year=1993|pages= 345–374|issue= 4|doi=10.1023/A:1022419800503|url=https://deepblue.lib.umich.edu/bitstream/2027.42/46173/1/10801_2004_Article_415600.pdf|doi-access=free}}{{citation|last1=Fomin|first1=Sergey|author1-link=Sergey Fomin|last2=Stanley|first2= Richard P. | author2-link=Richard P. Stanley |title=Schubert polynomials and the nil-Coxeter algebra|journal= Advances in Mathematics |volume=103 |year=1994|pages= 196–207|issue= 2|doi=10.1006/aima.1994.1009|doi-access=free}} Macdonald polynomials,{{citation|last=Assaf|first= Sami|title=Dual Equivalence Graphs I: A combinatorial proof of LLT and Macdonald positivity|year= 2010|arxiv=1005.3759|bibcode = 2010arXiv1005.3759A }}

Hecke algebras,{{citation|last1=Duchamp|first1= Gérard|last2= Krob|first2= Daniel|last3= Leclerc|first3= Bernard|last4= Thibon|first4= Jean-Yves|title= Fonctions quasi-symétriques, fonctions symétriques non commutatives et algèbres de Hecke à $q=0$|journal= C. R. Acad. Sci. Paris |series=Sér. I Math. |volume=322 |year=1996|pages= 107–112|issue= 2}} and Kazhdan–Lusztig polynomials.{{citation |last1=Billera |first1= Louis J. |authorlink1=Louis Billera |last2= Brenti |first2= Francesco |year=2011 |title= Quasisymmetric functions and Kazhdan–Lusztig polynomials| arxiv=0710.3965 |mode=cs2|journal = Israel Journal of Mathematics|volume = 184|pages = 317–348|doi = 10.1007/s11856-011-0070-0|doi-access=free}} 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.{{citation|last1=Aguiar|first1= Marcelo|last2=Bergeron|first2= Nantel|last3= Sottile|first3= Frank |title=Combinatorial Hopf algebras and generalized Dehn–Sommerville relations|journal= Compositio Mathematica |volume=142 |year=2006|pages= 1–30 |issue= 1|bibcode=2003math.....10016A|arxiv=math/0310016|doi=10.1112/S0010437X0500165X|s2cid= 2635356}}

Hence any such Hopf algebra has a morphism to the ring of quasisymmetric functions.

One example of this is the peak algebra.{{citation|last=Stembridge|first= John R. |title=Enriched P-partitions|journal= Trans. Amer. Math. Soc. |volume=349|year=1997|pages= 763–788 |issue=2|doi=10.1090/S0002-9947-97-01804-7|doi-access=free}}

The Malvenuto–Reutenauer algebra{{citation|last1=Malvenuto|first1=Clauda|last2= Reutenauer|first2= Christophe |title=Duality between quasi-symmetric functions and the Solomon descent algebra|journal= Journal of Algebra |volume=177 |year=1995 |pages=967–982 |issue= 3|doi=10.1006/jabr.1995.1336|doi-access=free}} is a Hopf algebra based on permutations that relates the rings of symmetric functions, quasisymmetric functions, and noncommutative symmetric functions, (denoted Sym, QSym, and NSym respectively), as depicted the following commutative diagram. The duality between QSym and NSym mentioned above is reflected in the main diagonal of this diagram.

Image:QSymDiagram.png

Many related Hopf algebras were constructed from Hopf monoids in the category of species by Aguiar and Majahan.Aguiar, Marcelo; Mahajan, Swapneel Monoidal Functors, Species and Hopf Algebras CRM Monograph Series, no. 29. American Mathematical Society, Providence, RI, 2010.

One can also construct the ring of quasisymmetric functions in noncommuting variables.Hivert, Florent, Ph.D. Thesis, Marne-la-Vallée{{citation|last1=Bergeron|first1= Nantel|last2= Zabrocki|first2= Mike|title= The Hopf algebras of symmetric functions and quasi-symmetric functions in non-commutative variables are free and co-free|journal= Journal of Algebra and Its Applications |volume= 8 |year=2009|pages= 581–600|issue= 4|doi=10.1142/S0219498809003485|arxiv=math/0509265|s2cid= 18601994}}

{{Reflist}}

• [http://www.birs.ca/events/2010/5-day-workshops/10w5031 BIRS Workshop on Quasisymmetric Functions]

Category:Algebraic combinatorics

Category:Types of functions

Category:Polynomials

*

Category:Ring theory

Category:Hopf algebras