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...


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

