Packing number of $\ell_1$ ball in $\ell_{\infty}$ metric

Consider the $d$-dimensional $\ell_1$ ball $\mathbb B_d=\{x\in\mathbb R^d: \|x\|_1\leq 1\}$, where $\|x\|_1=\sum_{i=1}^d{|x_i|}$. I'm interested in the maximum size of the (finite) subset $S\subseteq\mathbb B_d$ such that for any two distinct elements $x,y\in S$, $\|x-y\|_{\infty}\geq \delta$, where $\|z\|_{\infty}=\max_{1\leq i\leq d}|z_i|$. $\delta$ is, of course, strictly between 0 and 1.

My main point of reference is Lemma 5.2 of the following note: https://www.stat.berkeley.edu/~wainwrig/nachdiplom/Chap5_Sep10_2015.pdf

If I understand it correctly, the (lower bound) side of Lemma 5.2 implies that

1. If $\delta\lesssim 1/d$, then $\log |S|\asymp d\log(1/\delta)$ as $d\to\infty$, and this bound is almost tight;
2. However, if $d\delta\to\infty$ it seems to me that the lower bound of $\log |S|$ becomes $\Omega(1)$ as $d\to\infty$, which clearly sounds loose to me.

My question is hence the following: What is the asymptotic scaling of $\log |S|$ as $d\to\infty$ in the regime of $\delta\to 0$ and $d\delta\to\infty$? More concretely, if $\delta\asymp d^{-\alpha}$ for some $\alpha\in(0,1)$, how should $\log |S|$ scale with $d$ as $d\to\infty$? And furthermore, what if we consider the general $\ell_p$ ball $\{x\in\mathbb R^d: \|x\|_p\leq 1\}$ for $1\leq p<\infty$?

1 Answer

I address only the $\ell_1$ question.

Let $k=\lfloor 1/\delta\rfloor$. Then you can take all points in $\mathbb B_d$ with coordinates in $\frac1k\mathbb Z$ (let their number be $f_k(d)$). On the other hand, the $\ell_\infty$-balls centered at the points of $\mathbb B_d$ with coordinates in $\frac1{2k}\mathbb Z$ cover $\mathbb B_d$, so an example cannot contain more than $f_{2k}(d)$ points.

Now we are interested in an asymptotics of $f_k(d)$ (luckily, it is close enough to that of $f_d(2k)$. We have $$f_k(d)=1+\sum_{i=1}^k2^i{k\choose i}{d\choose i}$$ (here we count separately the points with $i$ nonzero coordinates). If, say, $1/\delta\sim k=o(d^{1/2})$, then the main term is with $i=k$, so $f_k(d)=\Theta((2d)^k/k!)$ and hence $\log|S|=\Theta( k\log d)$.

If $k=o(d)$ but $k\neq o(d^{1/2})$ then the index $i_0=k-o(k)$ of the maximal term satisfies $(k-i_0)d\approx k^2$, so $i_0\approx k-k^2/d$. If $k\sim d^\alpha$, then $$f_k(d)\approx 2^{d^\alpha-d^{2\alpha-1}}{d^\alpha\choose d^{2\alpha-1}}{d\choose d^{2\alpha-1}},$$ and for $1>\alpha>1/2$ we have $$\log|S|=\Theta(d^\alpha)=\Theta(k).$$ The other cases can be treated similarly: we only need to realize what is the asymptotics of the main term in $f_k(d)$.