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

<ul>
<li>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.</li>
</ul>

<p>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).</p>

CC BY-SA 3.0
2017-03-02T16:24:30.480Z
2017-03-02T16:24:30.480Z
Joshua Grochow
<p>My question is about theorems 4.1 and 4.2 in <a href="https://arxiv.org/abs/1209.5993" rel="noreferrer">"Geometric Complexity Theory V"</a>. </p>

<p>The first theorem states that there exists an <strong>EXPSPACE</strong> 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).</p>

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

<p>Can theses results be extended to an algebraic closure of a finite field?</p>

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

<gct>
Noether’s Normalization Lemma for finite fields
Alexey Milovanov
# Noether’s Normalization Lemma for finite fields

(Asked by: username_0 on 2017-03-02)

My question is about theorems 4.1 and 4.2 in ["Geometric Complexity Theory V"](https://arxiv.org/abs/1209.5993).

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

**Tags:** gct


---

## 1 answers

### Answer by username_1 on 2017-03-02. Score: 6 | Accepted answer

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


---

