BoolBLR.fourier_coeff_le_of_dist_ge
theoremverifiedimported Lean
Fourier coefficient bound from distance. Let $f,g:\{0,1\}^n\to\{0,1\}$ be Boolean-valued functions, let $S\subseteq[n]$, and let $\varepsilon\in\bbr$. Write $f^{\pm},g^{\pm}:\{0,1\}^n\to\bbr$ for their $\pm1$ lifts, given by $x\mapsto(-1)^{f(x)}$ and $x\mapsto(-1)^{g(x)}$. Suppose that $g^{\pm}$ coincides with the Walsh character $\chi_S$, and that $\dist(f,g)=\Pr_{x}[f(x)\ne g(x)]\ge\varepsilon$. Then the Fourier coefficient of $f^{\pm}$ at $S$ satisfies \[\widehat{f^{\pm}}(S)\;\le\;1-2\varepsilon.\]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in lemma BoolBLR.fourier_coeff_le_of_dist_ge {n : ℕ} (f g : hypercube n → Bool) (S : Finset (Fin n)) (hchar : lift_pm1 g = char_S S) (hdist : bool_dist f g ≥ ε) : fourier_coeff (lift_pm1 f) S ≤ 1 - 2 * ε
- Source
- TCSlib, `BoolBLR.fourier_coeff_le_of_dist_ge`
- 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.fourier_coeff_le_of_dist_ge← BoolBLR.fourier_coeff_le_of_dist_ge (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:268): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 22
- 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.card_hypercubeCardinality of the Boolean hypercube. For every natural number $n$, the Boolean hypercube $\{0,1\}^n$ has exactly $2^n$ elements.
- 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*…
- BoolFourier.char_SFor a set $S \subseteq [n]$, the Walsh character $\chi_S : \{0,1\}^n \to \mathbb{R}$ is \[ \chi_S(x) = \prod_{i \in S} (-1)^{x_i}, \]…
- 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.instModuleRealBooleanFuncBooleanAnalysis.instModuleRealBooleanFunc
- BooleanAnalysis.innerProduct_chi_selfWalsh characters have unit norm. Let $n$ be a natural number and let $S \subseteq [n]$. Under the uniform measure on the Boolean hypercube…
- BoolFourier.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for
BooleanAnalysis.BoolCube$n$. - BoolBLR.fourier_coeff_le_of_dist_ge_aux_h_lift_pm1Product of $\pm 1$ lifts as a disagreement indicator. Let $f, g : \{0,1\}^n \to \{0,1\}$ be Boolean-valued functions on the hypercube, and…
- 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_falseSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- 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. \]
- BoolBLR.bool_distThe distance between two Boolean functions $f, g : \{0,1\}^n \to \{0,1\}$ is…
- 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$;…
- BoolFourier.inner_productThe inner product of $f, g : \{0,1\}^n \to \mathbb{R}$ is…
- 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$;…
- 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…
- BooleanAnalysis.instAddCommGroupBooleanFuncBoolean functions form an
ℝ-vector space. - 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.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- BoolFourier.BoolFunA Boolean function of arity $n$ is an element of type $\{0,1\}^n \to \mathbb{R}$, defined as an abbreviation for…
- Used by 2
- 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…
- StandardModel.repU1The 2d representation of U(1) with charge 3 as a homomorphism from U(1) to
unitaryGroup (Fin 2) ℂ.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Finset BoolFourier in/-- Bounds a Fourier coefficient using distance from the corresponding linear function. **Source:** [OD14, §1.6 (Fourier soundness proof)]. -/lemma BoolBLR.fourier_coeff_le_of_dist_ge {n : ℕ} (f g : hypercube n → Bool) (S : Finset (Fin n)) (hchar : lift_pm1 g = char_S S) (hdist : bool_dist f g ≥ ε) : fourier_coeff (lift_pm1 f) S ≤ 1 - 2 * ε := by -- Reduce to f̂(S) ≤ 1 - 2 · dist(f,g). refine le_trans ?_ ( sub_le_sub_left ( mul_le_mul_of_nonneg_left hdist <| by norm_num ) 1 ); unfold fourier_coeff bool_dist; unfold inner_product expectation; -- Pointwise identity: lift(f)(x)·lift(g)(x) = 1 - 2·𝟙[f(x) ≠ g(x)]. simp_all +decide [ ← hchar, Finset.sum_ite , (fourier_coeff_le_of_dist_ge_aux_h_lift_pm1 f g)]; ring_nf; norm_num [ card_hypercube ] ; norm_num [ ← mul_pow ]-- if f is epsilon-far from all linear functions, then f-hat (S) ≤ 1 - 2 * ε for all S