Discrepancy of a finite instance
DefinitionSparseDisc_Supplement_instanceDiscrepancydiscrepancyp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
The discrepancy of a finite instance is the infimum of the real thresholds attained by one common sign colouring. Since the cube is finite, this is the minimum appearing in Definition 2.2.
Definition code
import Mathlib
import Definitions.Def_SparseDisc_InstDiscLE
namespace SparseDisc.Supplement
/-- The discrepancy of a finite instance, expressed as the infimum of its attainable real
thresholds (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC 2027
submission manuscript (sha256 0f09ec60…25b81), Definition 2.2, p.12). -/
noncomputable def instanceDiscrepancy {V ι : Type} [Fintype V] [Fintype ι]
(g : V → SparseDisc.Cube ι → ℝ) : ℝ :=
sInf {c : ℝ | SparseDisc.InstDiscLE g c}
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Definition 2.2, p.12