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$
5
  • $\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, 2014 at 3:10
  • $\begingroup$ @NoahStein I am not much familiar with wreath product. could you explicitly comment the action? $\endgroup$
    – Turbo
    Dec 16, 2014 at 3:34
  • $\begingroup$ is the coefficient ring $\mathbb{Z}/2\mathbb{Z}$? $\endgroup$ Dec 16, 2014 at 4:22
  • 1
    $\begingroup$ updated to clarify ring. $\endgroup$
    – Turbo
    Dec 16, 2014 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$ Dec 16, 2014 at 4:43

3 Answers 3

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$
7
  • 1
    $\begingroup$ (I only now realize there is another answer; sorry) $\endgroup$ Dec 16, 2014 at 8:30
  • 1
    $\begingroup$ Yes, I used the same notation as in your post, $x:=(x_1,\dots,x_{16})$ $\endgroup$ Dec 16, 2014 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$ Dec 16, 2014 at 8:35
  • $\begingroup$ nice answer I like it. $\endgroup$
    – Turbo
    Dec 16, 2014 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$ Dec 16, 2014 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$
7
  • $\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$
    – Turbo
    Dec 16, 2014 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$ Dec 16, 2014 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$
    – Turbo
    Dec 16, 2014 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$
    – Turbo
    Dec 16, 2014 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$ Dec 16, 2014 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 and acknowledge you have read our privacy policy.

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