AFTD Auto-Formalizing Theoretical Domains

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.
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

Lean source view module on GitHub

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]
See it in the graphDiscuss this resultChallenge it