HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Thursday, November 10, 2005 - 11:32:59 AM
Last modification on : Tuesday, July 6, 2021 - 3:39:55 AM
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