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?