Theorem 1.6 — bundle-degree discrepancy bound
OpenSparseDisc.Supplement.theorem_1_6discrepancyhypergraphsp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
Let be a finite -sparse family. For each bundle hyperedge , let
where is the number of bundle hyperedges containing . After discarding functions with no non-private hyperedge as in the source's standing paragraph,
If and , then . If the underlying simple graph is a cycle, with arbitrary bundle sizes and private items, then .
Differences from the source:
- encoding: the pre-theorem convention discards functions of bundle degree zero and says → the main Lean clause explicitly assumes for every indexed function; reason: makes the section's standing convention binding and prevents a private-only function from making the displayed maximum zero
- encoding: finite families, hyperedges, sums and maxima → finite types and
Finsetsums/suprema; reason: Lean convention, with exactly the paper's finite bundle hypergraph
Preamble
import Mathlib import Definitions.Def_SparseDisc_IsOneLipschitz import Definitions.Def_SparseDisc_DiscLE import Definitions.Def_SparseDisc_relevant import Definitions.Def_SparseDisc_pattern import Definitions.Def_SparseDisc_IsCycle import Definitions.Def_SparseDisc_IsTwoSparse import Definitions.Def_SparseDisc_Supplement_IsTSparse import Definitions.Def_SparseDisc_Supplement_bundleEdges
Formal statement
namespace SparseDisc.Supplement
open Classical in
/-- **Theorem 1.6** (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC
2027 submission manuscript (sha256 0f09ec60…25b81), pp.3–4). For bundle-hypergraph degrees
`d_v`, put `k_e = ∑_{v∈e} max(1,2^(d_v-2))`. The discrepancy is bounded by the maximum
incident `k_e`-sum, itself at most `t Δ max(1,2^(Δ-2))`; the full `t=2` and cycle consequences
are included.
**Formalization Note** The source's paragraph immediately before the theorem discards functions
that meet no non-private hyperedge and then says `d_v ≥ 1`; the first clause states that standing
condition explicitly. Natural subtraction in the exponent is harmless under `1 ≤ d_v` because
`max(1,·)` gives the source value for `d_v=1`. -/
theorem theorem_1_6 :
(∀ (t : ℕ), 1 ≤ t → ∀ (V ι : Type) [Fintype V] [DecidableEq V]
[Fintype ι] [DecidableEq ι] (f : V → Finset ι → ℝ),
(∀ v, SparseDisc.IsOneLipschitz (f v)) → IsTSparse t f →
let U := fun v => SparseDisc.relevant (f v)
let E := bundleEdges U
let d := fun v => (E.filter (fun e => v ∈ e)).card
let k := fun e => ∑ v ∈ e, max 1 (2 ^ (d v - 2))
let load := fun v => ∑ e ∈ E.filter (fun e => v ∈ e), k e
let Δ := Finset.univ.sup d
(∀ v, 1 ≤ d v) →
SparseDisc.DiscLE f ((Finset.univ.sup load : ℕ) : ℝ) ∧
Finset.univ.sup load ≤ t * Δ * max 1 (2 ^ (Δ - 2))) ∧
(∀ (V ι : Type) [Fintype V] [DecidableEq V] [Fintype ι] [DecidableEq ι]
(f : V → Finset ι → ℝ), (∀ v, SparseDisc.IsOneLipschitz (f v)) →
SparseDisc.IsTwoSparse f →
let U := fun v => SparseDisc.relevant (f v)
let E := bundleEdges U
let d := fun v => (E.filter (fun e => v ∈ e)).card
let Δ := Finset.univ.sup d
2 ≤ Δ → SparseDisc.DiscLE f ((Δ * 2 ^ (Δ - 1) : ℕ) : ℝ)) ∧
(∀ (V ι : Type) [Fintype V] [DecidableEq V] [Fintype ι] [DecidableEq ι]
(f : V → Finset ι → ℝ), (∀ v, SparseDisc.IsOneLipschitz (f v)) →
SparseDisc.IsTwoSparse f → SparseDisc.IsCycle (SparseDisc.pattern f) →
SparseDisc.DiscLE f 4) := by sorry
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 1.6, pp.3–4