Covering/packing number of a sphere instead of a ball

278 Views Asked by At

Let $\Theta$ be a subset of $\mathbb{R}^d$ with the Euclidean norm. Let the covering number $N_2(\Theta, \epsilon)$ denote the smallest $n$ such that there exists a covering $\{\theta_1, \ldots, \theta_n\} \subseteq \Theta$ of $\Theta$, that is, $\min_{1 \le i \le n} \|\theta - \theta_i\|_2 < \epsilon$ for any $\theta \in \Theta$.

When $\Theta$ is the unit ball, we have $$\frac{1}{\epsilon^d} \le N(\Theta, \epsilon) \le \left(1 + \frac{2}{\epsilon}\right)^d,$$ see Example 14.1 here or Section 6.1.3 here.

I am wondering whether these asymptotics hold when $\Theta$ is the unit sphere. Clearly a covering of the ball is also a covering of the sphere, so the upper bound of $(1 + 2/\epsilon)^d$ still holds. But I am not sure whether the lower bound is still tight. The covering number could be much smaller, but it is also possibly that in high dimensions it still behaves like $c\epsilon^{-d}$.

The only similar question I could find was this one which is still unanswered, although they seem to think the exponent should be $d-1$ rather than $d$.