Theorem 5.2 — arbitrary bundle structures
OpenSparseDisc.Supplement.theorem_5_2discrepancyhypergraphsp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
Let be an instance with bundle structure , and suppose . Put
Then there is a sign colouring satisfying
In particular, if the structure is -bounded and for every , then .
Differences from the source:
- encoding: finite bundle structure → finite index types and
Finsetbundles with nonemptiness, pairwise disjointness and support coverage stated inIsBundleStructure; reason: Lean convention, matching Definition 5.1 clause by clause
Preamble
import Mathlib import Definitions.Def_SparseDisc_IsInstance import Definitions.Def_SparseDisc_InstDiscLE import Definitions.Def_SparseDisc_Supplement_IsBundleStructure
Formal statement
namespace SparseDisc.Supplement
open Classical in
/-- **Theorem 5.2** (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC
2027 submission manuscript (sha256 0f09ec60…25b81), p.21). For an arbitrary bundle structure,
there is one colouring satisfying every per-function sum of `min(k_e,|B_e|)`; the exact
`tΔ max(1,2^(Δ-2))` consequence is included. -/
theorem theorem_5_2 :
∀ (V ι E : Type) [Fintype V] [DecidableEq V] [Fintype ι] [DecidableEq ι]
[Fintype E] [DecidableEq E] (g : V → SparseDisc.Cube ι → ℝ)
(U : V → Finset ι) (B : E → Finset ι) (S : E → Finset V),
SparseDisc.IsInstance g U → IsBundleStructure U B S →
let N := fun v => Finset.univ.filter (fun e => v ∈ S e)
let d := fun v => (N v).card
let k := fun e => ∑ v ∈ S e, max 1 (2 ^ (d v - 2))
(∀ v, 1 ≤ d v) →
(∃ x : SparseDisc.Cube ι, ∀ v,
|g v x| ≤ ((∑ e ∈ N v, min (k e) (B e).card : ℕ) : ℝ)) ∧
∀ (t Δ : ℕ), (∀ e, (S e).card ≤ t) → (∀ v, d v ≤ Δ) →
SparseDisc.InstDiscLE g ((t * Δ * max 1 (2 ^ (Δ - 2)) : ℕ) : ℝ) := by sorry
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 5.2, p.21