Constante en la conjetura 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$

El mejor límite superior es $c=O(\sqrt{\log n})$ .

¿Hay un conjunto de ejemplos para $c=1+\delta$ para cualquier $\delta>0$ donde falla la conjetura de Komlos?

Una manera simple de obtener un límite inferior es considerar los pares de vectores . En primer lugar, tiene sentido centrarse en pares de vectores unitarios para los que todas las combinaciones lineales son lo más largas posible (tenga en cuenta que este es solo un caso especial interesante, no estoy diciendo que es opotimal de cualquier manera). Esto se logra cuando son ortogonales, y al verificar las posibles rotaciones encontramos que muestran que debe ser al 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 ejemplo se puede generalizar a los conjuntos de vectores , donde el -ésimo coeficiente de es si el dígito binario en es , y caso contrario.$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$

La -norm de cualquier combinación lineal de los vectores en es , que alcanza su máximo en , con el conjunto de vectores$\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)\}$ .

Puede haber mejores límites inferiores, pero este es un comienzo.

Si consideramos que son las columnas de esta matriz, se muestra (encontré y verifiqué la matriz mediante un experimento informático):$v_i$$c \geq \frac{4}{\sqrt{6}} \approx 1.633$

No hay mejor límite inferior, porque c es un límite superior. El límite superior más conocido es , como lo demostró Banaszczyk en 1998.$O(\sqrt{\log n})$