Conjectura
Beta.Proofs cannot be submitted yet. The corpus is open to read, and we are looking for researchers to maintain a subject area.Maintaining a field →
← problemsWP0003openMathematics/ Combinatorics

Beck–Fiala theorem and conjecture

Maintainer — open

The Beck–Fiala theorem If S1,,Sm[n]S_1, \dots, S_m \subseteq [n] is a set system of degree at most tt, i.e. every j[n]j \in [n] lies in at most tt of the sets, and t1t \ge 1, then there is a colouring χ ⁣:[n]{1,+1}\chi \colon [n] \to \{-1, +1\} with jSiχ(j)2t1\left|\sum_{j \in S_i} \chi(j)\right| \le 2t - 1 for every ii. The hypothesis t1t \ge 1 is necessary: a system of degree 00 consists of empty sets only, whose d

Motivation

The Beck–Fiala theorem If S1,,Sm[n]S_1, \dots, S_m \subseteq [n] is a set system of degree at most tt, i.e. every j[n]j \in [n] lies in at most tt of the sets, and t1t \ge 1, then there is a colouring χ ⁣:[n]{1,+1}\chi \colon [n] \to \{-1, +1\} with jSiχ(j)2t1\left|\sum_{j \in S_i} \chi(j)\right| \le 2t - 1 for every ii. The hypothesis t1t \ge 1 is necessary: a system of degree 00 consists of empty sets only, whose discrepancy is 0>2010 > 2 \cdot 0 - 1. [J. Beck and T. Fiala, "Integer-making" theorems, Discrete Applied Mathematics 3 (1981), 1–8.]

Adapted from formal-conjectures, Wikipedia/BeckFialaConjecture.lean. Catalogued at https://en.wikipedia.org/wiki/Beck%E2%80%93Fiala_theorem.

Lean API
import Mathlib.Analysis.Real.Sqrt

namespace Conjectura.WP0003

/-- **The Beck–Fiala theorem** If $S_1, \dots, S_m \subseteq [n]$ is a set system of degree at most $t$, i.e. every $j \in [n]$ lies in at most $t$ of the sets, and $t \ge 1$, then there is a colouring $\chi \colon [n] \to \{-1, +1\}$ with $\left|\sum_{j \in S_i} \chi(j)\right| \le 2t - 1$ for every $i$. The hypothesis $t \ge 1$ is necessary: a system of degree $0$ consists of empty sets only, whose discrepancy is $0 > 2 \cdot 0 - 1$. [J. Beck and T. Fiala, *"Integer-making" theorems*, Discrete Applied Mathematics **3** (1981), 1–8.] -/
def goal : Prop :=
  ∃ 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

end Conjectura.WP0003
Definition3
Related work2
For your AI
Download as .md
I am proving a theorem in Lean 4 and submitting it to Conjectura.

## Problem WP0003 — Beck–Fiala theorem and conjecture

**The Beck–Fiala theorem** If $S_1, \dots, S_m \subseteq [n]$ is a set system of degree at most $t$, i.e. every $j \in [n]$ lies in at most $t$ of the sets, and $t \ge 1$, then there is a colouring $\chi \colon [n] \to \{-1, +1\}$ with $\left|\sum_{j \in S_i} \chi(j)\right| \le 2t - 1$ for every $i$. The hypothesis $t \ge 1$ is necessary: a system of degree $0$ consists of empty sets only, whose d

## Environment (fixed — do not assume anything newer)

- Lean toolchain: `leanprover/lean4:v4.33.0-rc1`
- Mathlib: `v4.33.0-rc1`

If a lemma you want does not exist in that Mathlib, prove it inline instead of
importing something newer.

## The exact statement I must prove

```lean
theorem solution : Conjectura.WP0003.goal := by
  sorry
```

## The file I submit

```lean
import Conjectura.Problems.WP0003.Statement

namespace Submission

theorem solution : Conjectura.WP0003.goal := by
  sorry

end Submission

```

## The Lean definitions of every term in this problem

These are the actual definitions your proof will be checked against. Do not
substitute your own version of any of them.

### Finset

structure

```lean
Finset
```
Defined in Mathlib.

### filter

def

```lean
Finset.univ.filter
```
Defined in Mathlib.

### sqrt

def

```lean
Real.sqrt
```
Defined in Mathlib.

## Rules — submissions violating these are rejected automatically

1. **Do not change the name or type of `solution`.** It must satisfy the
   statement above exactly.
2. **Do not redefine or shadow anything from the problem's Statement module.**
   Declaring your own `goal`, or redefining a name it depends on, produces a
   proof of a *different* statement and is rejected. This is the single most
   common rejection.
3. **No `sorry`** anywhere, including in helper lemmas. It surfaces as the
   axiom `sorryAx` and is detected transitively through imports.
4. **No `native_decide`** — it surfaces as `Lean.ofReduceBool` and is not
   accepted, because it trusts compiled code rather than the kernel.
5. Only these axioms are permitted: `propext`, `Classical.choice`,
   `Quot.sound`.
6. Follow Mathlib style: hypotheses left of the colon, explicit types,
   `snake_case` theorem names, `UpperCamelCase` types.

## What I want from you

Here is my argument in informal mathematics:

> [PASTE YOUR PROOF SKETCH HERE]

Turn it into Lean 4 that compiles under the environment above and satisfies the
statement exactly. Where you are unsure a lemma exists in this Mathlib version,
say so explicitly rather than guessing a name.

Submissions are not open yet

Conjectura is in beta. You can read every statement, every definition and the Lean behind them, and download the exact files the checker uses — but proofs are not being accepted yet.

The reason is a deliberate order of operations. Accepting a proof means running a stranger’s code and standing behind a verdict, and no statement here yet carries a researcher’s name. A machine-checked answer to a question nobody has vouched for is worth very little, so the vouching comes first.

The English write-ups are also switched off during the beta. Nothing on this page is generated by a model.

Discussion

  • Nothing yet.

Sign in to take part.