AFTD Auto-Formalizing Theoretical Domains

DecisionTree.coeffs_eq_zero_of_depth_lt

theoremverifiedimported Lean

Fourier coefficients vanish above the tree depth. Let $T$ be a decision tree on $n$ Boolean variables, and let $S \subseteq \{0,1,\dots,n-1\}$ be a set of variables whose cardinality $\abs{S}$ exceeds the depth of $T$. Then the coefficient assigned to the frequency $S$ vanishes, $\mathrm{coeffs}\,T\,S = 0$.

Statement

open BooleanAnalysis in
variable {n : ℕ} in
lemma DecisionTree.coeffs_eq_zero_of_depth_lt (T : DecisionTree n) (S : Finset (Fin n))
    (h : T.depth < S.card) : T.coeffs S = 0
Source
TCSlib, `DecisionTree.coeffs_eq_zero_of_depth_lt`
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 4
  • DecisionTree.card_symmDiff_singletonCardinality under singleton symmetric difference. Let $S$ be a finite subset of $\{0,1,\dots,n-1\}$ and let $i$ be one of these indices.…
  • DecisionTree.depthThe depth of a decision tree (maximum path length to a leaf): a leaf has depth $0$ and a branch has depth $1$ plus the maximum of its two…
  • DecisionTree.coeffsThe coefficient function $\mathrm{coeffs}\,T : \mathcal{P}(\mathrm{Fin}\,n) \to \bbr$ defined by structural recursion on $T$. A leaf…
  • DecisionTreeA decision tree on $n$ Boolean variables: a leaf $\mathtt{leaf}\,b$ outputs $b$, and a branch $\mathtt{branch}\,i\,lo\,hi$ queries…
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

open BooleanAnalysis invariable {n : ℕ} in/-- Frequencies above the depth carry no Fourier weight. -/lemma DecisionTree.coeffs_eq_zero_of_depth_lt (T : DecisionTree n) (S : Finset (Fin n))    (h : T.depth < S.card) : T.coeffs S = 0 := by  induction T generalizing S with  | leaf b =>      have hS : S ≠ ∅ := by        intro hS        rw [hS] at h        simp [DecisionTree.depth] at h      simp [coeffs, hS]  | branch i lo hi ih_lo ih_hi =>      simp only [DecisionTree.depth] at h      have hSi := card_symmDiff_singleton S i      rw [coeffs, ih_lo _ (by omega), ih_hi _ (by omega),        ih_lo _ (by omega), ih_hi _ (by omega)]      ring
See it in the graphDiscuss this resultChallenge it