9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ if you don't have any bounds on the degree, isn't there a polynomial which realizes any specific function? $\endgroup$ – Peter Shor Oct 21 '14 at 22:47
  • $\begingroup$ @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}$]. $\;\;\;\;$ $\endgroup$ – user6973 Oct 22 '14 at 0:40
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Oct 22 '14 at 11:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Geoffrey Irving Oct 22 '14 at 16:58
  • 1
    $\begingroup$ @GeoffreyIrving Thanks! Is it easy to efficiently check $(x^p - 1) | f$ when $f$ is given as a circuit? $\endgroup$ – user94741 Oct 22 '14 at 18:04
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Oct 25 '14 at 20:55
  • $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Oct 26 '14 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.