Polynomials of low degree that clone polynomials of higher degree 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]?$$
 A: Suppose $g\in \mathbb R[x_1,\dots,x_{16}]$ is a polynomial with the same vanishing set as $f$ within $\{0,1\}^{16}$. Define $h\in \mathbb R[x_1,\dots,x_{16}]$ to be the polynomial you obtain by changing every occurrence of $x_i^d$ in the monomials appearing in $g$ to $x_i$. Therefore $h$ is a multilinear polynomial with the same vanishing set as $g$ within $\{0,1\}^{16}$, and moreover $\deg (h)\le \deg(g)$.
Next we can show that any such multilinear polynomial must have degree at least $4$, implying $\deg g\geq 4$. Let's expand
$$h=\sum_{S\subset \{1,\dots 16\}}c_Sx_S,$$
where $x_S=\prod_{i\in S} x_i$. You can notice that $c_{\emptyset}=0$, denote by $e_I$ the $\{0,1\}$ characteristic vector of $I$. Suppose $|I|\le 3$ and we have checked the coefficients $c_J=0$ for all $J\subset I$. Since $|I|\le 3$ we have $f(e_I)=0$ so we must also have $h(e_I)=0$. We can check that $h(e_I)=\sum_{J\subseteq I} c_Jx_J=c_I$ and conclude that $c_I=0$. This implies the desired claim. 
The argument above is essentially the one used in "Covering the Cube by Affine Hyperplanes", by Alon and Furedi, to answer a question of Komjath.
A: 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$). 
A: Here's a very general result that solves your problem. 
Let $F$ be a field, and let $A = A_1 \times \dots \times A_n$ be a finite grid in $F^n$. A polynomial $P \in F[t_1, \dots, t_n]$ is called $A$-reduced if for all $i$ we have $\deg_{t_i} P < |A_i|$. 
Then we can show that for every polynomial $P \in F[t_1, \dots, t_n]$, there exists a unique reduced polynomial $\widehat P \in F[t_1, \dots, t_n]$, such that $P(x) = \widehat P(x)$ for all $x \in A$. 
This idea is used in proving the Chevalley-Warning theorem and in proving Combinatorial Nullstellensatz. For full details, and further generalisations see this paper by Pete L. Clark: The Combinatorial Nullstellensätze Revisited.
