<p>It’s not exactly clear to me what is the input of the problem and how do you enforce the restriction $p=2^{\Omega(n)}$, however, under any reasonable formulation the answer is <em>no</em> for multivariate polynomials unless NP = RP, due to the reduction below.</p>

<p>Given a prime power $q$ in binary and a Boolean circuit $C$ (wlog using only $\land$ and $\neg$ gates), we can construct in polynomial time an arithmetic circuit $C_q$ such that $C$ is unsatisfiable iff $C_q$ computes an identically zero polynomial over $\mathbb F_q$ as follows: translate $a\land b$ with $ab$, $\neg a$ with $1-a$, and a variable $x_i$ with $x_i^{q-1}$ (which can be expressed by a circuit of size $O(\log q)$ using repeated squaring).</p>

<p>If $q=p$ is prime (which I don’t think actually matters) and sufficiently large, we can even make the reduction univariate: modify the definition of $C_p$ so that $x_i$ is translated with the polynomial
$$f_i(x)=((x+i)^{(p-1)/2}+1)^{p-1}.$$
On the one hand, $f_i(a)\in\{0,1\}$ for every $a\in\mathbb F_p$, hence if $C$ is unsatisfiable, then $C_p(a)=0$ for every $a$. On the other hand, assume that $C$ is satisfiable, say $C(b_1,\dots,b_n)=1$, where $b_i\in\{0,1\}$. Notice that
$$f_i(a)=\begin{cases}1&amp;\text{if $a+i$ is a quadratic residue (including $0$),}\\
0&amp;\text{if $a+i$ is a quadratic nonresidue.}\end{cases}$$
Thus, we have $C_p(a)=1$ if $a\in\mathbb F_p$ is such that
$$a+i\text{ is a quadratic residue }\iff b_i=1$$
for every $i=1,\dots,n$. Corollary 5 in <a href="http://www.jstor.org/stable/2153045" rel="nofollow">Peralta</a> implies that such $a$ always exists for $p\ge(1+o(1))2^{2n}n^2$.</p>

CC BY-SA 3.0
2014-10-25T20:55:47.567Z
The univariate reduction actually works for nonprime $q$ as well, as long as it is odd (and one can probably handle powers of $2$ in another way). Instead of the constants $1,\dots,n$, one can take any fixed sequence of $n$ distinct elements of the field; the required $a$ again exists if $q\ge2^{2n}n^2$ by essentially the same argument as in Peralta’s paper (the real work is in Weil’s bound on character sums, which holds for all finite fields).
Emil Jeřábek
CC BY-SA 3.0
2014-10-26T17:57:48.703Z
Ah, yes: if $q=2^k\ge2^n$, we can fix $\mathbb F_2$-linearly independent $\{a_i:i=1,\dots,n\}\subseteq\mathbb F_q$, and translate $x_i$ with $T(a_ix)$, where $T(x)=\sum_{j<k}x^{2^j}$ is the trace of $\mathbb F_q/\mathbb F_2$.
Emil Jeřábek
CC BY-SA 3.0
2014-10-23T12:06:29.850Z
2014-10-23T14:26:16.570Z
2014-10-23T14:26:16.570Z
Emil Jeřábek
<p>Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime. </p>

<p>Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with  time $\mbox{poly}(n)$ and error probability $\leq 1-1/\mbox{poly}(n)$, even if the degree is not a priori bounded? What if $f$ is univariate?</p>

<p>Note that you can efficiently test if $f$ is identically zero as a <em>formal</em> <em>expression</em>, by applying Schwartz-Zippel over a field of size say $2^{2|f|}$, because the maximum degree of $f$ is $2^{|f|}$.</p>

CC BY-SA 3.0
2014-10-21T22:47:47.093Z
if you don't have any bounds on the degree, isn't there a polynomial which realizes any specific function?
Peter Shor 
CC BY-SA 3.0
2014-10-22T11:28:51.570Z
I think that the crucial point of this question is that the field GF(p) is neither large enough to use the Schwartz–Zippel lemma to construct a randomized polynomial-time algorithm in a standard way, nor small enough (like GF(2)) to use arithmetization to construct a reduction from SAT in a standard way.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-22T16:58:26.733Z
In the univariate case, the question asks whether $x^p-1$ divides $f$, which can be checked in a larger field if that helps.  Not sure if that generalizes to multivariate.
Geoffrey Irving
CC BY-SA 3.0
2014-10-22T18:04:29.133Z
@GeoffreyIrving Thanks! Is it easy to efficiently check $(x^p - 1) | f$ when $f$ is given as a circuit?
user94741
<polynomials><arithmetic-circuits>
Randomized identity-testing for high degree polynomials?
user94741
# Randomized identity-testing for high degree polynomials?

(Asked by: username_0 on 2014-10-21)

Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime.

Can you test if $f$ is identically zero over $\mathbb{Z}\_p$, with time $\mbox{poly}(n)$ and error probability $\leq 1-1/\mbox{poly}(n)$, even if the degree is not a priori bounded? What if $f$ is univariate?

Note that you can efficiently test if $f$ is identically zero as a *formal* *expression*, by applying Schwartz-Zippel over a field of size say $2^{2|f|}$, because the maximum degree of $f$ is $2^{|f|}$.

**Tags:** polynomials, arithmetic-circuits
> **Comments:**
> **username_1**: if you don't have any bounds on the degree, isn't there a polynomial which realizes any specific function?  
> **username_2**: I think that the crucial point of this question is that the field GF(p) is neither large enough to use the Schwartz–Zippel lemma to construct a randomized polynomial-time algorithm in a standard way, nor small enough (like GF(2)) to use arithmetization to construct a reduction from SAT in a standard way.  
> **username_3**: In the univariate case, the question asks whether $x^p-1$ divides $f$, which can be checked in a larger field if that helps.  Not sure if that generalizes to multivariate.  
> **username_0**: @GeoffreyIrving Thanks! Is it easy to efficiently check $(x^p - 1) | f$ when $f$ is given as a circuit?  

---

## 1 answers

### Answer by username_4 on 2014-10-23. Score: 8 | Accepted answer

It’s not exactly clear to me what is the input of the problem and how do you enforce the restriction $p=2^{\Omega(n)}$, however, under any reasonable formulation the answer is *no* for multivariate polynomials unless NP = RP, due to the reduction below.

Given a prime power $q$ in binary and a Boolean circuit $C$ (wlog using only $\land$ and $\neg$ gates), we can construct in polynomial time an arithmetic circuit $C\_q$ such that $C$ is unsatisfiable iff $C\_q$ computes an identically zero polynomial over $\mathbb F\_q$ as follows: translate $a\land b$ with $ab$, $\neg a$ with $1-a$, and a variable $x\_i$ with $x\_i^{q-1}$ (which can be expressed by a circuit of size $O(\log q)$ using repeated squaring).

If $q=p$ is prime (which I don’t think actually matters) and sufficiently large, we can even make the reduction univariate: modify the definition of $C\_p$ so that $x\_i$ is translated with the polynomial
$$f\_i(x)=((x+i)^{(p-1)/2}+1)^{p-1}.$$
On the one hand, $f\_i(a)\in\{0,1\}$ for every $a\in\mathbb F\_p$, hence if $C$ is unsatisfiable, then $C\_p(a)=0$ for every $a$. On the other hand, assume that $C$ is satisfiable, say $C(b\_1,\dots,b\_n)=1$, where $b\_i\in\{0,1\}$. Notice that
$$f\_i(a)=\begin{cases}1&\text{if $a+i$ is a quadratic residue (including $0$),}\\
0&\text{if $a+i$ is a quadratic nonresidue.}\end{cases}$$
Thus, we have $C\_p(a)=1$ if $a\in\mathbb F\_p$ is such that
$$a+i\text{ is a quadratic residue }\iff b\_i=1$$
for every $i=1,\dots,n$. Corollary 5 in [Peralta](http://www.jstor.org/stable/2153045) implies that such $a$ always exists for $p\ge(1+o(1))2^{2n}n^2$.

> **Comments:**
> **username_4**: The univariate reduction actually works for nonprime $q$ as well, as long as it is odd (and one can probably handle powers of $2$ in another way). Instead of the constants $1,\dots,n$, one can take any fixed sequence of $n$ distinct elements of the field; the required $a$ again exists if $q\ge2^{2n}n^2$ by essentially the same argument as in Peralta’s paper (the real work is in Weil’s bound on character sums, which holds for all finite fields).  
> **username_4**: Ah, yes: if $q=2^k\ge2^n$, we can fix $\mathbb F_2$-linearly independent $\{a_i:i=1,\dots,n\}\subseteq\mathbb F_q$, and translate $x_i$ with $T(a_ix)$, where $T(x)=\sum_{j<k}x^{2^j}$ is the trace of $\mathbb F_q/\mathbb F_2$.  

---

