AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.Protocol.nonneg_of_discrepancy_bound

theoremverifiedimported Lean

Discrepancy bound is nonnegative. Let $X \times Y$ carry a finite probability space $\mu$, let $g : X \to Y \to \mathrm{Bool}$ be a Boolean function, and let $\gamma \in \bbr$. If every rectangle $R \subseteq X \times Y$ satisfies $\abs{\mathrm{disc}_\mu(g, R)} \le \gamma$, then $\gamma \ge 0$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory in
open scoped BigOperators in
variable {X Y : Type*} in
lemma CommunicationComplexity.Deterministic.Protocol.nonneg_of_discrepancy_bound
    [μ : FiniteProbabilitySpace (X × Y)]
    (g : X → Y → Bool) (γ : ℝ)
    (hdisc : ∀ R : Set (X × Y), Rectangle.IsRectangle R → |discrepancy g R| ≤ γ) :
    0 ≤ γ
Source
TCSlib, `CommunicationComplexity.Deterministic.Protocol.nonneg_of_discrepancy_bound`
Lean proof
By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory inopen scoped BigOperators invariable {X Y : Type*} in/-- A uniform bound `γ` on the absolute discrepancy of all rectangles is nonnegative (apply the bound to the full rectangle `X × Y`). -/lemma CommunicationComplexity.Deterministic.Protocol.nonneg_of_discrepancy_bound    [μ : FiniteProbabilitySpace (X × Y)]    (g : X → Y → Bool) (γ : ℝ)    (hdisc : ∀ R : Set (X × Y), Rectangle.IsRectangle R → |discrepancy g R| ≤ γ) :    0 ≤ γ := by  have huniv :=    hdisc Set.univ ⟨Set.univ, Set.univ, by      ext xy      simp⟩  exact le_trans (abs_nonneg _) huniv
See it in the graphDiscuss this resultChallenge it