Komlós conjecture

The Komlós conjecture in discrepancy theory: there is a universal constant $K$ such that for all $n, m$ and all vectors $v_1, \dots, v_n \in \mathbb{R}^m$ with $\|v_i\|_2 \le 1$, there exist signs $\varepsilon_i \in \{-1, +1\}$ such that $$\left\|\sum_{i=1}^n \varepsilon_i v_i\right\|_\infty \le K.$$

The best known bound is due to Banaszczyk, who proved that one can always achieve $O(\sqrt{\log n})$. The Beck–Fiala theorem on the discrepancy of sparse set systems is a special case (up to scaling), and the conjecture would imply the Beck–Fiala conjecture that set systems of degree $t$ have discrepancy $O(\sqrt{t})$.

References:

• Wikipedia
• W. Banaszczyk, Balancing vectors and Gaussian measures of n-dimensional convex bodies, Random Structures & Algorithms 12 (1998), 351–360
• J. Spencer, Six standard deviations suffice, Trans. Amer. Math. Soc. 289 (1985), 679–706

theorem KomlosConjecture.komlos_conjecture : ∃ (K : ℝ), 0 < K ∧ ∀ (n m : ℕ) (v : Fin n → Fin m → ℝ), (∀ (i : Fin n), ∑ j : Fin m, v i j ^ 2 ≤ 1) → ∃ (ε : Fin n → ℝ), (∀ (i : Fin n), ε i = 1 ∨ ε i = -1) ∧ ∀ (j : Fin m), |∑ i : Fin n, ε i * v i j| ≤ K

The Komlós conjecture

There exists a universal constant $K > 0$ such that for all $n, m \in \mathbb{N}$ and all vectors $v_1, \dots, v_n \in \mathbb{R}^m$ with $\|v_i\|_2 \le 1$ (encoded here as $\sum_j v_{ij}^2 \le 1$), there exist signs $\varepsilon_i \in \{-1, +1\}$ such that $\left\|\sum_i \varepsilon_i v_i\right\|_\infty \le K$, i.e. $\left|\sum_i \varepsilon_i v_{ij}\right| \le K$ for every coordinate $j$.

theorem KomlosConjecture.komlos_conjecture.variants.banaszczyk : ∃ (C : ℝ), 0 < C ∧ ∀ (n m : ℕ) (v : Fin n → Fin m → ℝ), (∀ (i : Fin n), ∑ j : Fin m, v i j ^ 2 ≤ 1) → ∃ (ε : Fin n → ℝ), (∀ (i : Fin n), ε i = 1 ∨ ε i = -1) ∧ ∀ (j : Fin m), |∑ i : Fin n, ε i * v i j| ≤ C * √(Real.log (↑n + 2))

Banaszczyk's theorem

There exists a constant $C > 0$ such that for all $n, m \in \mathbb{N}$ and all vectors $v_1, \dots, v_n \in \mathbb{R}^m$ with $\|v_i\|_2 \le 1$, there exist signs $\varepsilon_i \in \{-1, +1\}$ such that $\left\|\sum_i \varepsilon_i v_i\right\|_\infty \le C \sqrt{\log(n + 2)}$. This is the best known bound towards the Komlós conjecture. (The shift $n + 2$ inside the logarithm is a harmless normalization keeping it positive for $n \in \{0, 1\}$.)

[W. Banaszczyk, Balancing vectors and Gaussian measures of n-dimensional convex bodies, Random Structures & Algorithms 12 (1998), 351–360.]

theorem KomlosConjecture.komlos_conjecture.variants.zero_vectors (m : ℕ) (v : Fin 0 → Fin m → ℝ) : ∃ (ε : Fin 0 → ℝ), (∀ (i : Fin 0), ε i = 1 ∨ ε i = -1) ∧ ∀ (j : Fin m), |∑ i : Fin 0, ε i * v i j| ≤ 1

Sanity check: with no vectors at all ($n = 0$), the empty signed sum is $0$ in every coordinate, so any constant bound holds.