# Partitioning $\{0,1\}^n$ into $n$ sets

I am working on an answer to the question

Magic trick based on deep mathematics

and came across the following problem: I am trying to partition the cube $$\{0,1\}^n$$ into $$n$$ sets $$P_1,\dots,P_n$$ such that, for any point $$x\in\{0,1\}^n$$ and any $$i\in\{1,\dots,n\}$$, there exists a point $$y\in P_i$$ such that $$x$$ and $$y$$ differ in at most one term. Using my computer I know that this is possible for $$n\leq 4$$, impossible for $$n=5$$ and $$6$$, and possible for $$n=7$$ and $$8$$ (by brute force integer programming). For example, one solution for $$n=4$$ is \begin{align*} P_{1} & =xyyy\text{ or }xxxx\\ P_{2} & =xyxx\text{ or }xyyx\\ P_{3} & =xxyx\text{ or }xyxy\\ P_{4} & =xxxy\text{ or }xxyy \end{align*} where $$x$$ and $$y$$ are separate values in $$\{0,1\}$$. My question is: can this partition (or something like it) extend to $$n=8$$ in a simple way? Alternatively, are there any values of $$n$$ for which there is a simple and natural partition?

To clarify my notation here is an explicit list of the $$P_i$$'s for $$n=4$$:

\begin{align*} P_{1} & =0111\text{ or }1000\text{ or }0000\text{ or }1111\\ P_{2} & =0100\text{ or }1011\text{ or }0110\text{ or }1001\\ P_{3} & =0010\text{ or }1101\text{ or }0101\text{ or }1010\\ P_{4} & =0001\text{ or }1110\text{ or }0011\text{ or }1100 \end{align*}

• $n=4$, your example, $i=1$, how does $yxyx$ differ in at most one term from a point in $P_1=\{\,xyyy,xxxx\,\}$? Maybe I'm misunderstanding, and you mean $P_1=\{\,0111,1000,0000,1111\,\}$. – Gerry Myerson Mar 19 '19 at 1:02
• @GerryMyerson yes, that is exactly what I mean by $P_1$. Both $0111$ and $1000$ are of the form $xyyy$. – Josh C Mar 19 '19 at 1:03
• How does $0101$ get into $xyyy,xxxx$? – Gerry Myerson Mar 19 '19 at 1:04
• Ack! Sorry! Edited my comment. It goes $0101 \mapsto 0111$. Revising the question... – Josh C Mar 19 '19 at 1:05
• My question mathoverflow.net/q/243459/7709, also motivated by a magic trick, asks for such a partition with the stronger property that, given any $x \in \{0,1\}^n$ and any $i \in \{1,\ldots, n\}$, there exists $y \in P_i$ such that $x_i = y_i$ and $x$ and $y$ differ in at most one term. In this case a covering code argument shows that $n$ has to be a power of two. – Mark Wildon Mar 19 '19 at 12:34

You are looking for a binary code with covering radius 1, which is in general a well studied and difficult problem.

Basically you need a collection of codewords such that the union of the spheres with radius 1 around them cover the whole space.

If you took any of your collections, say $$P_1$$ for length 4, you could obtain what you need for length $$n=8,$$ by the following construction.

Take $$P_i,P_j$$, create the sets $$U\otimes P_i$$ and $$P_j \otimes U$$ where $$U$$ (the universe) is the set of all $$4-$$tuples. The union of these two sets will give you a covering code with radius 1. So picking $$i=j=1,$$ gives \begin{align*} P_{1} \otimes U & =0111xxxx\text{ or }1000xxxx\text{ or }0000xxxx\text{ or }1111xxxx\\ U\otimes P_{1} & =xxxx0111\text{ or }xxxx1000\text{ or }xxxx0000\text{ or }xxxx1111 \end{align*} where $$xxxx$$ means we take all possible bit patterns of length $$4.$$

Edit: A simpler and optimal construction is to take the codewords of the perfect Hamming code with length 7 bits and minimum distance 3. This code has 16 codewords, and covering radius 1. Add a zero bit and a 1 bit at the end of each codeword to obtain an optimal set of only 32 codewords covering $$\{0,1\}^8$$ with covering radius 1.

Since all binary Hamming codes with lengths $$2^m-1$$ are perfect, and have $$2^{2^m-m-1}$$ codewords, the above construction yields optimal covering codes with covering radius 1 and $$2^{2^m-m}$$ codewords when $$n=2^m.$$

It is known in general that for any length $$n$$ the quantity $$2^n/(n+1)$$ is a lower bound to the cardinality of any binary code with covering radius 1.

• OP asks for more: a partition into $n$ covering codes of radius 1. Furthermore, an optimal code has size $2^n/(n+1)$ (not $2^n/n$). Hamming cosets do indeed partition the space, giving $n+1$ of them, not $n$. One could take the $(n+1)$-st coset and divvy it up among other cosets to get exactly $n$. Hamming codes exist for $n$ one less than a power of $2$, and perhaps the difference between $n$ and $n+1$ provides enough wiggle room for other values. You might look in Cohen-Honkala-Litsuyn-Lobstein to see what error term is in the asymptotic size of the smallest known $R=1$ covering code. – anonymous_coward Mar 20 '19 at 15:46