On polynomials over finite fields?

208 Views Asked by At

Pick prime $q\in\Bbb Z$ such that $q>B^{3t}>(mB)^{2t}$.

Suppose I have a multilinear polynomial $g(x)\in \Bbb Z[x_1,\dots,x_n]$ of degree $t$ with $m^t$ non-zero coefficients that bound by $|B|>2$, I pick a set $S\subseteq \Bbb Z^n$ such that $|S|<\infty$ and each element of $S$ is bounded by $B$.

Let $\forall s\in S,\mbox{ }g(s)\in[-(mB)^t,(mB)^t]\bigcap\Bbb Z$ and $q\nmid g(s)$.

Let $h(x)=g^2(x)$. So $\forall s\in S,\mbox{ }h(s)\in[0,(mB)^{2t}]\bigcap\Bbb Z$ and coefficients of $h(x)$ are bound by $m^{2t}|B|^2$.

Consider $h(x)$ as element in $\Bbb F_{q}[x_1,\dots,x_n]$. Call this element $\hat{h}(x)$.

Hence $\hat{H}(x)=\hat{h}^{q-1}(x)$ always takes values in $\{0,1\}$ when evaluated on $S$ and has coefficients in $\{0,1\}$. Is this observation correct?

Now consider $\hat{H}(x)$ as sitting in $\Bbb Z[x]$ and call this polynomial $H(x)$.

Since $q>B^{3t}>(mB)^{2t}$, and we evaluate on $S$, $x_i^{q-1}$ can replaced by $x_i$ in $\hat{H}(x)$ where $x_i\in\{0,1\}$ now. Call this element as $\hat{H}_l(x)$ in $\Bbb F_{q}[x_1,\dots,x_n]$. $\hat{H}_l(x)$ and $\hat{H}(x)$ take same value (either $0$ or $1$) in $S$.

Call the $\hat{H}_l(x)$ when considered as an element in $\Bbb Z[x]$ as $H_l(x)$. Now we evaluate $H_l(x)$ in $\{0,1\}^n$.

Precisely, does $$H_l(x)=0\iff\hat{H}_l(x)=0\iff\hat{H}(x)=0 \iff H(x)=0$$$$\iff \hat{h}(x)=0\iff h(x)=0\iff g(x)=0$$ hold true when evaluated on $\{0,1\}^n$?

Is there a way to force the evaluations of some modification of $H_l(x)$ to $\{0,1\}$ when evaluated on $\{0,1\}^n$? Are there any studies of transferring results in polynomials over finite fields to polynomials over integer coefficients?