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]?$$