3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm not sure that it matters, but this polynomial is invariant under $S_4\wr S_4$, not just $S_4^4$. $\endgroup$ – Noah Stein Dec 16 '14 at 3:10
  • $\begingroup$ @NoahStein I am not much familiar with wreath product. could you explicitly comment the action? $\endgroup$ – 1.. Dec 16 '14 at 3:34
  • $\begingroup$ is the coefficient ring $\mathbb{Z}/2\mathbb{Z}$? $\endgroup$ – Pietro Majer Dec 16 '14 at 4:22
  • 1
    $\begingroup$ updated to clarify ring. $\endgroup$ – 1.. Dec 16 '14 at 4:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Ryan Budney Dec 16 '14 at 4:43
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ (I only now realize there is another answer; sorry) $\endgroup$ – Pietro Majer Dec 16 '14 at 8:30
  • 1
    $\begingroup$ Yes, I used the same notation as in your post, $x:=(x_1,\dots,x_{16})$ $\endgroup$ – Pietro Majer Dec 16 '14 at 8:32
  • 1
    $\begingroup$ 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})$ $\endgroup$ – Pietro Majer Dec 16 '14 at 8:35
  • $\begingroup$ nice answer I like it. $\endgroup$ – 1.. Dec 16 '14 at 8:38
  • 1
    $\begingroup$ 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$ $\endgroup$ – Pietro Majer Dec 16 '14 at 8:55
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – 1.. Dec 16 '14 at 6:23
  • $\begingroup$ 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. $\endgroup$ – Gjergji Zaimi Dec 16 '14 at 6:37
  • $\begingroup$ 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? $\endgroup$ – 1.. Dec 16 '14 at 6:45
  • $\begingroup$ 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)? $\endgroup$ – 1.. Dec 16 '14 at 21:51
  • 1
    $\begingroup$ @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. $\endgroup$ – Gjergji Zaimi Dec 16 '14 at 22:30
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.