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.CommunicationComplexity.Deterministic.Protocol.nonneg_of_discrepancy_bound← CommunicationComplexity.Deterministic.Protocol.nonneg_of_discrepancy_bound (TCSlib/CommunicationComplexity/NewmanTheorem/Discrepancy.lean:136): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- CommunicationComplexity.discrepancyLet $\mu$ be a finite probability space on $X \times Y$, let $g : X \to Y \to \mathrm{Bool}$, and let $S \subseteq X \times Y$. The…
- CommunicationComplexity.Rectangle.IsRectangleA subset $S \subseteq X \times Y$ is a rectangle if it factors as a product $A \times B$ for some $A \subseteq X$ and…
- CommunicationComplexity.FiniteProbabilitySpaceA typeclass bundling a
MeasureSpacestructure on $\Omega$ together with aCommunicationComplexity.FiniteMeasureSpace…
- Used by 1
- CommunicationComplexity.Deterministic.Protocol.one_sub_two_distributionalError_le_two_pow_mulDiscrepancy lower bound on distributional error. Let $\mu$ be a finite probability measure on $X \times Y$, let…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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