AFTD Auto-Formalizing Theoretical Domains

BoolBLR.fourier_coeff_le_of_far_from_linear

theoremverifiedimported Lean

Fourier coefficient bound for functions far from linear. Let $f : \{0,1\}^n \to \{0,1\}$ be $\varepsilon$-far from linear, meaning that $0 \le \varepsilon \le 1$ and 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 $\Pr_{x}[f(x) \ne g(x)] \ge \varepsilon$ under the uniform distribution. Let $F(x) = (-1)^{f(x)}$ be the $\pm 1$ lift of $f$. Then for every subset $S \subseteq [n]$, the Fourier coefficient of $F$ at $S$ satisfies \[ \hat F(S) \;=\; \E_{x}\bigl[F(x)\,\chi_S(x)\bigr] \;\le\; 1 - 2\varepsilon, \] where $\chi_S(x) = \prod_{i \in S}(-1)^{x_i}$ is the Walsh character indexed by $S$.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BoolFourier in
lemma BoolBLR.fourier_coeff_le_of_far_from_linear
    {n : ℕ}
    (f : hypercube n → Bool)
    (ε : ℝ)
    (hfar : epsilon_far_from_linear f ε) :
    ∀ S : Finset (Fin n),
      fourier_coeff (lift_pm1 f) S ≤ 1 - 2 * ε
Source
TCSlib, `BoolBLR.fourier_coeff_le_of_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.
What was changed in BoolBLR.fourier_coeff_le_of_far_from_linear
--- TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:288 (BoolBLR.fourier_coeff_le_of_far_from_linear)
+++ as compiled here
@@ -1,5 +1,5 @@
-/-- Bounds every Fourier coefficient of a function far from all linear functions.
-
-**Source:** [OD14, §1.6 (Fourier soundness proof)]. -/
-lemma fourier_coeff_le_of_far_from_linear
+set_option autoImplicit true in
+set_option relaxedAutoImplicit true in
+open Finset BoolFourier in
+lemma BoolBLR.fourier_coeff_le_of_far_from_linear
     {n : ℕ}
@@ -16,15 +16,14 @@
       use fun x => (S.filter (fun i => x i)).card % 2 = 1;
-      funext x; simp [lift_pm1, char_S];
+      funext x; simp only [lift_pm1, char_S];
       -- Induction on S to compare parity-of-count vs product of (-1)^{x_i}.
-      induction S using Finset.induction <;> try simp_all +decide ;
-      · by_cases h : x ‹_› <;> simp_all +decide [ Finset.filter_insert ];
-        · cases Nat.mod_two_eq_zero_or_one ( Finset.card ( Finset.filter ( fun i => x i = true ) ‹_› ) ) <;> simp_all +decide [ Nat.add_mod ];
-          · simp only [BooleanAnalysis.chiS, Finset.prod_insert ‹_ ∉ _›, ‹x _ = true›,
-                       BooleanAnalysis.boolToSign_true] ; ring
-          ·
-            simp only [BooleanAnalysis.chiS, Finset.prod_insert (‹_›), ‹x _ = true›,
-                       BooleanAnalysis.boolToSign_true] at *
-            linarith
-        · simp only [BooleanAnalysis.chiS, Finset.prod_insert ‹_ ∉ _›, ‹x _ = false›,
-                     BooleanAnalysis.boolToSign_false] ; ring
+      induction S using Finset.induction with
+      | empty => simp [BooleanAnalysis.chiS, BooleanAnalysis.boolToSign]
+      | insert a s ha ih =>
+        simp only [BooleanAnalysis.chiS] at ih ⊢
+        rw [Finset.prod_insert ha, ← ih, Finset.filter_insert]
+        by_cases hx : x a = true
+        · rw [if_pos hx, Finset.card_insert_of_notMem (fun h => ha (Finset.mem_filter.mp h).1)]
+          rcases Nat.mod_two_eq_zero_or_one (s.filter (fun i => x i = true)).card with h | h <;>
+            simp [h, Nat.add_mod, hx, BooleanAnalysis.boolToSign]
+        · simp [hx, BooleanAnalysis.boolToSign]
     -- Then use linear_bool_iff_character to conclude g is linear.
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 25
  • 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…
  • 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), \]…
  • 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…
  • BoolBLR.linear_bool_iff_characterLinear Boolean functions are exactly the Walsh characters. Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean function. Then $f$ is linear —…
  • 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}, \]…
  • 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.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.chiSThe Walsh--Fourier character associated to $S\subseteq[n]$ is…
  • BooleanAnalysis.boolToSignThe sign encoding maps $\mathrm{Bool}$ to $\{-1,1\}\subset\bbr$:…
  • 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.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…
  • 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.BoolFunA Boolean function of arity $n$ is an element of type $\{0,1\}^n \to \mathbb{R}$, defined as an abbreviation for…
  • BoolFourier.BoolToPM1The map $\mathrm{BoolToPM1} : \mathrm{Bool} \to \mathbb{R}$ sends $\mathtt{false}$ to $1$ and $\mathtt{true}$ to $-1$, realising the…
  • BoolBLR.bool_distThe distance between two Boolean functions $f, g : \{0,1\}^n \to \{0,1\}$ is…
  • BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
Used by 1

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BoolFourier in
/-- Bounds every Fourier coefficient of a function far from all linear functions. **Source:** [OD14, §1.6 (Fourier soundness proof)]. -/
lemma BoolBLR.fourier_coeff_le_of_far_from_linear
    {n : ℕ}
    (f : hypercube n → Bool)
    (ε : ℝ)
    (hfar : epsilon_far_from_linear f ε) :
    ∀ S : Finset (Fin n),
      fourier_coeff (lift_pm1 f) S ≤ 1 - 2 * ε := by
  intro S
  -- Build a linear g whose ±1 lift equals χ_S, witnessing closeness to χ_S.
  obtain ⟨g, hg⟩ : ∃ g : hypercube n → Bool, is_linear_bool g ∧ (lift_pm1 g) = (char_S S) := by
    -- First, exhibit g as parity over coordinates in S.
    obtain ⟨g, hg⟩ : ∃ g : hypercube n → Bool, lift_pm1 g = char_S S := by
      use fun x => (S.filter (fun i => x i)).card % 2 = 1;
      funext x; simp only [lift_pm1, char_S];
      -- Induction on S to compare parity-of-count vs product of (-1)^{x_i}.
      induction S using Finset.induction with
      | empty => simp [BooleanAnalysis.chiS, BooleanAnalysis.boolToSign]
      | insert a s ha ih =>
        simp only [BooleanAnalysis.chiS] at ih ⊢
        rw [Finset.prod_insert ha, ← ih, Finset.filter_insert]
        by_cases hx : x a = true
        · rw [if_pos hx, Finset.card_insert_of_notMem (fun h => ha (Finset.mem_filter.mp h).1)]
          rcases Nat.mod_two_eq_zero_or_one (s.filter (fun i => x i = true)).card with h | h <;>
            simp [h, Nat.add_mod, hx, BooleanAnalysis.boolToSign]
        · simp [hx, BooleanAnalysis.boolToSign]
    -- Then use linear_bool_iff_character to conclude g is linear.
    exact ⟨ g, by exact linear_bool_iff_character g |>.2 ⟨ S, hg ⟩, hg ⟩;
  -- Apply the previous lemma using the ε-farness from this specific linear g.
  exact fourier_coeff_le_of_dist_ge f g S hg.2 ( hfar.2.2 g hg.1 )

-- if f is epsilon-far from all linear functions, then the sum of cubes term is ≤ 1 - 2 * ε
See it in the graphDiscuss this resultChallenge it