Theorem 1.10 — thin shared bundles
OpenSparseDisc.Supplement.theorem_1_10discrepancyp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
Let be a finite -sparse family of functions such that any two functions share at most relevant items. Then
If the item multigraph is simple, in particular for with single-item bundles, then . More generally, a -sparse family under the same pairwise cap satisfies
Differences from the source:
- encoding: functions and pairwise shared relevant items →
nis the cardinality of a finite function type and intersections of published relevance supports have cardinality at mosts; reason: Lean convention, with the same families - reading: the item multigraph is simple → every pair of relevance supports intersects in at most one item; reason: in a 2-sparse family this is exactly absence of parallel non-private item edges
Preamble
import Mathlib import Definitions.Def_SparseDisc_IsOneLipschitz import Definitions.Def_SparseDisc_DiscLE import Definitions.Def_SparseDisc_relevant import Definitions.Def_SparseDisc_IsTwoSparse import Definitions.Def_SparseDisc_Supplement_IsTSparse import Definitions.Def_SparseDisc_Supplement_PairwiseSharedCap
Formal statement
namespace SparseDisc.Supplement
/-- **Theorem 1.10** (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC
2027 submission manuscript (sha256 0f09ec60…25b81), p.5). Pairwise shared-item cap `s` gives the
exact `2`-sparse ceiling bound, its simple-item-multigraph consequence, and the general
`t`-sparse bound. -/
theorem theorem_1_10 :
(∀ (V ι : Type) [Fintype V] [DecidableEq V] [Fintype ι] [DecidableEq ι]
(f : V → Finset ι → ℝ) (s : ℕ), (∀ v, SparseDisc.IsOneLipschitz (f v)) →
SparseDisc.IsTwoSparse f →
PairwiseSharedCap (fun v => SparseDisc.relevant (f v)) s →
SparseDisc.DiscLE f
(1 + 2 * ((Nat.ceil (Real.sqrt (((s * Fintype.card V : ℕ) : ℝ) / 2)) : ℕ) : ℝ))) ∧
(∀ (V ι : Type) [Fintype V] [DecidableEq V] [Fintype ι] [DecidableEq ι]
(f : V → Finset ι → ℝ), (∀ v, SparseDisc.IsOneLipschitz (f v)) →
SparseDisc.IsTwoSparse f →
PairwiseSharedCap (fun v => SparseDisc.relevant (f v)) 1 →
SparseDisc.DiscLE f (Real.sqrt (2 * Fintype.card V) + 3)) ∧
(∀ (t s : ℕ), 1 ≤ t → ∀ (V ι : Type) [Fintype V] [DecidableEq V]
[Fintype ι] [DecidableEq ι] (f : V → Finset ι → ℝ),
(∀ v, SparseDisc.IsOneLipschitz (f v)) → IsTSparse t f →
PairwiseSharedCap (fun v => SparseDisc.relevant (f v)) s →
SparseDisc.DiscLE f
(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 1.10, p.5