Theorem 1
Let
![$ P$](img11.gif)
be a symmetric polynomial (with integer coefficients)
in
![$ x_1, \dots, x_n$](img12.gif)
. Then
![$ P$](img11.gif)
can be expressed as a polynomial
(with integer coefficients) in
the elementary symmetric functions
![$ \sigma_1, \dots, \sigma_n$](img13.gif)
given
by
Proof.
The idea is to deal with the terms of
![$ P$](img11.gif)
``from the outside in''. That is,
we first deal with terms which are as ``unbalanced'' as possible.
We can write
We put an ordering on
![$ n$](img9.gif)
-tuples by saying that
![$ (a_1, \dots, a_n)
> (b_1, \dots, b_n)$](img19.gif)
if and only if
![$ na_1 + (n-1)a_2 + \cdots + a_n
> nb_1 + (n-1)b_2 + \cdots + b_n$](img20.gif)
.
Now sort the terms in decreasing order by
![$ na_1+(n-1)a_2+\cdots+a_n$](img21.gif)
.
Choose the biggest term
![$ (a_1, \dots, a_n)$](img22.gif)
and notice that the polynomial
has the same largest term, and the coefficient of that term is 1.
So subtract off
![$ c_{a_1,\dots,a_n}$](img24.gif)
times this product, and repeat.