Reference to a conjecture on unit vectors in Euclidean space

Question

I have heard that there exists the following conjecture (if I am not mistaken).

Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists another unit vector $x$ such that $$\sum_{i=1}^n |( x,u_i)|\geq \sqrt{n}.$$

I am looking for a reference for this conjecture. Also I will be happy to know what is known about it.

Answer 1

That isn't a conjecture but a routine exercise assigned after the students learn about Bang's solution of the Tarski plank problem. The proof goes in 2 steps:

1) Consider all sums $\sum_j \varepsilon_i u_i$ with $\varepsilon_i=\pm 1$ and choose the longest one. Replacing some $u_j$ with $-u_j$ if necessary, we can assume WLOG that it is $y=\sum_i u_i$. Comparing $y$ with $y-2u_i$ (a single sign flip) we get $$ \|y\|^2\ge \|y-2u_i\|^2=\|y\|^2-4\langle y,u_i\rangle+4\|u_i\|^2 $$ whence $\langle y,u_i\rangle\ge 1$ for all $i$. (That part is the main step in the solution of the plank problem).

2) Now we have $\|y\|^2=\sum_i\langle y,u_i\rangle\ge n$, so for $x=\frac y{\|y\|}$, we get $$ \sum_i\langle x,u_i\rangle=\sqrt{\sum_i\langle y,u_i\rangle}\ge \sqrt n $$ The End :-)

Answer 2

(Too long for a comment).

Here is a way to get $\ge c \sqrt{n}$ for some constant $c$: First pick $x$ uniformly at random from the sphere and consider $\mathbf{E}|\langle x,u_1 \rangle|$. We can assume the first vector of the basis is $u_1$ and form the rest of the orthonormal basis. Then the expected value is just the absolute value of the first coordinate $|x_1|$.

To calculate this, we note that we can generate a random vector by taking a random gaussian and normalizing it. This means that

$$\mathbf{E}|\langle x,u_1 \rangle| = \int_0^{\infty} \mathbf{P}(|x_1| \ge t) \ dt \approx \int_0^{\infty} \mathbf{P}(g \ge t \sqrt{n})\ dt $$ where $g$ is a standard normal random variable. In the approximation step, we use strong concentration of chi-squared random variables to say the norm of a random gaussian vector concentrates around $\sqrt{n}$ (the details need to be spelled out but they should be straightforward). Finally, the tail of the gaussian tells us that $\mathbf{P}(g \ge t \sqrt{n}) \le \exp(-t^2n)$ so the integral evaluates to $c/\sqrt{n}$ for some fixed constant $c$.

Since the expected value is at least $c \sqrt{n}$, this tells us that there exists a $x$ for which the bound holds.