__
Revision #1 to TR12-081 | 7th September 2012 09:17
__
#### An exponential lower bound for the sum of powers of bounded degree polynomials

**Abstract:**
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)}$.

**Changes to previous version:**
The lower bound has been improved and it now asymptotically matches the upper bound. Some other relevant references have been added.

__
TR12-081 | 26th June 2012 10:25
__

#### An exponential lower bound for the sum of powers of bounded degree polynomials

**Abstract:**
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)}$.