AFTD Auto-Formalizing Theoretical Domains

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.
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

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