Discrepancy for degree- set systems
ProvedKomlos.beck_fiala_banaszczyk(Banaszczyk 1998, corollary.) There is a constant such that every incidence matrix with column degree at most admits signs with each row sum at most in absolute value. This has the conjectured dependence of the Beck--Fiala conjecture but retains a factor; it beats the Beck--Fiala bound once . It follows from the vector-balancing bound by scaling degree- columns to unit norm.
import Mathlib import Definitions.Def_Komlos_model
namespace Komlos
theorem beck_fiala_banaszczyk :
∃ C : ℝ, 0 < C ∧ ∀ (t n m : ℕ) (A : Fin m → Fin n → ℝ),
(∀ i j, A i j = 0 ∨ A i j = 1) →
(∀ j, ({i | A i j = 1} : Finset (Fin m)).card ≤ t) →
∃ ε : Fin n → ℝ, IsSignVector ε ∧
∀ i, |∑ j, A i j * ε j| ≤ C * Real.sqrt (t * Real.log (n + 2)) := by sorry
end KomlosRead-back
What the Lean code literally says, in plain math · claude-fable-5
Read-back — Komlos.beck_fiala_banaszczyk.
The statement asserts the existence of a single real constant with such that the following holds for every choice of the three natural numbers , , (each ranging over , so the degenerate values , , and are all included) and every real matrix with rows and columns, i.e. a function assigning a real number to each row index and column index .
Two hypotheses are imposed on :
- Zero–one entries: for every row and column , either or .
- Column sparsity: for every column , the number of rows with is at most ; that is,
(The count is over the finite row-index set of size . Note that is universally quantified alongside , , and , so this is a genuine hypothesis for each fixed ; when it forces every column, hence the whole matrix, to be identically .)
Under these hypotheses, the conclusion is that there exists a vector of signs of real numbers — one sign per column — satisfying the bundle's sign-vector predicate, which unfolds to: for every index , either or ; and such that every row of the signed column-sum obeys
Here the sum runs over all columns, is the absolute value of a real number, is the real natural logarithm, and inside the square root both and are the natural numbers cast to reals — so the logarithm's argument is at least (in particular even when ), and the quantity under the square root is nonnegative. Both inequalities in the statement ( in the sparsity hypothesis and in the conclusion) are non-strict.
Degenerate instances silently covered by the quantifiers: when the sign vector is the empty function, each row sum is the empty sum , and the conclusion holds trivially; when there are no rows, so both the entry condition of hypothesis 1 and the conclusion's per-row bound are vacuous (each column count in hypothesis 2 is ); when the matrix is forced to be zero as noted above.
The constant is chosen before , , , and , so it is uniform in all of them; the bound depends on the instance only through the factor , where is the assumed column-sparsity parameter and is the number of columns (equivalently, the length of the sign vector). Nothing in the statement constrains beyond positivity, and nothing relates to or .
Confirmed by the mission captain (proposal self-audit).