The volumetric lower bound on covering numbers

ProofIntermediate⏱ 30 minHigh-Dim Probabilitycovering numbervolumelower bound

Theory: Nets, Covering Numbers and Metric Entropy →

Problem

Prove that any $\eps$ -net of the unit ball $B^d$ in the Euclidean metric has at least $\eps^{-d}$ points, and that a maximal $\eps$ -separated set has at most $(3/\eps)^d$ . Deduce $\log N(B^d,\|\cdot\|_2,\eps) = \Theta(d\log(1/\eps))$ for $\eps$ bounded away from $1$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Volume concentrates near the boundary	High-Dim Probability	Numerical	Beginner	15 min
Single-stream decode latency floors	LLM Ops	Numerical	Intermediate	30 min
The irreducible loss is the conditional entropy	LLMs	Proof	Intermediate	30 min
The operator norm on a net	High-Dim Probability	Proof	Intermediate	30 min
Covering numbers of the set of sparse unit vectors	High-Dim Probability	Proof	Advanced	1 hour