BoolBLR.bool_dist
defimported Lean
The distance between two Boolean functions $f, g : \{0,1\}^n \to \{0,1\}$ is \[ \dist(f, g) \;=\; \Pr_{x \sim \{0,1\}^n}[f(x) \ne g(x)], \] computed as the uniform expectation of the indicator $\mathbf{1}[f(x) \ne g(x)]$.
Statement
open Finset BoolFourier in noncomputable def BoolBLR.bool_dist {n : ℕ} (f g : hypercube n → Bool) : ℝ
- Defined in
- TCSlib, `BoolBLR.bool_dist`
- 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.bool_dist← BoolBLR.bool_dist (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:55): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- 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.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for
BooleanAnalysis.BoolCube$n$.
- Used by 3
- 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.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.fourier_coeff_le_of_dist_geFourier coefficient bound from distance. Let $f,g:\{0,1\}^n\to\{0,1\}$ be Boolean-valued functions, let $S\subseteq[n]$, and let…
Lean source view module on GitHub
open Finset BoolFourier in /-- Defines the uniform Hamming distance between two Boolean functions. **Source:** [OD14, §1.6]. -/ noncomputable def BoolBLR.bool_dist {n : ℕ} (f g : hypercube n → Bool) : ℝ := expectation (fun x => if f x = g x then 0 else 1)