We prove an exponential lower bound for expressing a polynomial as a sum of product of low arity polynomials. Specifically, we show that for the iterated matrix multiplication polynomial, $IMM_{d, n}$ (corresponding to the product of $d$ matrices of size $n \times n$ each), any expression of the form
$$ IMM_{d, n} = \sum_{i=1}^{s} \quad \prod_{j=1}^{m} \quad Q_{ij}, $$
where the $Q_{ij}$'s are of arity at most $t \leq \sqrt{d}$ (i.e. each $Q_{ij}$ depends on at most $t$ variables), the number of summands $s$ must be at least $d^{\Omega\left( \frac{d}{t} \right)}$.


A special case of this problem where the $Q_{ij}$'s are further restricted to have degree at most one was posed as an open problem by Shpilka and Wigderson [SW99] and recently resolved in [KS15]. We show that a refinement of the argument in [KS15] yields the above-mentioned lower bound on s, regardless of the degrees of the $Q_{ij}$'s (and also regardless of $m$, the number of factors in each summand). Lower bounds for the same model were also obtained in an almost simultaneous but independent work by Kumar and Saraf [KS15b].