Assume I am given a polynomial of two variables by the list of its coefficients, $P(X,Y)=\sum_{i,j}C_{ij}X^i Y^j$, and that this polynomial is symmetric, i.e. $C_{ij}=C_{ji}$.
I am looking for an efficient algorithm for rewriting this polynomial on the basis of the elementary symmetric polynomials $\{X+Y,XY\}$.
Hint: Note that if $i\ge j$, then $C_{ij}(X+Y)^{i-j}(XY)^j$ has $C_{ij}X^iY^j$ as its highest term in the lexicographic ordering. Moreover it is symmetric, thus the difference between your starting polynomial and this symmetric polynomial is symmetric too. Now try to find the algorithm in an inductive type of way.
By the way, the algorithm is usually the proof that any symmetric polynomial can be written as polynomial in the elementary symmetric polynomials.