Symmetric polynomials, step by step

A polynomial in $x_1, \ldots, x_n$ is symmetric when permuting the variables leaves it unchanged: $x_1^2 + x_2^2 + x_3^2$ and $x_1 x_2 x_3 - 1$ are, $x_1^2 x_2$ is not, since swapping $x_1$ and $x_2$ turns it into $x_1 x_2^2$. The fundamental theorem of symmetric polynomials says that, over a field $F$, every symmetric polynomial can be written in exactly one way as a polynomial in a few basic ones, the elementary symmetric polynomials $e_1, \ldots, e_n$:

$$\begin{aligned} \operatorname{Sym}[X_n] &= F[e_1, \ldots, e_n] \\ &\cong F[y_1, \ldots, y_n]. \end{aligned}$$

Here $X_n$ is the set $\{x_1, \ldots, x_n\}$, $\operatorname{Sym}[X_n]$ is the ring of symmetric polynomials in $X_n$ with coefficients in $F$, and $F[y_1, \ldots, y_n]$ is a ring of polynomials in $n$ new variables. The equality says that every symmetric polynomial is a polynomial in the $e_i$; the isomorphism, which sends each $y_i$ to $e_i$, that it is one in exactly one way.

The usual proof is an algorithm, and a short one. I first implemented it in 2022, in a SageMath archive notebook; here it runs in your browser.

The elementary symmetric polynomials

Fix $n \in \NN^+$, the number of variables. The elementary symmetric polynomial of degree $d \geq 1$ is the sum of all the products of $d$ distinct variables,

$$e_d = \sum_{1 \leq i_1 < i_2 < \cdots < i_d \leq n} \underbrace{x_{i_1} \cdots x_{i_d}}_{d \text{ factors}},$$

and $e_0 = 1$. With three variables, for instance,

$$\begin{aligned} e_1 &= x_1 + x_2 + x_3, \\ e_2 &= x_1 x_2 + x_1 x_3 + x_2 x_3, \\ e_3 &= x_1 x_2 x_3, \end{aligned}$$

and $e_d = 0$ for every $d > n$, as there are not enough variables to choose from.

Ordering the monomials

The algorithm needs to know which term of a polynomial comes first. A monomial $x_1^{\alpha_1} \cdots x_n^{\alpha_n}$ is written $x^\alpha$, with $\alpha = (\alpha_1, \ldots, \alpha_n) \in \NN^n$, and monomials are ordered by the degree lexicographic order (deglex): first by total degree $\alpha_1 + \cdots + \alpha_n$, then, between monomials of the same degree, by the exponent of $x_1$, then by that of $x_2$, and so on. So $x_1^3 > x_1 x_2^2 > x_2^3 > x_1^2$, and in general $x_1 > x_2 > \cdots > x_n$. The leading term of a non-zero polynomial is its term with the largest monomial, and that monomial is its leading monomial.

Deglex is not just any way of ordering monomials: it is a monomial order, that is, a total order on the monomials such that

1. it is compatible with multiplication: if $x^\alpha < x^{\alpha'}$, then $x^\alpha x^\gamma < x^{\alpha'} x^\gamma$ for every monomial $x^\gamma$;
2. it is a well-order: every non-empty set of monomials has a smallest element. Equivalently, there is no infinite strictly decreasing sequence of monomials $x^{\alpha^{(1)}} > x^{\alpha^{(2)}} > x^{\alpha^{(3)}} > \cdots$.

Deglex has both properties. Multiplying by $x^\gamma$ adds the same amount to the degrees of $x^\alpha$ and $x^{\alpha'}$ and the same exponents to both, so neither comparison changes. And below any monomial there are only finitely many others, those of degree no larger than its own, so a strictly decreasing sequence has to stop.

The first property is what makes leading terms behave: the leading term of a product is the product of the leading terms. Every other product of a term of $g$ by a term of $h$ involves at least one smaller monomial, and multiplying keeps it smaller. The second property is what will make the algorithm stop.

One more fact is specific to symmetric polynomials: their leading monomial has non-increasing exponents, $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n$. If $x^\alpha$ appears with $\alpha_i < \alpha_{i+1}$, swapping $x_i$ and $x_{i+1}$ gives another monomial of the polynomial, and a larger one: so $x^\alpha$ was not the leading monomial.

Cancelling the leading term

Let $f$ be symmetric, with leading term $c \, x^\alpha$. The idea of the proof is to remove this term with a product of elementary symmetric polynomials: to find a finite sequence of exponents $b = (b_1, \ldots, b_n) \in \NN^n$ such that

$$e^b = e_1^{b_1} e_2^{b_2} \cdots e_n^{b_n}$$

has the same leading monomial $x^\alpha$. Then in $f - c \, e^b$ the two leading terms cancel.

Since leading terms multiply, the leading term $\operatorname{lt}(e^b)$ of $e^b$ is the product of those of its factors, and the leading term of $e_k$ is $x_1 x_2 \cdots x_k$, with coefficient $1$. The variable $x_i$ occurs in it exactly when $k \geq i$, so

$$\begin{aligned} \operatorname{lt}(e^b) &= \prod_{k=1}^{n} (x_1 x_2 \cdots x_k)^{b_k} \\ &= x_1^{b_1 + b_2 + \cdots + b_n} \, x_2^{b_2 + \cdots + b_n} \cdots x_n^{b_n}. \end{aligned}$$

For this to be $x^\alpha$, the exponents have to match, and $b$ must solve a triangular system:

$$\begin{aligned} \alpha_1 &= b_1 + b_2 + \cdots + b_n, \\ \alpha_2 &= b_2 + \cdots + b_n, \\ &\;\;\vdots \\ \alpha_n &= b_n. \end{aligned}$$

Subtracting each equation from the one above it leaves $b_i = \alpha_i - \alpha_{i+1}$, and the last one gives $b_n = \alpha_n$. So there is exactly one candidate, which we call $\beta(\alpha)$:

$$\beta(\alpha)_i = \begin{cases} \alpha_i - \alpha_{i+1} & \text{if } 1 \leq i < n, \\ \alpha_i & \text{otherwise.} \end{cases}$$

It is a valid sequence of exponents, with no negative entries, exactly when $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n$, which is what the leading monomial of a symmetric polynomial always satisfies. For instance, with $n = 3$ and leading monomial $x_1^3 x_2 x_3$, $\alpha = (3, 1, 1)$ gives $\beta(\alpha) = (2, 0, 1)$, and indeed $e_1^2 e_3 = (x_1 + x_2 + x_3)^2 \, x_1 x_2 x_3$ has leading monomial $x_1^2 \cdot x_1 x_2 x_3 = x_1^3 x_2 x_3$.

The algorithm

Given a symmetric polynomial $f$:

• if $f$ is $0$ or a constant, it already is a polynomial in the $e_i$, and there is nothing to do;
• otherwise, let $c \, x^\alpha$ be its leading term in deglex, and $b = \beta(\alpha)$. Then $f$ is $c \, e^b$ plus the expression in the $e_i$ of $f - c \, e^b$, where $e^b$ is expanded in the $x_i$; this one is found by running the algorithm again.

The polynomial $f - c \, e^b$ is still symmetric, being a difference of symmetric polynomials, and its leading monomial is smaller than $x^\alpha$: the two leading terms cancel, and every other term of $f$ and of $c \, e^b$ has a smaller monomial. Running the algorithm thus produces symmetric polynomials $f_0 = f, f_1, f_2, \ldots$ whose leading monomials strictly decrease. Deglex being a well-order, such a sequence cannot go on forever: after finitely many steps what is left is $0$, and the terms $c \, e^b$ collected along the way add up to $f$.

The expression is also unique. Suppose $f = P(e_1, \ldots, e_n) = Q(e_1, \ldots, e_n)$ for two polynomials $P, Q \in F[y_1, \ldots, y_n]$. Their difference $R = P - Q$ then satisfies $R(e_1, \ldots, e_n) = 0$, and it is enough to show that this forces $R = 0$, that is, that no non-zero polynomial vanishes when the $e_i$ are substituted for its variables (the $e_i$ are algebraically independent). Write

$$\begin{aligned} R &= \sum_{b \in S} c_b \, y^b, \\ R(e_1, \ldots, e_n) &= \sum_{b \in S} c_b \, e^b, \end{aligned}$$

where $S \subset \NN^n$ is the finite set of exponents whose coefficient $c_b$ is not zero, and suppose $S$ is not empty. Each $e^b$ has leading term $x^{\alpha(b)}$, with coefficient $1$ and $\alpha(b)_i = b_i + b_{i+1} + \cdots + b_n$, and distinct $b$ give distinct $\alpha(b)$, since $b$ is recovered from $\alpha(b)$ as $\beta(\alpha(b))$. Among the finitely many monomials $x^{\alpha(b)}$ with $b \in S$ there is therefore a largest one, $x^{\alpha(b^*)}$, reached by a single $b^* \in S$. It occurs in $c_{b^*} e^{b^*}$ with coefficient $c_{b^*}$; every other $e^b$ has only monomials up to its own leading monomial $x^{\alpha(b)}$, which is smaller than $x^{\alpha(b^*)}$, so it does not contain $x^{\alpha(b^*)}$ at all. The coefficient of $x^{\alpha(b^*)}$ in $R(e_1, \ldots, e_n)$ is then $c_{b^*} \neq 0$, against $R(e_1, \ldots, e_n) = 0$. So $S$ is empty, $R = 0$, and $P = Q$.

The calculator below shows each step: the leading term, $\alpha$ and $\beta(\alpha)$, and what is left, $f_i$. To keep long polynomials readable, they are grouped into orbits: $m_\lambda$ is the sum of the distinct monomials whose exponents are a rearrangement of $\lambda$, so that with $n = 3$

$$\begin{aligned} m_{(2,1)} = {} & x_1^2 x_2 + x_1^2 x_3 + x_1 x_2^2 \\ & + x_2^2 x_3 + x_1 x_3^2 + x_2 x_3^2. \end{aligned}$$

A polynomial is symmetric exactly when it is a combination of the $m_\lambda$, with $\lambda_1 \geq \cdots \geq \lambda_n$; the calculator lists them from the largest $x^\lambda$ down, so the first one contains the leading term. The calculator also computes this way: it never expands a product $e^b$, but multiplies by each $e_j$ directly on the coefficients of the orbits.

The polynomial must be symmetric. If it is not, the algorithm cannot end successfully: if it did, the polynomial would be a combination of symmetric polynomials, and so symmetric itself, ↯. The Not symmetric example shows where it breaks down: sooner or later the leading term has exponents that are not in non-increasing order, $\beta(\alpha)$ has a negative entry, and no product of the $e_i$ has that leading term.

Sums of powers

For the power sums $p_k = x_1^k + \cdots + x_n^k$ there is a more direct route, the Newton–Girard identities archive. They give $p_k$, for $k \geq 1$, in terms of the $e_i$ and of the previous power sums:

$$p_k = (-1)^{k+1} \Bigl( k \, e_k + \sum_{i=1}^{k-1} (-1)^i \, p_i \, e_{k-i} \Bigr),$$

where $e_i = 0$ for every $i > n$ (and $p_0 = n$, since $x_i^0 = 1$). Computing $p_1$, then $p_2$, and so on up to $p_k$, each from the ones before it, gives one expression; the general algorithm applied to $x_1^k + \cdots + x_n^k$ gives another. By uniqueness they must be the same polynomial, and their difference is indeed zero:

The discriminant

Now let

$$f(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_0$$

have roots $x_1, x_2, \ldots, x_n$ in $\CC$, each listed as many times as its multiplicity, so that $f(x) = (x - x_1) \cdots (x - x_n)$. The discriminant of $f$ is the product

$$\Delta(f) = \prod_{1 \leq i < j \leq n} (x_i - x_j)^2,$$

and it tells whether $f$ has a repeated root:

$$\exists \, i \neq j : x_i = x_j \iff \Delta(f) = 0.$$

It is easy to check that $\Delta(f)$ is a symmetric polynomial in the roots. Every permutation is a composition of transpositions, so it is enough to check that swapping two roots $x_i$ and $x_j$ leaves it unchanged:

• the factors that contain neither of them are untouched;
• the factors that contain only one of them are exchanged in pairs, $(x_i - x_k)^2$ with $(x_j - x_k)^2$, at most with the sign of the base changed, which the square takes away;
• the factor that contains both changes the sign of its base, $(x_i - x_j)^2$ becoming $(x_j - x_i)^2$, and is unchanged once squared.

So, by the fundamental theorem, $\Delta(f)$ can be written in exactly one way in terms of the elementary symmetric polynomials of the roots. But these are nothing but the coefficients of $f$, up to sign: expanding $(x - x_1) \cdots (x - x_n)$ and comparing with $f$,

$$e_i(x_1, \ldots, x_n) = (-1)^i a_{n-i}$$

for $0 \leq i \leq n$, with $a_n = 1$. Running the algorithm on $\prod_{i<j} (x_i - x_j)^2$ and substituting $(-1)^i a_{n-i}$ for each $e_i$ thus gives the discriminant of every monic polynomial of degree $n$ in terms of its coefficients, without knowing its roots. For $n = 2$ it is the familiar $\Delta = a_1^2 - 4 a_0$; for $n = 3$,

$$\begin{aligned} \Delta = {} & a_1^2 a_2^2 - 4 a_0 a_2^3 - 4 a_1^3 \\ & + 18 \, a_0 a_1 a_2 - 27 a_0^2, \end{aligned}$$

which for $x^3 + p x + q$ reduces to $-4p^3 - 27q^2$.

A polynomial whose leading coefficient $a_n$ is not $1$ has the same roots as $f / a_n$, which is monic; its discriminant is usually defined as $a_n^{2n-2} \, \Delta(f / a_n)$. The factor makes it a polynomial in $a_0, \ldots, a_n$ with integer coefficients, and it is zero exactly when $\Delta(f / a_n)$ is.

Below, the formula for the degree of the polynomial you type is computed with the algorithm and then evaluated at its coefficients. The first example, $(x - 1)^2 (x + 2) = x^3 - 3x + 2$, has a double root, so its discriminant is zero; the second, $(x - 1)(x + 1)(x + 3) = x^3 + 3x^2 - x - 3$, has three distinct roots, and a discriminant that is not zero.