BoolBLR.BLR_accept_prob_pm1
theoremverifiedimported Lean
BLR acceptance probability in ±1 form. Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean-valued function, and write $F(x) = (-1)^{f(x)} \in \{\pm 1\}$ for its sign lift. Then the BLR acceptance probability of $f$, the probability that $F(x \oplus y) = F(x)\,F(y)$ when $x$ and $y$ are drawn independently and uniformly from $\{0,1\}^n$, satisfies \[ \Pr_{x,y}[\text{BLR accepts}] \;=\; \frac{1 + \E_{x}\!\left[\E_{y}\!\left[ F(x)\,F(y)\,F(x \oplus y) \right]\right]}{2}, \] where $x \oplus y$ denotes the componentwise XOR.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in lemma BoolBLR.BLR_accept_prob_pm1 {n : ℕ} (f : hypercube n → Bool) : BLR_accept_prob f = (1 + expectation (fun x => expectation (fun y => lift_pm1 f x * lift_pm1 f y * lift_pm1 f (xor_vec x y)))) / 2
- Source
- TCSlib, `BoolBLR.BLR_accept_prob_pm1`
- 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← BoolBLR.BLR_accept_prob_pm1 (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:197): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- BoolFourier.expectationFor $f : \{0,1\}^n \to \mathbb{R}$, the uniform expectation is \[ \mathbb{E}[f] = \frac{1}{2^n} \sum_{x \in \{0,1\}^n} f(x). \]
- BoolFourier.card_hypercubeCardinality of the Boolean hypercube. For every natural number $n$, the Boolean hypercube $\{0,1\}^n$ has exactly $2^n$ elements.
- BoolBLR.BLR_accept_prob_pm1_aux_h_eqPointwise $\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…
- BoolBLR.BLR_accept_probThe BLR acceptance probability of $f : \{0,1\}^n \to \{0,1\}$ is…
- 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…
- BoolFourier.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for
BooleanAnalysis.BoolCube$n$. - 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_soundnessSoundness of the BLR linearity test. Let $f : \{0,1\}^n \to \{0,1\}$ and let $\varepsilon \in \bbr$ satisfy $0 \le \varepsilon \le 1$.…
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 in/-- Expresses BLR acceptance probability through the `{±1}` triple correlation. **Source:** [OD14, §1.6]. -/lemma BoolBLR.BLR_accept_prob_pm1 {n : ℕ} (f : hypercube n → Bool) : BLR_accept_prob f = (1 + expectation (fun x => expectation (fun y => lift_pm1 f x * lift_pm1 f y * lift_pm1 f (xor_vec x y)))) / 2 := by unfold BLR_accept_prob expectation; -- Pointwise, the indicator equals (1 + product of three ±1 values)/2. -- Push the (1 + …)/2 form through expectations. simp_all +decide [ Finset.sum_add_distrib, add_div , (BLR_accept_prob_pm1_aux_h_eq f)]; norm_num [ ← Finset.sum_div _ _ _, card_hypercube ] ; ring-- E [ E [ f(x) f(y) f(x + y) ] ] = E [ f(x) E [ f(y) f(x + y) ] ] = E [ f(x) (f * f) (x) ]