CommunicationComplexity.Deterministic.Protocol.one_sub_two_distributionalError_le_two_pow_mul
theoremverifiedimported Lean
Discrepancy lower bound on distributional error. Let $\mu$ be a finite probability measure on $X \times Y$, let $g : X \times Y \to \mathrm{Bool}$, and let $\gamma \in \bbr$ be such that every rectangle $R \subseteq X \times Y$ satisfies $\abs{\mathrm{disc}_\mu(g, R)} \le \gamma$. Then for every deterministic Boolean-valued communication protocol $p$, writing $\mathrm{err}$ for the $\mu$-probability that $p$ disagrees with $g$ (that is, the measure of $\{(x,y) : p(x,y) \ne g(x,y)\}$) and $c$ for the communication complexity of $p$, \[ 1 - 2\,\mathrm{err} \;\le\; 2^{c}\cdot\gamma . \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped BigOperators in variable {X Y : Type*} in theorem CommunicationComplexity.Deterministic.Protocol.one_sub_two_distributionalError_le_two_pow_mul [μ : FiniteProbabilitySpace (X × Y)] (g : X → Y → Bool) (γ : ℝ) (p : Protocol X Y Bool) (hdisc : ∀ R : Set (X × Y), Rectangle.IsRectangle R → |discrepancy g R| ≤ γ) : 1 - 2 * p.distributionalError μ g ≤ (2 : ℝ) ^ p.complexity * γ
- Source
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.one_sub_two_distributionalError_le_two_pow_mul`
- 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.one_sub_two_distributionalError_le_two_pow_mul← CommunicationComplexity.Deterministic.Protocol.one_sub_two_distributionalError_le_two_pow_mul (TCSlib/CommunicationComplexity/NewmanTheorem/Discrepancy.lean:322): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 20
- CommunicationComplexity.Deterministic.Protocol.complexityThe communication complexity of a protocol $p$ is the worst-case total number of bits exchanged: an output node costs $0$, while an alice…
- CommunicationComplexity.Deterministic.Protocol.signedBias_eq_sum_rectanglesSigned bias as a sum over leaf rectangles. Let $\mu$ be a finite probability space on $X \times Y$, let $p$ be a deterministic Boolean…
- CommunicationComplexity.Deterministic.Protocol.rectangleSign_absRectangle sign has absolute value one. Let $p$ be a deterministic Boolean two-party communication protocol on input types $X$ (Alice) and…
- CommunicationComplexity.Deterministic.Protocol.rectangleSignFor a deterministic Boolean protocol $p$ and a set $R \subseteq X \times Y$, the rectangle sign is $+1$ if the protocol outputs…
- CommunicationComplexity.Deterministic.Protocol.mem_leafRectanglesFinsetMembership in the finite set of leaf rectangles. Let $X \times Y$ carry the structure of a finite probability space, let $p$ be a…
- CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalErrorSigned correlation and distributional error. Let $X$ and $Y$ be the input types of Alice and Bob, and let $\mu$ be a finite probability…
- CommunicationComplexity.boolSign_xorBoolean sign turns XOR into multiplication. Write $\mathrm{sgn} : \mathrm{Bool} \to \bbr$ for the Boolean sign map, which sends…
- 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.Deterministic.Protocol.nonneg_of_discrepancy_boundDiscrepancy bound is nonnegative. Let $X \times Y$ carry a finite probability space $\mu$, let $g : X \to Y \to \mathrm{Bool}$ be a…
- CommunicationComplexity.Deterministic.Protocol.leafRectanglesThe leaf rectangles of a protocol $p : \texttt{Protocol}\,X\,Y\,\alpha$ form the collection…
- CommunicationComplexity.Deterministic.Protocol.leafRectanglesFinsetGiven a finite probability space $\mu$ on $X \times Y$ and a deterministic protocol $p$, this is the canonical
Finsetenumerating… - 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.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.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… - CommunicationComplexity.Deterministic.Protocol.leafRectangles_isRectangleLeaf rectangles are combinatorial rectangles. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_cardLeaf rectangle count is at most two to the complexity. Let $p$ be a deterministic two-party communication protocol over input types $X$…
- 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.logb_le_complexity_of_distributionalErrorDiscrepancy lower bound on communication complexity. Let $\mu$ be a finite probability space 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/-- Core discrepancy bound: if every combinatorial rectangle has absolute discrepancy at most `γ` (with respect to `μ`), then every deterministic Boolean protocol `p` of complexity `c` and distributional error `e` (with respect to `μ` and `g`) satisfies `1 − 2e ≤ 2^c · γ`. [RY20, Thm 5.2 proof] (`1 − 2e ≤ 2^c · γ`). **Proof sketch.** Step 1: `γ ≥ 0`, and each leaf rectangle `R` of `p` is a rectangle, so `|rectangleSign p R · disc(g, R)| ≤ γ`. Step 2: by the triangle inequality, the sum over the leaf rectangles of these signed discrepancies has absolute value at most `(number of leaf rectangles) · γ`. Step 3: a protocol of complexity `c` has at most `2^c` leaf rectangles. Step 4: the signed bias of `p` with `g` equals that sum (`signedBias_eq_sum_rectangles`), hence is bounded by `2^c · γ` in absolute value. Step 5: the signed bias equals `1 − 2e` (`signedBias_eq_one_sub_two_distributionalError`), and `1 − 2e ≤ |1 − 2e|`. -/theorem CommunicationComplexity.Deterministic.Protocol.one_sub_two_distributionalError_le_two_pow_mul [μ : FiniteProbabilitySpace (X × Y)] (g : X → Y → Bool) (γ : ℝ) (p : Protocol X Y Bool) (hdisc : ∀ R : Set (X × Y), Rectangle.IsRectangle R → |discrepancy g R| ≤ γ) : 1 - 2 * p.distributionalError μ g ≤ (2 : ℝ) ^ p.complexity * γ := by -- Step 1: γ ≥ 0 and each leaf rectangle's signed discrepancy is at most γ have hγ_nonneg := nonneg_of_discrepancy_bound (μ := μ) g γ hdisc have hrect : ∀ R ∈ leafRectanglesFinset p, |rectangleSign p R * discrepancy g R| ≤ γ := by intro R hR have hRrect : Rectangle.IsRectangle R := Deterministic.Protocol.leafRectangles_isRectangle p R ((mem_leafRectanglesFinset p R).1 hR) calc |rectangleSign p R * discrepancy g R| = |rectangleSign p R| * |discrepancy g R| := by rw [abs_mul] _ = |discrepancy g R| := by rw [rectangleSign_abs, one_mul] _ ≤ γ := hdisc R hRrect -- Step 2: triangle inequality over the leaf rectangles have hsum : |Finset.sum (leafRectanglesFinset p) (fun R => rectangleSign p R * discrepancy g R)| ≤ ((leafRectanglesFinset p).card : ℝ) * γ := by calc |Finset.sum (leafRectanglesFinset p) (fun R => rectangleSign p R * discrepancy g R)| ≤ Finset.sum (leafRectanglesFinset p) (fun R => |rectangleSign p R * discrepancy g R|) := by simpa using (Finset.abs_sum_le_sum_abs (s := leafRectanglesFinset p) (f := fun R => rectangleSign p R * discrepancy g R)) _ ≤ Finset.sum (leafRectanglesFinset p) (fun _ => γ) := by exact Finset.sum_le_sum (fun R hR => hrect R hR) _ = ((leafRectanglesFinset p).card : ℝ) * γ := by simp [nsmul_eq_mul] -- Step 3: at most 2^c leaf rectangles have hcard : ((leafRectanglesFinset p).card : ℝ) ≤ (2 : ℝ) ^ p.complexity := by have hcard_nat : (leafRectanglesFinset p).card ≤ 2 ^ p.complexity := by rw [show (leafRectanglesFinset p).card = p.leafRectangles.ncard by simpa [leafRectanglesFinset] using (Set.ncard_eq_toFinset_card p.leafRectangles (Set.toFinite p.leafRectangles)).symm] simpa using (Deterministic.Protocol.leafRectangles_card p) exact_mod_cast hcard_nat -- Step 4: the signed bias is the rectangle sum, hence bounded by 2^c · γ have hbias : |∫ xy : X × Y, boolSign (p.run xy.1 xy.2) * boolSign (g xy.1 xy.2)| ≤ (2 : ℝ) ^ p.complexity * γ := by rw [signedBias_eq_sum_rectangles] exact hsum.trans (mul_le_mul_of_nonneg_right hcard hγ_nonneg) -- Step 5: the signed bias is 1 − 2e have habs : |1 - 2 * p.distributionalError μ g| ≤ (2 : ℝ) ^ p.complexity * γ := by simpa [signedBias_eq_one_sub_two_distributionalError] using hbias exact (le_abs_self _).trans habs