# 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}}\cdots x_{n}^{e_{n}}$ in $R[x_{1},\dots,x_{n}]$ to be $e_{1}+2e_{2}+\cdots+ne_{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 $cx_{1}^{e_{1}}\cdots x_{n}^{e_{n}}$ be the monomial term of maximal height in $f$. Consider the polynomial

 $g:=f-cs_{1}^{e_{n}-e_{n-1}}s_{2}^{e_{n-1}-e_{n-2}}\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},\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},\dots,s_{n}$, and it follows immediately that $f$ is also a polynomial in $s_{1},\dots,s_{n}$.

Title reduction algorithm for symmetric polynomials ReductionAlgorithmForSymmetricPolynomials 2013-03-22 12:11:17 2013-03-22 12:11:17 djao (24) djao (24) 6 djao (24) Proof msc 05E05 msc 12F10 height