19
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Alexander Chervov
    Commented Jun 18, 2012 at 12:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ben Green
    Commented Jun 18, 2012 at 13:00
  • 1
    $\begingroup$ @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}$. $\endgroup$
    – Douglas Zare
    Commented Jun 18, 2012 at 14:28
  • $\begingroup$ @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 .... $\endgroup$
    – Alexander Chervov
    Commented Jun 18, 2012 at 14:59
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Jyrki Lahtonen
    Commented Jun 19, 2012 at 7:51

3 Answers 3

Reset to default
23
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Scott Aaronson
    Commented Jun 18, 2012 at 15:50
15
$\begingroup$

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.

Improve this answer
$\endgroup$
10
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .