Theorem 8.38 — arbitrary-bundle square-root bound
OpenSparseDisc.Supplement.theorem_8_38discrepancyp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
Every finite -sparse instance with functions and satisfies
In particular, for arbitrary bundle sizes, every -sparse family of functions has the strict bound
The logarithm is natural, and the strict numerical consequence is retained rather than rounded.
Differences from the source:
- encoding: a non-strict instance discrepancy bound and a strict family consequence → the first uses
InstDiscLE, while the second explicitly exhibits a colouring satisfying strict inequalities for every function; reason: preserves the different inequality strengths exactly - encoding: a positive number of functions and natural logarithm →
nis the cardinality of a finite nonempty type andReal.logis applied to the positive argument under ; reason: Lean convention and explicit guards for the paper's positive and logarithm domain
Preamble
import Mathlib import Definitions.Def_SparseDisc_IsInstance import Definitions.Def_SparseDisc_InstDiscLE import Definitions.Def_SparseDisc_IsOneLipschitz import Definitions.Def_SparseDisc_IsTwoSparse import Definitions.Def_SparseDisc_Supplement_IsTSparseSupp
Formal statement
namespace SparseDisc.Supplement
/-- **Theorem 8.38** (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC
2027 submission manuscript (sha256 0f09ec60…25b81), p.47). Every `t`-sparse instance with `n`
functions, `t≥2`, has discrepancy at most `sqrt(2 ln(2t) n)`; every 2-sparse family has the
strict bound `1.666 sqrt(n)` for arbitrary bundle sizes.
**Formalization Note** `Real.log` is the natural logarithm. Its argument is positive because
`t≥2`. The function type is nonempty, matching the paper's positive `n` (and the proof's use of
division by `n`). The strict family conclusion is represented by a colouring satisfying strict
inequalities, not by the non-strict `DiscLE` predicate. -/
theorem theorem_8_38 :
(∀ (t : ℕ), 2 ≤ t → ∀ (V ι : Type) [Fintype V] [DecidableEq V]
[Nonempty V] [Fintype ι] [DecidableEq ι] (g : V → SparseDisc.Cube ι → ℝ)
(U : V → Finset ι), SparseDisc.IsInstance g U → IsTSparseSupp t U →
SparseDisc.InstDiscLE g
(Real.sqrt (2 * Real.log (2 * t) * Fintype.card V))) ∧
(∀ (V ι : Type) [Fintype V] [DecidableEq V] [Nonempty V] [Fintype ι] [DecidableEq ι]
(f : V → Finset ι → ℝ), (∀ v, SparseDisc.IsOneLipschitz (f v)) →
SparseDisc.IsTwoSparse f → ∃ S : Finset ι, ∀ v,
|f v S - f v (Finset.univ \ S)| < 1.666 * Real.sqrt (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.38, p.47