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)

strictlyless than double the lower-bound. $\endgroup$