Fundamental Theorem of Symmetric Polynomials

From ProofWiki
Jump to: navigation, search

Theorem

Let $K$ be a field, and $f$ a symmetric polynomial over $K$.


Then $f$ can be written uniquely as a polynomial in the elementary symmetric polynomials.


Proof


Let $p \in R := K[x_1,\ldots,x_n]$ be a symmetric polynomial, and denote by $\sigma_1,\ldots,\sigma_n$ the $n$ elementary symmetric polynomials. Let $<$ be the degree reverse lexicographic monomial order. If we designate by $LM(f)$ the leading monomial of any $f \in R$, that is to say the unique $<$-largest monomial appearing in $f$, then it is straightforward to verify that $LM(\sigma_k) = x_1 \cdots x_k$ for $1 \le k \le n$: for $k < n$, any other monomial appearing in $\sigma_k$ must contain a factor $x_j^{\alpha_1}$ with $j > k$ and $\alpha_1 > 0$, which makes it smaller than $x_1 \cdots x_k$ with respect to $<$. The case $k=n$ is trivial because $\sigma_n$ consists of only one monomial.

It follows the proof that $p$ may be written as a polynomial in $\sigma_1, \ldots, \sigma_k$. Firstly, since $p$ is symmetric, it must have the property $LM(p) = x_1^{a_1} \cdots x_n^{a_n}$ with $a_1 \ge a_2 \ge \ldots \ge a_n$. To see this, assume that $a_i > a_j$ for some $1 \le i < j \le n$. The monomial $x_1^{a_1} \cdots x_{i-1}^{a_{i-1}} \cdot x_i^{a_j} x_j^{a_i} \cdot x_{j+1}^{a_{j+1}} \cdots x_n^{a_n}$ must also appear in $p$, and if $a_i > a_j$ then it would be larger than $LM(p)$, a contradiction.

Now consider $\sigma := c \sigma_1^{a_1 - a_2} \cdot \sigma_2^{a_2-a_3} \cdot \ldots \cdot \sigma_{n-1}^{a_{n-1}-a_n} \cdot \sigma_n^{a_n}$, where $c$ is the coefficient of $LM(p)$ in $p$, and define $\bar{p} := p - \sigma$. Since \begin{align*} LM(\sigma) &= \prod_{i=1}^n LM(\sigma_i^{a_i - a_{i+1}}) \\ &= x_1^{a_1 - a_2} \cdot (x_1 x_2)^{a_2-a_3} \cdot \ldots \cdot (x_1 \ldots x_{n-1})^{a_{n-1} - a_n} \cdot (x_1 \ldots x_n)^{a_n} \\ &= x_1^{a_1} \ldots x_n^{a_n} \\ &= LM(p), \end{align*}

the leading monomials in the difference $\bar{p}$ cancel, and therefore $LM(\bar{p}) < LM(p)$. Iterate this method, and after finitely many steps one has decomposed $p$ into a polynomial $F \in K[y_1,\ldots,y_n]$ with $F(\sigma_1,\ldots,\sigma_n) = p$. (The termination of this algorithm follows immediately from Dickson's lemma.)