# Maximum number of Vertices of Hypercube covered by Ball of radius R

Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ball of radius $R$.

I would greatly appreciate any references to literature or ideas on how to approach the problem. I strongly suspect that a solution for any $R$ comes from placing the center of the ball at $(\frac{1}{2},\frac{1}{2},\ldots,\frac{1}{2},0,\ldots,0)$ with the number of nonzero coordinates being $\lfloor 4R^2 \rfloor=\lfloor D^2 \rfloor$, where $D$ is the diameter (for $D \leq n$).

Any references or ideas are welcome.

Thanks!

-
That seems like a good guess to me. You could try using the fact that any set of more than $2^k$ vertices of $H^n$ cannot be contained in a $k$-dimensional affine subspace of $\mathbb R^n$. – Greg Martin May 9 '13 at 0:52
This is not always true. Already if n=2 (we have a square), then if R is a little less than $\sqrt(2)/2$, then the best we can do is to cover 3 vertices. – domotorp Jun 25 '13 at 15:12
@domotorp Indeed, it is not always true. However, if one can cover 3 vertices then one can cover the whole square. I believe the conjecture first breaks down at dimension 16 – user21277 Jun 26 '13 at 19:42
I think you are mistaken, in my example with the given radius we can cover 3 vertices but not the whole square. – domotorp Jun 27 '13 at 15:14
@domotorp Consider 3 vertices of a square. These form an isosceles right triangle. The circumcenter of this triangle is the midpoint of the hypotenuse, which is also the center of the square. – user21277 Jun 28 '13 at 2:10

Let $n=8$ and $R=\sqrt{\frac{7}{8}}$. Then the ball with center $(\frac{1}{8}, \frac{1}{8}, \dots, \frac{1}{8})$ and radius $R$ covers exactly $9$ vertices (those with at most one coordinate equal to $1$), but a ball with radius $R$ cannot cover a $4$-dimensional unit hypercube, which requires radius at least $1$.
There is even no upper bound on the number of points a ball with radius $1$ can cover, provided the dimension is not bounded. Generalizing previous construction, a ball with center $(\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n})$ and radius $\sqrt{\frac{n-1}{n}}$ covers $n+1$ vertices of the $n$-dimensional hypercube. As user21277 points out, for $n=16$ this is better than placing the ball in the center of a $4$-dimensional face.
In general, for $n>2i$, a ball with center $(\frac{i}{n}, \frac{i}{n}, \dots, \frac{i}{n})$ and radius $\sqrt{\frac{i(n-i)}{n}}$ covers ${n \choose i} + {n \choose i-1} + \cdots +{n \choose 0}$ vertices: those with at most $i$ coordinates equal to $1$. A ball with the same radius cannot cover all $2^{4i}$ vertices of a $4i$-dimensional unit hypercube.