AFTD Auto-Formalizing Theoretical Domains

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.
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

Lean source view module on GitHub

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