DecisionTree.coeffs
defimported Lean
The coefficient function $\mathrm{coeffs}\,T : \mathcal{P}(\mathrm{Fin}\,n) \to \bbr$ defined by structural recursion on $T$. A leaf labelled $b$ assigns $\mathrm{boolToSign}(b)$ to the empty frequency and $0$ to all others; a branch on variable $i$ with subtrees $\mathrm{lo}, \mathrm{hi}$ assigns to $S$ the value \[ \frac{\mathrm{coeffs}\,\mathrm{lo}\,S + \mathrm{coeffs}\,\mathrm{hi}\,S}{2} + \frac{\mathrm{coeffs}\,\mathrm{lo}\,(S \triangle \{i\}) - \mathrm{coeffs}\,\mathrm{hi}\,(S \triangle \{i\})}{2}. \]
Statement
open BooleanAnalysis in variable {n : ℕ} in noncomputable def DecisionTree.coeffs : DecisionTree n → Finset (Fin n) → ℝ
- Defined in
- TCSlib, `DecisionTree.coeffs`
- 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← DecisionTree.coeffs (TCSlib/BooleanAnalysis/LMN/DecisionTreeFourier.lean:56): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- BooleanAnalysis.boolToSignThe sign encoding maps $\mathrm{Bool}$ to $\{-1,1\}\subset\bbr$:…
- 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 3
- DecisionTree.coeffs_eq_zero_of_depth_ltFourier coefficients vanish above the tree depth. Let $T$ be a decision tree on $n$ Boolean variables, and let…
- DecisionTree.fourierCoeff_signEvalFourier coefficients of a decision tree. Let $T$ be a decision tree on $n$ Boolean variables, and let $\sigma\!\circ\! T$ denote its…
- 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…
Lean source view module on GitHub
open BooleanAnalysis in variable {n : ℕ} in /-- The Fourier coefficients of `signEval`, computed by structural recursion. A branch on variable `i` satisfies `f = (f_lo + f_hi)/2 + χ_i (f_lo − f_hi)/2`, and multiplication by `χ_i` shifts frequency `S` to `S ∆ {i}`. -/ noncomputable def DecisionTree.coeffs : DecisionTree n → Finset (Fin n) → ℝ | .leaf b, S => if S = ∅ then boolToSign b else 0 | .branch i lo hi, S => (coeffs lo S + coeffs hi S) / 2 + (coeffs lo (symmDiff S {i}) - coeffs hi (symmDiff S {i})) / 2