EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS

By the fundamental theorem of symmetric polynomials, if P ∈ ℚ[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 ℚ[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 ℚ[X1,…,Xn] seen as a module over the ring of symmetric polynomials, as well as for the computation of the Reynolds operator.