An Extension of Strassen’s Degree Bound

Abstract

With every set $P_1 , \cdots ,P_m $ of multivariate polynomials we associate in a natural way several algebraic varieties, i.e., irreducible Zariski-closed sets. The degree of each of these closed sets can be nicely bounded in terms of the number $L_{ns} (P_1 , \cdots ,P_m )$ of nonscalar operations which are necessary to evaluate $P_1 , \cdots ,P_m $. We establish lower bounds $L_{ns} (P) \geqq \Omega (k\lg n)$ for single specific polynomials P of degree n, depending on $O(k)$ variables with 0, 1-coefficients. Typical examples are $L_{ns} (\sum_{i = 1}^k {x_i^n y^i } ) \geqq \frac{1} {2}k\lg n$, $L_{ns} (\sum_{i = 1}^k {(x_1 + x_2 + \cdots + x_i )^n y_i } ) > \frac{1}{2}k\lg n$, provided $k < n^{1/2} $. By our method and evaluating the degree of closed sets one obtains lower bounds $L_{ns} (P) > \Omega (k\lg n)$ for “almost all” polynomials P of degree n depending on k variables, $k \ll n$. These lower bounds hold for any field characteristic.