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})$.

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 degree $<4$ polynomial $g$ such that $$g(\mathcal{Z})=f(\mathcal{Z})=0$$ $$0\not\in(\mathcal{C}\backslash\mathcal{Z}) ?$$

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?