Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals

A central question in mathematics and computer science is the question of determining whether a given ideal I is prime, which geometrically corresponds to the zero set of I, denoted Z(I), being irreducible. The case of principal ideals (i.e., m = 1) corresponds to the more familiar absolute irreducibility testing of polynomials, where the seminal work of (Kaltofen 1995) yields a randomized, polynomial time algorithm for this problem. However, when m > 1, the complexity of the primality testing problem seems much harder. The current best algorithms for this problem are only known to be in EXPSPACE. Such drastic state of affairs has prompted research on the primality testing problem (and its more general variants, the primary decomposition problem, and the problem of counting the number of irreducible components) for natural classes of ideals. Notable classes of ideals are the class of radical ideals, complete intersections (and more generally Cohen-Macaulay ideals). For radical ideals, the current best upper bounds are given by (B ürgisser & Scheiblechner, 2007) , putting the problem in PSPACE. For complete intersections, the primary decomposition algorithm of (Eisenbud, Huneke, Vasconcelos 1992) coupled with the degree bounds of (DFGS 1991), puts the ideal primality testing problem in EXP. In these situations, the only known complexity-theoretic lower bound for the ideal primality testing problem is that it is coNPhard for the classes of radical ideals, and equidimensional Cohen-Macaulay ideals. In this work, we significantly reduce the complexity-theoretic gap for the ideal primality testing problem for the important families of ideals I (namely, radical ideals and equidimensional Cohen-Macaulay ideals). For these classes of ideals, assuming the Generalized Riemann Hypothesis, we show that primality testing lies in Σ p 3 ∩ Π p 3 . This significantly improves the upper bound for these classes, approaching their lower bound, as the primality testing problem is coNP-hard for these classes of ideals. Another consequence of our results is that for equidimensional Cohen-Macaulay ideals, we get the first PSPACE algorithm for primality testing, exponentially improving the space and time complexity of prior known algorithms.