Theorem 8.37 — thin shared bundles for instances
OpenSparseDisc.Supplement.theorem_8_37discrepancyp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
Let be a finite instance with functions in which any two declared supports share at most items.
- If is -sparse, then
In particular, a simple item multigraph gives . 2. If is -sparse, then
Differences from the source:
- encoding: functions and at most shared items →
nis the cardinality of a finite function type and every intersection of two distinct declared supports has cardinality at mosts; reason: Lean convention, preserving nonminimal supports - reading: simple item multigraph → pairwise declared-support intersections have cardinality at most one; reason: under 2-sparsity this is exactly absence of parallel non-private item edges
Preamble
import Mathlib import Definitions.Def_SparseDisc_IsInstance import Definitions.Def_SparseDisc_IsTwoSparseSupp import Definitions.Def_SparseDisc_InstDiscLE import Definitions.Def_SparseDisc_Supplement_IsTSparseSupp import Definitions.Def_SparseDisc_Supplement_PairwiseSharedCap
Formal statement
namespace SparseDisc.Supplement
/-- **Theorem 8.37** (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC
2027 submission manuscript (sha256 0f09ec60…25b81), p.46). The instance-level pairwise shared-item
bounds are stated for both `t=2` and general `t`, including the simple-item-multigraph consequence. -/
theorem theorem_8_37 :
(∀ (V ι : Type) [Fintype V] [DecidableEq V] [Fintype ι] [DecidableEq ι]
(g : V → SparseDisc.Cube ι → ℝ) (U : V → Finset ι) (s : ℕ),
SparseDisc.IsInstance g U → PairwiseSharedCap U s →
SparseDisc.IsTwoSparseSupp U →
SparseDisc.InstDiscLE g
(1 + 2 * ((Nat.ceil (Real.sqrt (((s * Fintype.card V : ℕ) : ℝ) / 2)) : ℕ) : ℝ))) ∧
(∀ (V ι : Type) [Fintype V] [DecidableEq V] [Fintype ι] [DecidableEq ι]
(g : V → SparseDisc.Cube ι → ℝ) (U : V → Finset ι),
SparseDisc.IsInstance g U → PairwiseSharedCap U 1 →
SparseDisc.IsTwoSparseSupp U →
SparseDisc.InstDiscLE g
(1 + 2 * ((Nat.ceil (Real.sqrt ((Fintype.card V : ℝ) / 2)) : ℕ) : ℝ))) ∧
(∀ (t s : ℕ), 1 ≤ t → ∀ (V ι : Type) [Fintype V] [DecidableEq V]
[Fintype ι] [DecidableEq ι] (g : V → SparseDisc.Cube ι → ℝ)
(U : V → Finset ι), SparseDisc.IsInstance g U → PairwiseSharedCap U s →
IsTSparseSupp t U → SparseDisc.InstDiscLE g
(1 + 2 * s * Real.sqrt ((t * (t - 1) * Fintype.card V : ℕ) : ℝ))) := by sorry
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 8.37, p.46