Let $f(x\_1,\dots,x\_{16})=(x\_1+x\_2+x\_3+x\_4)(x\_5+x\_6+x\_7+x\_8)(x\_9+x\_{10}+x\_{11}+x\_{12})(x\_{13}+x\_{14}+x\_{15}+x\_{16})\in\Bbb R[x]$.


Let $\mathcal{Z}$ be the zero set of $f$ in $\mathcal{C\_{16}}=\{0,1\}^{16}$.


Total degree of $f$ is $4$.


Can one show there is no polynomial $g$ of degree $\mathsf{deg}(g)<4=\mathsf{deg}(f)$ such that $$z\in\mathcal{Z}\implies g(\mathcal{Z})=f(\mathcal{Z})=0$$
$$z\in\mathcal{C}\backslash\mathcal{Z}\implies g(z)\neq 0,f(z)\neq 0?$$


The group fixing the polynomial under permutation of coordinates is $S\_4\times S\_4\times S\_4\times S\_4$. May be there is a different polynomial of lower degree with a different symmetry group that does the job?




---


What about for dual forms $$f(x\_1,\dots,x\_{20})=x\_1x\_2x\_3x\_4x\_5- x\_6x\_7x\_8x\_9x\_{10}+x\_{11}x\_{12}x\_{13}x\_{14}x\_{15}-x\_{16}x\_{17}x\_{18}x\_{19}x\_{20}\in\Bbb R[x]?$$



Polynomials of low degree that clone polynomials of higher degree
Let $\{e\_k\}\_{1\le k\le 16}$ denote the standard basis of $\mathbb{R}^{16}$, and $x:=(x\_1,\dots,x\_{16})$. Let's consider the difference operator in the $k$-th variable, $\delta\_k:\mathbb{R}[x]\to\mathbb{R}[x ]$, that is $\delta\_kp(x):=p(x+e\_k)-p(x)$. So $$\delta\_{13}\delta\_9 \delta\_5 \delta\_1p(x)=\sum\_{\epsilon } (-1)^{|\epsilon|\_1}p(x+\epsilon\_i ),$$
the sum being extended over all $\epsilon\in\{0,1\}^{16}$ with support in the set $S:=\{1,5,9,13\}$: it vanishes if and only if $p$ is of the form $p=\sum\_{k\in S} p\_k$ for some $p\_k\in\mathbb{R}[x]$ with $\deg\_k p\_k=0 $, for any $k\in S$.
Now if $g\in \mathbb{R}[x]$ has $g^{-1}(0)\cap\{0,1\}^{16}=\mathcal{Z},$ we have $\delta\_{13}\delta\_9 \delta\_5 \delta\_1g(0)=g(e\_1+e\_5+e\_9+e\_{13})\neq0$, proving that $g$ contains a monomial of positive degree in all variables $x\_1, x\_5, x\_9,$ and $x\_{13}$ (and for the same reason, it must also contain any term of the expansion of $f$). 


