40.03.08 · combinatorics / symmetric-functions-rsk

Quasisymmetric Functions and Gessel's Fundamental Basis

shipped3 tiersLean: none

Anchor (Master): Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.19 and §7.23 (quasisymmetric functions, the fundamental basis, Schur expansion into fundamentals by descent of standard Young tableaux); Gessel 1984 *Multipartite P-partitions and inner products of skew Schur functions* (Contemporary Mathematics 34, 289-301); Malvenuto-Reutenauer 1995 *J. Algebra* 177 (QSym and NSym as dual Hopf algebras, the descent-algebra duality); Aguiar-Bergeron-Sottile 2006 *Compositio Math.* 142 (QSym as the terminal object in the category of combinatorial Hopf algebras); Stanley 1995 *Adv. Math.* 111 (the chromatic symmetric function)

Intuition Beginner

A symmetric function does not care which variables carry its terms: $x_{1}^{2} x_{2}$ and $x_{3}^{2} x_{7}$ count the same. A quasisymmetric function relaxes that demand. It still does not care about the actual names of the variables, but it does insist on their order. It treats $x_{1}^{2} x_{2}$ and $x_{3}^{2} x_{7}$ as the same — in both, a squared variable comes before a plain one, reading left to right — yet it is free to treat $x_{1} x_{2}^{2}$ differently, because there the plain variable comes first. The only data a quasisymmetric function reads off a term is the run of exponents in increasing index order.

Why loosen the rule this way? Because many counting problems carry a built-in order that symmetric functions throw away. When you label the slots of a partly-ordered structure with numbers and ask how often each pattern of "equal here, strictly larger there" occurs, the answer remembers where the strict jumps sat. That memory is exactly a list of exponents read in order, and exactly what quasisymmetric functions keep.

The pay-off is a perfect home for the P-partition counts of the previous chapter. Each way of laying a poset out in a line contributes one simple building block, and the building blocks are indexed not by partitions but by compositions — ordered lists of positive numbers that add to $n$ . There are two natural families of blocks, and Gessel's family, the fundamental one, is the family in which P-partition counts come out clean.

Visual Beginner

A composition of $n$ is an ordered list of positive parts summing to $n$ ; order matters, so $(2, 1)$ and $(1, 2)$ are different. The table shows the two building-block families in three increasing variables $x_{1}, x_{2}, x_{3}$ , for the composition $(2, 1)$ of $3$ .

family	symbol	what it collects (composition $(2, 1)$ )
monomial	$M$	$x_{1}^{2} x_{2} + x_{1}^{2} x_{3} + x_{2}^{2} x_{3}$
fundamental	$F$	the $M$ for $(2, 1)$ plus the $M$ for the finer $(1, 1, 1)$

The monomial block $M_{(2, 1)}$ collects every term where one variable is squared and a strictly later variable is plain. The fundamental block $F_{(2, 1)}$ is more generous: it also throws in the terms where the parts get split finer, here the all-plain terms $x_{i} x_{j} x_{k}$ with $i < j < k$ . "Finer" means breaking a part into smaller pieces while keeping the running totals; that is the refinement relation, and it is the rule that turns monomial blocks into fundamental ones.

Worked example Beginner

Work in three variables $x_{1}, x_{2}, x_{3}$ and build the blocks for the compositions of $3$ , then watch a refinement appear. The compositions of $3$ are $(3)$ , $(2, 1)$ , $(1, 2)$ , and $(1, 1, 1)$ .

Step 1. Monomial blocks. $M_{(3)} = x_{1}^{3} + x_{2}^{3} + x_{3}^{3}$ , one cube per variable. $M_{(2, 1)} = x_{1}^{2} x_{2} + x_{1}^{2} x_{3} + x_{2}^{2} x_{3}$ : a square then a strictly later plain. $M_{(1, 2)} = x_{1} x_{2}^{2} + x_{1} x_{3}^{2} + x_{2} x_{3}^{2}$ : a plain then a strictly later square. $M_{(1, 1, 1)} = x_{1} x_{2} x_{3}$ , the one term with three strictly increasing plain variables.

Step 2. A fundamental block. Refining $(2, 1)$ means splitting its parts into smaller positive pieces with the same running totals. The only finer composition is $(1, 1, 1)$ . So $F_{(2, 1)} = M_{(2, 1)} + M_{(1, 1, 1)}$ .

Step 3. Write it out. $F_{(2, 1)} = (x_{1}^{2} x_{2} + x_{1}^{2} x_{3} + x_{2}^{2} x_{3}) + x_{1} x_{2} x_{3}$ .

Step 4. Check the coarsest case. The composition $(3)$ has no finer pieces other than itself when we only allow splitting where the running total is reached; in fact every composition refines $(3)$ , so $F_{(3)} = M_{(3)} + M_{(2, 1)} + M_{(1, 2)} + M_{(1, 1, 1)}$ , the sum of all four monomial blocks of degree $3$ .

What this tells us: the fundamental block $F_{α}$ is a bundle of monomial blocks, one for $α$ and one for each finer composition. The two families say the same total information, and the recipe for converting is "sum over refinements". Gessel found that P-partition counts are sums of these fundamental bundles, which is why the bundle, not the bare monomial, is the natural unit.

Check your understanding Beginner

Formal definition Intermediate+

Fix a commutative base ring, by default $Z$ , and work in the ring of formal power series of bounded degree in countably many variables $x_{1}, x_{2}, \dots$ , following the inverse-limit construction of 40.03.01. A composition of $n$ is a sequence $α = (α_{1}, \dots, α_{k})$ of positive integers with $∣ α ∣ = \sum_{i} α_{i} = n$ and length $ℓ (α) = k$ ; write $α ⊨ n$ . Compositions of $n$ are in bijection with subsets of $[n - 1] = {1, \dots, n - 1}$ via the partial-sum set $S (α) = {α_{1}, α_{1} + α_{2}, \dots, α_{1} + \dots + α_{k - 1}}$ ; the inverse sends $S = {s_{1} < \dots < s_{k - 1}}$ to $co (S) = (s_{1}, s_{2} - s_{1}, \dots, n - s_{k - 1})$ .

Definition (quasisymmetric function). A formal power series $f$ of bounded degree is quasisymmetric if for every composition $α = (α_{1}, \dots, α_{k})$ and every pair of strictly increasing index sequences $i_{1} < \dots < i_{k}$ and $j_{1} < \dots < j_{k}$ , the coefficients of $x_{i_{1}}^{α_{1}} \dots x_{i_{k}}^{α_{k}}$ and $x_{j_{1}}^{α_{1}} \dots x_{j_{k}}^{α_{k}}$ in $f$ are equal. The quasisymmetric functions form a graded subring $QSym = ⨁_{n \geq 0} QSym^{n}$ of the power-series ring.

Definition (the two bases). For each composition $α = (α_{1}, \dots, α_{k}) ⊨ n$ define, as elements of $QSym^{n}$ :

Monomial quasisymmetric $M_{α} = \sum_{i_{1} < i_{2} < \dots < i_{k}} x_{i_{1}}^{α_{1}} x_{i_{2}}^{α_{2}} \dots x_{i_{k}}^{α_{k}}$ , with $M_{()} = 1$ .
Fundamental (Gessel) $F_{α} = \sum_{β ⪯ α} M_{β}$ , the sum over all compositions $β$ of $n$ that refine $α$ (written $β ⪯ α$ ): $β$ refines $α$ when $α$ is obtained from $β$ by merging adjacent parts, equivalently $S (α) \subseteq S (β)$ .

The refinement relation makes the compositions of $n$ a Boolean lattice through $α \mapsto S (α)$ : $β ⪯ α ⟺ S (α) \subseteq S (β)$ , with the all-ones composition $(1^{n})$ the finest (subset $[n - 1]$ ) and the single part $(n)$ the coarsest (empty subset). The set ${M_{α} : α ⊨ n}$ is a $Z$ -basis of $QSym^{n}$ by construction. The transition $F_{α} = \sum_{β ⪯ α} M_{β}$ is unitriangular over this Boolean lattice with all coefficients $1$ , so ${F_{α} : α ⊨ n}$ is also a $Z$ -basis, with inverse $M_{α} = \sum_{β ⪯ α} (- 1)^{ℓ (β) - ℓ (α)} F_{β}$ by Möbius inversion on the Boolean lattice.

Definition (the inclusion $Λ \subset QSym$ ). Every symmetric function is quasisymmetric, so $Λ \subset QSym$ as graded rings. On the monomial bases the inclusion reads $m_{λ} = \sum_{α} M_{α}$ , the sum over all compositions $α$ that rearrange the partition $λ$ . The notation $M_{α}$ , $F_{α}$ , $co (\cdot)$ , $Des (\cdot)$ , $⪯$ , $α ⊨ n$ is introduced here and recorded in _meta/NOTATION.md; the symbols $⟨, ⟩$ , $z_{λ}$ , $p_{λ}$ carry over from 40.03.01.

Counterexamples to common slips Intermediate+

" $M_{(1, 2)}$ and $M_{(2, 1)}$ are the same because they involve the same multiset of exponents." They are different basis elements: $M_{(2, 1)}$ has a square in the earlier index and $M_{(1, 2)}$ a square in the later index. They merge only after symmetrising; their sum $M_{(2, 1)} + M_{(1, 2)}$ , together with the diagonal-free condition handled by the partition, is what reassembles the symmetric $m_{(2, 1)}$ .
" $F_{α}$ refines into coarser compositions." The sum is over compositions $β$ that refine $α$ (finer than $α$ , with $S (α) \subseteq S (β)$ ), not coarser. The coarsest composition $(n)$ has $F_{(n)} = \sum_{β ⊨ n} M_{β}$ , the sum of all monomial blocks, while the finest $(1^{n})$ has $F_{(1^{n})} = M_{(1^{n})}$ alone.
"Quasisymmetric functions in $n$ variables are quasisymmetric polynomials, full stop." As with $Λ$ , the ring $QSym$ is the stable inverse limit in countably many variables; in $n$ variables a composition of length exceeding $n$ gives $M_{α} = 0$ , a spurious relation that disappears in the limit.

Key theorem with proof Intermediate+

The signature theorem is Gessel's, the reason quasisymmetric functions exist: the generating function of a labelled poset's $(P, ω)$ -partitions is quasisymmetric, and it expands without remainder into fundamental functions, one per linear extension, indexed by the descent composition ^{[Gessel 1984]}.

For a labelled poset $(P, ω)$ with $∣ P ∣ = p$ as in 40.01.04, let $A (P, ω)$ be its set of $(P, ω)$ -partitions $σ : P \to N$ , and form the multivariate generating function $K_{P, ω} = \sum_{σ \in A (P, ω)} \prod_{t \in P} x_{σ (t) + 1}$ , recording each element's value as a variable index rather than only a power of $q$ . For a linear extension, i.e. a permutation $σ = σ_{1} \dots σ_{p}$ of the labels listing $P$ in an order refining $<_{P}$ , the **descent set** is $Des (σ) = {i \in [p - 1] : σ_{i} > σ_{i + 1}}$ and the descent composition is $co (σ) = co (Des (σ))$ , the composition of $p$ with that partial-sum set.

Theorem (fundamental expansion of $(P, ω)$ -partition generating functions). The series $K_{P, ω}$ is quasisymmetric, and $$ K_{P,\omega} ;=; \sum_{\sigma \in \mathcal{L}(P,\omega)} F_{\mathrm{co}(\sigma)}, $$ the sum over the linear extensions $σ$ of $(P, ω)$ , where $F_{co (σ)} \in QSym^{p}$ is Gessel's fundamental function of the descent composition. ^{[Stanley §7.19]}

Proof. The fundamental theorem of $(P, ω)$ -partitions, proved in 40.01.04, decomposes $A (P, ω)$ as the disjoint union $⨆_{σ \in L (P, ω)} A (σ, ω)$ over linear extensions, where $A (σ, ω)$ consists of the maps weakly decreasing along $σ$ and strictly decreasing at the descents of $σ$ . So $K_{P, ω} = \sum_{σ} K_{σ, ω}$ , and it suffices to compute $K_{σ, ω}$ for a single chain with descent set $D = Des (σ) \subseteq [p - 1]$ .

A map in $A (σ, ω)$ is a weakly decreasing assignment of values $a_{1} \geq a_{2} \geq \dots \geq a_{p} \geq 0$ to the chain, strict at each $i \in D$ , i.e. $a_{i} > a_{i + 1}$ for $i \in D$ and $a_{i} \geq a_{i + 1}$ otherwise. Reading the distinct values in decreasing order picks out an increasing sequence of variable indices $i_{1} < i_{2} < \dots$ carrying them, and the run lengths form precisely a composition $β$ of $p$ with $S (β) \supseteq D$ , that is $β ⪯ co (D)$ . Each such $β$ contributes exactly $M_{β}$ as the indices range over all strictly increasing choices. Summing, $K_{σ, ω} = \sum_{β ⪯ co (D)} M_{β} = F_{co (D)} = F_{co (σ)}$ . The series is quasisymmetric because each $M_{β}$ is. Summing over linear extensions gives the claimed expansion. $□$

Bridge. This expansion is the foundational reason quasisymmetric functions are the right ambient ring for ordered enumeration: it builds toward the symmetric-function world by exhibiting $K_{P, ω}$ as an honest element of $QSym$ whose coefficients are linear extensions counted by descent, and it appears again in 40.03.02 as the Schur expansion $s_{λ} = \sum_{T} F_{co (T)}$ , which is exactly this theorem applied to the poset whose linear extensions are the standard Young tableaux of shape $λ$ . This is exactly the $q$ -refinement of the chain factorisation $q^{maj (σ)} / \prod (1 - q^{i})$ of 40.01.04: setting $x_{i} = q^{i - 1}$ in $F_{co (σ)}$ recovers $q^{maj (σ)} / \prod_{i = 1}^{p} (1 - q^{i})$ , so the principal specialisation of the fundamental basis is the major-index chain generating function. The central insight is that the descent statistic on permutations — the engine of the Eulerian polynomials in 40.01.05 — is the same datum that indexes the fundamental basis, so descent combinatorics and the basis of $QSym$ are one object. Putting these together, P-partition theory, the descent statistic, and the fundamental basis are three views of a single decomposition of the order cone.

Exercises Intermediate+

Exercise 6 (hard, symbolic).

Prove that the principal specialisation $x_{i} \mapsto q^{i - 1}$ sends $F_{α}$ , for $α ⊨ p$ with descent set $S = S (α) \subseteq [p - 1]$ , to $\frac{q ^{\sum_{i \in S} i}}{( 1 - q ) ( 1 - q ^{2} ) \dots ( 1 - q ^{p} )}$ .

Hint

Specialise $M_{β}$ first: $M_{β} (1, q, q^{2}, \dots) = \sum_{0 \leq i_{1} < \dots < i_{k}} q^{\sum_{j} (i_{j}) β_{j}}$ . Sum over $β ⪯ α$ , or recognise the result as the major-index generating function for the chain with descent set $S$ .

Answer

A map in $A (σ, ω)$ for the chain with descent set $S$ is a weak chain of values $a_{1} \geq \dots \geq a_{p} \geq 0$ , strict at $S$ . Substitute $b_{i} = a_{i} - # {j \in S : j \geq i}$ to absorb the forced strict drops; then $b_{1} \geq b_{2} \geq \dots \geq b_{p} \geq 0$ is an arbitrary partition into at most $p$ parts, and $\sum_{i} a_{i} = \sum_{i} b_{i} + \sum_{i \in S} i$ . The specialisation $x_{a + 1} \mapsto q^{a}$ weights a partition by $q^{\sum a_{i}}$ , so $F_{α} (1, q, q^{2}, \dots) = q^{\sum_{i \in S} i} \sum_{b} q^{\sum b_{i}}$ , and the generating function for partitions into at most $p$ parts is $\prod_{i = 1}^{p} (1 - q^{i})^{- 1}$ . Hence $F_{α} (1, q, q^{2}, \dots) = q^{maj} / \prod_{i = 1}^{p} (1 - q^{i})$ with $maj = \sum_{i \in S} i$ , matching the chain factor of 40.01.04. Rubric: full credit for the strict-drop substitution, the identification with partitions into $\leq p$ parts, and the major-index exponent $\sum_{i \in S} i$ .

Exercise 7 (hard, symbolic).

Show that the product $M_{(1)} \cdot M_{(1)}$ in $QSym$ equals $2 M_{(1, 1)} + M_{(2)}$ , and contrast with the symmetric-function product $p_{1}^{2} = 2 m_{(1, 1)} + m_{(2)}$ to which it restricts.

Hint

$M_{(1)} = \sum_{i} x_{i} = p_{1}$ . Square the sum and sort the resulting terms $x_{i} x_{j}$ by whether $i < j$ , $i > j$ , or $i = j$ .

Answer

$M_{(1)} = \sum_{i} x_{i}$ , so $M_{(1)}^{2} = \sum_{i, j} x_{i} x_{j} = \sum_{i < j} x_{i} x_{j} + \sum_{i > j} x_{i} x_{j} + \sum_{i} x_{i}^{2}$ . The first sum is $M_{(1, 1)} = \sum_{i < j} x_{i} x_{j}$ ; the second, after relabelling, is again $\sum_{i < j} x_{i} x_{j} = M_{(1, 1)}$ (a term $x_{i} x_{j}$ with $i > j$ has its smaller index second, but the quasisymmetric monomial block $M_{(1, 1)}$ already counts each unordered pair once via $i < j$ , and the two sums are equal as series); the third is $M_{(2)} = \sum_{i} x_{i}^{2}$ . So $M_{(1)}^{2} = 2 M_{(1, 1)} + M_{(2)}$ . Since $M_{(1)} = p_{1} \in Λ$ and $M_{(1, 1)}$ restricts to $m_{(1, 1)}$ , $M_{(2)}$ to $m_{(2)}$ , this is the image of $p_{1}^{2} = 2 m_{(1, 1)} + m_{(2)}$ under $Λ \subset QSym$ . Rubric: full credit for the term sort, the coefficient $2$ on $M_{(1, 1)}$ , and the restriction to the symmetric identity.

Advanced results Master

The fundamental basis carries the chapter's Schur theory into $QSym$ , and $QSym$ acquires a Hopf structure dual to the noncommutative symmetric functions, terminal among combinatorial Hopf algebras.

Theorem 1 (Schur expansion into fundamentals). For a partition $λ ⊢ n$ , $$ s_\lambda ;=; \sum_{T \in \mathrm{SYT}(\lambda)} F_{\mathrm{co}(T)}, $$ the sum over standard Young tableaux of shape $λ$ , where $co (T)$ is the descent composition of $T$ (the descent set of $T$ is ${i : i + 1 lies in a strictly lower row than i}$ ) ^{[Stanley §7.19]}. This is the Key-theorem expansion applied to the poset whose linear extensions are the standard tableaux of shape $λ$ ; restricting both sides to symmetric functions and collecting fundamentals recovers $s_{λ} = \sum_{μ} K_{λ μ} m_{μ}$ of 40.03.02, and the formula is the combinatorial certificate that $s_{λ} \in Λ \subset QSym$ despite each $F_{co (T)}$ being only quasisymmetric. A symmetric function is Schur-positive iff its fundamental expansion, grouped by the descent sets of standard tableaux, assembles into a nonnegative integer combination of these tableau sums.

Theorem 2 ( $QSym$ as a Hopf algebra dual to $NSym$ ). With the coproduct $Δ M_{α} = \sum_{α = β \cdot γ} M_{β} \otimes M_{γ}$ summed over the deconcatenations of $α$ (and counit the degree- $0$ projection), $QSym$ is a graded connected Hopf algebra. Its graded dual is the Hopf algebra $NSym$ of noncommutative symmetric functions; in each degree $n$ the dual pairing identifies $NSym_{n}$ with Solomon's descent algebra of $S_{n}$ , the fundamental basis $F_{α}$ pairing dually with the ribbon basis $R_{α}$ of $NSym$ ^{[Malvenuto-Reutenauer 1995]}. The inclusion $Λ ↪ QSym$ is dual to the abelianisation $NSym ↠ Λ$ , and both sit inside the Malvenuto-Reutenauer Hopf algebra of permutations as a quotient and a sub respectively.

Theorem 3 ( $QSym$ terminal among combinatorial Hopf algebras). A combinatorial Hopf algebra is a graded connected Hopf algebra $H$ equipped with a multiplicative linear functional (character) $ζ : H \to Z$ . For every such $(H, ζ)$ there is a unique morphism of combinatorial Hopf algebras $Ψ : (H, ζ) \to (QSym, ζ_{Q})$ , where $ζ_{Q}$ is the canonical character $M_{α} \mapsto [ℓ (α) \leq 1]$ ; thus $QSym$ is the terminal object in the category of combinatorial Hopf algebras ^{[Aguiar-Bergeron-Sottile 2006]}. The map $Ψ$ records, in the fundamental basis, the values of the character on the descent flags, so every combinatorial invariant satisfying a Hopf-algebra recursion lands in $QSym$ canonically; quasisymmetric functions are the universal home for such invariants.

Theorem 4 (chromatic symmetric function and its fundamental expansion). Stanley's chromatic symmetric function of a finite graph $G$ on vertex set $V$ is $X_{G} = \sum_{κ} \prod_{v \in V} x_{κ (v)}$ , summed over proper colourings $κ : V \to {1, 2, \dots}$ ; it is symmetric, refines the chromatic polynomial via $X_{G} (1^{k}) = χ_{G} (k)$ , and expands in the fundamental basis as $X_{G} = \sum_{π} F_{co (π)}$ over acyclic orientations weighted by descent data ^{[Stanley 1995]}. The Stanley-Stembridge conjecture asserts that for the incomparability graph of a $(3 + 1)$ -free poset, $X_{G}$ is $e$ -positive (a nonnegative combination of elementary symmetric functions); the weaker Schur-positivity is read through the fundamental expansion and the tableau grouping of Theorem 1, and was established by Gasharov.

Synthesis. Putting these together, the foundational reason $QSym$ governs ordered enumeration is that it is simultaneously the universal recipient of P-partition generating functions, the terminal combinatorial Hopf algebra, and the dual of the descent algebra, and these three faces force the fundamental basis to behave. The Key-theorem expansion $K_{P, ω} = \sum_{σ} F_{co (σ)}$ is exactly the structure that Theorem 1 specialises to the Schur case, where the linear extensions become standard Young tableaux and $Λ \subset QSym$ recaptures the Kostka unitriangularity of 40.03.02; the central insight is that the descent statistic indexing the fundamental basis is the same datum that defines Solomon's descent algebra, so the duality of Theorem 2 is dual to the descent combinatorics rather than parallel to it. The terminality of Theorem 3 generalises this from one poset to all combinatorial Hopf algebras: every invariant obeying a deconcatenation recursion, the chromatic symmetric function of Theorem 4 among them, factors uniquely through $QSym$ . The bridge is the principal specialisation $x_{i} = q^{i - 1}$ , which turns each $F_{co (σ)}$ into the major-index chain factor $q^{maj (σ)} / \prod (1 - q^{i})$ of 40.01.04 and ties the entire ring back to the Eulerian and descent statistics of 40.01.05; what the symmetric-function involution $ω$ does to $Λ$ , the composition-reversal and complementation operations do to $QSym$ , and the inclusion intertwines them.

Full proof set Master

Proposition 1 (the two bases and their refinement transition). Both ${M_{α} : α ⊨ n}$ and ${F_{α} : α ⊨ n}$ are $Z$ -bases of $QSym^{n}$ , related by $F_{α} = \sum_{β ⪯ α} M_{β}$ and $M_{α} = \sum_{β ⪯ α} (- 1)^{ℓ (β) - ℓ (α)} F_{β}$ .

Proof. A quasisymmetric function of degree $n$ is, by the defining condition, determined by one coefficient per composition $α ⊨ n$ (the common coefficient of $x_{i_{1}}^{α_{1}} \dots x_{i_{k}}^{α_{k}}$ ), and $M_{α}$ is the element with that coefficient $1$ and all others $0$ ; so ${M_{α}}$ is a $Z$ -basis of $QSym^{n}$ . The map $α \mapsto S (α) \subseteq [n - 1]$ is a bijection onto subsets carrying refinement $⪯$ to reverse inclusion: $β ⪯ α ⟺ S (α) \subseteq S (β)$ . The compositions of $n$ thus form a Boolean lattice, and $F_{α} = \sum_{β ⪯ α} M_{β}$ is the zeta-function sum over the order ideal below $α$ . The transition matrix from ${F_{α}}$ to ${M_{β}}$ is unitriangular with $1$ 's (it is the incidence matrix of $⪯$ , upper-unitriangular after a linear extension of the lattice), hence invertible over $Z$ ; so ${F_{α}}$ is a $Z$ -basis. The inverse is Möbius inversion on the Boolean lattice, where $μ (β, α) = (- 1)^{∣ S (β) ∣ - ∣ S (α) ∣} = (- 1)^{ℓ (β) - ℓ (α)}$ , giving $M_{α} = \sum_{β ⪯ α} (- 1)^{ℓ (β) - ℓ (α)} F_{β}$ . $□$

Proposition 2 (the inclusion $Λ \subset QSym$ and the monomial expansion). Every symmetric function is quasisymmetric, $Λ$ is a graded subring of $QSym$ , and $m_{λ} = \sum_{α} M_{α}$ summed over compositions $α$ whose underlying multiset of parts is $λ$ .

Proof. A symmetric function is invariant under every permutation of the variables, in particular under permutations preserving the order of any chosen increasing index sequence, so its coefficients satisfy the quasisymmetric condition; hence $Λ \subseteq QSym$ , and the inclusion respects products and grading. For the expansion, $m_{λ} = \sum x^{α}$ over distinct monomials $x^{α}$ whose exponent multiset is $λ$ . Group these monomials by the composition $α$ obtained from reading the nonzero exponents in increasing index order: each such composition $α$ rearranges $λ$ , and the monomials of $m_{λ}$ with that increasing-order exponent pattern are exactly the terms of $M_{α}$ . Distinct compositions give disjoint term sets, and every rearrangement of $λ$ occurs, so $m_{λ} = \sum_{α} M_{α}$ over compositions $α$ that rearrange $λ$ . $□$

Proposition 3 (Gessel's fundamental expansion of $K_{P, ω}$ ). For a labelled poset $(P, ω)$ with $p$ elements, $K_{P, ω} = \sum_{σ \in L (P, ω)} F_{co (σ)}$ , a quasisymmetric function.

Proof. By the fundamental theorem of $(P, ω)$ -partitions (40.01.04, Proposition 4 there), $A (P, ω) = ⨆_{σ \in L (P, ω)} A (σ, ω)$ , so $K_{P, ω} = \sum_{σ} K_{σ, ω}$ . Fix a linear extension $σ$ with descent set $D = Des (σ) \subseteq [p - 1]$ . The maps in $A (σ, ω)$ are the weak chains $a_{1} \geq \dots \geq a_{p} \geq 0$ with $a_{i} > a_{i + 1}$ for $i \in D$ . For such a map let $i_{1} < i_{2} < \dots < i_{r}$ be the distinct values used (as variable indices, after the shift $a \mapsto x_{a + 1}$ ), in decreasing order of value, and let $β_{j}$ be the number of chain positions taking the $j$ -th largest value. The strictness at $D$ forces a value change at each descent, so $D \subseteq S (β)$ , i.e. $β ⪯ co (D)$ ; conversely every $β ⪯ co (D)$ and every strictly increasing index choice arises once. The contribution of all maps with value-pattern $β$ is therefore $M_{β}$ , and $K_{σ, ω} = \sum_{β ⪯ co (D)} M_{β} = F_{co (σ)}$ . Each $M_{β}$ is quasisymmetric, hence so is $K_{P, ω}$ . $□$

Proposition 4 (Schur expansion into fundamentals). For $λ ⊢ n$ , $s_{λ} = \sum_{T \in SYT (λ)} F_{co (T)}$ , where $co (T)$ is the descent composition of $T$ .

Proof. The Schur function is the generating function $s_{λ} = \sum_{S} x^{S}$ over semistandard Young tableaux of shape $λ$ , weakly increasing along rows and strictly increasing down columns (40.03.02). This is the $(P, ω)$ -partition generating function $K_{P_{λ}, ω}$ for the poset $P_{λ}$ of cells of $λ$ with the column-strict labelling: an order-preserving filling is a column-strict tableau, and the strict/weak pattern matches the SSYT condition. The linear extensions of $(P_{λ}, ω)$ are exactly the standard Young tableaux $T$ of shape $λ$ (bijective fillings refining the cell order), and the descent set of the linear extension is the tableau descent set ${i : i + 1 in a strictly lower row than i}$ . Applying Proposition 3, $s_{λ} = K_{P_{λ}, ω} = \sum_{T \in SYT (λ)} F_{co (T)}$ . That the right side lies in $Λ$ , though each $F$ is only quasisymmetric, is the content of $s_{λ}$ being symmetric, established independently in 40.03.02. $□$

Connections Master

The ring $QSym$ is built on the symmetric-function ring $Λ$ of 40.03.01 as a strictly larger graded ring, $Λ \subset QSym$ , with the monomial symmetric functions $m_{λ}$ expanding as sums $\sum_{α} M_{α}$ over compositions rearranging $λ$ ; the symmetric-function involution $ω$ of 40.03.01 lifts to $QSym$ as the composition-reversal-and-complement operation on the fundamental basis, and the rank gap $2^{n - 1} - p (n)$ in degree $n$ measures how much order-data $QSym$ retains that $Λ$ discards. This unit is the quasisymmetric extension of the symmetric-function theory owned there.
The defining application is the fundamental expansion of the $(P, ω)$ -partition generating function of 40.01.04: the chain factor $q^{maj (σ)} / \prod_{i = 1}^{p} (1 - q^{i})$ proved there is exactly the principal specialisation $x_{i} = q^{i - 1}$ of the fundamental function $F_{co (σ)}$ , so the quasisymmetric expansion $K_{P, ω} = \sum_{σ} F_{co (σ)}$ is the multivariate lift of that single-variable factorisation; the descent set $Des (σ)$ that indexes the fundamental basis is the same permutation statistic whose distribution gives the Eulerian polynomials of 40.01.05, so the Eulerian numbers count linear extensions by the composition of their fundamental expansion.
The Schur expansion $s_{λ} = \sum_{T \in SYT (λ)} F_{co (T)}$ ties the fundamental basis to the Schur functions of 40.03.02 by descent of standard Young tableaux, and is the standard route to proving Schur-positivity of a symmetric function: expand it in fundamentals and match the descent classes of standard tableaux. The same plane-partition and column-strict-tableau enumeration that the nonintersecting-path determinants of 40.03.04 compute can be read as principal specialisations of these fundamental expansions, and the plane-partition generating functions developed in the companion unit 40.03.07 are the column-strict $(P, ω)$ -partition specialisations of $K_{P, ω}$ for product-of-chains posets.

Historical & philosophical context Master

Quasisymmetric functions were isolated by Ira Gessel in 1984 ^{[Gessel 1984]}, who introduced the fundamental functions $F_{α}$ to give Stanley's theory of $(P, ω)$ -partitions a symmetric-function-style home and to compute inner products of skew Schur functions; the ring itself had appeared implicitly in Stanley's 1972 Ordered Structures and Partitions through the descent-composition organisation of P-partition generating functions, and Stanley codified the modern account in Enumerative Combinatorics, Volume 2 §7.19. The Hopf-algebra structure and the duality with the noncommutative symmetric functions $NSym$ — and through them with Solomon's descent algebra of the symmetric group — were established by Claudia Malvenuto and Christophe Reutenauer in 1995 ^{[Malvenuto-Reutenauer 1995]}, placing $QSym$ and $NSym$ as graded dual Hopf algebras inside the larger Hopf algebra of permutations.

The universal role of $QSym$ was identified by Marcelo Aguiar, Nantel Bergeron, and Frank Sottile in 2006 ^{[Aguiar-Bergeron-Sottile 2006]}, who proved that $QSym$ equipped with its canonical character is the terminal object in the category of combinatorial Hopf algebras, so that every combinatorial invariant defined by a Hopf-algebraic recursion maps canonically into it. Stanley's chromatic symmetric function, introduced in 1995 ^{[Stanley 1995]} as a symmetric-function refinement of the chromatic polynomial, supplied a central testing ground; the Stanley-Stembridge $e$ -positivity conjecture for incomparability graphs of $(3 + 1)$ -free posets remains open, while the weaker Schur-positivity was proved by Gasharov through the fundamental expansion.

Bibliography Master

@incollection{gessel1984multipartite,
  author    = {Gessel, Ira M.},
  title     = {Multipartite {P}-partitions and inner products of skew {S}chur functions},
  booktitle = {Combinatorics and Algebra (Boulder, 1983)},
  series    = {Contemporary Mathematics},
  volume    = {34},
  pages     = {289--301},
  publisher = {American Mathematical Society},
  year      = {1984}
}

@book{stanley1999ec2,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 2},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {62},
  publisher = {Cambridge University Press},
  year      = {1999}
}

@article{malvenutoreutenauer1995,
  author  = {Malvenuto, Claudia and Reutenauer, Christophe},
  title   = {Duality between quasi-symmetric functions and the {S}olomon descent algebra},
  journal = {Journal of Algebra},
  volume  = {177},
  number  = {3},
  pages   = {967--982},
  year    = {1995}
}

@article{aguiarbergeronsottile2006,
  author  = {Aguiar, Marcelo and Bergeron, Nantel and Sottile, Frank},
  title   = {Combinatorial {H}opf algebras and generalized {D}ehn-{S}ommerville relations},
  journal = {Compositio Mathematica},
  volume  = {142},
  number  = {1},
  pages   = {1--30},
  year    = {2006}
}

@article{stanley1995chromatic,
  author  = {Stanley, Richard P.},
  title   = {A symmetric function generalization of the chromatic polynomial of a graph},
  journal = {Advances in Mathematics},
  volume  = {111},
  number  = {1},
  pages   = {166--194},
  year    = {1995}
}

@book{stanley1972ordered,
  author    = {Stanley, Richard P.},
  title     = {Ordered Structures and Partitions},
  series    = {Memoirs of the American Mathematical Society},
  number    = {119},
  publisher = {American Mathematical Society},
  year      = {1972}
}

Prerequisites

40.03.01
40.01.04

Tier anchors

beginner: Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) §7.19 opening (quasisymmetric functions by example: power series in which the coefficient sees only the shape of the exponent run, not which variables carry it); Gessel 1984 *Multipartite P-partitions and inner products of skew Schur functions* (Contemp. Math. 34) §1 (the fundamental quasisymmetric functions as P-partition generating functions)
intermediate: Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.19 (the ring QSym, compositions of $n$, the monomial basis $M_\alpha$ and the fundamental basis $F_\alpha = \sum_{\beta \preceq \alpha} M_\beta$, the inclusion $\Lambda \subset \mathrm{QSym}$, and the $(P,\omega)$-partition expansion $K_{P,\omega} = \sum_{\sigma} F_{\mathrm{co}(\sigma)}$ over linear extensions); Gessel 1984 *Multipartite P-partitions* (Contemp. Math. 34) for the fundamental theorem
master: Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.19 and §7.23 (quasisymmetric functions, the fundamental basis, Schur expansion into fundamentals by descent of standard Young tableaux); Gessel 1984 *Multipartite P-partitions and inner products of skew Schur functions* (Contemporary Mathematics 34, 289-301); Malvenuto-Reutenauer 1995 *J. Algebra* 177 (QSym and NSym as dual Hopf algebras, the descent-algebra duality); Aguiar-Bergeron-Sottile 2006 *Compositio Math.* 142 (QSym as the terminal object in the category of combinatorial Hopf algebras); Stanley 1995 *Adv. Math.* 111 (the chromatic symmetric function)

References

Stanley, R. P. — Enumerative Combinatorics, Volume 2 · Cambridge Studies in Advanced Mathematics 62 (1999). §7.19 introduces the ring $\mathrm{QSym}$ of quasisymmetric functions: a formal power series of bounded degree in $x_1, x_2, \dots$ is quasisymmetric when, for every composition $\alpha = (\alpha_1, \dots, \alpha_k)$, the coefficient of $x_{i_1}^{\alpha_1}\cdots x_{i_k}^{\alpha_k}$ is the same for every strictly increasing index sequence $i_1 < \cdots < i_k$. Compositions of $n$ index two bases of $\mathrm{QSym}^n$: the monomial quasisymmetric functions $M_\alpha = \sum_{i_1 < \cdots < i_k} x_{i_1}^{\alpha_1}\cdots x_{i_k}^{\alpha_k}$ and Gessel's fundamental quasisymmetric functions $F_\alpha = \sum_{\beta \preceq \alpha} M_\beta$, where $\beta \preceq \alpha$ means $\beta$ refines $\alpha$ (coarsening corresponds to merging adjacent parts). The standard bijection between compositions of $n$ and subsets of $[n-1]$ (the set of partial sums) makes $F_\alpha = F_{S}$ a function of a descent set $S \subseteq [n-1]$. The symmetric functions $\Lambda$ form a subring $\Lambda \subset \mathrm{QSym}$, with $m_\lambda = \sum_{\alpha} M_\alpha$ summed over compositions $\alpha$ that rearrange $\lambda$. The fundamental theorem (Gessel) states that the $(P,\omega)$-partition generating function expands as $K_{P,\omega} = \sum_{\sigma \in \mathcal{L}(P,\omega)} F_{\mathrm{co}(\sigma)}$ over linear extensions, where $\mathrm{co}(\sigma)$ is the descent composition. §7.19 also gives the expansion of a Schur function $s_\lambda = \sum_{T} F_{\mathrm{co}(T)}$ over standard Young tableaux $T$ of shape $\lambda$, with $\mathrm{co}(T)$ the descent composition of $T$, and discusses the Hopf-algebra structure and the chromatic symmetric function of §7.23.
Gessel, I. M. — Multipartite P-partitions and inner products of skew Schur functions · Contemporary Mathematics 34 (1984), 289-301. The originating paper for the fundamental quasisymmetric functions. Gessel attaches to each finite labelled poset $(P,\omega)$ the generating function for its $(P,\omega)$-partitions, organised by the multiset of values, and proves it is quasisymmetric; the fundamental theorem of $(P,\omega)$-partitions (the order cone decomposes over linear extensions) then expresses this generating function as a sum of the functions $F_{\mathrm{co}(\sigma)}$ over linear extensions $\sigma$, where $\mathrm{co}(\sigma)$ is the composition of $n$ recording the descent set $\mathrm{Des}(\sigma) \subseteq [n-1]$. Skew Schur functions arise as the generating functions of column-strict labellings, and their fundamental expansions, combined with the comultiplication of $\mathrm{QSym}$, compute inner products of skew Schur functions combinatorially. The paper is the bridge between Stanley's P-partition theory and the modern quasisymmetric viewpoint.
Malvenuto, C. & Reutenauer, C. — Duality between quasi-symmetric functions and the Solomon descent algebra · Journal of Algebra 177 (1995), 967-982. Establishes that $\mathrm{QSym}$ is a graded Hopf algebra whose graded dual is $\mathrm{NSym}$, the Hopf algebra of noncommutative symmetric functions, and that in each degree $n$ the dual pairing identifies $\mathrm{NSym}_n$ with Solomon's descent algebra of the symmetric group $S_n$. The fundamental basis $F_\alpha$ of $\mathrm{QSym}$ is dual to the ribbon basis $R_\alpha$ of $\mathrm{NSym}$, and the monomial basis $M_\alpha$ is dual to the complete-noncommutative basis. The Malvenuto-Reutenauer Hopf algebra of permutations sits above both, with $\mathrm{QSym}$ a quotient and $\mathrm{NSym}$ a sub. This supplies the Hopf-algebraic and descent-algebra context for the fundamental basis.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m