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](https://www.sciencedirect.com/science/article/pii/S0012365X97818250), *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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.392.3162))
* $K(K(n, 1) - 1, 1) \leq (n + 1) \cdot 2^{K(n, 1) - n - 1}$ (Cor. 1 of [Östergård and Kaikkonen](https://www.sciencedirect.com/science/article/pii/S0012365X97818250))



How many Hamming spheres of radius 1 does it take to cover the cube?
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$.


