Documentation

Atlas.ProbabilisticMethodsInCombinatorics.code.Chapter5.KomlosConjecture

theorem Discrepancy.komlos_conjecture :
∃ (K : ), 0 < K ∀ (n m : ) (v : Fin mEuclideanSpace (Fin n)), (∀ (i : Fin m), v i 1)∃ (ε : Fin m), (∀ (i : Fin m), ε i = 1 ε i = -1) ∀ (j : Fin n), |i : Fin m, ε i * (v i).ofLp j| K

Komlós conjecture (Conjecture 5.1.5). There exists an absolute constant $K > 0$ such that for any vectors $v_1, \dots, v_m \in \mathbb{R}^n$ with $\|v_i\| \leq 1$, one can choose signs $\varepsilon_i \in \{\pm 1\}$ so that $\left\|\sum_i \varepsilon_i v_i\right\|_\infty \leq K$.