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

Question

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)

Answer 1

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