Beck–Fiala problem

DefinitionLinear Beck–Fiala conjecture#✓fully proved

This is the statement that there is a real constant \(C > 0\) such that the following holds for all natural numbers \(n\), \(m\) and \(t \ge 1\). Let \(S_1, \dots, S_n\) be subsets of \(\{1, \dots, m\}\) such that each \(S_i\) has at most \(t\) elements, each element of \(\{1, \dots, m\}\) lies in at most \(t\) of the sets \(S_i\), and \(S_i\) and \(S_{i'}\) have at most one common element whenever \(i \ne i'\). Then there are signs \(\varepsilon_1, \dots, \varepsilon_m \in \{1, -1\}\) such that \(\left|\sum_{j \in S_i} \varepsilon_j\right| \le C\sqrt{t}\) for every \(i\).

In matrix terms: a \(t\)-sparse \(0/1\) matrix (in rows and columns) in which every two rows share at most one nonzero entry has discrepancy \(O(\sqrt{t})\), improving the general bound \(O(\sqrt{t \log t})\).

def conjecture : Prop :=
  ∃ C : ℝ, 0 < C ∧
  ∀ (n m t : ℕ), 0 < t →
    ∀ incidence : Fin n → Finset (Fin m),
      (∀ i, (incidence i).card ≤ t) →
      (∀ j, (Finset.univ.filter (fun i => j ∈ incidence i)).card ≤ t) →
      (∀ i₁ i₂, i₁ ≠ i₂ → ((incidence i₁ ∩ incidence i₂).card) ≤ 1) →
      ∃ ε : Fin m → ℝ, (∀ j, ε j = 1 ∨ ε j = -1) ∧
        ∀ i, |∑ j ∈ incidence i, ε j| ≤ C * Real.sqrt t

Sources

AIM-COMBINATORICS-0044__20000919; AIM Hereditary discrepancy, item 1.7.

Used by 1

Used byLinear Beck–Fiala systems have discrepancy \(O(\sqrt{t})\)

TheoremLinear Beck–Fiala systems have discrepancy \(O(\sqrt{t})\)#●ready to prove

There is a real constant \(C > 0\) such that the following holds for all natural numbers \(n\), \(m\) and \(t \ge 1\). Let \(S_1, \dots, S_n\) be subsets of \(\{1, \dots, m\}\) such that each \(S_i\) has at most \(t\) elements, each element of \(\{1, \dots, m\}\) lies in at most \(t\) of the sets \(S_i\), and \(S_i\) and \(S_{i'}\) have at most one common element whenever \(i \ne i'\). Then there are signs \(\varepsilon_1, \dots, \varepsilon_m \in \{1, -1\}\) such that \(\left|\sum_{j \in S_i} \varepsilon_j\right| \le C\sqrt{t}\) for every \(i\).

Guo, Fang and Lu prove that every \(0/1\) matrix with at most \(t\) nonzero entries in each column has discrepancy less than \(3\sqrt{2\pi t}\) (arXiv:2609.11189, Corollary 1.2 of their Komlós bound, Theorem 1.1; Karingula and Lovett give an elementary proof of the Komlós bound with constant 36, arXiv:2609.20979). Linear systems with \(t\)-sparse rows and columns are a special case.

public theorem_wanted conjecture_holds : conjecture

def conjecture : Prop :=
  ∃ C : ℝ, 0 < C ∧
  ∀ (n m t : ℕ), 0 < t →
    ∀ incidence : Fin n → Finset (Fin m),
      (∀ i, (incidence i).card ≤ t) →
      (∀ j, (Finset.univ.filter (fun i => j ∈ incidence i)).card ≤ t) →
      (∀ i₁ i₂, i₁ ≠ i₂ → ((incidence i₁ ∩ incidence i₂).card) ≤ 1) →
      ∃ ε : Fin m → ℝ, (∀ j, ε j = 1 ∨ ε j = -1) ∧
        ∀ i, |∑ j ∈ incidence i, ε j| ≤ C * Real.sqrt t

WantedExt/Combinatorics/LinearBeckFialaWanted.lean:36

Sources

Shengtao Guo, Ethan X. Fang and Junwei Lu, Vector balancing via directional total variation, arXiv:2609.11189 (2026), https://arxiv.org/abs/2609.11189.

Uses 1

Statement usesLinear Beck–Fiala conjecture

1 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.