0
$\begingroup$

Given $S_0\cup S_1=T_0\cup T_1=\{0,1\}^n$, $S_0\cap S_1=T_0\cap T_1=\emptyset$, with $|S_i|=|T_i|$ for both $i\in\{0,1\}$, what is degree of transformation that simultaneously maps $S_i$ to $T_i$ for both $i\in\{0,1\}$?

What is the maximum absolute value of any entry in the coefficient of transformation equations?

Note that transformation can be multilinear ($x_i^c=x_i\forall c\in\Bbb N$) since we seek to transform $\{0,1\}^n$. Hence total degree of transformation is at most $n$.

$\endgroup$
4
  • $\begingroup$ If $S_0$ is the intersection of $\{0,1\}^n$ with a subspace (e.g. $x_1=0$), then a linear transformation would have to map $S_0$ into a subspace of $\mathbb R^n$. A typical subset of $\{0,1\}^n$ with $2^{n-1}$ elements is not contained in any subspace, so in general there is no linear transformation. $\endgroup$ May 7, 2015 at 22:13
  • $\begingroup$ Ok What is minimum degree necessary? $\endgroup$
    – Turbo
    May 7, 2015 at 22:13
  • $\begingroup$ Huge, no doubt. But I don't know how huge. $\endgroup$ May 7, 2015 at 23:12
  • $\begingroup$ It cannot be more than $n$ since we are looking at only $\{0,1\}^n$ transformation. $\endgroup$
    – Turbo
    May 7, 2015 at 23:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.