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

• I'm not sure that it matters, but this polynomial is invariant under $S_4\wr S_4$, not just $S_4^4$. – Noah Stein Dec 16 '14 at 3:10
• @NoahStein I am not much familiar with wreath product. could you explicitly comment the action? – 1.. Dec 16 '14 at 3:34
• is the coefficient ring $\mathbb{Z}/2\mathbb{Z}$? – Pietro Majer Dec 16 '14 at 4:22
• updated to clarify ring. – 1.. Dec 16 '14 at 4:35
• The wreath product means not only the permutations of the form $x_i \longmapsto x_{i+4}$ but also things like $x_i \longmapsto x_{i+1}$, i.e. you can permute the groups of four, but inside the groups of four you can also permute freely. – Ryan Budney Dec 16 '14 at 4:43

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

• (I only now realize there is another answer; sorry) – Pietro Majer Dec 16 '14 at 8:30
• Yes, I used the same notation as in your post, $x:=(x_1,\dots,x_{16})$ – Pietro Majer Dec 16 '14 at 8:32
• Here $e_k$ is the k-th element of the standard basis, so $x+e_k=(x_1,x_2,\dots,x_k+1,\dots,x_{16})$ – Pietro Majer Dec 16 '14 at 8:35
• nice answer I like it. – 1.. Dec 16 '14 at 8:38
• Yes, in other words the sum is over all $\epsilon=\sum_{j\in R}e_j$, and $R$ varies among the $2^4$ subsets of $S$ – Pietro Majer Dec 16 '14 at 8:55

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.

• Also the proof may not work if we had $$f(x_1,\dots,x_{24})=(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})(x_{17}+x_{19}+x_{19}+x_{20})(x_{21}+x_{22}+x_{23}+x_{24})\in\Bbb R[x]$$ or $$f(x_1,\dots,x_{24})=(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}+x_{17}+x_{18})(x_{19}+x_{20}+x_{21}+x_{22}+x_{23}+x_{24})\in\Bbb R[x]$$ correct? – 1.. Dec 16 '14 at 6:23
• The proof would work the same way for all such polynomials. Try to work out an example by hand, the argument is much simpler than my notation makes it seem. – Gjergji Zaimi Dec 16 '14 at 6:37
• Yeah you seem correct. My understanding was that $|S|\leq 3$ comes from the fact that $f=0$ if $3$ or less variables are set. It seems the same idea will work for both polynomials(for the first polynomial you can take $|S|\leq 5$ and for the second you can take $|S|\leq3$). But could you clarify the induction step further? – 1.. Dec 16 '14 at 6:45
• Would the idea work if we had $(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})$ (some terms have negative sign)? – 1.. Dec 16 '14 at 21:51
• @Turbo it works for any product of linear forms. This is essentially the argument Alon used to prove the Komjath conjecture about covering the hypercube with hyperplanes. – Gjergji Zaimi Dec 16 '14 at 22:30

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.