For what values of $n$, it is possible to partition $\mathbb{Z}_2^n$ into $n$ disjoint parts, say $A_1, ..., A_n$ such that every element in $\mathbb{Z}_2^n$ is at most one-edit away from each part, i.e., the Hamming distance between $x$ and $A_k$ is at most 1 for all $x\in\mathbb{Z}_2^n$ and $k\in[n]$?

Moreover, if $n=2^m-1$ for some $m$, is it always possible to partition the space into $n+1$ parts with the same property?

Here are some observations.

  1. We can not hope for more than $n+1$ parts. If we can partition the space into $n+1$ parts. Then $n+1$ must divide $2^n$. Hence $n=2^m-1$ for some $m$. In fact, we can partition $\mathbb{Z}_2^n$ into $n+1$ parts for $n=1,3$.
  2. We can partition $\mathbb{Z}_2^n$ into $n$ parts for $n=2,4$, but NOT for $n=5$. This does not work for $n=5$ because one of the parts must have $\leq 6$ elements and it is not possible to have $6$ points in $\mathbb{Z}_2^n$ that 'controls' the entire space. In fact, there are at least 2 points that are 'not under control'.

The answer to the second question is yes.

For $n=2^m-1$, there exists a binary Hamming code, which is a special type of a linear code. It is a linear subspace $H$ of $\mathbb{Z}_2^n$ of dimension $n-m$, such that every two elements of $H$ have Hamming distance at least three. More importantly, the $1$-neighborhoods of the elements of $H$ cover the whole cube $\mathbb{Z}_2^n$. Now the affine subspaces $H, H+e_1, \dots, H+e_n$, where $e_i$ is the vector with $i$th coordinate equal to $1$ and other coordinates zero, form a partition with required properties.

This also implies that the answer to the first question is yes if $n=2^m$.

Edit: One could also try to find some lower bounds on the size of the sets $A_i$, generalizing the second observation. Every $A_i$ has to be a binary 1-covering code of length $n$. See also http://www.sztaki.hu/~keri/codes/ for tables of the best bounds for small values of $n$. The lower bounds in the table for $R=1$ imply that the answer to the first question is no also for $n=6,9,10,12,14, \ldots$

  • $\begingroup$ Thanks, @Jan Kyncl. You are absolutely correct. Also, the construction you gave for $n=2^m$ has a stronger property that for every $x$ and $k$ there is $y$ in $A_k$ such that $x$ and $y$ are exactly 1-edit away. I am still interested to see if other values of $n$ would work. $\endgroup$ – Zilin J. Feb 21 '14 at 15:31
  • $\begingroup$ @zilinj Well, I actually did not say exactly how to define the partition for $n=2^m$; one could take an arbitrary "rotation" of the construction for $2^m-1$ in each of two parallel hyperplanes. But the "most natural" way, indeed, has the property you state. $\endgroup$ – Jan Kyncl Feb 22 '14 at 4:01
  • $\begingroup$ Indeed. Also, with some hindsight, one can find a construction for $n=2^m$ without appealing to Hamming code. Suppose the binary is $a_0a_1 ... a_{n-1}$. Then we put it into $A_k$ if and only if $k = XOR_{a_i\neq 1}i$. $\endgroup$ – Zilin J. Feb 22 '14 at 4:17
  • 1
    $\begingroup$ I have edited the answer, adding a remark about binary covering codes. $\endgroup$ – Jan Kyncl Feb 22 '14 at 4:35
  • $\begingroup$ @zilinj This direct construction is elegant, indeed. However, it seems to me that in the hyperplane $a_0=0$, it is equivalent to the standard construction of Hamming codes. $\endgroup$ – Jan Kyncl Feb 22 '14 at 7:52

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.