The ideal membership problem and polynomial identity testing

AbstractGiven a monomial ideal I=〈m1,m2,…,mk〉 where mi are monomials and a polynomial f by an arithmetic circuit, the Ideal Membership Problem is to test if f∈I. We study this problem and show the following results.(a)When the ideal I=〈m1,m2,…,mk〉 for a constant k, we can test whether f∈I in randomized polynomial time. This result holds even for f given by a black-box, when f is of small degree.(b)When I=〈m1,m2,…,mk〉 for a constant kandf is computed by a ΣΠΣ circuit with output gate of bounded fanin, we can test whether f∈I in deterministic polynomial time. This generalizes the Kayal–Saxena result [11] of deterministic polynomial-time identity testing for ΣΠΣ circuits with bounded fanin output gate.(c)When k is not constant the problem is coNP-hard. We also show that the problem is upper bounded by coMAPP over the field of rationals, and by coNPModpP over finite fields.(d)Finally, we discuss identity testing for certain restricted depth 4 arithmetic circuits.For ideals I=〈f1,…,fℓ〉 where each fi∈F[x1,…,xk] is an arbitrary polynomial but k is a constant, we show similar results as (a) and (b) above