Worst discrepancy of functions
DefinitionSparseDisc_Supplement_Kdiscrepancyp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
For , is the supremum of the discrepancies of all finite instances with exactly odd -Lipschitz functions and any positive number of items:
The supremum is retained; no attainment is assumed.
Definition code
import Mathlib
import Definitions.Def_SparseDisc_IsInstance
import Definitions.Def_SparseDisc_Supplement_instanceDiscrepancy
namespace SparseDisc.Supplement
/-- `K n`, the supremum of the discrepancies of all finite instances with exactly `n` functions
and at least one item (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC
2027 submission manuscript (sha256 0f09ec60…25b81), Definition 2.4, p.12).
**Formalization Note** The source defines this only for `n ≥ 1`; every theorem using `K n` states
that condition. Both extrema are genuine finite-instance extrema: each inner attainable-threshold
set is nonempty and bounded below, and the source's Lemma 2.5 bounds the outer set. -/
noncomputable def K (n : ℕ) : ℝ :=
sSup {c : ℝ | ∃ (m : ℕ) (g : Fin n → SparseDisc.Cube (Fin m) → ℝ)
(U : Fin n → Finset (Fin m)), 1 ≤ m ∧ SparseDisc.IsInstance g U ∧
c = instanceDiscrepancy g}
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Definition 2.4, p.12