Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Normalized biased Walsh characters, Fourier components, and coordinate residuals

Definition
NarrowDNF_Fourier

by chenghua.liu · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsnarrow-dnf-authors-importprobabilitystoc-2027

For 0<p<10<p<10<p<1, the normalized centered Bernoulli bit is ψp(b)=(b−p)/p(1−p)\psi_p(b)=(b-p)/\sqrt{p(1-p)}ψp​(b)=(b−p)/p(1−p)​, with Boolean values read as 000 and 111. A support mask s:I→{0,1}s:I\to\{0,1\}s:I→{0,1} selects the tensor character

χp,s(x)=∏i:si=1ψp(xi).\chi_{p,s}(x)=\prod_{i:s_i=1}\psi_p(x_i).χp,s​(x)=i:si​=1∏​ψp​(xi​).

For f:{0,1}I→Rf:\{0,1\}^I\to\mathbb Rf:{0,1}I→R on a finite cube, define f^p(s)=Eμp[f(x)χp,s(x)]\widehat f_p(s)=\mathbb E_{\mu_p}[f(x)\chi_{p,s}(x)]f​p​(s)=Eμp​​[f(x)χp,s​(x)] and deg⁡(s)=∣{i:si=1}∣\deg(s)=|\{i:s_i=1\}|deg(s)=∣{i:si​=1}∣. An explicit mask-to-subset equivalence provides the same coefficients and characters indexed by finite coordinate subsets SSS. The component fS(x)f_S(x)fS​(x) is f^p(S)χp,S(x)\widehat f_p(S)\chi_{p,S}(x)f​p​(S)χp,S​(x).

Conditional coordinate averaging is Mif(x)=(1−p)f(xi←0)+pf(xi←1)M_i f(x)=(1-p)f(x^{i\leftarrow0})+p f(x^{i\leftarrow1})Mi​f(x)=(1−p)f(xi←0)+pf(xi←1), and the residual is f−Miff-M_i ff−Mi​f. These are finite-sum definitions underlying the biased Fourier expansion and resampling-influence identities. Orthogonality and expansion properties use their stated bias hypotheses in separate theorem nodes.

Definition code
import Mathlib.Algebra.BigOperators.GroupWithZero.Finset
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Algebra.Order.BigOperators.Ring.Finset
import Mathlib.Analysis.SpecialFunctions.Sqrt
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Real.Basic
import Mathlib.Logic.Equiv.Prod
import Mathlib.Tactic.FieldSimp
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.Ring
import Definitions.Def_NarrowDNF_ProductMeasure

namespace NarrowDNF.Fourier
end NarrowDNF.Fourier


/-!
# Finite biased Fourier expansion

A basis index is a Boolean support mask. Its true coordinates are exactly the
usual subset index. All expectations use Bernoulli product weights, and the
normalization of influence is independent resampling rather than bit flipping.
-/

noncomputable section
open scoped BigOperators

namespace NarrowDNF.Fourier

/-- Centered normalized Bernoulli bit. -/
def standardBit (p : ℝ) (b : Bool) : ℝ :=
  (if b then 1-p else -p) / Real.sqrt (p * (1-p))

/-- The two one-coordinate orthonormal functions: constant and centered bit. -/
def bitBasis (p : ℝ) (s b : Bool) : ℝ := if s then standardBit p b else 1







section Cube
variable {ι : Type*} [Fintype ι] [DecidableEq ι]

/-- Tensor basis indexed by the coordinates selected by a Boolean support mask. -/
def character (p : ℝ) (s x : ι → Bool) : ℝ := ∏ i, bitBasis p (s i) (x i)

/-- Fourier coefficient in the real biased orthonormal basis. -/
def coefficient (p : ℝ) (f : (ι → Bool) → ℝ) (s : ι → Bool) : ℝ :=
  ProductMeasure.expectation p (fun x => f x * character p s x)

/-- Spectral degree, equivalently the cardinality of the support subset. -/
def degree (s : ι → Bool) : ℕ := (Finset.univ.filter fun i => s i = true).card













/-- Conditional averaging in one input coordinate. -/
def coordinateMean (p : ℝ) (f : (ι → Bool) → ℝ) (i : ι) (x : ι → Bool) : ℝ :=
  (1-p) * f (Function.update x i false) + p * f (Function.update x i true)

/-- The component removed by conditional averaging in a coordinate. -/
def coordinateResidual (p : ℝ) (f : (ι → Bool) → ℝ) (i : ι) (x : ι → Bool) : ℝ :=
  f x - coordinateMean p f i x
























/-- Explicit equivalence between support masks and the paper's subset indices. -/
def maskEquivFinset : (ι → Bool) ≃ Finset ι where
  toFun s := Finset.univ.filter fun i => s i = true
  invFun S i := decide (i ∈ S)
  left_inv s := by
    funext i
    simp
  right_inv S := by
    ext i
    simp

/-- The same Fourier coefficient indexed by a finite subset. -/
def setCoefficient (p : ℝ) (f : (ι → Bool) → ℝ) (S : Finset ι) : ℝ :=
  coefficient p f (maskEquivFinset.symm S)

/-- The same basis function indexed by a finite subset. -/
def setCharacter (p : ℝ) (S : Finset ι) (x : ι → Bool) : ℝ :=
  character p (maskEquivFinset.symm S) x






































/-- Generalized Walsh component in the subset-indexed Fourier decomposition. -/
def component (p : ℝ) (f : (ι → Bool) → ℝ) (S : Finset ι) (x : ι → Bool) : ℝ :=
  setCoefficient p f S * setCharacter p S x















end Cube
end NarrowDNF.Fourier






Source
https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L261-L270 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L272-L274 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L276-L278 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L54-L55 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L503-L505 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L57-L59 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L61-L62 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L20-L22 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L152-L154 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L156-L158 https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/Fourier.lean#L24-L25

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me