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.DecisionTree.coeffs_eq_zero_of_depth_lt← DecisionTree.coeffs_eq_zero_of_depth_lt (TCSlib/BooleanAnalysis/LMN/DecisionTreeFourier.lean:147): verbatim
- 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
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.
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