4
$\begingroup$

Given a boolean $0/1$ cube in $n$ dimensions with $2^{n-1}$ red and $2^{n-1}$ blue points can we complement the cube (blue becomes red and vice versa) in $\operatorname{poly}(n)$ transformations?

Here by transformation I mean the following.

  1. Cutting the cube by $h=\operatorname{poly}(n)$ hyperplane inequalities each describable by $poly(n)$ bit coefficients into $r=\operatorname{poly}(n)$ pieces $P_1,\dots,P_r$.

  2. Permuting coordinates of each piece (for example if $101$ was blue and $011$ was red then permuting first and second coordinate $011$ is blue and $101$ is blue).

  3. Negating coordinates of each piece (for example if $101$ was blue and $111$ was red then negating first coordinate $111$ is blue and $101$ is blue).

  4. Rotating, translating each piece.

  5. Finally repasting all pieces so it becomes cube again.

$\endgroup$
2
$\begingroup$

There are at most $2^{\mathrm{poly}(n)}$ partitions $P_1, \dots, P_r$ satisfying condition 1. Each such partition has a part $P_i$ of size at least $2^n/\mathrm{poly}(n)$. There are at most $2^{\mathrm{poly}(n)}$ transformations of $P_i$ satisfying conditions 2-4.

Each such transformation $T$ of $P_i$ can be represented by a one-to-one mapping from $P_i$ to a subset of the hypercube, and a condition that the mapping preserves all colors or switches all colors. There are at most $2^{2^n}/2^{2|P_i|/2}\le2^{2^n}/2^{2^n/\mathrm{poly}(n)}$ colorings of the hypercube satisfying these conditions for $T$.

In total, the transformations satisfying conditions 1-4 can switch at most $$ 2^{2^n-\frac{2^n}{\mathrm{poly}(n)}+\mathrm{poly}(n)} $$ colorings of the hypercube, but the total number of colorings is $2^{2^n - \mathrm{poly}(n)}$, which is larger. Therefore, for sufficiently large $n$, there are colorings of the hypercube that cannot be switched (complemented) by the given transformations.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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