Skip to main content
4 of 5
Use tex for formulae
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Can you cover the Boolean cube $\{0,1\}^n$ with $O(1)$ Hamming-balls each of radius $n/2-c\sqrt(n)$?

(where c>0 and the balls need not be disjoint?)

This is an embarrassingly simple question, yet somehow I couldn't find an answer (not even, "this is a well-known open problem") after spending some time googling the literature on covering codes.

A simple probabilistic argument shows that you can cover the Boolean cube with O(n) Hamming balls of radius $n/2-c\sqrt n$ each, for any $c>0$. My guess would be that you can't do it with (much) fewer---O(1) Hamming balls seems aggressively optimistic---but I don't know if it's known how to prove that.

(In the language of coding theory, I want to know whether $K_2(n,n/2-c\sqrt n)$, the minimum size of a binary covering code with radius $n/2-c\sqrt n$, can be upper-bounded by a constant depending only on c, not on n, at least for some c>0.)

Scott Aaronson
  • 9.8k
  • 5
  • 65
  • 71