<p>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}$.</p>

<p>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.</p>

<p>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</p>

<p>$V_2=\{\frac{1}{2}(1,1,1,1),\frac{1}{2}(1,1,-1,-1),\frac{1}{2}(1,-1,1,-1)\}$.</p>

<p>There may be better lower bounds, but this is a start.</p>

CC BY-SA 3.0
2015-08-20T09:41:29.090Z
It seems to me that your example is already pretty good. Could $c$ be much more than this?
Turbo
CC BY-SA 3.0
2015-08-19T12:33:04.997Z
2015-08-21T13:02:57.210Z
2015-08-21T13:02:57.210Z
Klaus Draeger
<p>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):</p>

<p>$$M = \frac{1}{\sqrt{6}}\begin{pmatrix}
1 &amp; 1 &amp; 1 &amp; -1 &amp; 1 &amp; -1\\
1 &amp; 1 &amp; -1 &amp; 1 &amp; -1 &amp; -1\\
-1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1\\
-1 &amp; 1 &amp; 1 &amp; -1 &amp; -1 &amp; 1\\
-1 &amp; -1 &amp; 1 &amp; 1 &amp; -1 &amp; -1 \\
-1 &amp; 1 &amp; -1 &amp; -1 &amp; 1 &amp; -1
\end{pmatrix}$$ </p>

CC BY-SA 4.0
2018-06-07T21:03:56.617Z
2018-06-07T21:03:56.617Z
Chris Jones
<p>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 <a href="http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1098-2418(199807)12:4%3C351::AID-RSA3%3E3.0.CO;2-S/abstract?deniedAccessCustomisedMessage=&amp;userIsAuthenticated=false" rel="nofollow">Banaszczyk</a> in 1998.</p>

CC BY-SA 3.0
2015-08-17T21:16:44.800Z
*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.
usul
CC BY-SA 3.0
2015-08-18T07:17:42.257Z
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.
Yossi Lonke
CC BY-SA 3.0
2015-08-18T08:43:18.187Z
@Turbo  Why don't you delete the whole post?
Yossi Lonke
CC BY-SA 3.0
2015-08-17T13:26:41.360Z
2015-08-17T13:26:41.360Z
Yossi Lonke
<p>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&lt;c.$$ What is best <strong>lower bound</strong> known for $c$?</p>

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

<p>Is there a set of examples for $c=1+\delta$ for any $\delta&gt;0$ where Komlos conjecture fails?</p>

CC BY-SA 3.0
2015-08-18T17:17:25.900Z
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.
Klaus Draeger
CC BY-SA 3.0
2015-08-19T00:52:41.700Z
@KlausDraeger Yes it does if you can also tell the logic behind the example. I can see how you might have constructed this.
Turbo
<co.combinatorics><extremal-combinatorics>
Constant in Komlos conjecture
Turbo
# Constant in Komlos conjecture

(Asked by: username_0 on 2015-08-17)

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\|\_\inftylower 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?

**Tags:** co.combinatorics, extremal-combinatorics

> **Comments:**
> **username_1**: 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.  
> **username_0**: @KlausDraeger Yes it does if you can also tell the logic behind the example. I can see how you might have constructed this.  

---

## 3 answers

### Answer by username_1 on 2015-08-19. Score: 8

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.

> **Comments:**
> **username_0**: It seems to me that your example is already pretty good. Could $c$ be much more than this?  

---

### Answer by username_2 on 2018-06-07. Score: 5

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}$$


---

### Answer by username_3 on 2015-08-17. Score: -3

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](http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1098-2418(199807)12:4%3C351::AID-RSA3%3E3.0.CO;2-S/abstract?deniedAccessCustomisedMessage=&userIsAuthenticated=false) in 1998.

> **Comments:**
> **username_4**: *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.  
> **username_3**: username_0: 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." username_4: 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.  
> **username_3**: @username_0  Why don't you delete the whole post?  

---

