Skip to Main content Skip to Navigation
Journal articles

Evaluation properties of symmetric polynomials

Abstract : By the fundamental theorem of symmetric polynomials, if $P \in \Q[X_1,\dots,X_n]$ is symmetric, then it can be written $P=Q(\sigma_1,\dots,\sigma_n)$, where $\sigma_1,\dots,\sigma_n$ are the elementary symmetric polynomials in $n$ variables, and $Q$ is in $\Q[S_1,\dots,S_n]$. We investigate the complexity properties of this construction in the straight-line program model, showing that the complexity of evaluation of $Q$ depends only on $n$ and on the complexity of evaluation of $P$. Similar results are given for the decomposition of a general polynomial in a basis of $\Q[X_1,\dots,X_n]$ seen as a module over the ring of symmetric polynomials, as well as for the computation of the Reynolds operator.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Pierrick Gaudry <>
Submitted on : Thursday, November 10, 2005 - 11:32:59 AM
Last modification on : Wednesday, September 16, 2020 - 4:04:41 PM
Long-term archiving on: : Friday, April 2, 2010 - 6:54:40 PM





Pierrick Gaudry, Eric Schost, Nicolas Thiéry. Evaluation properties of symmetric polynomials. International Journal of Algebra and Computation, World Scientific Publishing, 2006, 16 (3), pp.505 - 523. ⟨10.1142/S0218196706003128⟩. ⟨inria-00000629⟩



Record views


Files downloads