0
$\begingroup$

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}[4],P_1[4],P_1[4])$, 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}[4],P_1[4],P_1[4])$, $(P_{3}[4],P_1[4],P_1[4])$, $(P_{4}[4],P_1[4],P_1[4])$. 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}[4],P_0[4],P_1[4]),(P_{2}[4],P_1[4],P_0[4])$ to above?

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

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

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

$p$ will be degree $0$.

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

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


Through tedious calculations if I possibly could show triplet in $(P_{2}[4],P_1[4],P_1[4])$ 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}[4]$ 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}[4]$ 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?

$\endgroup$
  • $\begingroup$ @PietroMajer Your polynomial is not multilinear (you have $s_j^2$ term). $\endgroup$ – Brout Jan 13 '15 at 8:46
  • $\begingroup$ 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. $\endgroup$ – S. Carnahan Jan 13 '15 at 23:46
  • $\begingroup$ @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. $\endgroup$ – Brout Jan 13 '15 at 23:58
  • $\begingroup$ What do you mean when you say that one question implies another? This is not an expression that is commonly used in English. $\endgroup$ – S. Carnahan Jan 14 '15 at 1:57
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ corrected question. No. This is ok just that $p$ has to be multilinear. maybe I am wrong (a silly triplet possibly exists). $\endgroup$ – Brout Jan 13 '15 at 4:46
0
$\begingroup$

Your conjecture is false for $P_4[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.

For the lower degree cases, you should ask a computer.

$\endgroup$
  • $\begingroup$ I think I am not explaining well. $\endgroup$ – Brout Jan 14 '15 at 3:58
  • $\begingroup$ Modified question so it is clear. $\endgroup$ – Brout Jan 14 '15 at 4:04
  • $\begingroup$ 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}}?$$ $\endgroup$ – Brout Jan 14 '15 at 5:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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