A question on vectors represented by multilinear polynomials

37 Views Asked by At

Let the set of multilinear polynomials of degree atmost $t$ in $\Bbb Z[x_1,\dots,x_n]$ be $\Bbb Z^{t}[x_1,\dots,x_n]$.

Let $S=\{0,1\}^n$. Fix an ordering of $S$.

For every $f\in\Bbb Z^{t}[x_1,\dots,x_n]$, let $f(S)$ be the $2^n$ length vector of values obtained by evaluating $f$ on all points in $S$.

Let $\mathfrak F_{t}$ be the set of all vectors $f(S)$.

Show that there is a fixed $c\geq 2$ such that if $\exists w,w'\in\mathfrak F_{t}$ such that $$\langle w,w\rangle + \langle w',w'\rangle=\langle w+w',w+w'\rangle$$ then there exists $u\in\mathfrak F_{t^c}$ such that $$\langle w,w\rangle =\langle w, w\odot u\rangle$$$$\langle w',w'\rangle=\langle w', w'\odot (\Bbb 1 - u)\rangle$$ where $\Bbb 1$ is the length $2^n$ all $1$ vector and $\odot$ is the elementwise product.