0

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\}$.

francois
  • 69

1 Answers1

1

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.

Marc
  • 6,861
  • Thanks for your reply. I am aware of the general proof and the fact that it provides an algorithm for doing it in practice. But I was hoping there may be shortcuts or tricks specific to polynomials of only two variables.. – francois Mar 27 '15 at 08:15