AFTD Auto-Formalizing Theoretical Domains

fourier_cross_level

def

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
Used by 4

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
See it in the graphDiscuss this resultChallenge it