Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1 (Stronger Beck–Fiala bound, Bansal–Jiang) — O(k)O(k)O(k), O(k1/3log⁡1/3n)O(k^{1/3}\log^{1/3} n)O(k1/3log1/3n), O(k1/2)O(k^{1/2})O(k1/2) by regime of kkk

Open
Komlos.bansal_jiang_stronger_beck_fiala

by Himan · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsdiscrepancytheory

This is the stronger Beck–Fiala bound of Bansal and Jiang, which lists the discrepancy bound in every regime of the column sparsity kkk.

Let A∈{0,±1}m×nA \in \{0, \pm 1\}^{m \times n}A∈{0,±1}m×n be a matrix in which each column has at most kkk non-zero entries. Its discrepancy is

disc⁡(A)=min⁡x∈{−1,1}nmax⁡i∈[m]∣∑j=1nAijxj∣.\operatorname{disc}(A) = \min_{x \in \{-1,1\}^n} \max_{i \in [m]} \Big| \sum_{j=1}^n A_{ij} x_j \Big| .disc(A)=x∈{−1,1}nmin​i∈[m]max​​j=1∑n​Aij​xj​​.

Then

disc⁡(A)={O(k)if k≤log⁡1/2n,O(k1/3log⁡1/3n)if log⁡1/2n≤k≤log⁡2n,O(k1/2)if k≥log⁡2n.\operatorname{disc}(A) = \begin{cases} O(k) & \text{if } k \le \log^{1/2} n, \\ O(k^{1/3} \log^{1/3} n) & \text{if } \log^{1/2} n \le k \le \log^2 n, \\ O(k^{1/2}) & \text{if } k \ge \log^2 n . \end{cases}disc(A)=⎩⎨⎧​O(k)O(k1/3log1/3n)O(k1/2)​if k≤log1/2n,if log1/2n≤k≤log2n,if k≥log2n.​

The implied constant is absolute: it does not depend on kkk, nnn, mmm or AAA, and there are no hidden poly(log⁡log⁡n)\mathrm{poly}(\log\log n)poly(loglogn) factors.

The third regime is the Beck–Fiala conjecture for k≥log⁡2nk \ge \log^2 nk≥log2n (Theorem 1.3 of the same paper), stated for the larger class of 0/±10/\pm10/±1 matrices. The second regime improves Banaszczyk's O(k1/2log⁡1/2n)O(k^{1/2}\log^{1/2} n)O(k1/2log1/2n) bound for all kkk between log⁡1/2n\log^{1/2} nlog1/2n and log⁡2n\log^2 nlog2n, and the first regime is the classical O(k)O(k)O(k) bound of Beck and Fiala. Set systems are the special case of 0/10/10/1 incidence matrices, where kkk is the maximum number of sets containing one element.

Formalization Note The O(⋅)O(\cdot)O(⋅) is rendered by a single constant C>0C > 0C>0 quantified before kkk, nnn, mmm and AAA, and the three regimes by one case expression that CCC multiplies. The logarithm is the natural logarithm taken at n+2n + 2n+2, as elsewhere in this mission, so that it is positive for every nnn; since the bound is non-decreasing in the logarithm and log⁡n≤log⁡(n+2)\log n \le \log(n+2)logn≤log(n+2), this does not strengthen the source statement for n≥2n \ge 2n≥2, and for n≤1n \le 1n≤1 every row sum is at most 111 in absolute value. The two boundary values k=log⁡1/2(n+2)k = \log^{1/2}(n+2)k=log1/2(n+2) and k=log⁡2(n+2)k = \log^2(n+2)k=log2(n+2) 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 000, 111 or −1-1−1, column sparsity counts the rows iii with Aij≠0A_{ij} \ne 0Aij​=0, and signs are real vectors with entries ±1\pm 1±1 (IsSignVector). The case k=0k = 0k=0 forces A=0A = 0A=0 and the bound 000. The source also asserts that the colouring is found in polynomial time; only existence is stated here.

Preamble
import Mathlib
import Definitions.Def_Komlos_model
Formal statement
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
Source
N. Bansal, H. Jiang, Decoupling via affine spectral-independence: Beck-Fiala and Komlos bounds beyond Banaszczyk, 2025, https://arxiv.org/abs/2508.03961 (v2), Section 5, p. 23, Theorem 5.1 (Stronger Beck-Fiala bound)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me