fourier_variance
def
The Fourier variance $\mathrm{Var}(f)$ of a function $f : \{0,1\}^n \to \mathbb{R}$ is the sum of the squares of its non-empty Fourier--Walsh coefficients: $\mathrm{Var}(f) = \sum_{S \subseteq [n], S \neq \emptyset} \hat{f}(S)^2$.
Statement
noncomputable def fourier_variance {n : ℕ} (f : BooleanAnalysis.BooleanFunc n) : ℝ
- Defined in
- arXiv:2611.08289 Section 2.1 (line 360)
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 2
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- Used by 3
- fourier_cross_level_one_le_sqrt_variance_mulCauchy-Schwarz inequality for the first cross Fourier level: for any two functions f, g : {0,1}^n → ℝ, W_1[f, g] ≤ sqrt(Var(f) * Var(g)).
- discrete_level_one_to_three_sharp_constant_of_lt_threeThe sharp level 1 to 3 inequality holds for all n < 3 (i.e. n = 1, 2) because W_3[f,g] = 0 and the left-hand side is nonpositive by…
- discrete_level_one_to_three_ratioThe discrete level 1 to 3 ratio for functions $f, g : \{0,1\}^n \to \mathbb{R}$ is defined as…
Read back from the Lean
Given a natural number $n$ and a Boolean function $f : \mathrm{BooleanAnalysis.BooleanFunc}\ n$, fourier_variance f is defined as the real number equal to the sum over all non-empty subsets $S \subseteq \mathrm{Fin}\ n$ of the squared Fourier coefficient $(\mathrm{BooleanAnalysis.fourierCoeff}\ f\ S)^2$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The Fourier variance Var(f) = ∑_{S ≠ ∅} f̂(S)^2 of a Boolean function. -/ noncomputable def fourier_variance {n : ℕ} (f : BooleanAnalysis.BooleanFunc n) : ℝ := ∑ S ∈ (Finset.univ : Finset (Finset (Fin n))).filter Finset.Nonempty, BooleanAnalysis.fourierCoeff f S ^ 2