Given a set of polynomials as an algebraic circuit, we study the problem of testing if the ideal generated by these polynomials is prime. This is a generalisation of the problem of testing if the polynomials have a common solution. It is also a generalisation of the problem of testing if a polynomial is absolutely irreducible. Assuming GRH, we show that for certain classes of ideals, namely radical ideals and complete intersection ideals, the problem of testing primality lies in the third level of the polynomial hierarchy. This is almost optimal, since the problems are NP-hard. Previously, the best known bound for these problems was PSPACE.

 

Our method is a vast generalisation of the method used by Koiran to show that satisfiability of polynomials is in PH. We study how algebraic and geometric properties of ideals such as irreducibility and dimension behave under mod p reduction of coefficients. We give new effective versions of classical results from algebraic geometry and commutative algebra that may have independent applications.

 

This is joint work with Rafael Oliveira and Nitin Saxena.

 

Short Bio: Abhibhav is a fourth year PhD student at the University of Waterloo, advised by Rafael Oliveira. His research interests include algebraic complexity theory, and computational algebraic geometry and commutative algebra.