Theorem 5.1 (Stronger Beck–Fiala bound, Bansal–Jiang) — , , by regime of
OpenKomlos.bansal_jiang_stronger_beck_fialaThis is the stronger Beck–Fiala bound of Bansal and Jiang, which lists the discrepancy bound in every regime of the column sparsity .
Let be a matrix in which each column has at most non-zero entries. Its discrepancy is
Then
The implied constant is absolute: it does not depend on , , or , and there are no hidden factors.
The third regime is the Beck–Fiala conjecture for (Theorem 1.3 of the same paper), stated for the larger class of matrices. The second regime improves Banaszczyk's bound for all between and , and the first regime is the classical bound of Beck and Fiala. Set systems are the special case of incidence matrices, where is the maximum number of sets containing one element.
Formalization Note The is rendered by a single constant quantified before , , and , and the three regimes by one case expression that multiplies. The logarithm is the natural logarithm taken at , as elsewhere in this mission, so that it is positive for every ; since the bound is non-decreasing in the logarithm and , this does not strengthen the source statement for , and for every row sum is at most in absolute value. The two boundary values and are assigned to the first and second case respectively; at each boundary the two adjacent expressions agree. The matrix is a function A : Fin m → Fin n → ℝ with every entry equal to , or , column sparsity counts the rows with , and signs are real vectors with entries (IsSignVector). The case forces and the bound . The source also asserts that the colouring is found in polynomial time; only existence is stated here.
import Mathlib import Definitions.Def_Komlos_model
namespace Komlos
theorem bansal_jiang_stronger_beck_fiala :
∃ C : ℝ, 0 < C ∧
∀ (k n m : ℕ) (A : Fin m → Fin n → ℝ),
(∀ i j, A i j = 0 ∨ A i j = 1 ∨ A i j = -1) →
(∀ j, ({i | A i j ≠ 0} : Finset (Fin m)).card ≤ k) →
∃ ε : Fin n → ℝ, IsSignVector ε ∧
∀ i, |∑ j, A i j * ε j| ≤
C * (if (k : ℝ) ≤ Real.sqrt (Real.log (n + 2)) then (k : ℝ)
else if (k : ℝ) ≤ Real.log (n + 2) ^ 2 then
(k : ℝ) ^ ((1 : ℝ) / 3) * Real.log (n + 2) ^ ((1 : ℝ) / 3)
else Real.sqrt k) := by sorry
end Komlos