BoolBLR.epsilon_far_from_linear
defimported Lean
A function $f : \{0,1\}^n \to \{0,1\}$ is $\varepsilon$-far from linear if $0 \le \varepsilon \le 1$ and for every linear function $g : \{0,1\}^n \to \{0,1\}$ we have $\dist(f, g) \ge \varepsilon$.
Statement
open Finset BoolFourier in def BoolBLR.epsilon_far_from_linear {n : ℕ} (f : hypercube n → Bool) (ε : ℝ) : Prop
- Defined in
- TCSlib, `BoolBLR.epsilon_far_from_linear`
- 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.epsilon_far_from_linear← BoolBLR.epsilon_far_from_linear (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:63): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 3
- BoolBLR.is_linear_boolA function $f : \{0,1\}^n \to \{0,1\}$ is linear if for all $x, y \in \{0,1\}^n$ we have \[ f(x \oplus y) = f(x) \oplus f(y), \]…
- BoolFourier.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for
BooleanAnalysis.BoolCube$n$. - BoolBLR.bool_distThe distance between two Boolean functions $f, g : \{0,1\}^n \to \{0,1\}$ is…
- Used by 4
- BoolBLR.fourier_coeff_le_of_far_from_linearFourier coefficient bound for functions far from linear. Let $f : \{0,1\}^n \to \{0,1\}$ be $\varepsilon$-far from linear, meaning that…
- 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_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_soundness_via_fourier_aux_h_boundPer-coefficient cube bound for functions far from linear. Let $f : \{0,1\}^n \to \{0,1\}$ be $\varepsilon$-far from linear, meaning that…
Lean source view module on GitHub
open Finset BoolFourier in /-- Defines when a Boolean function is at least `ε`-far from every linear Boolean function. **Source:** [OD14, §1.6]. -/ def BoolBLR.epsilon_far_from_linear {n : ℕ} (f : hypercube n → Bool) (ε : ℝ) : Prop := 0 ≤ ε ∧ ε ≤ 1 ∧ ∀ g : hypercube n → Bool, is_linear_bool g → bool_dist f g ≥ ε -- f is linear if and only if (-1)^f = χ_S for some S