18
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @AlexandreEremenko, $4/\pi < \sqrt2$, so doesn't the bound you quote for $n = 2$ imply the one that @‌MKO wants? $\endgroup$
    – LSpice
    Feb 14, 2020 at 18:40

2 Answers 2

29
$\begingroup$

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 :-)

$\endgroup$
6
  • $\begingroup$ Thanks! It seems you even did not use that the dimension is equal to $n$. $\endgroup$
    – asv
    Feb 15, 2020 at 1:05
  • 2
    $\begingroup$ What are the courses in which students learn about Bang's solution of the Tarsky plank's problem? Is there some online course like that? $\endgroup$
    – aglearner
    Feb 15, 2020 at 22:10
  • 2
    $\begingroup$ @aglearner I sometimes include it into "History of Mathematics" (just because I believe it is more interesting and useful than, say, Roman numerals). "Explorations in modern math." might be another good place for it but there one cannot be sure that the students know vectors well enough. There is also "Euclidean geometry for teachers" but I taught that one only once and did something else. As to online courses, I just don't know. $\endgroup$
    – fedja
    Feb 15, 2020 at 23:10
  • $\begingroup$ That's very interesting. Do you write down notes for such courses? $\endgroup$
    – aglearner
    Feb 16, 2020 at 0:09
  • $\begingroup$ @aglearner Alas, no. I'm too lazy :-) $\endgroup$
    – fedja
    Feb 16, 2020 at 12:10
0
$\begingroup$

(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.

$\endgroup$
2
  • $\begingroup$ I don't understand the claim in your last sentence. How do you go from $c n^{-1/2}$ to $c n^{1/2}$? $\endgroup$
    – kodlu
    Feb 19, 2020 at 23:52
  • 1
    $\begingroup$ $n^{-1/2}$ was for one particular $u$. By linearity of expectations we can multiply by $n$. $\endgroup$ Feb 19, 2020 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.