fourier_cross_level
The $k$-th cross Fourier level $W_k[f,g]$ of two real-valued functions $f, g : \{0,1\}^n \to \mathbb{R}$ is the sum $\sum_{|S|=k} \hat{f}(S)\hat{g}(S)$ over all subsets $S \subseteq [n]$ of cardinality $k$, where $\hat{f}(S)$ and $\hat{g}(S)$ are the Fourier--Walsh coefficients.
Statement
noncomputable def fourier_cross_level {n : ℕ} (k : ℕ) (f g : BooleanAnalysis.BooleanFunc n) : ℝ
- Defined in
- arXiv:2611.08289 Section 2.1 (equation (13), line 358)
- 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 4
- 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…
- fourier_cross_level_eq_zero_of_card_ltFor any two functions $f, g : \{0,1\}^n \to \mathbb{R}$ and any integer $k > n$, the $k$-th cross Fourier level $W_k[f,g]$ equals zero.
Read back from the Lean
fourier_cross_level is a definition taking an implicit natural number n, an explicit natural number k, and two Boolean functions f and g on n variables (BooleanAnalysis.BooleanFunc n), and returning the real number defined as the sum over all subsets S of Fin n of cardinality k (Finset.powersetCard k Finset.univ) of the product of their Fourier coefficients at S: BooleanAnalysis.fourierCoeff f S * BooleanAnalysis.fourierCoeff g S.
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 k-th cross Fourier level W_k[f,g] = ∑_{|S|=k} f̂(S)ĝ(S) of two Boolean functions. -/ noncomputable def fourier_cross_level {n : ℕ} (k : ℕ) (f g : BooleanAnalysis.BooleanFunc n) : ℝ := ∑ S ∈ Finset.powersetCard k (Finset.univ : Finset (Fin n)), BooleanAnalysis.fourierCoeff f S * BooleanAnalysis.fourierCoeff g S