View source for Quasi-symmetric function

{{MSC|05E05}}{{TEX|done}}

''quasi-symmetric polynomial (in combinatorics)''

Let $X$ be a finite or infinite set (of variables) and consider the ring of polynomials $R[X]$ and the ring of power series $R[[X]]$ over a [[commutative ring]] $R$ with unit element in the commuting variables from $X$. A polynomial or power series $f(X) \in R[[X]]$ is called ''symmetric'' if for any two finite sequences of indeterminates $X_1,\ldots,X_n$ and $Y_1,\ldots,Y_n$ from $X$ and any sequence of exponents $i_1,\ldots,i_n \in \mathbf{N}$, the coefficients in $f$ of $X_1^{i_1} \cdots X_n^{i_n}$ and $Y_1^{i_1} \cdots Y_n^{i_n}$ are the same.

Quasi-symmetric formal power series are a generalization introduced by I.M. Gessel, [[#References|[a2]]], in connection with the combinatorics of plane partitions and descent sets of permutations [[#References|[a3]]]. This time one takes a totally ordered set of indeterminates, e.g. $V = \{V_1,V_2,\ldots\}$, with the ordering that of the natural numbers, and the condition is that the coefficients of $X_1^{i_1} \cdots X_n^{i_n}$ and $Y_1^{i_1} \cdots Y_n^{i_n}$ are equal for all totally ordered sets of indeterminates $X_1 < \ldots < X_n$ and $Y_1 < \ldots < Y_n$. For example,
$$
X_1 X_2^2 + X_1 X_3^2 + X_2 X_3^2
$$
is a quasi-symmetric polynomial in three variables that is not symmetric.

Products and sums of quasi-symmetric polynomials and power series are again quasi-symmetric (obviously), and thus one has, for example, the ring of quasi-symmetric power series
$$
\widehat{ \mathbf{Q}^{\mathrm{sym}}_{\mathbf{Z}}(X)) }
$$
in countably many commuting variables over the integers and its subring
$$
\mathbf{Q}^{\mathrm{sym}}_{\mathbf{Z}}(X))
$$
of quasi-symmetric polynomials in finite of countably many indeterminates, which are the quasi-symmetric power series of bounded degree.

Given a word $w=[a_1,\ldots,a_n]$ over $\mathbf{N}$, also called a composition in this context, consider the quasi-monomial function
$$
M_w = \sum_{Y_1 < \cdots < Y_n} Y_1^{a_1}\cdots Y_n^{a_n}
$$
defined by $w$. These form a basis over the integers of $\mathbf{Q}^{\mathrm{sym}}_{\mathbf{Z}}(X))$.

The algebra of quasi-symmetric functions is dual to the [[Leibniz–Hopf algebra]], or, equivalently to the Solomon descent algebra, more precisely, to the direct sum
$$
\mathcal{D} = \bigoplus_n D(S_n)
$$
of the Solomon descent algebras $D(S_n)$ of the [[symmetric group]]s (cf. also [[Symmetric group|Symmetric group]]), [[#References|[a5]]], with a new multiplication over which the direct sum of the original multiplications is distributive. See [[#References|[a1]]], [[#References|[a4]]].

The algebra of quasi-symmetric functions in countably many indeterminates over the integers, $\mathbf{Q}^{\mathrm{sym}}_{\mathbf{Z}}(X))$, is a free polynomial algebra over the integers, [[#References|[a6]]].

There is a completely different notion in the theory of functions of a complex variable that also goes by the name quasi-symmetric function; cf., e.g., [[#References|[a7]]] and [[Quasi-symmetric function of a complex variable]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  I.M. Gel'fand,   D. Krob,   A. Lascoux,   B. Leclerc,   V.S. Retakh,   J.-Y. Thibon,   "Noncommutative symmetric functions"  ''Adv. Math.'' , '''112'''  (1995)  pp. 218–348</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  I.M. Gessel,   "Multipartite $P$-partitions and inner product of skew Schur functions"  ''Contemp. Math.'' , '''34'''  (1984)  pp. 289–301</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  I.M. Gessel,   Ch. Reutenauer,   "Counting permutations with given cycle-structure and descent set"  ''J. Combin. Th. A'' , '''64'''  (1993)  pp. 189–215</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Malvenuto,   Ch. Reutenauer,   "Duality between quasi-symmetric functions and the Solomon descent algebra"  ''J. Algebra'' , '''177'''  (1994)  pp. 967–982</TD></TR>
<TR><TD valign="top">[a5]</TD> <TD valign="top">  L. Solomon,   "A Mackey formula in the group ring of a Coxeter group"  ''J. Algebra'' , '''41'''  (1976)  pp. 255–268</TD></TR>
<TR><TD valign="top">[a6]</TD> <TD valign="top">  M. Hazewinkel,   "The algebra of quasi-symmetric functions is free over the integers"  ''Preprint CWI (Amsterdam) and ICTP (Trieste)''  (1999)</TD></TR>
<TR><TD valign="top">[a7]</TD> <TD valign="top">  M. Chuaqui,   B. Osgood,   "Weak Schwarzians, bounded hyperbolic distortion, and smooth quasi-symmetric functions"  ''J. d'Anal. Math.'' , '''68'''  (1996)  pp. 209–252</TD></TR>
</table>