AFTD Auto-Formalizing Theoretical Domains

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

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