CommunicationComplexity.boolSign_mul_boolSign_eq_sub_two_indicator
theoremverifiedimported Lean
Product of two Boolean signs. For all Boolean values $a$ and $b$, the product of their signs satisfies \[ \mathrm{sign}(a)\cdot\mathrm{sign}(b) \;=\; 1 - 2\,\mathbf{1}[a \ne b], \] where $\mathrm{sign}(\cdot)$ sends $\mathrm{false}$ to $1$ and $\mathrm{true}$ to $-1$, and $\mathbf{1}[a \ne b]$ is $1$ when $a$ and $b$ differ and $0$ when they agree. Equivalently, this product equals $1$ when the two bits are equal and $-1$ when they disagree.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma CommunicationComplexity.boolSign_mul_boolSign_eq_sub_two_indicator (a b : Bool) : boolSign a * boolSign b = (1 : ℝ) - 2 * (if a ≠ b then 1 else 0)
- Source
- TCSlib, `CommunicationComplexity.boolSign_mul_boolSign_eq_sub_two_indicator`
- 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.boolSign_mul_boolSign_eq_sub_two_indicator← CommunicationComplexity.boolSign_mul_boolSign_eq_sub_two_indicator (TCSlib/CommunicationComplexity/DeterministicCC/Helper.lean:90): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- CommunicationComplexity.boolSign$\texttt{boolSign} : \mathrm{Bool} \to \mathbb{R}$ assigns the real value $1$ to $\mathrm{false}$ and $-1$ to $\mathrm{true}$, embedding…
- Used by 1
- 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…
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 in/-- Two `boolSign` factors collapse to `1 - 2 * indicator(a ≠ b)`. -/lemma CommunicationComplexity.boolSign_mul_boolSign_eq_sub_two_indicator (a b : Bool) : boolSign a * boolSign b = (1 : ℝ) - 2 * (if a ≠ b then 1 else 0) := by cases a <;> cases b <;> norm_num [boolSign]