The fundamental theorem of symmetric polynomials states that for a symmetric polynomial f_Sym in C[x₁,x₂,...,x_n], there exists a unique "witness" f in C[y₁,y₂,...,y_n] such that f_Sym=f(e₁,e₂,...,e_n), where the e__i's are the elementary symmetric polynomials.
In this work, we study the arithmetic complexity L(f) of the witness f as a function of the arithmetic complexity L(f_Sym) of f_Sym. We show that the arithmetic complexity L(f) of f is bounded by poly(L(f_Sym),deg(f),n). Prior to this work, only exponential upper bounds were known for L(f). The main ingredient in our result is an algebraic analogue of Newton’s iteration on power series.
As a corollary of this result, we show that if VP is not equal to VNP then there are symmetric polynomial families which have super-polynomial arithmetic complexity. This is joint work with Markus Bläser.