BoolBLR.BLR_soundness
theoremverifiedformalizationimported Lean
Soundness of the BLR linearity test. Let $f : \{0,1\}^n \to \{0,1\}$ and let $\varepsilon \in \bbr$ satisfy $0 \le \varepsilon \le 1$. Suppose $f$ is $\varepsilon$-far from linear, meaning that every linear function $g : \{0,1\}^n \to \{0,1\}$ (one satisfying $g(x \oplus y) = g(x) \oplus g(y)$ for all $x, y$) has distance $\Pr_{x}[f(x) \ne g(x)] \ge \varepsilon$ from $f$. Then the BLR acceptance probability of $f$ satisfies \[ \E_{x}\!\left[\E_{y}\!\left[\mathbf{1}\!\left[(-1)^{f(x \oplus y)} = (-1)^{f(x)}\,(-1)^{f(y)}\right]\right]\right] \;\le\; 1 - \varepsilon, \] where $x$ and $y$ range uniformly over $\{0,1\}^n$; equivalently, the test rejects $f$ with probability at least $\varepsilon$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in lemma BoolBLR.BLR_soundness {n : ℕ} (f : hypercube n → Bool) (ε : ℝ) (hfar : epsilon_far_from_linear f ε) : BLR_accept_prob f ≤ 1 - ε
- Formalizes
- Soundness of the BLR linearity test, as formalized in TCSlib (`BoolBLR.BLR_soundness`)
- 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_soundness← BoolBLR.BLR_soundness (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:391): verbatim
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 21
- BoolBLR.BLR_soundness_via_fourierSum of cubed Fourier coefficients bounds distance to linearity. Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean function and let…
- BoolBLR.BLR_accept_probThe BLR acceptance probability of $f : \{0,1\}^n \to \{0,1\}$ is…
- 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…
- BoolBLR.epsilon_far_from_linearA function $f : \{0,1\}^n \to \{0,1\}$ is $\varepsilon$-far from linear if $0 \le \varepsilon \le 1$ and for every linear function…
- BoolBLR.triple_expectation_eq_cube_fourierCube of Fourier coefficients as an autocorrelation expectation. Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean-valued function on the…
- BoolFourier.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for
BooleanAnalysis.BoolCube$n$. - 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_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_sqSign 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_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$.…
- 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.flipBit_flipBitBit-flip is an involution. For a point $x$ in the Boolean hypercube $\{0,1\}^n$ and a coordinate $i$, flipping the $i$-th coordinate of…
- 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.instAddCommGroupBooleanFuncBoolean functions form an
ℝ-vector space. - BooleanAnalysis.instModuleRealBooleanFuncBooleanAnalysis.instModuleRealBooleanFunc
- 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…
- 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…
- BoolFourier.fourier_coeffThe Fourier coefficient of $f : \{0,1\}^n \to \mathbb{R}$ at $S \subseteq [n]$ is \[ \hat f(S) = \langle f, \chi_S \rangle. \]
- 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). \]
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in /-- Shows that a function `ε`-far from linearity is rejected by BLR with probability at least `ε`. **Source:** [OD14, §1.6]. -/ lemma BoolBLR.BLR_soundness {n : ℕ} (f : hypercube n → Bool) (ε : ℝ) (hfar : epsilon_far_from_linear f ε) : BLR_accept_prob f ≤ 1 - ε := by rw [BLR_accept_prob_pm1]; -- Combine the cube-sum identity and the soundness bound; linarith finishes. linarith [ BLR_soundness_via_fourier f ε hfar, triple_expectation_eq_cube_fourier f ]