16
$\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.

| cite | improve this question | | | | |
$\endgroup$
  • $\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 at 18:40
27
$\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 :-)

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thanks! It seems you even did not use that the dimension is equal to $n$. $\endgroup$ – MKO Feb 15 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 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 at 23:10
  • $\begingroup$ That's very interesting. Do you write down notes for such courses? $\endgroup$ – aglearner Feb 16 at 0:09
  • $\begingroup$ @aglearner Alas, no. I'm too lazy :-) $\endgroup$ – fedja Feb 16 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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\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 at 23:52
  • 1
    $\begingroup$ $n^{-1/2}$ was for one particular $u$. By linearity of expectations we can multiply by $n$. $\endgroup$ – Sandeep Silwal Feb 19 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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