8
$\begingroup$

Given $n$ vectors $v_1,\dots,v_n\in\Bbb R^N$ with $\|v_i\|_2^2\leq1$ at every $i\in\{1,\dots,n\}$, Komlos conjecture states that, there is a $c\in\Bbb R$ (independent of $n,N$) such that at some $\epsilon\in\{-1,+1\}^n$, $$\Big\|\sum_{i=1}^n\epsilon_iv_i\Big\|_\infty<c.$$ What is best lower bound known for $c$?

Best upper bound is $c=O(\sqrt{\log n})$.

Is there a set of examples for $c=1+\delta$ for any $\delta>0$ where Komlos conjecture fails?

$\endgroup$
  • $\begingroup$ An easy way to see that $c$ must be at least $\frac{3}{2}$ is to consider the vectors $\frac{1}{2}(1,1,1,1)$,$\frac{1}{2}(1,1,-1,-1)$, and $\frac{1}{2}(1,-1,1,-1)$. Not sure if this warrants an answer. $\endgroup$ – Klaus Draeger Aug 18 '15 at 17:17
  • $\begingroup$ @KlausDraeger Yes it does if you can also tell the logic behind the example. I can see how you might have constructed this. $\endgroup$ – T.... Aug 19 '15 at 0:52
8
$\begingroup$

A simple way of obtaining a lower bound $c\ge\sqrt{2}$ is to consider pairs of vectors $u,v\in\mathbb{R}$. First of all, it makes sense to focus on pairs of unit vectors for which all $\{-1,1\}$-linear combinations are as long as possible (note that this is just an interesting special case, I'm not saying that it is opotimal in any way). This is achieved when $u,v$ are orthogonal, and by checking the possible rotations we find that $u=\frac{1}{\sqrt{2}}(1,1), v=\frac{1}{\sqrt{2}}(1,-1)$ show that $c$ must be at least $\sqrt{2}$.

This example can be generalized to the sets of vectors $V_k=\{2^{-\frac{k}{2}}v_{i,k}\ |\ 0\le i\le k\}\subseteq\mathbb{R}^{2^k}$, where the $j$-th coefficient $(v_{i,k})_j$ of $v_{i,k}$ is $1$ if the $i-th$ binary digit in $j$ is $0$, and $-1$ otherwise.

The $\infty$-norm of any $\{-1,1\}$-linear combination of the vectors in $V_k$ is $(k+1)2^{-\frac{k}{2}}$, which reaches its maximum $\frac{3}{2}$ at $k=2$, with the set of vectors

$V_2=\{\frac{1}{2}(1,1,1,1),\frac{1}{2}(1,1,-1,-1),\frac{1}{2}(1,-1,1,-1)\}$.

There may be better lower bounds, but this is a start.

$\endgroup$
  • $\begingroup$ It seems to me that your example is already pretty good. Could $c$ be much more than this? $\endgroup$ – T.... Aug 20 '15 at 9:41
4
$\begingroup$

Taking the $v_i$ to be the columns of this matrix shows $c \geq \frac{4}{\sqrt{6}} \approx 1.633$ (I found and verified the matrix by computer experiment):

$$M = \frac{1}{\sqrt{6}}\begin{pmatrix} 1 & 1 & 1 & -1 & 1 & -1\\ 1 & 1 & -1 & 1 & -1 & -1\\ -1 & 1 & 1 & 1 & 1 & 1\\ -1 & 1 & 1 & -1 & -1 & 1\\ -1 & -1 & 1 & 1 & -1 & -1 \\ -1 & 1 & -1 & -1 & 1 & -1 \end{pmatrix}$$

$\endgroup$
-3
$\begingroup$

There is no best lower bound, because c is an upper bound. The best known upper bound is $O(\sqrt{\log n})$, as proved by Banaszczyk in 1998.

$\endgroup$
  • 7
    $\begingroup$ There is no best lower bound - I don't understand what you mean by this. I interpret the question as "what is the largest $c$ for which the conjecture statement is known to be false?" which seems well-defined. $\endgroup$ – usul Aug 17 '15 at 21:16
  • 2
    $\begingroup$ Turbo: Ok, so you have corrected your formuation, but it still lacks mathematical precision, because for all we know, the Komlos conjecture may be false, so that there might not be "smallest such value" for the c's, because the set is not bounded below. Now if your question is something like "Assuming that the Komlos conjecture is true, what is the infimum of the c's"? then the best currently known answer is "I don't know." usul: That's a nice interpretation. I don't think anyone looked into it with much depth. In some ad-hoc experiments I did, I found that there are counterexamples for c = 2. $\endgroup$ – Yossi Lonke Aug 18 '15 at 7:17
  • $\begingroup$ @Turbo Why don't you delete the whole post? $\endgroup$ – Yossi Lonke Aug 18 '15 at 8:43

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.