Theorem 1.8 — heavy functions with bounded ports per lobe
OpenSparseDisc.Supplement.theorem_1_8discrepancyhypergraphsp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
Fix . Let be a finite -sparse family. If every heavy function—one meeting more than bundle hyperedges—has at most ports in each lobe, then
In particular, for , block maximum degree at most gives , and every cactus pattern has discrepancy at most , with arbitrary degrees and bundle sizes.
Differences from the source:
- encoding: lobes are connected classes after deleting the heavy function and ports are incident hyperedges meeting a class → connectivity is the reflexive-transitive closure of co-membership in remaining hyperedges and ports are counted by a finite filter; reason: direct finite hypergraph encoding of Definition 7.1
- encoding: finite families and discrepancy inequalities → finite types and the existential colouring predicate
DiscLE; reason: Lean convention, preserving arbitrary bundle sizes and private items
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_IsTwoSparse import Definitions.Def_SparseDisc_BlockDegreeLE import Definitions.Def_SparseDisc_IsCactus import Definitions.Def_SparseDisc_Supplement_IsTSparse import Definitions.Def_SparseDisc_Supplement_PortCondition
Formal statement
namespace SparseDisc.Supplement
/-- **Theorem 1.8** (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC
2027 submission manuscript (sha256 0f09ec60…25b81), p.4). If every heavy function has at most
`Δ` ports in each lobe, discrepancy is at most `tΔ max(1,2^(Δ-2))`; the theorem also contains
the stated block-degree and cactus consequences for `t=2`. -/
theorem theorem_1_8 :
(∀ (t Δ : ℕ), 1 ≤ t → 2 ≤ Δ → ∀ (V ι : Type) [Fintype V]
[DecidableEq V] [Fintype ι] [DecidableEq ι] (f : V → Finset ι → ℝ),
(∀ v, SparseDisc.IsOneLipschitz (f v)) → IsTSparse t f →
PortCondition (fun v => SparseDisc.relevant (f v)) Δ →
SparseDisc.DiscLE f ((t * Δ * max 1 (2 ^ (Δ - 2)) : ℕ) : ℝ)) ∧
(∀ (Δ : ℕ), 2 ≤ Δ → ∀ (V ι : Type) [Fintype V] [DecidableEq V]
[Fintype ι] [DecidableEq ι] (f : V → Finset ι → ℝ),
(∀ v, SparseDisc.IsOneLipschitz (f v)) → SparseDisc.IsTwoSparse f →
SparseDisc.BlockDegreeLE (SparseDisc.pattern f) Δ →
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.IsCactus (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.8, p.4