/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilKomló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.$$
For a long time the best known bound was 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 implies the Beck–Fiala conjecture that set systems of degree $t$ have discrepancy $O(\sqrt{t})$.
The conjecture was proved in September 2026 by Guo, Fang and Lu with $K = 3\sqrt{2\pi}$.
Karingula and Lovett gave an elementary proof with $K = 36$. A formalisation of their proof is
recorded in the formal_proof attributes below.
References:
@[expose] public sectionnamespace KomlosConjectureset_option linter.style.formal_proof_palomar false inThe 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$.
Proved by Guo, Fang and Lu with $K = 3\sqrt{2\pi}$ and by Karingula and Lovett with $K = 36$.
@[category research solved, AMS 5, formal_proof using formal_conjectures at
"https://github.com/mo271/formal-conjectures/blob/416b6597cb193b6745748fdfef0d64342c71dae9/FormalConjectures/Wikipedia/KomlosConjecture.lean#L64"]
theorem komlos_conjecture :
∃ K : ℝ, 0 < K ∧ ∀ (n m : ℕ) (v : Fin n → Fin m → ℝ),
(∀ i, ∑ j, (v i j) ^ 2 ≤ 1) →
∃ ε : Fin n → ℝ, (∀ i, ε i = 1 ∨ ε i = -1) ∧
∀ j, |∑ i, ε i * v i j| ≤ K := ⊢ ∃ K,
0 < K ∧
∀ (n m : ℕ) (v : Fin n → Fin m → ℝ),
(∀ (i : Fin n), ∑ j, v i j ^ 2 ≤ 1) →
∃ ε, (∀ (i : Fin n), ε i = 1 ∨ ε i = -1) ∧ ∀ (j : Fin m), |∑ i, ε i * v i j| ≤ K
All goals completed! 🐙set_option linter.style.formal_proof_palomar false inBanaszczyk'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 was the best known bound towards the Komlós conjecture before its solution. (The shift $n + 2$ inside the logarithm is a harmless normalization keeping it positive for $n \in {0, 1}$.) It follows from the Komlós conjecture with $C = 36 / \sqrt{\log 2}$.
[W. Banaszczyk, Balancing vectors and Gaussian measures of n-dimensional convex bodies, Random Structures & Algorithms 12 (1998), 351–360.]
@[category research solved, AMS 5, formal_proof using formal_conjectures at
"https://github.com/mo271/formal-conjectures/blob/416b6597cb193b6745748fdfef0d64342c71dae9/FormalConjectures/Wikipedia/KomlosConjecture.lean#L86"]
theorem komlos_conjecture.variants.banaszczyk :
∃ C : ℝ, 0 < C ∧ ∀ (n m : ℕ) (v : Fin n → Fin m → ℝ),
(∀ i, ∑ j, (v i j) ^ 2 ≤ 1) →
∃ ε : Fin n → ℝ, (∀ i, ε i = 1 ∨ ε i = -1) ∧
∀ j, |∑ i, ε i * v i j| ≤ C * Real.sqrt (Real.log (n + 2)) := ⊢ ∃ C,
0 < C ∧
∀ (n m : ℕ) (v : Fin n → Fin m → ℝ),
(∀ (i : Fin n), ∑ j, v i j ^ 2 ≤ 1) →
∃ ε, (∀ (i : Fin n), ε i = 1 ∨ ε i = -1) ∧ ∀ (j : Fin m), |∑ i, ε i * v i j| ≤ C * √(Real.log (↑n + 2))
All goals completed! 🐙Sanity check: with no vectors at all ($n = 0$), the empty signed sum is $0$ in every coordinate, so any constant bound holds.
@[category test, AMS 5]
theorem komlos_conjecture.variants.zero_vectors (m : ℕ) (v : Fin 0 → Fin m → ℝ) :
∃ ε : Fin 0 → ℝ, (∀ i, ε i = 1 ∨ ε i = -1) ∧
∀ j, |∑ i, ε i * v i j| ≤ 1 :=
⟨Fin.elim0, fun i => i.elim0, m:ℕv:Fin 0 → Fin m → ℝ⊢ ∀ (j : Fin m), |∑ i, i.elim0 * v i j| ≤ 1 All goals completed! 🐙⟩end KomlosConjecture