AFTD Auto-Formalizing Theoretical Domains

BoolBLR.BLR_soundness_via_fourier_aux_h_bound

theoremverifiedimported Lean

Per-coefficient cube 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 distance $\Pr_{x}[f(x) \ne g(x)] \ge \varepsilon$ from $f$. Write $\hat F(S) = \E[F \cdot \chi_S]$ for the Fourier coefficient of $F = (-1)^{f}$, the $\pm 1$ lift of $f$, at a subset $S \subseteq [n]$. Then for every such $S$, \[ \hat F(S)^3 \;\le\; \hat F(S)^2\,(1 - 2\varepsilon). \]

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BoolFourier in
lemma BoolBLR.BLR_soundness_via_fourier_aux_h_bound {n : ℕ} (f : BoolFourier.hypercube n → Bool) (ε : ℝ) (hfar : epsilon_far_from_linear f ε) :
    ∀ (S : Finset (Fin n)),
  BoolFourier.fourier_coeff (lift_pm1 f) S ^ 3 ≤ BoolFourier.fourier_coeff (lift_pm1 f) S ^ 2 * (1 - 2 * ε)
Source
TCSlib, `BoolBLR.BLR_soundness_via_fourier_aux_h_bound`
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
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 16
Used by 1

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BoolFourier in
lemma BoolBLR.BLR_soundness_via_fourier_aux_h_bound {n : ℕ} (f : BoolFourier.hypercube n → Bool) (ε : ℝ) (hfar : epsilon_far_from_linear f ε) :
    ∀ (S : Finset (Fin n)),
  BoolFourier.fourier_coeff (lift_pm1 f) S ^ 3 ≤ BoolFourier.fourier_coeff (lift_pm1 f) S ^ 2 * (1 - 2 * ε) :=
  by
  exact fun S => by nlinarith only [ show fourier_coeff ( lift_pm1 f ) S ≤ 1 - 2 * ε by exact fourier_coeff_le_of_far_from_linear f ε hfar S ] ;
See it in the graphDiscuss this resultChallenge it