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 in to be . 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 be a symmetric polynomial. We reduce into elementary symmetric polynomials by induction on the height of . Let be the monomial term of maximal height in . Consider the polynomial
where is the –th elementary symmetric polynomial in the variables . Then is a symmetric polynomial of lower height than , so by the induction hypothesis, is a polynomial in , and it follows immediately that is also a polynomial in .