BoolBLR.BLR_accept_prob_pm1_aux_h_eq
theoremverifiedimported Lean
Pointwise $\pm 1$ form of the BLR indicator. Fix $n \in \bbn$ and a Boolean-valued function $f : \{0,1\}^n \to \{0,1\}$, and let $g : \{0,1\}^n \to \bbr$ be its $\pm 1$ lift, $g(x) = (-1)^{f(x)}$. Then for all $x, y \in \{0,1\}^n$, \[ \mathbf{1}\!\left[\, g(x \oplus y) = g(x)\,g(y) \,\right] \;=\; \frac{1 + g(x)\,g(y)\,g(x \oplus y)}{2}, \] where $x \oplus y$ denotes the componentwise XOR and the left-hand side is $1$ when the equality holds and $0$ otherwise.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in lemma BoolBLR.BLR_accept_prob_pm1_aux_h_eq {n : ℕ} (f : BoolFourier.hypercube n → Bool) : ∀ (x y : BoolFourier.hypercube n), (if lift_pm1 f (BoolFourier.xor_vec x y) = lift_pm1 f x * lift_pm1 f y then 1 else 0) = (1 + lift_pm1 f x * lift_pm1 f y * lift_pm1 f (BoolFourier.xor_vec x y)) / 2
- Source
- TCSlib, `BoolBLR.BLR_accept_prob_pm1_aux_h_eq`
- Lean proof
- By Prastik Mohanraj, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Prastik Mohanraj. 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.BoolBLR.BLR_accept_prob_pm1_aux_h_eq← BoolBLR.BLR_accept_prob_pm1_aux_h_eq (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:183): adapted
What was changed in
BoolBLR.BLR_accept_prob_pm1_aux_h_eq--- TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:183 (BoolBLR.BLR_accept_prob_pm1_aux_h_eq) +++ as compiled here @@ -1,2 +1,5 @@ -private lemma BLR_accept_prob_pm1_aux_h_eq {n : ℕ} (f : BoolFourier.hypercube n → Bool) : +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open Finset BoolFourier in +lemma BoolBLR.BLR_accept_prob_pm1_aux_h_eq {n : ℕ} (f : BoolFourier.hypercube n → Bool) : ∀ (x y : BoolFourier.hypercube n), @@ -7,4 +10,4 @@ -- Accept case: triple product is +1, so (1+1)/2 = 1. - · cases h : f x <;> cases h' : f y <;> simp_all +decide [ lift_pm1 ]; + · cases h : f x <;> cases h' : f y <;> simp_all +decide [ lift_pm1 ] <;> norm_num [BooleanAnalysis.boolToSign] at *; -- Reject case: triple product is -1, so (1-1)/2 = 0. - · cases h : f x <;> cases h' : f y <;> cases h'' : f ( xor_vec x y ) <;> simp_all +decide [ lift_pm1 ]; + · cases h : f x <;> cases h' : f y <;> cases h'' : f ( xor_vec x y ) <;> simp_all +decide [ lift_pm1 ] <;> norm_num [BooleanAnalysis.boolToSign] at *; - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- BooleanAnalysis.sum_boolToSignSign encoding sums to zero over the Booleans. Let $\sigma\colon\mathrm{Bool}\to\{-1,1\}$ be the sign encoding, sending the value *false*…
- BooleanAnalysis.boolToSignThe sign encoding maps $\mathrm{Bool}$ to $\{-1,1\}\subset\bbr$:…
- BoolFourier.xor_vecFor $x, y \in \{0,1\}^n$, the vector $\mathrm{xor\_vec}(x,y)_i = x_i \oplus y_i$ is the componentwise XOR, giving the group operation on…
- BooleanAnalysis.boolToSign_mul_selfSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- BooleanAnalysis.chiS_singletonValue of a singleton Walsh character. Fix a dimension $n$, a coordinate $i \in [n]$, and a point $x$ of the Boolean hypercube $\{0,1\}^n$.…
- BoolFourier.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for
BooleanAnalysis.BoolCube$n$. - BooleanAnalysis.boolToSign_trueSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- BooleanAnalysis.boolToSign_falseSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- BooleanAnalysis.boolToSign_notSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- BooleanAnalysis.boolToSign_sqSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- BoolBLR.lift_pm1Given $f : \{0,1\}^n \to \{0,1\}$, its $\pm 1$ lift $\texttt{BoolBLR.lift\_pm1}\,f : \{0,1\}^n \to \mathbb{R}$ is defined by…
- Used by 1
- BoolBLR.BLR_accept_prob_pm1BLR acceptance probability in ±1 form. Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean-valued function, and write…
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 autoImplicit true inset_option relaxedAutoImplicit true inopen Finset BoolFourier inlemma BoolBLR.BLR_accept_prob_pm1_aux_h_eq {n : ℕ} (f : BoolFourier.hypercube n → Bool) : ∀ (x y : BoolFourier.hypercube n), (if lift_pm1 f (BoolFourier.xor_vec x y) = lift_pm1 f x * lift_pm1 f y then 1 else 0) = (1 + lift_pm1 f x * lift_pm1 f y * lift_pm1 f (BoolFourier.xor_vec x y)) / 2 := by intro x y; split_ifs; -- Accept case: triple product is +1, so (1+1)/2 = 1. · cases h : f x <;> cases h' : f y <;> simp_all +decide [ lift_pm1 ] <;> norm_num [BooleanAnalysis.boolToSign] at *; -- Reject case: triple product is -1, so (1-1)/2 = 0. · cases h : f x <;> cases h' : f y <;> cases h'' : f ( xor_vec x y ) <;> simp_all +decide [ lift_pm1 ] <;> norm_num [BooleanAnalysis.boolToSign] at *;