# Complementing the red and blue boolean cube?

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.

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.