Computing generators of the ideal of a smooth affine algebraic variety

AbstractLet K be an algebraically closed field, V⊂Kn be a smooth equidimensional algebraic variety and I(V)⊂K[x1,…,xn] be the ideal of all polynomials vanishing on V. We show that there exists a system of generators f1,…,fm of I(V) such that m≤(n−dimV)(1+dimV) and deg(fi)≤degV for i=1,…,m. If char(K)=0 we present a probabilistic algorithm which computes the generators f1,…,fm from a set-theoretical description of V. If V is given as the common zero locus of s polynomials of degrees bounded by d encoded by straight-line programs of length L, the algorithm obtains the generators of I(V) with error probability bounded by ε within complexity s(ndn)O(1)log2(⌈1/ε⌉)L