AFTD Auto-Formalizing Theoretical Domains

BoolBLR.BLR_accept_prob

defimported Lean

The BLR acceptance probability of $f : \{0,1\}^n \to \{0,1\}$ is \[ \Pr_{x,y}[\text{BLR accepts}] \;=\; \E_{x}\!\left[\E_{y}\!\left[ \mathbf{1}\!\left[ \texttt{BoolBLR.lift\_pm1}\,f(x \oplus y) = \texttt{BoolBLR.lift\_pm1}\,f(x)\cdot\texttt{BoolBLR.lift\_pm1}\,f(y) \right] \right]\right], \] where $x, y$ are drawn uniformly from $\{0,1\}^n$.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BoolFourier in
noncomputable def BoolBLR.BLR_accept_prob {n : ℕ} (f : hypercube n → Bool) : ℝ
Defined in
TCSlib, `BoolBLR.BLR_accept_prob`
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
none listed
Built on 4
  • 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.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 3
  • BoolBLR.BLR_completenessCompleteness of the BLR linearity test. Let $n$ be a natural number and let $f : \{0,1\}^n \to \{0,1\}$ be linear, meaning that…
  • 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$.…
  • 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 in
set_option relaxedAutoImplicit true in
open Finset BoolFourier in
/-- Defines the acceptance probability of the Boolean BLR linearity test. **Source:** [OD14, §1.6]. -/
noncomputable def BoolBLR.BLR_accept_prob {n : ℕ} (f : hypercube n → Bool) : ℝ :=
  expectation (fun x =>
    expectation (fun y =>
      if lift_pm1 f (xor_vec x y) = lift_pm1 f x * lift_pm1 f y then 1 else 0))

-- Pr [ BLR accepts f ] = ( 1 + E [ E [ f(x) f(y) f(x + y) ] ] ) / 2
See it in the graphDiscuss this resultChallenge it