HereHere 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.
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.
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.
Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?
As a (somewhat disguised) extensionSince my original posting some ten days ago, I discovered an amazing example which changed significantly my perception of my recent MO postthe problem. Accordingly, the whole post got re-written now.
GivenThe most general form of the question I am interested in is as follows: Given integers $n\ge k\ge 1$ and $N$$N\le 2^n$, for a collection of $N$ Hamming Hamming spheres in ${\mathbb F}_2^n$ of radius $1$, what is the smallest possible possible number of points in ${\mathbb F}_2^n$ covered by at least $k$ spheres spheres?
SupposeDenote 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 even-weight points of ${\mathbb F}_2^n$, and denote by $F_0$ the set of all even-weight points. (The motivation motivation here is that even-centered and odd-centered spheres are disjoint; hencedisjoint; hence, the sets they $k$-cover are disjoint, too.) It is not difficult difficult to find a linear subspace $L<F_0$$L < F_0$ of co-dimension $\lceil \log_2 n/(k-1) \rceil$$\lceil \log_2 n/(k-1) \rceil$ such that no point in ${\mathbb F}_2^n$ is covered by by $k$ (or more) spheres, centered centered at the elements of $L$. Therefore, if we have fewer than $\sim2^{n-1}k/n$the number of spheres is $N\lesssim2^{n-1}k/n$, then the set of $k$-covered points can be empty. On the the other hand, by a simple double counting counting, for any system of $N$ even even-centered spheres, the number of $k$-covered points is at least $$ \Big(1-\frac{2^{n-1}k}{n}\Big)\,N. $$$$ \Big(1-\frac{2^{n-1}k}{nN}\Big) \, N. $$ My question is:To what extent can this trivial estimate be improved, assuming that $k$ is$N$ is reasonably smalllarge (say, and $N$ is reasonably large$N>2^{n-2}$)? Is it true, can this estimate be improved to showfor instance, that the the number of $k$-covered points points is at least $N$? Without goingHere 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 detailsa union $I_1\cup\dotsb\cup I_{2^k}$, I would consider "reasonable" the valueswith every set $k<n^\epsilon$$I_s$ of size $k+1$, and let $B$ denote the set of all those points $N\ge2^{n-2}$$(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$. (although I have no evidenceLoosely 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 estimate number of odd points in question fails slightly outside this range$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. And soThus, we have just $N-1$ points, covered by "really many" spheres.
Another example to put itkeep in a self-contained formmind: 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 $k\le n^\epsilon$ and$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\ge 2^{n-2}$$N>2^{n-2}$ even-centered unit spheres spheres in ${\mathbb F}_2^n$, there are at least $N$ points, covered by $k$ or$c\log n$ or more spheres (for some absolute constant $c>0$)?
The answer is (trivially) positive forHere lies an argument showing that there are at least $k=1$$N$ points, and the case $k=2$ is treated herecovered by two or more spheres. Unfortunately, thethis argument for the case $k=2$ does not seem to extendseem to extend onto the larger values of $k$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 centeredspheres centered at the elements of $C$, then $\overline S:=F_0\setminus S$ is exactly the set of all points $(n-k)$-covered by the spheres centered at the elements elements of $\overline C$ is exactly the set of all odd points not in $S$. This shows that my question can be equivalentlyallows one to restated as followsequivalently restate the two questions above; say, the first of them gets the following shape:
Is it true that for any $k\le n^\epsilon$ and any collection of $N\le 2^{n-2}$$N<2^{n-2}$ even-centered unit spheres spheres in ${\mathbb F}_2^n$, there are at most $N$$N+1$ points, covered by $n-k$ $(1-c)n$ or more spheres (for some absolute constant $c>0$)?
Intersecting Hamming spheres
As a (somewhat disguised) extension of my recent MO post.
Given integers $n\ge k\ge 1$ and $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?
Suppose that all our spheres are centered at the even-weight points of ${\mathbb F}_2^n$, and denote by $F_0$ the set of all even-weight points. (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 we have fewer than $\sim2^{n-1}k/n$ spheres, 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}{n}\Big)\,N. $$ My question is: assuming that $k$ is reasonably small, and $N$ is reasonably large, can this estimate be improved to show that the number of $k$-covered points is at least $N$? Without going into details, I would consider "reasonable" the values $k<n^\epsilon$ and $N\ge2^{n-2}$ (although I have no evidence that the estimate in question fails slightly outside this range). And so, to put it in a self-contained form:
Is it true that for any $k\le n^\epsilon$ and any collection of $N\ge 2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at least $N$ points, covered by $k$ or more spheres?
The answer is (trivially) positive for $k=1$, and the case $k=2$ is treated here. Unfortunately, the argument for the case $k=2$ does not seem to extend onto the larger values of $k$.
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 $\overline S:=F_0\setminus S$ is exactly the set of all points $(n-k)$-covered by the spheres centered at the elements of $\overline C$. This shows that my question can be equivalently restated as follows:
Is it true that for any $k\le n^\epsilon$ and any collection of $N\le 2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at most $N$ points, covered by $n-k$ or more spheres?
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$)?
As a (somewhat disguised) extension of my recent MO post.
Given integers $n\ge k\ge 1$ and $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?
Suppose that all our spheres are centered at the even-weight points of ${\mathbb F}_2^n$, and denote by $F_0$ the set of all even-weight points. (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 find a linear subspace $L<F_0$ of co-dimension $\lceil\log_2n/(k-1)\rceil$ such$\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 we have fewer than $\sim2^{n-1}k/n$ spheres, 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}{n}\Big)\,N. $$ My question is: assuming that $k$ is reasonably small, and $N$ is reasonably large, can this estimate be improved to show that the number of $k$-covered points is at least $N$? Without going into details, I would consider "reasonable" "reasonable" the values $k<n^\epsilon$ and $N\ge2^{n-2}$ (although I have no evidence evidence that the estimate in question fails slightly outside this range). And And so, to put it in a self-contained form:
Is it true that for any $k\le n^\epsilon$ and any collection of $N\ge 2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at least $N$ points, covered by $k$ or more spheres?
The answer is (trivially) positive for $k=1$, and the case $k=2$ is treated here. Unfortunately, the argument for the case $k=2$ does not seem to extend onto the larger values of $k$.
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 $\overline S:=F_0\setminus S$ is exactly the set of all points $(n-k)$-covered by the spheres centered at the elements of $\overline C$. This shows that my question can be equivalently restated as follows:
Is it true that for any $k\le n^\epsilon$ and any collection of $N\le 2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at most $N$ points, covered by $n-k$ or more spheres?
As a (somewhat disguised) extension of my recent MO post.
Given integers $n\ge k\ge 1$ and $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?
Suppose that all our spheres are centered at the even-weight points of ${\mathbb F}_2^n$, and denote by $F_0$ the set of all even-weight points. (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_2n/(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 we have fewer than $\sim2^{n-1}k/n$ spheres, 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}{n}\Big)\,N. $$ My question is: assuming that $k$ is reasonably small, and $N$ is reasonably large, can this estimate be improved to show that the number of $k$-covered points is at least $N$? Without going into details, I would consider "reasonable" the values $k<n^\epsilon$ and $N\ge2^{n-2}$ (although I have no evidence that the estimate in question fails slightly outside this range). And so, to put it in a self-contained form:
Is it true that for any $k\le n^\epsilon$ and any collection of $N\ge 2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at least $N$ points, covered by $k$ or more spheres?
The answer is (trivially) positive for $k=1$, and the case $k=2$ is treated here. Unfortunately, the argument for the case $k=2$ does not seem to extend onto the larger values of $k$.
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 $\overline S:=F_0\setminus S$ is exactly the set of all points $(n-k)$-covered by the spheres centered at the elements of $\overline C$. This shows that my question can be equivalently restated as follows:
Is it true that for any $k\le n^\epsilon$ and any collection of $N\le 2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at most $N$ points, covered by $n-k$ or more spheres?
As a (somewhat disguised) extension of my recent MO post.
Given integers $n\ge k\ge 1$ and $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?
Suppose that all our spheres are centered at the even-weight points of ${\mathbb F}_2^n$, and denote by $F_0$ the set of all even-weight points. (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 we have fewer than $\sim2^{n-1}k/n$ spheres, 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}{n}\Big)\,N. $$ My question is: assuming that $k$ is reasonably small, and $N$ is reasonably large, can this estimate be improved to show that the number of $k$-covered points is at least $N$? Without going into details, I would consider "reasonable" the values $k<n^\epsilon$ and $N\ge2^{n-2}$ (although I have no evidence that the estimate in question fails slightly outside this range). And so, to put it in a self-contained form:
Is it true that for any $k\le n^\epsilon$ and any collection of $N\ge 2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at least $N$ points, covered by $k$ or more spheres?
The answer is (trivially) positive for $k=1$, and the case $k=2$ is treated here. Unfortunately, the argument for the case $k=2$ does not seem to extend onto the larger values of $k$.
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 $\overline S:=F_0\setminus S$ is exactly the set of all points $(n-k)$-covered by the spheres centered at the elements of $\overline C$. This shows that my question can be equivalently restated as follows:
Is it true that for any $k\le n^\epsilon$ and any collection of $N\le 2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at most $N$ points, covered by $n-k$ or more spheres?