In this work we consider representations of multivariate polynomials in F[x] of the form f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s}, where the e_i's are positive integers and the Q_i's are arbitary multivariate polynomials of degree at most d. We give an explicit n-variate polynomial f of degree n such that any representation of the above form for f requires the number of summands s to be 2^{\Omega(n/d)}.

The lower bound has been improved and it now asymptotically matches the upper bound. Some other relevant references have been added.

In this work we consider representations of multivariate polynomials in F[x] of the form f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s}, where the e_i's are positive integers and the Q_i's are arbitary multivariate polynomials of bounded degree. We give an explicit n-variate polynomial f of degree n such that any representation of the above form for f requires the number of summands s to be 2^{\Omega(n)}.