Constante na conjectura de Komlos

$n$$v_1,\dots,v_n\in\Bbb R^N$$\|v_i\|_2^2\leq1$$i\in\{1,\dots,n\}$$c\in\Bbb R$$n,N$$\epsilon\in\{-1,+1\}^n$

O melhor limite superior é .$c=O(\sqrt{\log n})$

Existe um conjunto de exemplos para para qualquer que a conjectura de Komlos falha?$c=1+\delta$$\delta>0$

Uma maneira simples de obter um limite inferior é considerar pares de vetores . Antes de tudo, faz sentido focar nos pares de vetores unitários para os quais todas as combinações lineares - são tão longas quanto possível (observe que esse é apenas um caso especial interessante, não estou dizendo que é opotimal de qualquer maneira). Isso é obtido quando são ortogonais e, verificando as possíveis rotações, descobrimos que mostra que deve ser pelo menos .$c\ge\sqrt{2}$$u,v\in\mathbb{R}$$\{-1,1\}$$u,v$$u=\frac{1}{\sqrt{2}}(1,1), v=\frac{1}{\sqrt{2}}(1,-1)$$c$$\sqrt{2}$

Este exemplo pode ser generalizado para os conjuntos de vetores , onde o coeficiente de é se o dígito binário em for e caso contrário.$V_k=\{2^{-\frac{k}{2}}v_{i,k}\ |\ 0\le i\le k\}\subseteq\mathbb{R}^{2^k}$$j$$(v_{i,k})_j$$v_{i,k}$$1$$i-th$$j$$0$$-1$

A -norm de qualquer combinação linear dos vetores em é , que atinge seu máximo em , com o conjunto de vetores$\infty$$\{-1,1\}$$V_k$$(k+1)2^{-\frac{k}{2}}$$\frac{3}{2}$$k=2$

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

Pode haver limites inferiores melhores, mas isso é um começo.

Tomando o como as colunas desta matriz mostra (eu encontrei e verifiquei a matriz por experimento em computador):$v_i$$c \geq \frac{4}{\sqrt{6}} \approx 1.633$

Não há melhor limite inferior, porque c é um limite superior. O limite superior mais conhecido é , conforme comprovado por Banaszczyk em 1998.$O(\sqrt{\log n})$