Evaluation properties of symmetric polynomials

By the fundamental theorem of symmetric polynomials, if P ∈ Q[X1,...,Xn] is symmetric, then it can be written P = Q(σ1,..., σn), where σ1,..., σn are the elementary symmetric polynomials in n variables, and Q is in Q[S1,..., Sn]. 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[X1,...,Xn] seen as a module over the ring of symmetric polynomials, as well as for the computation of the Reynolds operator.