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


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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.