Elusive functions and lower bounds for arithmetic circuits

A basic fact in linear algebra is that the image of the curve f(x)=(x¹,x²,x³,...,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 Γ: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 Γ:C^m-1 → C^m of degree 2? In this paper, 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 (with the right notion of explicitness implies super-polynomial lower bounds for computing the permanent over~C. More generally, we say that a polynomial-mapping f:Fⁿ → F^m is (s,r)-elusive, if for every polynomial-mapping Γ:F^s → F^m of degree r, Im(f) ⊄ Im(Γ). 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ⁿ → Fⁿ², of degree O(r), that is (s,r)-elusive for s = n^1+Ω(1/r). We use this to construct for any r, an explicit example for an n-variate polynomial of total-degree O(r), with coefficients in {0,1,}such that, any depth r arithmetic circuit for this polynomial (over any field) is of size ≥ n^1+Ω(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+Ω(1). Previously, only lower bounds of the type Ω(n • λ_r (n)), where λ_r (n) are extremely slowly growing functions (e.g., λ₅(n) = log n, and λ₇(n) = log* log*n), were known for constant-depth arithmetic circuits for polynomials of constant degree.