AFTD Auto-Formalizing Theoretical Domains

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

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