AFTD Auto-Formalizing Theoretical Domains

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