CommunicationComplexity.Deterministic.Protocol.rectangleSign_eq_boolSign
theoremverifiedimported Lean
Rectangle sign equals Boolean sign on leaf rectangles. Let $p$ be a deterministic two-party communication protocol with Boolean output, over input types $X$ (Alice) and $Y$ (Bob). If $R$ is a leaf rectangle of $p$ and $(x, y)$ is any point of $R$, then the rectangle sign of $R$ agrees with the Boolean sign of the value that $p$ computes on $(x, y)$: it equals $+1$ when $p$ outputs $\mathrm{false}$ at $(x, y)$ and $-1$ when $p$ outputs $\mathrm{true}$.
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.rectangleSign_eq_boolSign (p : Protocol X Y Bool) {R : Set (X × Y)} (hR : R ∈ p.leafRectangles) {xy : X × Y} (hxy : xy ∈ R) : rectangleSign p R = boolSign (p.run xy.1 xy.2)
- Source
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.rectangleSign_eq_boolSign`
- 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.rectangleSign_eq_boolSign← CommunicationComplexity.Deterministic.Protocol.rectangleSign_eq_boolSign (TCSlib/CommunicationComplexity/NewmanTheorem/Discrepancy.lean:169): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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.leafRectanglesThe leaf rectangles of a protocol $p : \texttt{Protocol}\,X\,Y\,\alpha$ form the collection…
- 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.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.Deterministic.Protocol.leafRectangles_monoLeaf rectangles of a protocol are monochromatic. Let $p$ be a deterministic two-party communication protocol over input types $X$ and $Y$…
- Used by 1
- CommunicationComplexity.Deterministic.Protocol.sum_indicator_leafRectangles_eqIndicator sum over leaf rectangles recovers the protocol output. Let $X$ and $Y$ be input types whose product $X \times Y$ carries a…
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/-- On a leaf rectangle `R` of `p`, the rectangle sign of `R` equals the `±1` sign of the protocol's output at any point of `R` (the output is constant on leaf rectangles). **Proof sketch.** Case on whether the protocol outputs `false` at every point of `R`. If so, the rectangle sign is `1` and so is the sign of the output at `xy`. Otherwise the output is constant on the leaf rectangle (`leafRectangles_mono`), so it cannot be `false` at `xy` (it would then be `false` on all of `R`); hence it is `true` and both sides equal `-1`. -/lemma CommunicationComplexity.Deterministic.Protocol.rectangleSign_eq_boolSign (p : Protocol X Y Bool) {R : Set (X × Y)} (hR : R ∈ p.leafRectangles) {xy : X × Y} (hxy : xy ∈ R) : rectangleSign p R = boolSign (p.run xy.1 xy.2) := by classical by_cases hfalse : ∀ z ∈ R, p.run z.1 z.2 = false · rw [rectangleSign, if_pos hfalse] simp [boolSign, hfalse xy hxy] · have hmono := leafRectangles_mono p p.run rfl R hR have htrue : p.run xy.1 xy.2 = true := by cases hrun : p.run xy.1 xy.2 with | false => exfalso apply hfalse intro z hz rw [hmono z.1 xy.1 z.2 xy.2 hz hxy, hrun] | true => rfl · rw [rectangleSign, if_neg hfalse] simp [boolSign, htrue]