# 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.)

-
just may be stupid questions. If I have 2 balls I need radius = n/2 (just take 00000 and 11111 as centers). If we have 3,4... balls what radius do we need ? – Alexander Chervov Jun 18 '12 at 12:55
I agree it should probably be linear in n, but this might be rather hard to prove. Benny Sudakov was telling me that it is known (but difficult) that Hamming Balls of radius 1 cover with efficiency 1 + o(1), but this is an open problem for balls of radius 2. He may known about your question too; I'll ask him this afternoon. – Ben Green Jun 18 '12 at 13:00
@Alexander Chervov: The Central Limit Theorem says the volume approaches a constant fraction of the cube. The question is whether to cover everything, you need the efficiency of the covering to decrease to $0$ as $n \to \infty$. Also, I'm not familiar with your C_n^r notation. The volume of the ball of radius $r$ is $\sum_{k=0}^r {n \choose k}$. – Douglas Zare Jun 18 '12 at 14:28
@Douglas Thanks. Okay, the last term may be dominating the sum ? it seems called sphere hardening.... if like this then if we cover cube the total volume should be greater than 2^n, which will contradict to : last term/2^n tends to zero .... – Alexander Chervov Jun 18 '12 at 14:59
A related result is that when $c=1/2$, $n=2^m$, $m$ even, then the first order Reed-Muller code with $2n$ words has covering radius $n-c\sqrt{n}$. You probably knew about this. I have a feeling that the particular covering is very good, so in spite of not being exactly the question that you ask, this strongly suggests that with $c=1/2$ the number of balls needed grows linearly with $n$. – Jyrki Lahtonen Jun 19 '12 at 7:51

I think the answer to this is no. Suppose you can cover the cube with $m$ translates of the Hamming ball of radius $\frac{n}{2} - c\sqrt{n}$. Restrict this to a covering of the sets of size $k := \frac{n}{2} - \frac{1}{10} c \sqrt{n}$. This gives an $m$-colouring of these sets in a natural way. Now if two sets have the same colour then they intersect, and therefore we have an $m$-colouring of the Kneser graph $KG_{n,k}$. But Lovasz famously proved that the chormatic number of the Kneser graph is $n - 2k + 2 = \Omega(\sqrt{n})$.

I'm not sure whether one can use similar methods to get $\Omega(n)$, which is likely the sharp bound. Searching in the literature for "Borsuk graph" may yield results. With thanks to Benny Sudakov.

-
Thanks so much, Ben!! In your argument, the 1/10 seems unimportant; we could have chosen k=r+1 where r is the radius of each ball. Doing so yields a lower bound of m >= n-2r on the number of Hamming balls needed. – Scott Aaronson Jun 18 '12 at 15:50

Spencer's famous "Six Standard Deviations Suffice" is essentially equivalent to what you're asking (for a statement and proof see, e.g., the Alon-Spencer book or the new proof by Lovett and Meka). It shows, e.g., that with balls of radius $n/2-6\sqrt{n}$ you need n balls to cover the cube. It also gives $\Omega(n)$ for any radius $n/2-c\sqrt{n}$.

-

Striped out of the coding-theory notation, Theorem 12.5.10 of "Covering Codes" by Cohen, Honkala, Litsyn, and Lobstein reads as follows:

If every element of ${\mathbb F}_2^n$ is at most Hamming distance $r$ away from an element of a set $A\subset{\mathbb F}_2^n$, then $$r\ge n/2-12\sqrt{|A|}.$$

(A remark on page 352 indicates that this theorem originates from a year 1986 paper of Lovasz, Spencer, and Vesztergombi.)

An immediate corollary is that in order to cover the whole space with balls of radius $r=n/2-c\sqrt n$, one needs at least $(c^2/144)n=\Omega(n)$ balls.

-