Abstract:
A basic fact in linear algebra is that the image of the curve $f(x)=(x^1,x^2,x^3,...,x^m)$, say over $C$, is not contained in any $m-1$ dimensional affine subspace of $C^m$. In other words, the image of $f$ is not contained in the image of any polynomial-mapping $G:C^{m-1} ---> C^m$ of degree 1(that is, an affine mapping). Can one give an explicit example for a polynomial curve $f:C ---> C^m$, such that, the image of $f$ is not contained in the image of any polynomial-mapping $G:C^{m-1} ---> C^m$ of degree 2 ? We show that problems of this type are closely related to proving lower bounds for the size of general arithmetic circuits. For example, any explicit $f$ as above of degree up to $2^{m^{o(1)}}$, implies super-polynomial lower bounds for computing the permanent over $C$. More generally, we say that a polynomial-mapping $f:F^n ---> F^m$ is $(s,r)$-elusive, if for every polynomial-mapping $G:F^s ---> F^m$ of degree $r$, $Image(f)$ is not contained in Image(G)$. We show that for many settings of the parameters $n,m,s,r$, explicit constructions of elusive polynomial-mappings imply strong (up to exponential) lower bounds for general arithmetic circuits. Finally, for every $r < log n$, we give an explicit example for a polynomial-mapping $f:F^n ---> F^{n^2}$, of degree $O(r)$, that is $(s,r)$-elusive for $s = n^{1+\Omega(1/r)}$. We use this to construct for any $r$, an explicit example for an $n$-variate polynomial of total-degree $O(r)$, such that, any depth $r$ arithmetic circuit for this polynomial (over any field) is of size $> n^{1+\Omega(1/r)}$. In particular, for any constant $r$, this gives a constant degree polynomial, such that, any depth $r$ arithmetic circuit for this polynomial is of size $> n^{1+\Omega(1)}$. Previously, only lower bounds of the type $\Omega(n \cdot \lambda_r (n))$, where $\lambda_r (n)$ are extremely slowly growing functions (e.g., $\lambda_5(n) = \log^{*}n$, and $\lambda_7(n) = \log^* \log^{*}n$), were known for constant-depth arithmetic circuits for polynomials of constant degree.