Testing polynomials which are easy to compute (Extended Abstract)

@[x 1 ,..,x n ] of degree ≤d which can be evaluated with ≤v nonscalar steps can be embedded into a Zariski-closed affine set W(d,n,v),dim W(d,n,v)≤(v+1 +n) 2 and deg W(d,n,v)≤(2vd) (v+1+n) 2 . As a consequence we prove that for u:e 2v(d+1) 2 and s:e 6(v+1+n) 2 there exist a 1 ,..,a s e [u] n e {1,2,..,u} n such that for all polynomials PeW(d,n,v):P(a 1 ) e p(a 2 ) e...e p(a s ) e O implies PXO. This means that a 1 ,...,a s is a correct test sequence for a zero test on all polynomials in W(d,n,v). Moreover, “almost every” sequence a 1 ,..,a s e[u] n is such a correct test sequence for W(d,n,v). The existence of correct test sequences a 1 ,..,a s e [u] n is established by a counting argument without constructing a correct test sequence. We even show that it is beyond the known methods to establish (i.e. to construct and to prove correctness) of such a short correct test sequence for W(d,n,v). We prove that given such a short, correct test sequence for W(d,n,v) we can efficiently construct a multivariate polynomial Pe