Polynomials of low degree that clone polynomials of higher degree

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.