There exists a universal constant C>0 such that, for every integer t≥ 1, every finite set system (U,F) in which each element of U belongs to at most t members of F admits a coloring chi:U→-1,+1 satisfying |∑_u∈ Fchi(u)|≤ C√t for every F∈F.

Beck–Fiala conjecture

The Beck–Fiala conjecture predicts discrepancy bounded by a universal constant times $\sqrt{t}$ , independent of the set system’s size and dimension. A new preprint claims this full bound through a directional-variation argument.

Known results

Beck and Fiala proved the classical bound $2t$ .
Bukh obtained the dimension-independent bound $2t-\log^* t$ .
Bansal and Jiang established an $O(\sqrt{d})$ bound in a regime such as $d\ge (\log n)^2$ .
A newer online result reaches $O_\eta(\sqrt{d})$ when $d\ge C(\log T)(\log\log T)^{2+\eta}$ , but does not settle the unrestricted problem.

September 10, 2026 claimed proof

Shengtao Guo, Ethan X. Fang, and Junwei Lu’s preprint claims a dimension- and size-independent constant multiplying $\sqrt{t}$ , which would settle the conjecture. It attributes discovery of the proof to the Odin Automatic AI Research Agent. The claim is from an unrefereed preprint and has no independent verification reported here.

Current status (as of September 2026): A full Beck–Fiala bound is claimed in an unrefereed preprint, but the claim remains unverified, so the conjecture is not settled.

Beck–Fiala conjecture

Primary source

Additional references

Progress summary

Solutions 0