DecisionTree.fourierCoeff_signEval
theoremverifiedimported Lean
Fourier coefficients of a decision tree. Let $T$ be a decision tree on $n$ Boolean variables, and let $\sigma\!\circ\! T$ denote its sign-encoded function $x \mapsto \sigma(T(x))$ on the Boolean hypercube $\{0,1\}^n$. Then for every frequency set $S \subseteq [n]$, the Fourier–Walsh coefficient of this function at $S$ agrees with the recursively defined tree coefficient: \[ \widehat{\sigma\!\circ\! T}(S) \;=\; \mathrm{coeffs}(T)(S). \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open BooleanAnalysis in variable {n : ℕ} in theorem DecisionTree.fourierCoeff_signEval (T : DecisionTree n) (S : Finset (Fin n)) : fourierCoeff T.signEval S = T.coeffs S
- Source
- TCSlib, `DecisionTree.fourierCoeff_signEval`
- Lean proof
- By Hydroxyi, Owen McGinty, Seyoon Ragavan (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.DecisionTree.fourierCoeff_signEval← DecisionTree.fourierCoeff_signEval (TCSlib/BooleanAnalysis/LMN/DecisionTreeFourier.lean:298): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- DecisionTree.signEval_eq_sum_coeffsWalsh expansion of a decision tree's sign function. Let $T$ be a decision tree on $n$ Boolean variables, computing the $\pm 1$-valued…
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- DecisionTree.coeffsThe coefficient function $\mathrm{coeffs}\,T : \mathcal{P}(\mathrm{Fin}\,n) \to \bbr$ defined by structural recursion on $T$. A leaf…
- BooleanAnalysis.innerProduct_chi_selfWalsh characters have unit norm. Let $n$ be a natural number and let $S \subseteq [n]$. Under the uniform measure on the Boolean hypercube…
- DecisionTree.signEvalThe $\pm 1$-valued function computed by a decision tree $T$, namely $x \mapsto \mathrm{boolToSign}(T.\mathrm{eval}\,x)$, where…
- DecisionTreeA decision tree on $n$ Boolean variables: a leaf $\mathtt{leaf}\,b$ outputs $b$, and a branch $\mathtt{branch}\,i\,lo\,hi$ queries…
- BooleanAnalysis.chiSThe Walsh--Fourier character associated to $S\subseteq[n]$ is…
- DecisionTree.fourierCoeff_sum_chiSRecovery of coefficients from a character expansion. Fix $n$, let $c$ assign a real number $c(S)$ to each subset $S \subseteq [n]$, and…
- Used by 1
- DecisionTree.degree_le_depthFourier degree of a decision tree is at most its depth. Let $T$ be a decision tree on $n$ Boolean variables, and let…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen BooleanAnalysis invariable {n : ℕ} in/-- The Fourier coefficients of the tree function are exactly `T.coeffs`. -/theorem DecisionTree.fourierCoeff_signEval (T : DecisionTree n) (S : Finset (Fin n)) : fourierCoeff T.signEval S = T.coeffs S := by have hrepr : T.signEval = fun x => ∑ S : Finset (Fin n), T.coeffs S * chiS S x := funext fun x => signEval_eq_sum_coeffs T x rw [hrepr, fourierCoeff_sum_chiS]