CommunicationComplexity.boolSign_xor
theoremverifiedimported Lean
Boolean sign turns XOR into multiplication. Write $\mathrm{sgn} : \mathrm{Bool} \to \bbr$ for the Boolean sign map, which sends $\mathrm{false}$ to $1$ and $\mathrm{true}$ to $-1$. Then for all Boolean values $a, b$, \[ \mathrm{sgn}(a \oplus b) \;=\; \mathrm{sgn}(a)\,\mathrm{sgn}(b), \] where $a \oplus b$ denotes the exclusive-or of $a$ and $b$; equivalently, $\mathrm{sgn}$ is a homomorphism from $(\mathrm{Bool}, \oplus)$ to the multiplicative group $\{\pm 1\}$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in @[simp] lemma CommunicationComplexity.boolSign_xor (a b : Bool) : boolSign (Bool.xor a b) = boolSign a * boolSign b
- Source
- TCSlib, `CommunicationComplexity.boolSign_xor`
- 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_xor← CommunicationComplexity.boolSign_xor (TCSlib/CommunicationComplexity/DeterministicCC/Helper.lean:72): 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 4
- 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.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.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…
- 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 in/-- The sign of an exclusive or is the product of the signs: `boolSign (a xor b)` equals `boolSign a * boolSign b`. This is the one-bit case of the character identity `χ_S · χ_T = χ_{S △ T}` [OD14, §1.3]. -/@[simp] lemma CommunicationComplexity.boolSign_xor (a b : Bool) : boolSign (Bool.xor a b) = boolSign a * boolSign b := by cases a <;> cases b <;> norm_num [boolSign]