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

In this work we consider representations of multivariate polynomials in F[x] of the form f(x) = Q1(x) +Q2(x) + . . .+Qs(x) , where the ei’s are positive integers and the Qi’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. Motivation. Let F be a field, F[x] be the set of n-variate polynomials over F and d ≥ 1 be an integer. For a polynomial f(x) ∈ F[x], we consider representations of the form f(x) = Q1 1 (x) +Q e2 2 (x) + . . .+Q es s (x), (1) where the Qi(x)’s are polynomials of degree at most d. We do this with an eye towards proving lower bounds for the number of summands s required to write some explicit polynomial f in the above form. Our motivation for this line of inquiry stems from some recent results and problems posed in the field of arithmetic complexity. Agrawal and Vinay [AV08] showed that proving exponential lower bounds for depth four arithmetic circuits implies exponential lower bounds for arbitrary depth arithmetic circuits. In our case, a representation of the form (1) above corresponds to computing f via a depth four ΣΠΣΠ arithmetic circuit where the bottommost layer of multiplication gates have fanin bounded by d and the second-last layer of multiplication gates actually consists of exponentiation gates of arbitrarily large degree (i.e. multiplication gates where all the incoming edges originate from a single node). Meanwhile Hrubes, Wigderson and Yehudayoff [HWY10] look at the situation where d = e1 = e2 = . . . = es = 2 and ask for a superlinear lower bound on the number of summands s for an explicit n-variate biquadratic polynomial f . They show that such a superlinear lower bound implies an exponential lower bound on the size of arithmetic circuits computing the noncommutative permanent. Finally Chen, Kayal and Wigderson [CKW11] pose the problem of proving lower bounds for bounded depth arithmetic circuits with addition and exponentiation gates. Our main theorem is a lower bound on the number of summands in any representation of the form (1) for an explicit polynomial. Theorem 1. (Lower bound for sum of powers). Let F be any field and F[x] be the ring of polynomials over the set of indeterminates x = (x1, x2, . . . , xn). Let e1, e2, . . . , es be positive integers and Q1, Q2, . . . , Qs ∈ F[x] be multivariate polynomials each of degree at most d. If Q1 1 +Q e2 2 + . . .+Q es s = (x1 · x2 · . . . · xn), then we must have that (log s) = Ω( n 2d ). In particular, if d is a constant then s = 2Ω(n). Remark 2. 1. The fact that the f in the lower bound above consists of a single monomial indicates above all the severe limitation of representations of the form (1). ∗Microsoft Research India, neeraka@microsoft.com 1 ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 81 (2012) 2. An upper bound of 2n/d is an easy corollary of Fischer [Fis94]. Specifically, let F be an algebraically closed field with char(F) > n. Then for all integers d ≥ 1 there exist polynomials Q1, Q2, . . . , Qs each of degree d such that Q1 1 +Q e2 2 + . . .+Q es s = (x1 · x2 · . . . · xn), and the number of summands s is at most 2n/d. Fischer [Fis94] gives an explicit set of 2m−1 linear forms `1, `2, . . . , `2m such that (y1 · y2 · . . . · ym) = ∑