reduction algorithm for symmetric polynomials

We give here an algorithm for reducing a symmetric polynomial into a polynomial in the elementary symmetric polynomials.

We define the height of a monomial $x_1^{e_1}\mathrm{\cdots }{x}_n^{e_n}$ in $R[x_1,\mathrm{\dots },x_n]$ to be $e_1+2e_2+\mathrm{\cdots }+n{e}_n$. The height of a polynomial is defined to be the maximum height of any of its monomial terms, or 0 if it is the zero polynomial.

Let $f$ be a symmetric polynomial. We reduce $f$ into elementary symmetric polynomials by induction on the height of $f$. Let $c{x}_1^{e_1}\mathrm{\cdots }{x}_n^{e_n}$ be the monomial term of maximal height in $f$. Consider the polynomial

$$g:=f-c{s}_1^{e_n-e_{n-1}}{s}_2^{e_{n-1}-e_{n-2}}\mathrm{\cdots }{s}_{n-1}^{e_2-e_1}{s}_n^{e_1}$$

where $s_k$ is the $k$–th elementary symmetric polynomial in the $n$ variables $x_1,\mathrm{\dots },x_n$. Then $g$ is a symmetric polynomial of lower height than $f$, so by the induction hypothesis, $g$ is a polynomial in $s_1,\mathrm{\dots },s_n$, and it follows immediately that $f$ is also a polynomial in $s_1,\mathrm{\dots },s_n$.

Title	reduction algorithm for symmetric polynomials
Canonical name	ReductionAlgorithmForSymmetricPolynomials
Date of creation	2013-03-22 12:11:17
Last modified on	2013-03-22 12:11:17
Owner	djao (24)
Last modified by	djao (24)
Numerical id	6
Author	djao (24)
Entry type	Proof
Classification	msc 05E05
Classification	msc 12F10
Defines	height