CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalError
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.CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalError← CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalError (TCSlib/CommunicationComplexity/NewmanTheorem/Discrepancy.lean:241): adapted
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
- CommunicationComplexity.boolSign_xorBoolean sign turns XOR into multiplication. Write $\mathrm{sgn} : \mathrm{Bool} \to \bbr$ for the Boolean sign map, which sends…
- CommunicationComplexity.boolSign_mul_boolSign_eq_sub_two_indicatorProduct of two Boolean signs. For all Boolean values $a$ and $b$, the product of their signs satisfies…
- CommunicationComplexity.Deterministic.ProtocolA deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an…
- CommunicationComplexity.Deterministic.Protocol.distributionalErrorGiven a deterministic protocol $p : \mathrm{Protocol}\,X\,Y\,\alpha$, a finite probability space $\mu$ on $X \times Y$, and a target…
- CommunicationComplexity.FiniteProbabilitySpace.measureReal_eq_integral_indicator_oneMeasure of a set as the integral of its indicator. Let $\Omega$ be a finite probability space and let $S \subseteq \Omega$. Then the…
- CommunicationComplexity.boolSign$\texttt{boolSign} : \mathrm{Bool} \to \mathbb{R}$ assigns the real value $1$ to $\mathrm{false}$ and $-1$ to $\mathrm{true}$, embedding…
- CommunicationComplexity.Deterministic.Protocol.runGiven a protocol $p$,
runevaluates $p$ on inputs $x : X$ and $y : Y$ by recursively following the bit-branching structure until… - CommunicationComplexity.FiniteProbabilitySpaceA typeclass bundling a
MeasureSpacestructure on $\Omega$ together with aCommunicationComplexity.FiniteMeasureSpace… - CommunicationComplexity.FiniteMeasureSpaceA typeclass for a measurable space $\Omega$ that is simultaneously finite (carries a
Fintypeinstance) and discrete (every subset…
- 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/-- 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]