Namespaces
Variants
Actions

Difference between revisions of "Quasi-symmetric function"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (→‎References: + ZBL link)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
 +
{{MSC|05E05}}{{TEX|done}}
 +
 
''quasi-symmetric polynomial (in combinatorics)''
 
''quasi-symmetric polynomial (in combinatorics)''
  
Line 19: Line 21:
 
of quasi-symmetric polynomials in finite of countably many indeterminates, which are the quasi-symmetric power series of bounded degree.
 
of quasi-symmetric polynomials in finite of countably many indeterminates, which are the quasi-symmetric power series of bounded degree.
  
Given a word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q120/q120060/q12006022.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q120/q120060/q12006023.png" />, also called a composition in this context, consider the quasi-monomial function
+
Given a word $w=[a_1,\ldots,a_n]$ over $\mathbf{N}$, also called a composition in this context, consider the quasi-monomial function
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q120/q120060/q12006024.png" /></td> </tr></table>
+
M_w = \sum_{Y_1 < \cdots < Y_n} Y_1^{a_1}\cdots Y_n^{a_n}
 
+
$$
defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q120/q120060/q12006025.png" />. These form a basis over the integers of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q120/q120060/q12006026.png" />.
+
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
 
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]]].
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q120/q120060/q12006027.png" /></td> </tr></table>
+
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]]].
  
of the Solomon descent algebras <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q120/q120060/q12006028.png" /> of the symmetric groups (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]]].
+
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]].
 
 
The algebra of quasi-symmetric functions in countably many indeterminates over the integers, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q120/q120060/q12006029.png" />, 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]]].
 
  
 
====References====
 
====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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q120/q120060/q12006030.png" />-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>
+
<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>
{{TEX|part}}
+
<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 {{ZBL|0838.05100}}</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>

Latest revision as of 13:51, 20 March 2023

2020 Mathematics Subject Classification: Primary: 05E05 [MSN][ZBL]

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, [a2], in connection with the combinatorics of plane partitions and descent sets of permutations [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 groups (cf. also Symmetric group), [a5], with a new multiplication over which the direct sum of the original multiplications is distributive. See [a1], [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, [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., [a7] and Quasi-symmetric function of a complex variable.

References

[a1] 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
[a2] I.M. Gessel, "Multipartite $P$-partitions and inner product of skew Schur functions" Contemp. Math. , 34 (1984) pp. 289–301
[a3] I.M. Gessel, Ch. Reutenauer, "Counting permutations with given cycle-structure and descent set" J. Combin. Th. A , 64 (1993) pp. 189–215
[a4] C. Malvenuto, Ch. Reutenauer, "Duality between quasi-symmetric functions and the Solomon descent algebra" J. Algebra , 177 (1994) pp. 967–982 Zbl 0838.05100
[a5] L. Solomon, "A Mackey formula in the group ring of a Coxeter group" J. Algebra , 41 (1976) pp. 255–268
[a6] M. Hazewinkel, "The algebra of quasi-symmetric functions is free over the integers" Preprint CWI (Amsterdam) and ICTP (Trieste) (1999)
[a7] M. Chuaqui, B. Osgood, "Weak Schwarzians, bounded hyperbolic distortion, and smooth quasi-symmetric functions" J. d'Anal. Math. , 68 (1996) pp. 209–252
How to Cite This Entry:
Quasi-symmetric function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Quasi-symmetric_function&oldid=43036
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article