Problem 1606

1. Gram-Schmidt Process and Orthonormal Basis:
We start by applying the Gram-Schmidt process to the unit vectors $v_1, v_2, \ldots, v_d$ to obtain an orthonormal basis $e_1, e_2, \ldots, e_d$ of $\mathbb{R}^d$. This process ensures that each $e_k$ lies in the span of $v_1, \ldots, v_k$.

2. **Choosing the Vector $u$:**
We aim to construct a vector $u = a_1 e_1 + a_2 e_2 + \cdots + a_d e_d$ such that $|u \cdot v_i| \leq \frac{1}{\sqrt{d}}$ for all $i = 1, 2, \ldots, d$. We will choose the coefficients $a_i$ by induction.

3. Inductive Step:
Assume we have chosen $a_1, a_2, \ldots, a_k$ such that $|u_i \cdot v_i| \leq \frac{1}{\sqrt{d}}$ for all $i \leq k$, where $u_k = a_1 e_1 + a_2 e_2 + \cdots + a_k e_k$.

4. Function Definition:
Consider the function $f(t) = (u_k + t e_{k+1}) \cdot v_{k+1}$. Note that $e_{k+1} \cdot v_{k+1} \neq 0$ because if $e_{k+1} \cdot v_{k+1} = 0$, then $v_1, \ldots, v_{k+1}$ would all be perpendicular to $e_{k+1}$. However, since the spans of $e_1, \ldots, e_{k+1}$ and $v_1, \ldots, v_{k+1}$ are the same, this would imply $e_{k+1} \cdot e_{k+1} = 0$, which is a contradiction.

5. **Range of $f(t)$:**
Since $e_{k+1} \cdot v_{k+1} \leq 1$, the function $f(t)$ maps the interval $\left( -\frac{1}{\sqrt{d}}, \frac{1}{\sqrt{d}} \right)$ to an interval of length at most $2 \frac{1}{\sqrt{d}}$. Because $f(t)$ is linear with a non-zero slope, it is surjective on this interval.

6. **Choosing $t_0$:**
There exists a $t_0$ such that $|t_0| \leq \frac{1}{\sqrt{d}}$ and $|f(t_0)| \leq \frac{1}{\sqrt{d}}$. We set $a_{k+1} = t_0$.

7. **Constructing $u$:**
By repeating this process for $k = 1, 2, \ldots, d$, we construct a vector $u$ such that $|u \cdot v_i| \leq \frac{1}{\sqrt{d}}$ for all $i = 1, 2, \ldots, d$.

8. Normalization:
The vector $u$ constructed in this manner may not be a unit vector. However, since $\|u\| \geq 1$, we can normalize $u$ by setting $u' = \frac{u}{\|u\|}$. This ensures that $u'$ is a unit vector and $|u' \cdot v_i| \leq \frac{1}{\sqrt{d}}$ for all $i$.

$\blacksquare$