4

Let $\varepsilon > 0$. Let $k_d(\varepsilon)$ be the minimum number of balls $B(x, \varepsilon) \subset \mathbb{R}^d$, $x \in \mathbb{S}^{d-1}$, w.r.t. the usual metric in $\mathbb{R}^d$, needed in order for the balls to cover $\mathbb{S}^{d-1}$.

Is there a neat way to calculate $k_d(\varepsilon)$? I'm interested in the rate at which it increases as $d$ grows. For example, the ratios $k_{d+1}(\varepsilon) / k_d(\varepsilon)$, would suffice.

So far, I have tried to look at regular polygons with vertexes on $\mathbb{S}^{d-1}$ and areas of spherical caps around $x$ in comparison to the area of $\mathbb{S}^{d-1}$, but things tend to get quite messy: For example with the spherical caps you end up looking at regularized incomplete Beta functions.

If somebody has a slick way to approach this, I would appreciate it if they shared. Of course literary references to something related to this would be great as well.

Thanks!

EDIT: It turns out that people have been seriously working on optimal spherical coverings. However, they study something called "covering density" which I'm not instantly sure how to turn into a number of spheres.

Matias Heikkilä
  • 2,542

1 Answers1

0

Some progress on a lower bound based on a result on covering density:

Let $\text{vol}$ denote the $d-1$ dimensional volume. The covering density of $a \, \mathbb{S}^{d-1}$, $a > 0$ is defined as $$ \nu \left( a\, \mathbb{S}^{d-1} \right) = \min \limits _{\mathcal{U}} \frac{ \sum \limits_{B \in \mathcal{U}} \text{vol} \left( B \cap a\,\mathbb{S}^{d-1} \right)}{\text{vol} \left(a\, \mathbb{S}^{d-1} \right)},$$ where $\mathcal{U}$ is a covering of $\mathbb{S}^{d-1}$ with unit balls. Now if $a > 0$ is large enough, according to Coxeter-Few-Rogers lower bound (see the paper linked in the EDIT above) there is a constant $c>0$ such that $$\nu \left(a \, \mathbb{S}^{d-1}\right) > c (d-1).$$

Now, we may turn things around. Let $a=1$ and require instead of $a>0$ being large enough, that $\varepsilon>0$, as in the original post, is small enough (if I have understood correctly, $\varepsilon < 1/2$ should do). We may normalize the $d-1$ dimensional volume s.t. $\text{vol}\left( \mathbb{S}^{d-1}\right)=1.$ Then the bound above reads as $$c (d-1) < \min \limits_{\mathcal{U}} \sum \limits_{B \in \mathcal{U}} \text{vol} \left( B_\varepsilon \cap \mathbb{S}^{d-1} \right) =k_d(\varepsilon) V_{d,\varepsilon},$$ where $k_d(\varepsilon)$ is as in the original post and $V_{d,\varepsilon}$ is the normalized $d-1$ volume of the spherical cap obtained as an intersection $B(x,\varepsilon) \cap \mathbb{S}^{d-1}$, $x \in \mathbb{S}^{d-1}$. Then $$k_d(\varepsilon) >c(d-1)/V_{d,\varepsilon}.$$ The question is then what happens to $V_{d,\varepsilon}$ as $d$ increases. Intuitively, I would say that $V_{d,\varepsilon} \to 0$, quickly, since by our normalization this is just the fraction of area of the sphere covered by the cap. This seems a bit tricky to show, though!

Matias Heikkilä
  • 2,542