40.03.01 · combinatorics / symmetric-functions-rsk

The Ring of Symmetric Functions and Its Bases

shipped3 tiersLean: none

Anchor (Master): Macdonald 1995 *Symmetric Functions and Hall Polynomials* 2e (Oxford) Ch. I §2-6 (the full algebra of $\Lambda$, the bases and transition matrices, the involution $\omega$, the Hall inner product foreshadow); Stanley 1999 *Enumerative Combinatorics, Volume 2* Ch. 7 and Appendix 2; Sagan 2001 *The Symmetric Group* 2e (Springer) Ch. 4; Newton 1707 *Arithmetica Universalis* (the power-sum/elementary identities); Cauchy 1815 (the antisymmetric-quotient definition of what become Schur functions)

Intuition Beginner

Imagine a recipe that asks for some ingredients but does not care which jar each one came from. If you swap the salt jar with the sugar jar — relabelling the containers while keeping the contents — the dish is exactly the same. A symmetric function is an algebraic expression in several variables with this property: rename the variables in any order and the expression does not change. The expression $x + y$ is symmetric, because $y + x$ is the same thing. So is $x y$ . But $x - y$ is not, because swapping $x$ and $y$ flips its sign.

Why care? Many natural quantities are blind to the order of their inputs. The total of a list, the product of a list, the sum of all pairwise products — none of these notice if you shuffle the list first. These order-blind quantities are exactly the symmetric functions, and they turn out to have a rich and tidy structure all their own. They are the right language for any problem where the objects are interchangeable, which in this curriculum means counting problems and the algebra of the symmetric group.

The central discovery of this unit is that there are a few basic building blocks, and every symmetric function is built from them in exactly one way. Think of how every whole number factors into primes: once you know the primes, you know all the numbers. Here the role of the primes is played by short families of simple symmetric functions. We will meet four such families in two or three variables, see that they say the same information in different dialects, and learn the recipe for translating between the dialects.

The pay-off is leverage. A messy-looking expression that happens to be symmetric can always be rewritten in terms of the building blocks, where it becomes short and computable. Newton found the first translation rules over three centuries ago, and they are still the workhorse of the subject.

Visual Beginner

The four families of building blocks, shown in just three variables $x, y, z$ . Each row is one family; the entries are the first few members. A partition — a way of writing a number as a sum of non-increasing pieces — is the address that labels each member.

family	symbol	first member	second member	what it sums
monomial	$m$	$x + y + z$	$x^{2} + y^{2} + z^{2}$	all rearrangements of one pattern
elementary	$e$	$x + y + z$	$x y + x z + y z$	products of distinct variables
complete	$h$	$x + y + z$	$x^{2} + y^{2} + z^{2} + x y + x z + y z$	all products of a given degree
power sum	$p$	$x + y + z$	$x^{2} + y^{2} + z^{2}$	each variable raised to a power

Notice the first members all agree: $m$ for the pattern "one", $e$ for "one distinct factor", $h$ for "all degree-one products", and $p$ for "first power" are each just $x + y + z$ . They part ways at degree two. Reading the table tells you the personality of each family: elementary uses distinct variables, complete uses every product, power sum keeps the variables separate. These different personalities are why translating between the families is the interesting part.

Worked example Beginner

Take two variables $x$ and $y$ , and let us compute the first members of each family and watch one translation rule appear.

Step 1. Elementary functions. The first is $e_{1} = x + y$ . The second is $e_{2} = x y$ , the single product of distinct variables. There is no $e_{3}$ in two variables, since you cannot pick three distinct ones.

Step 2. Power sums. The first is $p_{1} = x + y$ , the same as $e_{1}$ . The second is $p_{2} = x^{2} + y^{2}$ .

Step 3. Complete functions. The first is $h_{1} = x + y$ . The second is $h_{2} = x^{2} + x y + y^{2}$ , every product of total degree two.

Step 4. Translate $p_{2}$ into the elementary dialect. Start from the algebra identity $(x + y)^{2} = x^{2} + 2 x y + y^{2}$ . Rearranged, $x^{2} + y^{2} = (x + y)^{2} - 2 x y$ . In our names this reads $p_{2} = e_{1}^{2} - 2 e_{2}$ . We have rewritten a power sum purely in terms of elementary functions, with whole-number coefficients.

Step 5. A second translation, complete from elementary. Note $h_{2} = x^{2} + x y + y^{2} = (x + y)^{2} - x y = e_{1}^{2} - e_{2}$ . And reading the complete and elementary first members back, $h_{1} = e_{1}$ .

What this tells us: the families are interchangeable. A quantity written in one dialect can always be rewritten in another, and the translation uses only addition, subtraction, and multiplication of the building blocks. The rule $p_{2} = e_{1}^{2} - 2 e_{2}$ is the first case of Newton's identities, the systematic translation table this unit is built around.

Check your understanding Beginner

Formal definition Intermediate+

Fix a commutative base ring, by default $Z$ . For each $n$ let $Λ_{n} = Z [x_{1}, \dots, x_{n}]^{S_{n}}$ be the ring of polynomials invariant under the $S_{n}$ -action permuting the variables; it is graded by total degree, $Λ_{n} = ⨁_{d \geq 0} Λ_{n}^{d}$ . The ring of symmetric functions is the inverse limit in the category of graded rings, $$ \Lambda ;=; \varprojlim_n \Lambda_n, \qquad \Lambda^d ;=; \varprojlim_n \Lambda_n^d, $$ taken degree by degree along the surjections $ρ_{n} : Λ_{n + 1} \to Λ_{n}$ that set $x_{n + 1} = 0$ . An element of $Λ^{d}$ is a compatible family of symmetric polynomials of degree $d$ , one in each number of variables, agreeing under the restrictions $ρ_{n}$ ; informally it is a "symmetric polynomial in infinitely many variables $x_{1}, x_{2}, \dots$ " of bounded degree. The notation $⟨ a, b ⟩$ , $(a; q)_{n}$ , $z_{λ}$ , and the bases below are recorded in _meta/NOTATION.md.

Partitions index everything. A partition $λ = (λ_{1} \geq λ_{2} \geq \dots \geq λ_{ℓ} > 0)$ of $n = ∣ λ ∣ = \sum_{i} λ_{i}$ has length $ℓ (λ) = ℓ$ ; write $λ ⊢ n$ . For a partition $λ$ with $m_{i}$ parts equal to $i$ , set $z_{λ} = \prod_{i \geq 1} i^{m_{i}} m_{i}!$ , the order of the centralizer of a permutation of cycle type $λ$ in $S_{n}$ .

Definition (the four classical bases). For each partition $λ$ define, as elements of $Λ$ :

Monomial $m_{λ} = \sum x^{α}$ , the sum over all distinct monomials $x^{α} = x_{1}^{α_{1}} x_{2}^{α_{2}} \dots$ whose exponent sequence $α$ is a rearrangement of $λ$ (padded by zeros).
Elementary $e_{n} = m_{(1^{n})} = \sum_{i_{1} < \dots < i_{n}} x_{i_{1}} \dots x_{i_{n}}$ for $n \geq 1$ , $e_{0} = 1$ , and $e_{λ} = e_{λ_{1}} e_{λ_{2}} \dots$ .
Complete homogeneous $h_{n} = \sum_{∣ α ∣ = n} x^{α} = \sum_{μ ⊢ n} m_{μ}$ for $n \geq 0$ , and $h_{λ} = h_{λ_{1}} h_{λ_{2}} \dots$ .
Power sum $p_{n} = \sum_{i} x_{i}^{n} = m_{(n)}$ for $n \geq 1$ , and $p_{λ} = p_{λ_{1}} p_{λ_{2}} \dots$ .

The set ${m_{λ} : λ ⊢ d}$ is a $Z$ -basis of $Λ^{d}$ by construction: a symmetric function is determined by its coefficients on the orbit-sums $m_{λ}$ . The Schur functions $s_{λ}$ , the fifth and most important basis, are defined and developed in 40.03.02; they will satisfy $s_{λ} = \sum_{μ} K_{λ μ} m_{μ}$ with Kostka numbers $K_{λ μ}$ .

Generating-function form. Package the one-row functions into power series in a marker $t$ : $$ E(t) = \sum_{n \ge 0} e_n t^n = \prod_i (1 + x_i t), \qquad H(t) = \sum_{n \ge 0} h_n t^n = \prod_i (1 - x_i t)^{-1}. $$ These are the $q$ -analogue-free companions of the products met in 40.01.06: $E (t)$ chooses each variable at most once, $H (t)$ allows repetition. The power-sum series is $P (t) = \sum_{n \geq 1} p_{n} t^{n - 1} = \sum_{i} \frac{x _{i}}{1 - x _{i} t}$ .

Counterexamples to common slips Intermediate+

" $Λ$ is the ring of symmetric polynomials in some fixed number of variables." It is not: $Λ$ has infinitely many variables, taken as an inverse limit. In $n$ variables the relation $e_{n + 1} = 0$ holds, but in $Λ$ no $e_{k}$ vanishes. Working in $Λ$ avoids the spurious relations that finitely many variables impose.
"The $p_{λ}$ form a $Z$ -basis like the $m_{λ}$ , $e_{λ}$ , $h_{λ}$ ." They form a basis only after tensoring with $Q$ . For instance $h_{2} = \frac{1}{2} p_{1}^{2} + \frac{1}{2} p_{2}$ needs the denominator $2$ ; the power sums generate $Λ_{Q}$ but not $Λ$ over $Z$ .
" $ω$ is some external symmetry one imposes." It is the ring automorphism forced by $ω (e_{n}) = h_{n}$ once one knows the $e_{n}$ are algebraically independent generators; its existence is a theorem, not a definition by fiat, and $ω^{2} = id$ must be proved.

Key theorem with proof Intermediate+

The signature theorem is that the elementary functions are free polynomial generators of $Λ$ , and dually so are the complete functions, with the two systems locked together by a single generating-function identity.

Theorem (fundamental theorem of symmetric functions; the $H E$ relation). The ring of symmetric functions is a polynomial ring on the elementary functions, $$ \Lambda = \mathbb{Z}[e_1, e_2, e_3, \dots], $$ with the $e_{n}$ algebraically independent over $Z$ ; equivalently ${e_{λ} : λ ⊢ d}$ is a $Z$ -basis of $Λ^{d}$ . The complete functions satisfy $$ H(t),E(-t) = 1, \qquad \text{equivalently} \qquad \sum_{k=0}^{n} (-1)^k e_k, h_{n-k} = 0 \ \ (n \ge 1), $$ and consequently $Λ = Z [h_{1}, h_{2}, \dots]$ as well, with the $h_{n}$ algebraically independent. The ring automorphism $ω : Λ \to Λ$ determined by $ω (e_{n}) = h_{n}$ is an involution, $ω^{2} = id$ . ^{[Macdonald §2]}

Proof. The product expansion gives, directly, $$ H(t)E(-t) = \prod_i \frac{1}{1 - x_i t}\cdot \prod_i (1 - x_i t) = 1. $$ Extracting the coefficient of $t^{n}$ for $n \geq 1$ yields $\sum_{k = 0}^{n} (- 1)^{k} e_{k} h_{n - k} = 0$ . This is a triangular recursion: it expresses $h_{n} = e_{1} h_{n - 1} - e_{2} h_{n - 2} + \dots + (- 1)^{n - 1} e_{n}$ in terms of $e_{1}, \dots, e_{n}$ and lower $h$ 's, so by induction each $h_{n}$ lies in $Z [e_{1}, \dots, e_{n}]$ ; symmetrically each $e_{n}$ lies in $Z [h_{1}, \dots, h_{n}]$ . Hence the two subrings $Z [e_{1}, e_{2}, \dots]$ and $Z [h_{1}, h_{2}, \dots]$ of $Λ$ coincide.

To see this common subring is all of $Λ$ and that the $e_{n}$ are free, count in each degree. In $Λ^{d}$ the monomial functions ${m_{λ} : λ ⊢ d}$ are a $Z$ -basis, so $rk_{Z} Λ^{d} = p (d)$ , the number of partitions of $d$ . The products $e_{λ} = e_{λ_{1}} e_{λ_{2}} \dots$ for $λ ⊢ d$ also number $p (d)$ . Order partitions by dominance and expand: a computation of leading terms gives $e_{λ} = m_{λ^{'}} + \sum_{μ ⊳ λ^{'}} a_{λ μ} m_{μ}$ , where $λ^{'}$ is the conjugate and the sum runs over partitions strictly dominating $λ^{'}$ . The transition matrix from ${e_{λ}}$ to ${m_{μ}}$ is therefore unitriangular with respect to dominance (entries in $Z$ , ones on the diagonal after the reordering $λ \mapsto λ^{'}$ ), hence invertible over $Z$ . So ${e_{λ}}$ is a $Z$ -basis of $Λ^{d}$ , the $e_{n}$ generate $Λ$ , and any nonzero polynomial relation among them would make the $p (d)$ products $e_{λ}$ linearly dependent in some degree, contradicting the basis property. Thus the $e_{n}$ are algebraically independent and $Λ = Z [e_{1}, e_{2}, \dots]$ .

Because ${e_{n}}$ are free generators, the assignment $e_{n} \mapsto h_{n}$ extends uniquely to a ring endomorphism $ω$ . Apply $ω$ to the relation $\sum_{k} (- 1)^{k} e_{k} h_{n - k} = 0$ : it has the same shape with $e$ and $h$ swapped and the sign pattern preserved, and that swapped relation is the original read backwards, so $ω (h_{n}) = e_{n}$ . Therefore $ω^{2}$ fixes every generator $e_{n}$ , giving $ω^{2} = id$ , and $ω$ is an involutive automorphism. $□$

Bridge. This theorem is the foundational reason symmetric-function identities are algebra rather than infinite bookkeeping: once $Λ = Z [e_{1}, e_{2}, \dots]$ is a free polynomial ring, a symmetric function is a finite expression in the $e_{n}$ and any identity is a polynomial identity. It builds toward the Schur basis of 40.03.02, where the same unitriangular-against-dominance argument produces the Kostka matrix, and it appears again in the Hall inner product of 40.03.03, under which $ω$ becomes an isometry. The $H E$ relation is exactly the $q = 1$ , infinite-variable shadow of the elementary-versus-complete product identities of 40.01.06; this is the central insight that the involution $ω$ — swapping "distinct factors" with "all factors" — is the symmetric-function incarnation of conjugating Young diagrams. Putting these together, the fundamental theorem, the $H E$ relation, and $ω$ are three views of one fact: $Λ$ is a free polynomial ring with a conjugation symmetry, and every later structure on $Λ$ is constrained to respect it.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Derive Newton's identity $p_{n} = e_{1} p_{n - 1} - e_{2} p_{n - 2} + \dots + (- 1)^{n - 1} n e_{n}$ for $n = 3$ , i.e. show $p_{3} = e_{1}^{3} - 3 e_{1} e_{2} + 3 e_{3}$ .

Hint

Use $P (t) = H^{'} (t) / H (t)$ together with $H (t) E (- t) = 1$ , which gives $P (- t) = E^{'} (- t) / E (- t)$ , hence $E^{'} (- t) = - E (- t) \sum_{n} p_{n} (- t)^{n - 1}$ . Extract the coefficient of $t^{2}$ , or substitute $p_{1} = e_{1}$ , $p_{2} = e_{1}^{2} - 2 e_{2}$ into the recursion.

Answer

Newton's recursion in elementary form is $p_{n} = \sum_{k = 1}^{n - 1} (- 1)^{k - 1} e_{k} p_{n - k} + (- 1)^{n - 1} n e_{n}$ . For $n = 3$ : $p_{3} = e_{1} p_{2} - e_{2} p_{1} + 3 e_{3}$ . Substituting $p_{1} = e_{1}$ and $p_{2} = e_{1}^{2} - 2 e_{2}$ gives $p_{3} = e_{1} (e_{1}^{2} - 2 e_{2}) - e_{2} e_{1} + 3 e_{3} = e_{1}^{3} - 3 e_{1} e_{2} + 3 e_{3}$ . Rubric: full credit for the recursion with the $n e_{n}$ boundary term and the correct substitution to $e_{1}^{3} - 3 e_{1} e_{2} + 3 e_{3}$ .

Exercise 6 (hard, symbolic).

Prove the change-of-basis formula $h_{n} = \sum_{λ ⊢ n} z_{λ}^{- 1} p_{λ}$ , where $z_{λ} = \prod_{i} i^{m_{i}} m_{i}!$ and $m_{i}$ is the number of parts of $λ$ equal to $i$ .

Hint

Take $lo g H (t) = - \sum_{i} lo g (1 - x_{i} t) = \sum_{n \geq 1} p_{n} t^{n} / n$ , then exponentiate and collect terms by cycle type.

Answer

From $H (t) = \prod_{i} (1 - x_{i} t)^{- 1}$ , take logarithms: $lo g H (t) = - \sum_{i} lo g (1 - x_{i} t) = \sum_{i} \sum_{n \geq 1} \frac{( x _{i} t ) ^{n}}{n} = \sum_{n \geq 1} \frac{p _{n}}{n} t^{n}$ . Exponentiate, $H (t) = exp (\sum_{n} \frac{p _{n}}{n} t^{n}) = \prod_{n \geq 1} exp (\frac{p _{n}}{n} t^{n}) = \prod_{n \geq 1} \sum_{m_{n} \geq 0} \frac{1}{m _{n} !} (\frac{p _{n}}{n})^{m_{n}} t^{n m_{n}}$ . The coefficient of $t^{N}$ sums over choices $(m_{n})$ with $\sum_{n} n m_{n} = N$ , i.e. over partitions $λ ⊢ N$ with $m_{n}$ parts equal to $n$ , contributing $\prod_{n} \frac{1}{m _{n} ! n ^{m_{n}}} p_{n}^{m_{n}} = z_{λ}^{- 1} p_{λ}$ . Hence $h_{N} = \sum_{λ ⊢ N} z_{λ}^{- 1} p_{λ}$ . Rubric: full credit for the logarithm expansion, the exponential-formula collection by cycle type, and the identification of the coefficient as $z_{λ}^{- 1}$ .

Exercise 7 (hard, symbolic).

Show that the transition matrix expressing ${e_{λ}}$ in the monomial basis ${m_{μ}}$ on $Λ^{n}$ is unitriangular with respect to dominance order, and conclude that ${e_{λ} : λ ⊢ n}$ is a $Z$ -basis of $Λ^{n}$ .

Hint

Expand $e_{λ} = \prod_{j} e_{λ_{j}}$ and identify the lexicographically/dominance-leading monomial. Recall $e_{λ} = m_{λ^{'}} + (higher in dominance)$ where $λ^{'}$ is the conjugate.

Answer

Each $e_{k} = \sum_{i_{1} < \dots < i_{k}} x_{i_{1}} \dots x_{i_{k}}$ has all exponents in ${0, 1}$ . The product $e_{λ} = \prod_{j} e_{λ_{j}}$ expands into monomials whose exponent vector $α$ satisfies the majorization bound forcing the dominance-minimal monomial type to be the conjugate $λ^{'}$ : stacking the columns of heights $λ_{1}, λ_{2}, \dots$ produces the partition $λ^{'}$ , and every other monomial appearing dominates $λ^{'}$ . Thus $e_{λ} = m_{λ^{'}} + \sum_{μ ⊳ λ^{'}} a_{λ μ} m_{μ}$ with $a_{λ μ} \in Z_{\geq 0}$ . Reindexing $λ \mapsto λ^{'}$ (an involution on partitions of $n$ ), the matrix $(a)$ is upper-unitriangular in dominance order with $1$ 's on the diagonal, hence invertible over $Z$ ; an integer unitriangular matrix has an integer inverse. Therefore ${e_{λ}}$ is obtained from the $Z$ -basis ${m_{μ}}$ by an invertible integer matrix and is itself a $Z$ -basis. Rubric: full credit for the leading-term identification $e_{λ} = m_{λ^{'}} + higher$ , the unitriangularity, and the integer-invertibility conclusion.

Advanced results Master

The four classical bases assemble into a single graded Hopf algebra, and the transition matrices among them encode the combinatorics that the rest of the chapter exploits.

Theorem 1 (the five transition systems). On $Λ^{n}$ the bases ${m_{λ}}, {e_{λ}}, {h_{λ}}, {p_{λ}}$ , together with the Schur basis ${s_{λ}}$ of 40.03.02, are related by transition matrices that are all integral except those involving ${p_{λ}}$ . Specifically $e_{λ} \to m_{μ}$ , $h_{λ} \to m_{μ}$ , and $s_{λ} \to m_{μ}$ (the Kostka matrix) are unitriangular and integral with respect to dominance, while $h_{n} = \sum_{λ ⊢ n} z_{λ}^{- 1} p_{λ}$ and the inverse $p_{n} = \sum (\pm) \dots$ require denominators: ${p_{λ}}$ is a $Q$ -basis of $Λ_{Q}^{n}$ but not a $Z$ -basis of $Λ^{n}$ ^{[Macdonald §2]}. The arithmetic obstruction is exactly the cycle-centralizer order $z_{λ}$ , the same integer that controls conjugacy-class sizes in $S_{n}$ .

Theorem 2 ( $Λ$ as a self-dual Hopf algebra). With coproduct $Δ (p_{n}) = p_{n} \otimes 1 + 1 \otimes p_{n}$ (the $p_{n}$ are primitive) and counit the degree- $0$ projection, $Λ$ is a graded, connected, commutative and cocommutative Hopf algebra over $Z$ , free as an algebra and cofree in the appropriate sense; it is the universal example among such "positive self-dual Hopf algebras" (Zelevinsky). The antipode is $S = (- 1)^{d e g} ω$ on the primitive generators. The involution $ω$ is the Hopf automorphism exchanging the $e$ and $h$ generators; under the Hall inner product of 40.03.03 it is an isometry, and the self-duality identifies $Λ$ with its graded dual via $⟨ h_{λ}, m_{μ} ⟩ = δ_{λ μ}$ .

Theorem 3 (Newton's identities, full form). The power sums and elementary functions satisfy, for all $n \geq 1$ , $$ p_n - e_1 p_{n-1} + e_2 p_{n-2} - \cdots + (-1)^{n-1} e_{n-1} p_1 + (-1)^n n, e_n = 0, $$ equivalently the generating-function identity $P (- t) = E^{'} (- t) / E (- t) = \frac{d}{d t} lo g E (- t)$ . These determine the $p_{n}$ from the $e_{n}$ over $Z$ , but inverting to get $e_{n}$ from $p_{1}, \dots, p_{n}$ introduces the denominator $n!$ in general (the Newton-Girard formulas), which is why $Λ_{Q} = Q [p_{1}, p_{2}, \dots]$ but $Λ \neq = Z [p_{1}, p_{2}, \dots]$ . The same identities, read in a splitting field, are the passage between the coefficients of a polynomial (its $e_{k}$ , up to sign) and its power-sum symmetric functions of the roots — the computational heart of the resolvent method in Galois theory [40.03.06 context].

Theorem 4 (specialization and principal evaluations). Setting $x_{1} = \dots = x_{n} = 1$ and the rest $0$ (the principal specialization in $n$ variables) sends $e_{k} \mapsto (k n)$ , $h_{k} \mapsto (k n + k - 1)$ , and $p_{k} \mapsto n$ ; the $H E$ relation becomes the Vandermonde-type identity $\sum_{k} (- 1)^{k} (k n) (m - k n + ( m - k ) - 1) = 0$ . Replacing the constant specialization by $x_{i} = q^{i - 1}$ recovers the $q$ -binomial generating functions of 40.01.06, so the Gaussian binomial $(k n)_{q}$ is a principal specialization of $e_{k}$ , and the partition generating function $\prod (1 - q^{i})^{- 1}$ is a specialization of $H$ .

Synthesis. Putting these together, the foundational reason $Λ$ is the master ring of algebraic combinatorics is that it is simultaneously a free polynomial ring, a self-dual Hopf algebra, and an inverse limit of invariant rings, and these three faces force every basis to behave. The fundamental theorem makes ${e_{λ}}$ and ${h_{λ}}$ free bases; the Hopf self-duality of Theorem 2 is exactly the structure that the Hall inner product of 40.03.03 makes metric, and under it $ω$ is an isometry exchanging the two free bases. The central insight is that conjugation of Young diagrams, the $e$ – $h$ swap of $ω$ , and the antipode are one symmetry seen in combinatorics, algebra, and Hopf theory respectively; this is exactly why the Kostka unitriangularity that defines Schur functions in 40.03.02 and the cycle-centralizer denominators $z_{λ}$ that obstruct a $Z$ -structure on ${p_{λ}}$ are not accidents but consequences of the dominance order and the conjugacy combinatorics of $S_{n}$ . The bridge is the principal specialization of Theorem 4, which generalises the $q$ -binomial calculus of 40.01.06 into all of $Λ$ and appears again as the Frobenius characteristic of 40.03.06, where $p_{λ} \mapsto z_{λ}^{- 1}$ -weighted indicator functions translate the entire ring into the character theory of the symmetric groups. The $H E$ relation is the hinge: read in one variable it is conjugation, read across all degrees it is the antipode, and read on roots of a polynomial it is Newton-Girard.

Full proof set Master

Proposition 1 (the $H E$ recursion and mutual generation). For all $n \geq 1$ , $\sum_{k = 0}^{n} (- 1)^{k} e_{k} h_{n - k} = 0$ , and consequently $Z [e_{1}, e_{2}, \dots] = Z [h_{1}, h_{2}, \dots]$ inside $Λ$ .

Proof. In $Λ [[t]]$ the products $E (t) = \prod_{i} (1 + x_{i} t)$ and $H (t) = \prod_{i} (1 - x_{i} t)^{- 1}$ satisfy $H (t) E (- t) = \prod_{i} (1 - x_{i} t)^{- 1} (1 - x_{i} t) = 1$ . Equate coefficients of $t^{n}$ : $\sum_{k = 0}^{n} h_{n - k} (- 1)^{k} e_{k} = 0$ for $n \geq 1$ (the $n = 0$ coefficient is $1$ ). Solving for the top complete function, $h_{n} = \sum_{k = 1}^{n} (- 1)^{k - 1} e_{k} h_{n - k}$ , expresses $h_{n}$ over $Z$ in $e_{1}, \dots, e_{n}$ and $h_{1}, \dots, h_{n - 1}$ ; induction on $n$ (base $h_{0} = 1$ ) places every $h_{n} \in Z [e_{1}, \dots, e_{n}]$ . The relation is symmetric in $e \leftrightarrow h$ (it reads $\sum_{k} (- 1)^{k} h_{k} e_{n - k} = 0$ after substituting $t \mapsto - t$ and using $E (t) H (- t) = 1$ ), so likewise every $e_{n} \in Z [h_{1}, \dots, h_{n}]$ . The two subrings therefore coincide. $□$

Proposition 2 (algebraic independence; ${e_{λ}}$ is a basis). The elementary functions $e_{1}, e_{2}, \dots$ are algebraically independent over $Z$ , and ${e_{λ} : λ ⊢ n}$ is a $Z$ -basis of $Λ^{n}$ .

Proof. Fix $n$ . Order partitions of $n$ by dominance $⊳$ . Expanding the product $e_{λ} = e_{λ_{1}} e_{λ_{2}} \dots$ and selecting, in each factor $e_{λ_{j}} = \sum_{i_{1} < \dots < i_{λ_{j}}} x_{i_{1}} \dots x_{i_{λ_{j}}}$ , the lowest-indexed monomial, the product's exponent vector assembles the columns of heights $λ_{1}, λ_{2}, \dots$ into the conjugate partition $λ^{'}$ ; one checks every monomial of $e_{λ}$ has type $μ ⊵ λ^{'}$ . Hence $e_{λ} = m_{λ^{'}} + \sum_{μ ⊳ λ^{'}} a_{λ μ} m_{μ}$ , $a_{λ μ} \in Z_{\geq 0}$ . Since $λ \mapsto λ^{'}$ is a bijection of partitions of $n$ , the matrix $A = (a_{λ μ})$ is unitriangular for the dominance order (after this relabelling), with $1$ 's on the diagonal. A unitriangular integer matrix is invertible over $Z$ , so ${e_{λ}}$ and ${m_{μ}}$ are related by an integer change of basis; as ${m_{μ}}$ is a $Z$ -basis of $Λ^{n}$ (by definition of the monomial functions), so is ${e_{λ}}$ . Counting: there are $p (n)$ products $e_{λ}$ and $rk_{Z} Λ^{n} = p (n)$ , so any algebraic relation among the $e_{k}$ would, in some degree, make the $p (n)$ functions $e_{λ}$ $Z$ -linearly dependent, contradicting the basis property. Therefore the $e_{k}$ are algebraically independent and $Λ = Z [e_{1}, e_{2}, \dots]$ . $□$

Proposition 3 ( $ω$ is a well-defined involution). There is a unique ring automorphism $ω : Λ \to Λ$ with $ω (e_{n}) = h_{n}$ for all $n$ , and $ω^{2} = id$ ; moreover $ω (p_{n}) = (- 1)^{n - 1} p_{n}$ .

Proof. By Proposition 2 the $e_{n}$ are free polynomial generators, so $e_{n} \mapsto h_{n}$ extends uniquely to a ring endomorphism $ω$ . Applying $ω$ to the $H E$ relation $\sum_{k} (- 1)^{k} e_{k} h_{n - k} = 0$ gives $\sum_{k} (- 1)^{k} h_{k} ω (h_{n - k}) = 0$ ; comparing with the symmetric form $\sum_{k} (- 1)^{k} h_{k} e_{n - k} = 0$ of Proposition 1 and solving the same triangular system forces $ω (h_{n}) = e_{n}$ . Thus $ω^{2} (e_{n}) = ω (h_{n}) = e_{n}$ on generators, so $ω^{2} = id$ and $ω$ is an involutive automorphism. For the power sums, recall $h_{n} = \sum_{λ ⊢ n} z_{λ}^{- 1} p_{λ}$ (Exercise 6) and the dual $e_{n} = \sum_{λ ⊢ n} ε_{λ} z_{λ}^{- 1} p_{λ}$ with $ε_{λ} = (- 1)^{∣ λ ∣ - ℓ (λ)} = \prod_{i} (- 1)^{λ_{i} - 1}$ , obtained from $E (t) = exp (\sum_{n} (- 1)^{n - 1} p_{n} t^{n} / n)$ (take $lo g E (t) = \sum_{i} lo g (1 + x_{i} t)$ ). Applying $ω$ to $e_{n}$ and matching with $h_{n}$ shows $ω$ acts on the $p$ -expansion by $p_{λ} \mapsto ε_{λ} p_{λ}$ ; on a single $p_{n}$ this is $ω (p_{n}) = (- 1)^{n - 1} p_{n}$ . $□$

Proposition 4 (Newton's identities). For all $n \geq 1$ , $k = 0 \sum n - 1 (- 1)^{k} e_{k} p_{n - k} + (- 1)^{n} n e_{n} = 0$ .

Proof. Differentiate $lo g E (t) = \sum_{i} lo g (1 + x_{i} t)$ : $\frac{E ^{'} ( t )}{E ( t )} = \sum_{i} \frac{x _{i}}{1 + x _{i} t} = \sum_{i} \sum_{m \geq 0} x_{i} (- x_{i} t)^{m} = \sum_{m \geq 0} (- 1)^{m} p_{m + 1} t^{m}$ . Hence $E^{'} (t) = E (t) \sum_{m \geq 0} (- 1)^{m} p_{m + 1} t^{m}$ . The left side has $t^{n - 1}$ -coefficient $n e_{n}$ ; the right side has $t^{n - 1}$ -coefficient $\sum_{k = 0}^{n - 1} e_{k} (- 1)^{n - 1 - k} p_{n - k}$ . Equate: $n e_{n} = \sum_{k = 0}^{n - 1} (- 1)^{n - 1 - k} e_{k} p_{n - k}$ , which rearranges to $\sum_{k = 0}^{n - 1} (- 1)^{k} e_{k} p_{n - k} + (- 1)^{n} n e_{n} = 0$ . $□$

Connections Master

The indexing set of every basis in this unit is the partitions of $n$ , the combinatorial object whose generating function, conjugation symmetry, and $q$ -analogues are developed in 40.01.06; the dominance order used to prove unitriangularity of the $e_{λ} \to m_{μ}$ transition is the same partial order on partitions met there, and the principal specialization $x_{i} = q^{i - 1}$ turns the elementary functions $e_{k}$ into the Gaussian binomials $(k n)_{q}$ and the complete series $H$ into the partition generating function $\prod (1 - q^{i})^{- 1}$ . This unit is the algebraic ring built on top of the partition combinatorics of 40.01.06.
The Schur basis $s_{λ}$ , the fifth and central basis, is constructed in the co-produced unit 40.03.02 as the unitriangular completion $s_{λ} = m_{λ} + \sum_{μ ⊲ λ} K_{λ μ} m_{μ}$ against the dominance order introduced here, with the bialternant (Jacobi-Trudi) formulas expressing $s_{λ}$ as determinants in the $h$ and $e$ bases of this unit; the involution $ω$ defined here acts as $ω (s_{λ}) = s_{λ^{'}}$ on Schur functions. The Hall inner product of the co-produced 40.03.03 makes ${s_{λ}}$ orthonormal and ${p_{λ}}$ orthogonal with $⟨ p_{λ}, p_{λ} ⟩ = z_{λ}$ — the same $z_{λ}$ that obstructs a $Z$ -basis of power sums here — and turns $ω$ into an isometry.
The power-sum-to-character dictionary is the Frobenius characteristic of the co-produced 40.03.06: the map sending the indicator of the conjugacy class of cycle type $λ$ in $S_{n}$ to $z_{λ}^{- 1} p_{λ}$ is a ring isomorphism from the class functions of the symmetric groups onto $Λ$ , carrying irreducible characters to Schur functions. The cycle-centralizer order $z_{λ}$ appearing in Newton's change of basis is exactly the centralizer order in $S_{n}$ , so the arithmetic of ${p_{λ}}$ in this unit is the conjugacy-class arithmetic of the symmetric group; the Young-diagram and hook-length combinatorics that names the irreducibles is set up in the representation-theory units 07.05.02 and 07.05.10 (the Murnaghan-Nakayama rule, which is the power-sum expansion of Schur functions read as a character computation).

Historical & philosophical context Master

The elementary-symmetric and power-sum functions, and the recursive identities linking them, are due to Newton, who recorded them in the Arithmetica Universalis (compiled from lectures of the 1670s-80s, published 1707) ^{[Newton 1707]} as a method for computing the power sums of the roots of a polynomial from its coefficients without solving it; the formulas were given a determinantal form by Girard slightly earlier and are now called the Newton-Girard identities. The fundamental theorem of symmetric functions — that every symmetric polynomial is a unique polynomial in the elementary ones — was the technical engine of Lagrange's (1770) and later Galois's analysis of solvability, since the coefficients of a polynomial are, up to sign, the elementary symmetric functions of its roots, and Newton's identities convert between coefficient data and root data.

The Schur functions, foreshadowed here and built in 40.03.02, appear first as the antisymmetric-over-Vandermonde quotients in Cauchy's 1815 memoir on alternating functions ^{[Cauchy 1815]}, long before Schur's 1901 thesis identified them with the irreducible characters of the general linear group. The reorganization of the whole subject around the inverse-limit ring $Λ$ , the four bases, the involution $ω$ , and the Hall inner product is largely Philip Hall's (1950s, in the context of the Hall algebra of finite abelian $p$ -groups) and was codified in Macdonald's Symmetric Functions and Hall Polynomials (1979; 2nd ed. 1995). The Hopf-algebraic and self-duality structure was isolated by Zelevinsky (1981) and by Geissinger, placing $Λ$ as the universal positive self-dual Hopf algebra and tying its representation-theoretic ubiquity to that universality.

Bibliography Master

@book{macdonald1995symmetric,
  author    = {Macdonald, Ian G.},
  title     = {Symmetric Functions and Hall Polynomials},
  series    = {Oxford Mathematical Monographs},
  edition   = {2},
  publisher = {Oxford University Press},
  year      = {1995}
}

@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}
}

@book{sagan2001symmetric,
  author    = {Sagan, Bruce E.},
  title     = {The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions},
  series    = {Graduate Texts in Mathematics},
  volume    = {203},
  edition   = {2},
  publisher = {Springer},
  year      = {2001}
}

@book{newton1707arithmetica,
  author    = {Newton, Isaac},
  title     = {Arithmetica Universalis},
  publisher = {Cambridge},
  year      = {1707}
}

@article{cauchy1815memoire,
  author  = {Cauchy, Augustin-Louis},
  title   = {M\'{e}moire sur les fonctions qui ne peuvent obtenir que deux valeurs \'{e}gales et de signes contraires par suite des transpositions op\'{e}r\'{e}es entre les variables qu'elles renferment},
  journal = {Journal de l'\'{E}cole Polytechnique},
  volume  = {10},
  pages   = {29--112},
  year    = {1815}
}

@book{zelevinsky1981representations,
  author    = {Zelevinsky, Andrey V.},
  title     = {Representations of Finite Classical Groups: A Hopf Algebra Approach},
  series    = {Lecture Notes in Mathematics},
  volume    = {869},
  publisher = {Springer},
  year      = {1981}
}

@article{hall1959algebra,
  author  = {Hall, Philip},
  title   = {The algebra of partitions},
  journal = {Proceedings of the 4th Canadian Mathematical Congress (Banff)},
  pages   = {147--159},
  year    = {1959}
}

Prerequisites

40.01.06

Tier anchors

beginner: Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) §7.1-7.3 (symmetric functions as polynomials unchanged by relabelling the variables; the monomial, elementary, and complete bases by example); Macdonald 1995 *Symmetric Functions and Hall Polynomials* 2e (Oxford) Ch. I §2 opening (the elementary and complete functions in a handful of variables)
intermediate: Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.3-7.8 (the ring $\Lambda$ as an inverse limit, the five bases indexed by partitions, the fundamental theorem $\Lambda = \mathbb{Z}[e_1,e_2,\dots]$, generating-function identities $E(t)H(-t)=1$, Newton's identities, the involution $\omega$); Macdonald 1995 *Symmetric Functions and Hall Polynomials* 2e Ch. I §2 (elementary/complete/power-sum, $\omega$, transition matrices)
master: Macdonald 1995 *Symmetric Functions and Hall Polynomials* 2e (Oxford) Ch. I §2-6 (the full algebra of $\Lambda$, the bases and transition matrices, the involution $\omega$, the Hall inner product foreshadow); Stanley 1999 *Enumerative Combinatorics, Volume 2* Ch. 7 and Appendix 2; Sagan 2001 *The Symmetric Group* 2e (Springer) Ch. 4; Newton 1707 *Arithmetica Universalis* (the power-sum/elementary identities); Cauchy 1815 (the antisymmetric-quotient definition of what become Schur functions)

References

Macdonald, I. G. — Symmetric Functions and Hall Polynomials · Oxford Mathematical Monographs, 2nd edition (1995). Chapter I §1 sets up partitions, Ferrers/Young diagrams, conjugation, and dominance order; §2 defines the ring $\Lambda = \varprojlim \Lambda_n$ of symmetric functions as the inverse limit of the rings $\Lambda_n = \mathbb{Z}[x_1,\dots,x_n]^{S_n}$ of symmetric polynomials in the category of graded rings, and introduces the monomial $m_\lambda$, elementary $e_\lambda$, complete homogeneous $h_\lambda$, and power-sum $p_\lambda$ functions indexed by partitions. The generating functions $E(t) = \prod_i (1 + x_i t) = \sum_n e_n t^n$ and $H(t) = \prod_i (1 - x_i t)^{-1} = \sum_n h_n t^n$ are introduced with the fundamental relation $H(t)E(-t) = 1$; $P(t) = \sum_n p_n t^{n-1} = H'(t)/H(t) = \sum_i x_i/(1 - x_i t)$ gives Newton's identities $n h_n = \sum_{k=1}^n p_k h_{n-k}$ and $n e_n = \sum_{k=1}^n (-1)^{k-1} p_k e_{n-k}$. The fundamental theorem states $\Lambda = \mathbb{Z}[e_1, e_2, \dots] = \mathbb{Z}[h_1, h_2, \dots]$ with the $e_n$ (equivalently $h_n$) algebraically independent; over $\mathbb{Q}$, $\Lambda_\mathbb{Q} = \mathbb{Q}[p_1, p_2, \dots]$. The involution $\omega$ is the ring automorphism with $\omega(e_n) = h_n$, hence $\omega^2 = \mathrm{id}$ and $\omega(p_n) = (-1)^{n-1} p_n$. The Schur functions $s_\lambda$ and the Hall inner product appear in §3-4.
Stanley, R. P. — Enumerative Combinatorics, Volume 2 · Cambridge Studies in Advanced Mathematics 62 (1999). Chapter 7 develops symmetric functions for the combinatorialist: §7.1-7.2 motivate $\Lambda$ and its grading; §7.3-7.6 give the monomial, elementary, complete, and power-sum bases, the fundamental theorem of symmetric functions, and the generating-function identities; §7.7-7.8 treat the involution $\omega$, Newton's identities, and the change-of-basis (transition) matrices, noting that the power sums $p_\lambda$ form a $\mathbb{Q}$-basis but not a $\mathbb{Z}$-basis. Schur functions, the Hall inner product, RSK, and the Murnaghan-Nakayama rule occupy §7.10-7.18 and Appendix 2 (the characters of $S_n$ via the Frobenius characteristic).
Sagan, B. E. — The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions · Springer Graduate Texts in Mathematics 203, 2nd edition (2001). Chapter 4 introduces the ring of symmetric functions with the combinatorics of the symmetric group in view: the monomial, elementary, complete homogeneous, power-sum, and Schur bases; the fundamental theorem; the involution $\omega$; and the Hall inner product under which $\{s_\lambda\}$ is orthonormal and $\{p_\lambda\}$ orthogonal with $\langle p_\lambda, p_\lambda \rangle = z_\lambda$. The Frobenius characteristic map carrying class functions on $S_n$ to degree-$n$ symmetric functions, with irreducible characters going to Schur functions, is the bridge developed in the same chapter.

Estimated time

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