AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalError

theoremverifiedimported Lean

Signed correlation and distributional error. Let $X$ and $Y$ be the input types of Alice and Bob, and let $\mu$ be a finite probability measure on $X \times Y$. Write $\sigma \colon \mathrm{Bool} \to \{\pm 1\}$ for the map sending $\mathrm{false}$ to $1$ and $\mathrm{true}$ to $-1$. For a deterministic communication protocol $p$ with Boolean output and a target function $g \colon X \to Y \to \mathrm{Bool}$, the expected signed correlation between the protocol's output and the target satisfies \[ \E_{(x,y)\sim\mu}\bigl[\sigma\bigl(p(x,y)\bigr)\,\sigma\bigl(g(x,y)\bigr)\bigr] \;=\; 1 - 2\,\varepsilon_\mu(p,g), \] where $p(x,y)$ denotes the value computed by running $p$ on $(x,y)$ and $\varepsilon_\mu(p,g) = \mu\bigl(\{(x,y) \mid p(x,y) \ne g(x,y)\}\bigr)$ is the distributional error of $p$ against $g$ under $\mu$.

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.signedBias_eq_one_sub_two_distributionalError
    [μ : FiniteProbabilitySpace (X × Y)]
    (p : Protocol X Y Bool)
    (g : X → Y → Bool) :
    ∫ xy : X × Y, boolSign (p.run xy.1 xy.2) * boolSign (g xy.1 xy.2) =
      1 - 2 * p.distributionalError μ g
Source
TCSlib, `CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalError`
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.
What was changed in CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalError
--- TCSlib/CommunicationComplexity/NewmanTheorem/Discrepancy.lean:241 (CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalError)
+++ as compiled here
@@ -1,12 +1,7 @@
-/-- The expected product of the `±1` signs of the protocol's output and of `g` (the
-signed bias, or correlation, of `p` with `g` under `μ`) equals `1 − 2e`, where `e` is the
-distributional error of `p` with respect to `g`: pointwise the product is `1 − 2·1[p
-errs]`, and the integral of the error indicator is `e`.
-
-**Proof sketch.** Let `E` be the set of inputs on which `p` and `g` disagree. (1) Pointwise,
-the product of the two signs equals `1 − 2·1_E` (`boolSign_mul_boolSign_eq_sub_two_indicator`).
-(2) Integrate: on a finite space both terms are integrable, the constant `1` integrates to
-`1` under a probability measure, and the integral of the indicator of `E` is the measure of
-`E`, which is by definition the distributional error. -/
-private lemma signedBias_eq_one_sub_two_distributionalError
+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.signedBias_eq_one_sub_two_distributionalError
     [μ : FiniteProbabilitySpace (X × Y)]
@@ -31,3 +26,3 @@
     (Ω := X × Y) Err]
-  rw [measureReal_univ_eq_one]
+  rw [probReal_univ]
   simp [Deterministic.Protocol.distributionalError, Measure.real, Err]
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
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/-- The expected product of the `±1` signs of the protocol's output and of `g` (the signed bias, or correlation, of `p` with `g` under `μ`) equals `1 − 2e`, where `e` is the distributional error of `p` with respect to `g`: pointwise the product is `1 − 2·1[p errs]`, and the integral of the error indicator is `e`. **Proof sketch.** Let `E` be the set of inputs on which `p` and `g` disagree. (1) Pointwise, the product of the two signs equals `1 − 2·1_E` (`boolSign_mul_boolSign_eq_sub_two_indicator`). (2) Integrate: on a finite space both terms are integrable, the constant `1` integrates to `1` under a probability measure, and the integral of the indicator of `E` is the measure of `E`, which is by definition the distributional error. -/lemma CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalError    [μ : FiniteProbabilitySpace (X × Y)]    (p : Protocol X Y Bool)    (g : X → Y → Bool) :    ∫ xy : X × Y, boolSign (p.run xy.1 xy.2) * boolSign (g xy.1 xy.2) =      1 - 2 * p.distributionalError μ g := by  classical  let Err : Set (X × Y) := {xy : X × Y | p.run xy.1 xy.2 ≠ g xy.1 xy.2}  have hpoint :      (fun xy : X × Y => boolSign (p.run xy.1 xy.2) * boolSign (g xy.1 xy.2)) =      fun xy : X × Y => (1 : ℝ) - 2 * Set.indicator Err 1 xy := by    ext xy    by_cases hxy : p.run xy.1 xy.2 ≠ g xy.1 xy.2    · simp [Err, hxy, boolSign_mul_boolSign_eq_sub_two_indicator]    · simp [Err, hxy, boolSign_mul_boolSign_eq_sub_two_indicator]  rw [hpoint]  rw [integral_sub (Integrable.of_finite) (Integrable.of_finite)]  rw [MeasureTheory.integral_const]  rw [MeasureTheory.integral_const_mul]  rw [← FiniteProbabilitySpace.measureReal_eq_integral_indicator_one    (Ω := X × Y) Err]  rw [probReal_univ]  simp [Deterministic.Protocol.distributionalError, Measure.real, Err]
See it in the graphDiscuss this resultChallenge it