4
$\begingroup$

Since my original posting some ten days ago, I discovered an amazing example which changed significantly my perception of the problem. Accordingly, the whole post got re-written now.


The most general form of the question I am interested in is as follows: Given integers $n\ge k\ge 1$ and $N\le 2^n$, for a collection of $N$ Hamming spheres in ${\mathbb F}_2^n$ of radius $1$, what is the smallest possible number of points in ${\mathbb F}_2^n$ covered by at least $k$ spheres?

Denote by $F_0$ the set of all even-weight points of ${\mathbb F}_2^n$, and suppose that all our spheres are centered at the points of $F_0$. (The motivation here is that even-centered and odd-centered spheres are disjoint; hence, the sets they $k$-cover are disjoint, too.) It is not difficult to find a linear subspace $L < F_0$ of co-dimension $\lceil \log_2 n/(k-1) \rceil$ such that no point in ${\mathbb F}_2^n$ is covered by $k$ (or more) spheres, centered at the elements of $L$. Therefore, if the number of spheres is $N\lesssim2^{n-1}k/n$, then the set of $k$-covered points can be empty. On the other hand, by a simple double counting, for any system of $N$ even-centered spheres, the number of $k$-covered points is at least $$ \Big(1-\frac{2^{n-1}k}{nN}\Big) \, N. $$ To what extent can this trivial estimate be improved, assuming that $N$ is reasonably large (say, $N>2^{n-2}$)? Is it true, for instance, that the number of $k$-covered points is at least $N$? Here is a rather surprising construction which places some limits on what one can expect in this direction.

Suppose that $n=(k+1)2^k$. Partition the index set $[n]$ into a union $I_1\cup\dotsb\cup I_{2^k}$, with every set $I_s$ of size $k+1$, and let $B$ denote the set of all those points $(x_1,\ldots,x_n)\in{\mathbb F}_2^n$ such that for each $I_s$, there is an index $i\in I_s$ with $x_i=1$. (Loosely speaking, $B$ consists of all those vectors which do not vanish on any of the coordinate blocks determined by the sets $I_s$.) Next, let $C:=B\cap F_0$ and consider the system of $N:=|C|$ unit spheres, centered at the points of $C$. An easy computation confirms that $N>2^{n-2}$, and the number of odd points in $B$ is exactly $N-1$. Furthermore, every odd point in $B$ is covered by lots of spheres (at least $k2^k$ of them), while every odd point not in $B$ is covered by at most $k+1\le\log_2 n$ spheres. Thus, we have just $N-1$ points, covered by "really many" spheres.

Another example to keep in mind: fix $I\subset[n]$ with $|I|=k$, let $B$ consist of all vectors $(x_1,\ldots,x_n)\in{\mathbb F}_2^n$ such that there exists $i\in I$ with $x_i=1$, and consider the system of $N=(1-2^{-k})2^{n-1}$ unit spheres centered at the points of the set $C:=B\cap F_0$. There are exactly $N$ odd points in $B$, and every odd point not in $B$ is covered by only $k$ spheres. Therefore, we have $N$ points covered by many spheres, whereas all other points are covered by a very small number of spheres (for $k$ small).

These constructions suggest two questions.

Is it true that for any collection of $N>2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at least $N-1$ points, covered by $cn$ or more spheres (for some absolute constant $c>0$)?

Is it true that for any collection of $N>2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at least $N$ points, covered by $c\log n$ or more spheres (for some absolute constant $c>0$)?

Here lies an argument showing that there are at least $N$ points, covered by two or more spheres. Unfortunately, this argument does not seem to extend onto three or more spheres.


A curious observation is that if $C$ and $\overline C$ are complementary subsets of $F_0$, and $S$ is the set of all points $k$-covered by the spheres centered at the elements of $C$, then the set of all points $(n-k)$-covered by the spheres centered at the elements of $\overline C$ is exactly the set of all odd points not in $S$. This allows one to equivalently restate the two questions above; say, the first of them gets the following shape:

Is it true that for any collection of $N<2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at most $N+1$ points, covered by $(1-c)n$ or more spheres (for some absolute constant $c>0$)?

$\endgroup$
5
  • $\begingroup$ Are your spheres hollow? A bit non-standard, if you ask me. For example in the sphere packing bound of coding theory, the spheres consist of all the points at a distance at most the radius from the center. OTOH using the surface only may make the problem more interesting! I'm not an expert on variants of covering codes, but is your problem not a variant of bounding the size of multi-covering codes? Some people have worked on those. $\endgroup$ Commented Dec 22, 2011 at 19:17
  • $\begingroup$ @Jyrki: yes, the spheres are hollow; otherwise I would say Hamming balls. I am not sure of what exactly you mean by the problem of "bounding the size of multi-covering codes". It is quite possible that my question is related to some known coding-theory problems (and hence one of the tags); practically, I don't know of any such problem. $\endgroup$
    – Seva
    Commented Dec 23, 2011 at 8:15
  • $\begingroup$ Andrew Klapper has worked on multi-covering problems (see cs.uky.edu/~klapper/multicov.html), but I don't know if the problem is too well-studied. What I was getting at with my other remark is that in coding theory balls are often called spheres. I know that this is bit against the standard of the rest of math :-) $\endgroup$ Commented Dec 26, 2011 at 17:01
  • $\begingroup$ It seems that a duoble-counting argument mentioned at the beginning leads to a bit different estimate, namely $\frac{Nn-2^{n-1}(k-1)}{n-k+1}$. $\endgroup$ Commented Jan 16, 2012 at 12:10
  • $\begingroup$ @Ilya: right, this is what you get if you are not willing to sacrifice lower-order terms. My expression assumes a very marginal loss of accuracy, but a gain in clarity. (Just think of replacing $k-1$ with $k$ in the numerator of your fraction, and $n-k+1$ with $n$ in its denominator.) $\endgroup$
    – Seva
    Commented Jan 16, 2012 at 20:45

1 Answer 1

1
$\begingroup$

A counterexample to the first question can be found along the same lines.

Let $k>2$, $n=kM$; we will choose the value of $M$ later. Partition $[n]=I_1\sqcup\dots\sqcup I_M$, $|I_s|=k$. Let $B$ be the set of all points $x$ such that for each $s\leq M$, there exist two indices $i,j\in I_s$ such that $x_i=x_j=1$. Set $B_0=B\cap F_0$, $B_1=B\cap F_1$. Then $$ |B_0|-|B_1|=\left(\sum_{i=2}^{k}(-1)^i{k\choose i}\right)^M=(k-1)^M. $$ Now let us center the spheres at the points of $B_0$. Then each odd point which is not in $B_1$ will be covered at most $k-1$ times, hence the number of points covered at least $k$ times is (at most) $|B_1|=|B_0|-(k-1)^M$. Moreover, $$ |B_0|>|B|/2=(2^k-k-1)^M/2=2^{kM-1}\left(1-\frac{k-1}{2^k}\right)^M>2^{kM-2} $$ if, for instance, $M\approx \frac{2^k}{2(k-1)}$ and $n\approx 2^{k-1}$. Hence we have found a counterexample for the first question. Moreover, we have shown that in the second one, we should have $c\leq 1$.

$\endgroup$

You must log in to answer this question.

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