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

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$?

• Keyword: coding theory – Boris Bukh Oct 10 '17 at 13:19
• I suppose you're asking for a reasonably efficient algorithm to determine this maximum cardinality, right? – Wlodek Kuperberg Oct 10 '17 at 14:37
• @WlodekKuperberg right - and how to select $T$? I will google what Boris Bukh suggested on that behalf and see whether it gives me an answer – Dominic van der Zypen Oct 10 '17 at 14:47

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.

• "only 4 of them" meaning "2 of them, and 2 infinite families". – Gerry Myerson Oct 10 '17 at 22:00