# Randomized identity-testing for high degree polynomials?

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

• if you don't have any bounds on the degree, isn't there a polynomial which realizes any specific function? – Peter Shor Oct 21 '14 at 22:47
• @PeterShor : $\:$ The OP does have a bound on the degree; it can't be more than 2 to [the number of gates in $\hspace{.04 in}f\hspace{.02 in}$]. $\;\;\;\;$ – user6973 Oct 22 '14 at 0:40
• 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 Oct 22 '14 at 11:28
• 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 Oct 22 '14 at 16:58
• @GeoffreyIrving Thanks! Is it easy to efficiently check $(x^p - 1) | f$ when $f$ is given as a circuit? – user94741 Oct 22 '14 at 18:04

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 implies that such $a$ always exists for $p\ge(1+o(1))2^{2n}n^2$.
• 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 Oct 25 '14 at 20:55
• 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 Oct 26 '14 at 17:57