4
$\begingroup$

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'.
Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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$

Improve this answer
$\endgroup$
6
  • $\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.
    Commented Feb 21, 2014 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
    Commented Feb 22, 2014 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.
    Commented Feb 22, 2014 at 4:17
  • 1
    $\begingroup$ I have edited the answer, adding a remark about binary covering codes. $\endgroup$
    – Jan Kyncl
    Commented Feb 22, 2014 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
    Commented Feb 22, 2014 at 7:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .