2
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ $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\,\}$. $\endgroup$ – Gerry Myerson Mar 19 at 1:02
  • $\begingroup$ @GerryMyerson yes, that is exactly what I mean by $P_1$. Both $0111$ and $1000$ are of the form $xyyy$. $\endgroup$ – Josh C Mar 19 at 1:03
  • $\begingroup$ How does $0101$ get into $xyyy,xxxx$? $\endgroup$ – Gerry Myerson Mar 19 at 1:04
  • $\begingroup$ Ack! Sorry! Edited my comment. It goes $0101 \mapsto 0111$. Revising the question... $\endgroup$ – Josh C Mar 19 at 1:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Wildon Mar 19 at 12:34
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – anonymous_coward Mar 20 at 15:46

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.