Special-case algorithms for blackbox radical membership, nullstellensatz and transcendence degree

Abstract

Radical membership testing, resp. its special case of Hilbert's Nullstellensatz (HN), is a fundamental computational algebra problem. It is NP-hard; and has a famous PSPACE algorithm due to effective Nullstellensatz bounds. We identify a useful case of these problems where practical algorithms, & improved bounds, could be given---When transcendence degree (tr.deg) r of the input polynomials is smaller than the number of variables n. If d is the degree bound on the input polynomials, then we solve radical membership (even if input polynomials are blackboxes) in around dr time. The prior best was > dn time (always, dn ≥ dr). Also, we significantly improve effective Nullstellensatz degree-bound, when r ≪ n. Structurally, our proof shows that these problems reduce to the case of r + 1 polynomials of tr.deg ≥ r. This input instance (corresponding to none or a unique annihilator) is at the core of HN's hardness. Our pro of methods invoke basic algebraic-geometry.