How many nearly-orthogonal directions fit in R^d?

ProofAdvanced⏱ 30 minHigh-Dim Probabilitynear-orthogonalityunion boundpacking

Theory: High-Dimensional Geometry and Concentration of the Norm →

Problem

Fix $\eps\in(0,1)$ . Show that there exist $N = e^{c d\eps^2}$ unit vectors in $\R^d$ with all pairwise inner products at most $\eps$ in absolute value, for an absolute constant $c>0$ . Compute the value of $N$ for $d=768$ and $\eps=0.2$ .

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

Hints

Hints — 0 of 3 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
When is the union bound tight?	Probability	Proof	Foundation	15 min
Generalisation for a finite class	Learning Theory	Proof	Beginner	30 min
Volume concentrates near the boundary	High-Dim Probability	Numerical	Beginner	15 min
Simulate the measure of a spherical cap run	High-Dim Probability	Coding	Intermediate	30 min
The per-stage quantile budget, and when it is tight	AI Systems	Proof	Intermediate	1 hour