# 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"? – Denis Pankratov Jan 12 '16 at 1:44
• Let's say that total degree is bounded by some polynomial. – ivmihajlin 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? – chazisop 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.