Komlós discrepancy (Bansal–Jiang)
ProvedKomlos.bansal_jiang_komlos_boundThere are constants and such that for all and all vectors with , some signs give — the bound, with the hidden factor rendered as and both constants quantified before all instances. The first improvement over Banaszczyk's since 1998.
import Mathlib import Definitions.Def_Komlos_model
namespace Komlos
theorem bansal_jiang_komlos_bound :
∃ C γ : ℝ, 0 < C ∧ 0 < γ ∧
∀ (n m : ℕ) (v : Fin n → EuclideanSpace ℝ (Fin m)), (∀ i, ‖v i‖ ≤ 1) →
∃ ε : Fin n → ℝ, IsSignVector ε ∧
∀ j, |∑ i, ε i * v i j| ≤
C * Real.log (n + 2) ^ ((1 : ℝ) / 4) *
Real.log (Real.log (n + 8)) ^ γ := by sorry
end KomlosRead-back
What the Lean code literally says, in plain math · claude-fable-5
Read-back of bansal_jiang_komlos_bound
The theorem asserts the existence of two real constants and , with and , chosen once and for all before any other data — so the same pair must work uniformly for every choice of dimensions and vectors below. Note that is only required to be some positive real; no specific value of (nor of ) is pinned down by the statement.
Given such and , the claim is: for every natural number (the number of vectors), every natural number (the ambient dimension), and every family of vectors in Euclidean space (equipped with the standard norm) satisfying the hypothesis that each vector has Euclidean norm at most one,
there exists a function which is a sign vector — meaning, unfolding the bundle's definition IsSignVector, that every entry satisfies or — such that every coordinate of the signed sum obeys
where denotes the -th coordinate of , is the natural logarithm on the reals, and the powers are real-exponent powers (exponents and as real numbers). This is a coordinatewise () bound on the signed sum, with a non-strict inequality .
Details of the bound's exact form, including argument shifts:
- The natural number is cast into the reals inside the logarithms; the arguments are shifted: the single logarithm is taken at , and the iterated logarithm is — the inner shift is , and there is no outer shift or additional constant inside the outer log.
- Because and for every natural (including ), both bases are strictly positive: and . So the real powers are the ordinary positive powers, the right-hand side is strictly positive for every , and no degenerate branch of the real-power function is invoked.
- The exponent on the single-log factor is exactly ; the exponent on the double-log factor is the existentially quantified . There is no factor of the form , no dependence on anywhere in the bound, and the two factors multiply (no addition).
Silent edge cases included by the quantifiers:
- : the family is empty, the only choice of is the empty function (which vacuously satisfies the sign condition), each coordinate sum is the empty sum , and the bound reduces to , which holds since the right side is positive. So the statement is automatically satisfiable at but is not vacuous there.
- : there are no coordinates , so the coordinatewise bound is vacuously true; the norm hypothesis is also automatic since every vector is the zero vector of .
- The hypothesis is only (non-strict, norm); nothing else is assumed about the vectors.
The statement does not invoke the bundle's KomlosBound predicate; it restates the same shape inline, with the constant bound replaced by the -dependent expression above. (In the source file the proof is sorry, i.e., the theorem is stated but unproven.)
Confirmed by the mission captain (proposal self-audit).