<ul>
<li><p>For the question of when does $p=0 \Rightarrow q=0$, randomness can indeed help, as follows. First, <a href="http://www4.ncsu.edu/~kaltofen/bibliography/89/Ka89_slpfac.pdf">factor $p$</a> (uses randomness when $p$ is given as a straight-line program; <a href="http://www.ams.org/mathscinet-getitem?mr=682664">doesn't need randomness if $p$ is given as a coefficient vector</a>). Let $\tilde{p}$ denote the square-free version of $p$ - that is, if $p=p_1^{k_1} p_2^{k_2} \dotsb p_\ell^{k_\ell}$ then $\tilde{p} = p_1 p_2 \dotsb p_\ell$. Then $q=0$ follows from $p=0$ iff $\tilde{p}$ divides $q$, which happens iff $q$ is of the form $q=p_1^{k'_1} \dotsb p_\ell^{k'_\ell} f$ with all of the $k'_j$ strictly positive. The latter can be checked by factoring $q$ (uses randomness, as before).</p></li>
<li><p>For the general question of $p_1=\dotsb=p_k=0 \Rightarrow q=0$, randomness seems not to help from the complexity perspective, as <a href="http://www.ams.org/mathscinet-getitem?mr=683204">this problem is $\mathsf{EXPSPACE}$-complete</a> (randomness may help in practice though...). </p></li>
<li><p>For the problem of telling whether the variety $\{\vec{x} : p_1(x)=\dotsb=p_k(x)=0\}$ is empty or not (for polynomials given by a list of monomials and coefficients - which is "sparse but not succinct", that is, not SLPs), randomness also seems to help: assuming GRH, this problem is in $\mathsf{RP}^{\mathsf{NP}}$ by a <a href="http://www.ams.org/mathscinet-getitem?mr=1422712">result of Koiran</a>. It is $\mathsf{NP}$-hard, and not known to be in $\mathsf{P}^{\mathsf{NP}}$.</p></li>
</ul>

CC BY-SA 3.0
2014-03-07T18:59:59.967Z
2014-03-07T18:59:59.967Z
Joshua Grochow
<p>If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether the equation is always true.  We can similarly decide if a single polynomial inequation is always true over $\mathbb{C}$, since $p(z_1,\ldots,z_n) \ne 0$ for all $z_i$ iff the polynomial is a nonzero constant.</p>

<p>Does the simplicity of randomized checking extend to any systems of multivariate polynomial equations?  In particular, is there a simple algorithm for deciding whether
$$p(z_1,\ldots,z_n) = 0 \implies q(z_1,\dots,z_n) = 0$$
where $p,q$ are straight line programs over $\mathbb{C}$ with integer coefficients?  I'm fairly sure randomness does not provide simple algorithms if we go to arbitrary systems of equations and inequations, but I'm curious where the boundary is between easy and hard.</p>

CC BY-SA 3.0
2014-03-07T18:43:55.857Z
Did you mean $q(z_1,\dotsc,z_n)=0$ on the RHS (you forgot the "=0")?
Joshua Grochow
<randomized-algorithms><algebra><algebraic-complexity><polynomials>
Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?
Geoffrey Irving
# Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?

(Asked by: username_0 on 2014-03-07)

If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether the equation is always true. We can similarly decide if a single polynomial inequation is always true over $\mathbb{C}$, since $p(z\_1,\ldots,z\_n) \ne 0$ for all $z\_i$ iff the polynomial is a nonzero constant.

Does the simplicity of randomized checking extend to any systems of multivariate polynomial equations? In particular, is there a simple algorithm for deciding whether
$$p(z\_1,\ldots,z\_n) = 0 \implies q(z\_1,\dots,z\_n) = 0$$
where $p,q$ are straight line programs over $\mathbb{C}$ with integer coefficients? I'm fairly sure randomness does not provide simple algorithms if we go to arbitrary systems of equations and inequations, but I'm curious where the boundary is between easy and hard.

**Tags:** randomized-algorithms, algebra, algebraic-complexity, polynomials

> **Comments:**
> **username_1**: Did you mean $q(z_1,\dotsc,z_n)=0$ on the RHS (you forgot the "=0")?  

---

## 1 answers

### Answer by username_1 on 2014-03-07. Score: 7 | Accepted answer

* For the question of when does $p=0 \Rightarrow q=0$, randomness can indeed help, as follows. First, [factor $p$](http://www4.ncsu.edu/~kaltofen/bibliography/89/Ka89_slpfac.pdf) (uses randomness when $p$ is given as a straight-line program; [doesn't need randomness if $p$ is given as a coefficient vector](http://www.ams.org/mathscinet-getitem?mr=682664)). Let $\tilde{p}$ denote the square-free version of $p$ - that is, if $p=p\_1^{k\_1} p\_2^{k\_2} \dotsb p\_\ell^{k\_\ell}$ then $\tilde{p} = p\_1 p\_2 \dotsb p\_\ell$. Then $q=0$ follows from $p=0$ iff $\tilde{p}$ divides $q$, which happens iff $q$ is of the form $q=p\_1^{k'\_1} \dotsb p\_\ell^{k'\_\ell} f$ with all of the $k'\_j$ strictly positive. The latter can be checked by factoring $q$ (uses randomness, as before).
* For the general question of $p\_1=\dotsb=p\_k=0 \Rightarrow q=0$, randomness seems not to help from the complexity perspective, as [this problem is $\mathsf{EXPSPACE}$-complete](http://www.ams.org/mathscinet-getitem?mr=683204) (randomness may help in practice though...).
* For the problem of telling whether the variety $\{\vec{x} : p\_1(x)=\dotsb=p\_k(x)=0\}$ is empty or not (for polynomials given by a list of monomials and coefficients - which is "sparse but not succinct", that is, not SLPs), randomness also seems to help: assuming GRH, this problem is in $\mathsf{RP}^{\mathsf{NP}}$ by a [result of Koiran](http://www.ams.org/mathscinet-getitem?mr=1422712). It is $\mathsf{NP}$-hard, and not known to be in $\mathsf{P}^{\mathsf{NP}}$.


---

