# How to find a non-zero point of a non-zero polynomial of low degree?

Given a circuit that computes a polynomial $P(x_1 \dots x_n)$ of low formal degree over some large field $\mathbb{F}$. Moreover, given a point $X \in \mathbb{F}^n$, such that $P(X) \neq 0$. Can one deterministically find another point $X' \neq X$, such that $P(X') \neq 0$.

Basically, it is a standard Polynomial identity testing with only one new twist: we know that the solution exists. You can say that it is in some sense problem from $FRP \cap PPP$ (this is very informal statement, I am not sure that this problem is in $PPP$, but it has the same flavor).

• How low is "low degree"? Jan 12 '16 at 1:44
• Let's say that total degree is bounded by some polynomial. Jan 12 '16 at 2:04

If ​ (ceil(degree/n))+1 ​ is "large", then there doesn't actually need to be such an X$\hspace{.02 in}$'.
$\Bigg(\hspace{-0.08 in}$The polynomial can be $\;\;\; \displaystyle\prod_{i\hspace{.02 in}\in \hspace{.02 in}\text{coordinates}} \: \left(\displaystyle\prod_{c\hspace{.02 in}\in (\mathbb{F}\hspace{.03 in}-\{0\})} (x_{\hspace{.02 in}i}-c)\hspace{-0.07 in}\right) \;\;\;$ and X can be the origin.$\hspace{-0.08 in}\Bigg)$

If "large" means larger than 1 plus [the minimum over the variables of the degree in that variable], then there's a uniform NC$^0$ algorithm that will, with no access to the polynomial, with neither
bit operations nor field operations nor equality tests on field elements ($\hspace{.03 in}$just copying them and
moving them around), output a polynomial-length list of elements of $\mathbb{F}^n$ such that at least one
of those elements is such an X'. ​ (When B is an upper bound on the bracketed expression from
the previous sentence, the algorithm will have B+2 distinct hard-coded field elements and output the ​ n$\cdot$(B+2) ​ results of replacing one of X's coordinates with one of the B+2 field elements.)

Thus, you need to either consider fields of "intermediate" size, or allow polynomials of
large (superpolynomial) degree. ​ (Arithmetic circuits can easily have exponential degree.)

A problem that's closer to canonical for ​ FRP ∩ PPP ​ (and is actually obviously in PPP) is

Input: ​ ​ ​ A (circuit encoding a) function ​ f : {0,1}n+1 -> {0,1}n
and a (circuit encoding a) function ​ g : {0,1}n -> {0,1}n+1

Correct Outputs: ​ ​ ​ elements x of {0,1}n+1 such that ​ g(f(x)) ≠ x

.

• It seems as there's some problem with the formatting but I'm not sure what you were aiming for. Can you make an edit to make your answer easier to read? Jan 12 '16 at 12:49

This does not directly answer your question, but if $f$ is $n$-variate, and is known to have partial degrees at most $D$ and at most $T$ terms, and $\mathbb{F}$ is known to contain an element $\omega$ of multiplicative order exceeding $D$, then we cannot have $f(\omega^i, \dots, \omega^i)=0$ for $i=0,1,\dots,2T-1$ by Prony's method / BCH decoding / Ben-Or Tiwari algorithm.

Zippel calls your problem the zero avoidance problem.