What is the packing number of the unit cube?

Question

The $\varepsilon$-packing number of the unit cube $[0,1]^d$ with respect to the infinity norm is the biggest number of $\varepsilon$-strictly-separated points, i.e., the biggest cardinality of a set of points $E \subset [0,1]^d$ such that each two distinct $x,y\in E$ satisfy $\|x-y\|_\infty > \varepsilon$.

It seems geometrically intuitive to me that this is at most $\left( \bigl\lfloor \frac{1}{\varepsilon}\bigr\rfloor + 1 \right)^d$, where $\lfloor x \rfloor$ is the biggest integer lower or equal to $x$ (I am very naively taking a uniform grid of $(\varepsilon + \varepsilon')$-spaced points, for a small $\varepsilon'$).

Is this true? If so, how is it proven?

I can only found bounds like $(2/\varepsilon + 1)^d$ that upper bound the packing number with the related notion of covering number and proceed to find a covering.

Answer 1

By your definition, you are using axis-aligned cubes. Without this alignment things are a lot messier, as shown by square packings in a square.

I think you can prove it very straightforwardly. Let $q$ and $r$ be such that $1=q \varepsilon + r$, with $0 < r \le \varepsilon$. Now put a grid of $(q+1)^d$ points inside the cube, exactly $\varepsilon$ apart, centred in the cube. That is to say, each coordinate of each point is of the form $\frac r2 + k\varepsilon$ for some $k\in\{0,1,...,q\}$. Call this set of points $G$. Note that this grid of points is such that every point in the cube is no more than $\frac\varepsilon 2$ away from one of the points in $G$.

Consider any set $E$ of $\varepsilon$-strictly-separated points. Let $x,y\in E$ be distinct points. From the above, they will lie within a distance of $\frac\varepsilon 2$ from some points of $G$, so $\|x-g_1\|_\infty \le \frac\varepsilon2$ and $\|y-g_2\|_\infty \le \frac\varepsilon2$ for some $g_1,g_2\in G$. If $g_1$ and $g_2$ were the same point, then $\|x-y\|_\infty \le \|x-g\|_\infty + \|y-g\|_\infty \le \frac\varepsilon2 + \frac\varepsilon2 = \varepsilon$ which contradicts the fact that $x,y$ are distinct $\varepsilon$-strictly-separated points. Therefore we have an injection from $E$ to $G$, and $|E|\le|G|=(q+1)^d$. Finally you just have to show that equality is possible for some set $E$.

Answer 2

Under your definitions, placing $\varepsilon$-strictly-separated points in a unit cube is equivalent to placing non-overlapping axis-oriented cubes of side $\varepsilon$ in an axis-oriented cube of side $\varepsilon + 1.$ You can translate a point placement to a cube placement or vice versa by mapping each point to or from the center of a cube of size $\varepsilon$, and placing the cube of side $\varepsilon + 1$ so its center coincides with the center of the unit cube.

For $1/\varepsilon$ an integer I think the result is obvious (just use a total-volume argument). It takes just a little more work in the other case. You might find some ideas in the answers to Number of all squares placed side by side in a rectangle.