# How many Hamming spheres of radius 1 does it take to cover the cube?

I am looking for the sharpest known upper bound on $$K(n, 1)$$ as $$n \rightarrow \infty$$. This is the minimal cardinality of a (not-necessarily linear) covering code of $$\{0, 1\}^n$$ of radius 1.

In elementary terms: Using how few (possibly non-disjoint) Hamming balls of radius 1 can we cover $$\{0, 1\}^n$$? I am interested in upper-bounds to this quantity, especially asymptotically as $$n \rightarrow \infty$$. For example, even the statement $$K(n, 1) \in o(2^n)$$ I have not been able to find proven. (It's impossible to do strictly better than $$\lceil{\frac{2^n}{n + 1}} \rceil$$, by the sphere-covering bound.)

As of 1998, exact values of $$K(n, 1)$$ were only known for specific values of $$n$$. For example:

• $$K(2^k - 1, 1) = 2^{2^k - k - 1}$$ (Hamming code)
• $$K(2^k, 1) = 2^{2^k - k}$$ (Johnson 1972)
• $$K(2n + 1, 1) \leq 2^n \cdot K(n, 1)$$ (Cohen–Lobstein–Sloane 1986)
• $$K(K(n, 1) - 1, 1) \leq (n + 1) \cdot 2^{K(n, 1) - n - 1}$$ (Cor. 1 of Östergård and Kaikkonen)
• $K(n, 1) \in o(2^n)$ is easy: clearly $K(n, 1) \le 2K(n-1, 1)$ by the construction of taking each code word of length $n-1$ and adding one copy with a suffix of $0$ and one with a suffix of $1$. Then from $K(2^k, 1) = 2^{2^k - k}$ you get $K(n, 1) \le 2^{n - \lfloor \lg n\rfloor}$. Jun 16 '21 at 19:00
• Note that the upper bound in the comment by @PeterTaylor not only gives $o(2^n)$ but gets remarkably close to the sphere-covering lower bound mentioned in the question. Jun 16 '21 at 20:19
• @AndreasBlass indeed—if my calculations are correct, it looks like it stays strictly less than double the sphere-covering bound even in the worst case. Jun 16 '21 at 21:32
• No, the worst case is $n = 2^k - 1$ when it's exactly double the sphere-covering bound. Jun 16 '21 at 21:40
• @PeterTaylor actually it seems that your argument can be slightly improved—by bootstrapping form Hamming's $K(2^k - 1, 1) = 2^{2^k - k - 1}$ instead of Johnson's, you can actually attain equality at the case $n = 2^k - 1$, and then you get the improved estimate $K(n, 1) \leq 2^{n - \lfloor \log_2 (n + 1) \rfloor}$. This estimate is always strictly less than double the lower-bound. Jun 16 '21 at 21:42

Clearly $$K(n, 1) \le 2K(n-1, 1)$$ by the construction of taking each code word of length $$n-1$$ and adding one copy with a suffix of $$0$$ and one with a suffix of $$1$$. (This is comment r to table 1 in the Cohen-Lobstein-Sloane paper referenced in the question).
Then by taking the largest $$k$$ such that $$2^k - 1 \le n$$ and iterating this construction on the Hamming code we get $$K(n, 1) \le 2^{n - \lfloor \lg (n+1)\rfloor}$$. The sphere-covering lower bound can be written as $$2^{n - \lg(n+1)} \le K(n,1)$$, so the upper bound is less than twice the lower bound and we have the asymptotic $$K(n, 1) \in \Theta(2^{n - \lg(n+1)})$$
When $$n = 2^k - 1$$ the lower and upper bounds coincide; the gap is greatest when $$n = 2^k - 2$$, when the upper bound coincides with the size of the Hamming code for $$n+1$$.
• I meant to mention that the known exact values for small $n$ are OEIS A000983. Jun 17 '21 at 7:42