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

1 Answer 1

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.

$\endgroup$

Your Answer

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