Beck–Fiala theorem and conjecture

The question

The Beck–Fiala conjecture

There exists a universal constant $C>0$ such that every set system $S_1,\dots ,S_m\subseteq [n]$ of degree at most $t$ admits a colouring $\chi :[n]\to \{-1,+1\}$ with $\left|{\sum }_{j\in S_i}\chi (j)\right|\le C\sqrt{t}$ for every $i$.

Discrepancy of bounded-degree set systems. Given sets $S_1,\dots ,S_m\subseteq [n]$ such that every element of $[n]$ belongs to at most $t$ of the sets (the system has degree at most $t$), one seeks a colouring $\chi :[n]\to \{-1,+1\}$ making every set as balanced as possible, i.e. minimizing the discrepancy ${\max }_i\left|{\sum }_{j\in S_i}\chi (j)\right|$.

The Beck–Fiala theorem (1981) states that every set system of degree at most $t\ge 1$ has discrepancy at most $2t-1$. The Beck–Fiala conjecture asserts that the truth is much stronger: the discrepancy of a degree-$t$ system is $O(\sqrt{t})$, with a constant independent of $n$, $m$ and $t$.

Despite considerable attention the bound $2t-1$ has been improved only slightly: Bukh (2016) proved a bound of the form $2t-{\log }^{\ast }t$ (where ${\log }^{\ast }$ is the iterated logarithm), and Banaszczyk's vector balancing theorem yields $O(\sqrt{t\log n})$. The Komlós conjecture (see KomlosConjecture.lean) would imply the Beck–Fiala conjecture, since scaling the incidence vectors of a degree-$t$ system by $1/\sqrt{t}$ produces vectors of Euclidean norm at most $1$.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.Wikipedia.BeckFialaConjecture.

theorem beck_fiala_conjecture :
    ∃ C : ℝ, 0 < C ∧ ∀ (n m t : ℕ) (S : Fin m → Finset (Fin n)),
      (∀ j, (Finset.univ.filter fun i => j ∈ S i).card ≤ t) →
      ∃ χ : Fin n → ℝ, (∀ j, χ j = 1 ∨ χ j = -1) ∧
        ∀ i, |∑ j ∈ S i, χ j| ≤ C * Real.sqrt t

What counts as progress

• A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
• Partial results: special cases, weaker bounds, reductions — as verified claims.
• Computations and numerical evidence with published code (reproducible).
• Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

• Wikipedia
• [J. Beck and T. Fiala, "Integer-making" theorems, Discrete Applied Mathematics 3 (1981), 1–8](https://doi.org/10.1016/0166-218X(81)90022-6)
• [B. Bukh, An improvement of the Beck–Fiala theorem, Combinatorics, Probability and Computing 25 (2016), 380–398](https://doi.org/10.1017/S0963548315000140)
• [W. Banaszczyk, Balancing vectors and Gaussian measures of n-dimensional convex bodies, Random Structures & Algorithms 12 (1998), 351–360](https://doi.org/10.1002/(SICI)1098-2418(199807)12:4%3C351::AID-RSA3%3E3.0.CO;2-S)

Source and licence

Imported from Formal Conjectures (Wikipedia), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.