Banaszczyk: the Komlós bound
ProvedKomlos.banaszczyk_bound(Banaszczyk 1998.) There is a constant such that any vectors of Euclidean norm at most , in any dimension, admit signs with every coordinate of the signed sum at most in absolute value. This was the best bound toward the Komlós conjecture for nearly three decades, until the bound of Bansal--Jiang (2025). The formal statement uses so the bound is positive for all ; the dimension is unrestricted (coordinates whose column of entries has small norm are controlled automatically, reducing to effective dimension ).
import Mathlib import Definitions.Def_Komlos_model
namespace Komlos
theorem banaszczyk_bound :
∃ C : ℝ, 0 < C ∧ ∀ (n m : ℕ) (v : Fin n → EuclideanSpace ℝ (Fin m)),
(∀ i, ‖v i‖ ≤ 1) →
∃ ε : Fin n → ℝ, IsSignVector ε ∧
∀ j, |∑ i, ε i * v i j| ≤ C * Real.sqrt (Real.log (n + 2)) := by sorry
end KomlosRead-back
What the Lean code literally says, in plain math · claude-fable-5
Read-back: Komlos.banaszczyk_bound
The theorem asserts: there exists a real constant with such that for every natural number (the number of vectors, including ), every natural number (the ambient dimension, including ), and every family of vectors in the Euclidean space (formally, functions from an index set of size into equipped with the Euclidean norm), if every vector satisfies
then there exists a function assigning a real number to each index which is a sign vector — meaning, unfolding the custom definition IsSignVector, that for every index , either or — such that for every coordinate ,
Here denotes the -th coordinate of the vector , the sum is over all indices , and the logarithm is the natural logarithm applied to the real number (so the argument is at least and the square root is of a strictly positive quantity for every ). The bound is on the absolute value of each individual coordinate of the signed sum ; taken over all , this says the norm of the signed sum is at most . The order of quantifiers makes a single universal constant: it is chosen first and must work simultaneously for all , all , and all norm-bounded families .
Degenerate cases silently included: when the sum is empty, so the left-hand side is and the claim reduces to , with the sign condition on the empty family holding vacuously; when there are no coordinates , so the final condition holds vacuously (and every is the zero vector of ); the sign vector is only required to take values — no further structure is imposed on it. The hypothesis uses the Euclidean () norm on , while the conclusion bounds coordinates (equivalently, the norm). The statement asserts only existence of some positive constant ; no explicit value of is specified.
Confirmed by the mission captain (proposal self-audit).