My question is about theorems 4.1 and 4.2 in "Geometric Complexity Theory V".

The first theorem states that there exists an EXPSPACE algorithm for constructing h.s.o.p. for $\Delta[\text{det},m]$ (see definitions in the paper) on $\mathbb{C}$ (in fact on an arbitrary algebraically closed field of characteristic zero).

The second provides a probabilistic poly-time Monte-Carlo algorithm for the same problem.

Can theses results be extended to an algebraic closure of a finite field?

As I understand, it is possible because Hilbert’s Nullstellensatz problem belongs to PSPACE in this case too. Heintz and Schnorr theorem also holds for fields of arbitrary characteristic...


1 Answer 1


I believe the answer is yes. The only part I haven't checked carefully is:

  • The argument in the middle of Theorem 4.2 using the complex topology, and the fact that the Zariski closure = complex closure for Zariski-constructible sets over $\mathbb{C}$. This part of the argument should be replaceable by the standard algebraic technique of using Laurent series, though as I said, I haven't checked this carefully.

In Theorems 4.1 and 4.2, it seems the only other place characteristic zero is really used is the $\mathsf{EXPH}$ part of Theorem 4.1 (assuming GRH). This uses Koiran's result that, assuming GRH, Hilbert's Nullstellensatz is in $\mathsf{PH}$. Koiran's result relies pretty heavily on characteristic zero (since it considers the solutions of the system of equations modulo many different primes $p$). This is not needed to get the $\mathsf{EXPSPACE}$ part of Theorem 4.1, however, only the $\mathsf{EXPH}$ part (assuming GRH).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.