This is a question I originally asked on math.stackexchange, but didn't receive a satisfying answer.
Let $\epsilon>0$ and consider constructing a set $S_\epsilon\subseteq S^{d-1}$ of points on the sphere $\{x\in\mathbb R^d \mid \left\|x\right\|_2=1\}$, such that $$ \mathbb E\left[\min_{y\in S_\epsilon}\left\|x-y\right\|_2^2\right]\le \epsilon, $$
where $x$ is a random point on the sphere and the expectation is with respect to the choice of $x$.
How big must $S_\epsilon$ be?
I'm looking for a lower bound, although an upper bound may be interesting as well.
The motivation for this problem comes from an attempt to prove a lower bound on the number of bits that are needed to send a real-valued vector $x\in\mathbb R^d$ such that the receiver can estimate $x$ to within an ($\ell_2$ squared) error of $\epsilon\left\|x\right\|_2^2$. The formulation requires a few extra steps (including Yao's Minimax principle), but this is the component I'm missing.
