Algebraic Independence and Blackbox Identity Testing

Abstract

Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. The transcendence degree (trdeg) of a set f1, ..., fm ⊂ Fx1, ..., xn of polynomials is the maximal size r of an algebraically independent subset. In this paper we design blackbox and efficient linear maps ϕ that reduce the number of variables from n to r but maintain trdeg{ϕ(fi)}i = r, assuming fi's sparse and small r. We apply these fundamental maps to solve several cases of blackbox identity testing: 1. Given a circuit C and sparse subcircuits f1, ..., fm of trdeg r such that D := C(f1, ..., fm) has polynomial degree, we can test blackbox D for zeroness in poly(size(D))r time. 2. Define a ΣΠΣΠδ(k, s, n) circuit C to be of the form Σi=1k Πj=1s fi,j, where fi,j are sparse n-variate polynomials of degree at most δ. For k = 2, we give a poly (δsn)δ2 time blackbox identity test. 3. For a general depth-4 circuit we define a notion of rank. Assuming there is a rank bound R for minimal simple ΣΠΣΠδ(k, s, n) identities, we give a poly(δsnR)Rkδ2 time blackbox identity test for ΣΠΣΠδ(k, s, n) circuits. This partially generalizes the state of the art of depth-3 to depth-4 circuits.The notion of trdeg works best with large or zero characteristic, but we also give versions of our results for arbitrary fields.