Lemma 21 (Beck–Fiala) — exact linear rounding to at most fractional coordinates
ProvedProportionalGroupDivision.Main.lemma_21discrepancyfair-divisionindivisible-goodsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1proportionality
Let be integers, and . Then there is with
such that all but coordinates of are rounded, i.e. at most coordinates of lie outside .
Every row value is preserved exactly; the lemma reduces the rounding in Theorem 6 to the case .
Differences from the source:
- encoding: rows, agents and goods indexed 1, …, n → 0-based indices Fin n; agent (i, j) is a dependent pair with j : Fin (n i); reason: relabelling; changes no instance
Preamble
import Mathlib open scoped BigOperators
Formal statement
namespace ProportionalGroupDivision.Main
/-- Lemma 21 (Beck–Fiala, PDF p. 20): for integers `m > N > 0`, a matrix `A ∈ [0,1]^{N×m}` and a
point `x ∈ [0,1]^m` there is `x′ ∈ [0,1]^m` with `A x = A x′` such that all but `N` coordinates of
`x′` are rounded (equal to `0` or `1`). -/
theorem lemma_21 (N m : ℕ) (hN : 0 < N) (hNm : N < m) (A : Matrix (Fin N) (Fin m) ℝ)
(hA : ∀ i g, A i g ∈ Set.Icc (0 : ℝ) 1) (x : Fin m → ℝ) (hx : ∀ g, x g ∈ Set.Icc (0 : ℝ) 1) :
∃ x' : Fin m → ℝ, (∀ g, x' g ∈ Set.Icc (0 : ℝ) 1) ∧ A.mulVec x = A.mulVec x' ∧
(Finset.univ.filter (fun g => x' g ≠ 0 ∧ x' g ≠ 1)).card ≤ N := by sorry
end ProportionalGroupDivision.Main
Source
Alexander Shekhovtsov, Georgy Sokolov, Mikhail Cherniavskii, Andrey Kupavskii, Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy, STOC 2027 submission #606 (October 2026), PDF SHA-256 b01bf42964a30eaf9c85a3d02713fc0ac4cd63ae8653853fa44b062c0220f39a, Lemma 21, PDF p. 20 = printed p. 20
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.