Covering of $B^{n}$

Question

Suppose we have $B^{n} = \{0,1\}^{n}$.We want to find for what $n$ there is exist $B_{1}(q_{1}) \dots B_{1}(q_m)$ : $B_{1}(q_i) \cap B_1(q_j) = \emptyset$ and $\bigcup B(q_i) = B^n$, where $B_{1}(q) - $ is sphere with unit radius.

I think the answer is $2^k$ and $2^{k} - 1$. But does there any other solutions?

My idea based on Hammings codes and $B^{n} = B^{n-1} \times B$.

Answer 1

First let me confirm my understanding: $B(q)$ consists of $q \in B^n$ and any other bit-vector that is $1$-bit different from $q$ - that's what you mean by "unit sphere", right?

If my understanding is correct, you are seeking a partition of $B^n$ into disjoint unit spheres. This is possible iff $n = 2^k - 1$.

Necessity: Since each $|B(q)|=n+1$, this number must divide $|B^n| = 2^n$ to have any chance of a disjoint partition, so it is necessary that $n+1$ is a power of $2$ or $n=2^k−1$. In particular, I don't think the $n=2^k$ case works, e.g. $B^2 = \{(0,0), (0,1), (1,0), (1,1)\}$ cannot be partitioned into disjoint unit spheres because pick any $q \in B^2$ and its unit sphere $B(q)$ has size $3$.

Sufficiency: This comes from this line in the wikipedia article on Hamming code

For each integer $r \ge 2$ there is a [Hamming] code with block length $n = 2^r − 1$

The block length is the length of the bit vector, i.e. $n$ in your case. A Hamming code in this context consists of codewords (your $q_i$'s) which are distance $3$ apart, i.e. their unit spheres are disjoint. It remains to show that the union of the spheres cover the entire $B^n$. This can be seen from the section on "General algorithm". In particular:

The pattern of errors, called the error syndrome, identifies the bit in error. If all parity bits are correct, there is no error. Otherwise, the sum of the positions of the erroneous parity bits identifies the erroneous bit. For example, if the parity bits in positions $1, 2$ and $8$ indicate an error, then bit $1+2+8=11$ is in error.

So when the no. of bits is $n=2^k - 1$, any error syndrome maps to a single bit-error in a single position, and is therefore in $B(q)$ for some codeword $q$. This shows that the spheres together cover $B^n$. To be even more explicit (slightly paraphrased):

if you have $k$ parity bits, it can cover bits from 1 up to $n=2^k-1$. If we subtract out the parity bits, we are left with $2^k-k-1$ bits we can use for the data.

Since there are $2^k - k - 1 = n-k$ data bits, there are $2^{n-k}$ codewords. Each codeword's sphere $B(q)$ has size $n+1 = 2^k$. Since the spheres are disjoint, their union has size $2^{n-k} \times 2^k = 2^n$, proving that the union $= B^n$.