Skip to main content
4 of 4
replaced http://mathoverflow.net/ with https://mathoverflow.net/

Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?

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$)?

Seva
  • 23k
  • 2
  • 59
  • 141