# A specific polynomial triplet question

Notation

$P_k[n]=\{$multilinear polynomials in $\Bbb R[x_1,x_2,\dots,x_{n-1},x_n]$ of total degree exactly $k\}$.

$k=1$ is just linear polynomials.

QUESTION

Is there a triplet $(p,f,g)\in (P_{k},P_1,P_1)$, with $k\in\{2,3,4\}$ such that $\forall s\in\{0,1\}^4,\mbox{ }$ following four conditions are satisfied? $$(I):p(s)\in\{0,1\}$$ $$(II):f(s),g(s)\in\Bbb R$$ $$(III):p(s)=0\iff{f(s)=0}$$ $$(IV):\mbox{ }p(s)=1\iff{g(s)=0}$$

Note above conditions imply $$\forall s\in\{0,1\}^4:p(s)=\frac{f(s)}{f(s)+g(s)}$$

Hence it seems above question at $k=2$ is same as following question:

Is there a $4$ variable total degree $2$ multilinear polynomial that agrees with ratios of a pair of total degree $1$ linear polynomials over $\{0,1\}^4$ with each evaluation on $\{0,1\}^4$ evaluating to $\{0,1\}$?

$\underline{\text{Conjecture: Answer to above question is negative with cases }k\in \{2,3,4\}}$.

I am unable to find an example in $(P_{2},P_1,P_1)$, $(P_{3},P_1,P_1)$, $(P_{4},P_1,P_1)$. Examples in these three cases (Of these easiest seems $k=2$) will be interesting.

Is it possible to extend following attempt to prove no triplet exists in $(P_{2},P_0,P_1),(P_{2},P_1,P_0)$ to above?

Note that $\forall s\in\{0,1\}^4$, $p(s)=\frac{f(s)}{f(s)+g(s)}$.

Case $(P_{2},P_1,P_0)$: $g$ is constant function. So $f$ will be $0$.

Case $(P_{2},P_0,P_1)$: $f$ is constant function. So $g$ will be $0$.

$p$ will be degree $0$.

This will prove no triplet exists in $(P_{2},P_0,P_1),(P_{2},P_1,P_0)$.

Is there a similar approach to $(P_{2},P_1,P_1)$, $(P_{3},P_1,P_1)$, $(P_{4},P_1,P_1)$?

Through tedious calculations if I possibly could show triplet in $(P_{2},P_1,P_1)$ cannot exist provided if $2$ coordinates will be $0$, degree $2$ polynonmial still remains degree $2$, then possibly we will be done.

Example: If $p\in P_{2}$ will be of form $$\sum_{i,j=1,i\neq j}^4a_{i,j}x_ix_j+\sum_{i=1}^4b_{i}x_i+c$$ then at $x_3,x_4=0$, $p$ reduces to $$a_{1,2}x_1x_2+\sum_{i=1}^2b_{i}x_i+c$$ then there could be a tedious path to show non-existence of triplets of said property.

It seems every $p\in P_{2}$ will remain degree $2$ with some projection $(x_i,x_j)=(0,0)$.

I seem to have tedious path which is very inelegant. Is calculations only approach possible to question which is short?

• @PietroMajer Your polynomial is not multilinear (you have $s_j^2$ term). – T.... Jan 13 '15 at 8:46
• Your first question (about the existence of a triplet) and your second question (about ratios) seem to be quite different. The first question is rather trivial, since the conditions are satisfied vacuously by any suitably generic choice of coefficients. – S. Carnahan Jan 13 '15 at 23:46
• @S.Carnahan Both related by $\forall s\in\{0,1\}^4,p(s)=\frac{f(s)}{f(s)+g(s)}$, $f,g$ is degree $1$ while $p$ is degree $2$ multilinear if $f,g,p$ satisfy conditions. First question implies second question while second question implies first. – T.... Jan 13 '15 at 23:58
• What do you mean when you say that one question implies another? This is not an expression that is commonly used in English. – S. Carnahan Jan 14 '15 at 1:57

Do you mean to exclude something like $p(x_1,\ldots,x_4) = -x_1^2 + 2 x_1$, $f(x_1,\ldots,x_4) = x_1$, $g(x_1, \ldots, x_4) = 2 - x_1$?
• corrected question. No. This is ok just that $p$ has to be multilinear. maybe I am wrong (a silly triplet possibly exists). – T.... Jan 13 '15 at 4:46
Your conjecture is false for $P_4$, by linear algebra. Evaluation on $\{0,1\}^4$ is a linear map from any space of functions to $\mathbb{R}^{16}$, and it is injective for multilinear functions. The degree 4 multilinear functions form a 16 dimensional space, so a suitable $p$ always exists.
• So is dimension of $k$ degree multilinear polynomials on $\{0, 1\}^n$ $$2^{\sum_{i=1}^{k}\binom{n}{i}} - 2^{\sum_{i=1}^{k-1}\binom{n}{i}}?$$ – T.... Jan 14 '15 at 5:03