6
$\begingroup$

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:

$\endgroup$
5
  • 2
    $\begingroup$ $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}$. $\endgroup$ Jun 16 '21 at 19:00
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 16 '21 at 20:19
  • $\begingroup$ @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. $\endgroup$
    – BD107
    Jun 16 '21 at 21:32
  • $\begingroup$ No, the worst case is $n = 2^k - 1$ when it's exactly double the sphere-covering bound. $\endgroup$ Jun 16 '21 at 21:40
  • 2
    $\begingroup$ @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. $\endgroup$
    – BD107
    Jun 16 '21 at 21:42
4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ I meant to mention that the known exact values for small $n$ are OEIS A000983. $\endgroup$ Jun 17 '21 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.