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$
4
  • $\begingroup$ @PietroMajer Your polynomial is not multilinear (you have $s_j^2$ term). $\endgroup$
    – Turbo
    Jan 13, 2015 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, 2015 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$
    – Turbo
    Jan 13, 2015 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, 2015 at 1:57

2 Answers 2

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$
1
  • $\begingroup$ corrected question. No. This is ok just that $p$ has to be multilinear. maybe I am wrong (a silly triplet possibly exists). $\endgroup$
    – Turbo
    Jan 13, 2015 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$
3
  • $\begingroup$ I think I am not explaining well. $\endgroup$
    – Turbo
    Jan 14, 2015 at 3:58
  • $\begingroup$ Modified question so it is clear. $\endgroup$
    – Turbo
    Jan 14, 2015 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$
    – Turbo
    Jan 14, 2015 at 5:03

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.