Sphere packing in $\{0,1\}^n$ with Hamming distance

Question

If $(X,d)$ is a metric space, $x\in X$ and $r\in\mathbb{R}$ with $r>0$ we set $$S_r(x) = \{z\in X: d(x,z) < r\}.$$ Given positive integers $k<n\in\mathbb{N}$ and the metric space $(\{0,1\}^n, d)$ where $d$ denotes the Hamming distance, is it known how to choose a subset $T\subseteq \{0,1\}^n$ such that $$\{S_k(t):t\in T\}$$ is a set of disjoint spheres that is maximal in cardinality amongst all sets of disjoint spheres with radius $k$, in $\{0,1\}^n$?

Answer 1

By sphere packing arguments you can't do better in general than the Hamming bound $$ \# T \left(1+ \binom{n}{1}+ \cdots+ \binom{n}{r-1}\right)\leq 2^n, $$ or $$ \#T \#S_{r-1}(x)\leq 2^n, $$ in your notation. $t=r-1$ is the number of errors the code can correct.

Codes achieving the above are called perfect, there are only 4 of them in the binary alphabet case:

• the full space with $t=0,$ admittedly trivial,
• the $n$ length repetition codes consisting of the all zero and all one vectors with $t=(n-1)/2$, which exists for all positive odd $n$
• the family of Hamming codes with $t=1$ and $n=2^m-1$, and
• the binary Golay code of length $n=23$ and $t=3$ which is related to many combinatorial objects.

There is also a lower bound called Gilbert Varshamov which asserts the existence of sets $T$ with size at least equal to the bound given $n$ and $r$.

Nice coding theory texts include those by MacWilliams and Sloane, Roman, Bierbrauer, Roth.