DecisionTree.signEval_eq_sum_coeffs
theoremverifiedimported Lean
Walsh expansion of a decision tree's sign function. Let $T$ be a decision tree on $n$ Boolean variables, computing the $\pm 1$-valued sign-encoded function $x \mapsto \sigma(T(x))$, where $\sigma$ is the sign encoding sending $\mathrm{false}$ to $1$ and $\mathrm{true}$ to $-1$. For every point $x \in \{0,1\}^n$, \[ \sigma(T(x)) \;=\; \sum_{S \subseteq [n]} c_T(S)\,\chi_S(x), \] where the sum ranges over all subsets $S$ of $[n]$, $c_T(S)$ denotes the recursively defined coefficient of $T$ at the frequency $S$, and $\chi_S$ is the Walsh character of $S$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open BooleanAnalysis in variable {n : ℕ} in lemma DecisionTree.signEval_eq_sum_coeffs (T : DecisionTree n) (x : BoolCube n) : T.signEval x = ∑ S : Finset (Fin n), T.coeffs S * chiS S x
- Source
- TCSlib, `DecisionTree.signEval_eq_sum_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.signEval_eq_sum_coeffs← DecisionTree.signEval_eq_sum_coeffs (TCSlib/BooleanAnalysis/LMN/DecisionTreeFourier.lean:95): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- DecisionTree.chiS_symmDiff_singletonSymmetric difference by a singleton toggles a Walsh character. Let $S\subseteq[n]$, let $i\in[n]$, and let $x\in\{0,1\}^n$. Then the…
- BooleanAnalysis.boolToSignThe sign encoding maps $\mathrm{Bool}$ to $\{-1,1\}\subset\bbr$:…
- BooleanAnalysis.chiS_emptyEmpty-set Walsh character. The Walsh–Fourier character associated to the empty subset of $[n]$ is the constant function equal to $1$; that…
- DecisionTree.sum_symmDiff_reindexInvariance of a subset-sum under symmetric difference with a point. Fix $n \in \bbn$, let $i$ be an element of $\{0, 1, \dots, n-1\}$, and…
- DecisionTree.coeffsThe coefficient function $\mathrm{coeffs}\,T : \mathcal{P}(\mathrm{Fin}\,n) \to \bbr$ defined by structural recursion on $T$. A leaf…
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- 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.evalEvaluates a decision tree on an input $x$: a leaf returns its stored bit, and a branch on variable $i$ follows the high subtree when $x_i$…
- Used by 1
- 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…
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/-- `signEval T = ∑_S coeffs T S · χ_S` pointwise. -/lemma DecisionTree.signEval_eq_sum_coeffs (T : DecisionTree n) (x : BoolCube n) : T.signEval x = ∑ S : Finset (Fin n), T.coeffs S * chiS S x := by induction T with | leaf b => simp [signEval, DecisionTree.eval, coeffs, ite_mul, Finset.sum_ite_eq', chiS_empty] | branch i lo hi ih_lo ih_hi => have expand : ∑ S : Finset (Fin n), (DecisionTree.branch i lo hi).coeffs S * chiS S x = ((∑ S : Finset (Fin n), lo.coeffs S * chiS S x) + ∑ S : Finset (Fin n), hi.coeffs S * chiS S x) / 2 + ((∑ S : Finset (Fin n), lo.coeffs S * chiS S x) - ∑ S : Finset (Fin n), hi.coeffs S * chiS S x) / 2 * boolToSign (x i) := by have step1 : ∑ S : Finset (Fin n), (DecisionTree.branch i lo hi).coeffs S * chiS S x = (∑ S : Finset (Fin n), (lo.coeffs S + hi.coeffs S) / 2 * chiS S x) + ∑ S : Finset (Fin n), (lo.coeffs (symmDiff S {i}) - hi.coeffs (symmDiff S {i})) / 2 * chiS S x := by rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun S _ => ?_ simp only [coeffs]; ring have step2 : ∑ S : Finset (Fin n), (lo.coeffs (symmDiff S {i}) - hi.coeffs (symmDiff S {i})) / 2 * chiS S x = ∑ S : Finset (Fin n), (lo.coeffs S - hi.coeffs S) / 2 * chiS S x * boolToSign (x i) := by rw [← sum_symmDiff_reindex (fun S => (lo.coeffs S - hi.coeffs S) / 2 * chiS S x * boolToSign (x i)) i] refine Finset.sum_congr rfl fun S _ => ?_ rw [chiS_symmDiff_singleton] cases x i <;> simp [boolToSign] have hA : ∑ S : Finset (Fin n), (lo.coeffs S + hi.coeffs S) / 2 * chiS S x = ((∑ S : Finset (Fin n), lo.coeffs S * chiS S x) + ∑ S : Finset (Fin n), hi.coeffs S * chiS S x) / 2 := by have hterm : ∀ S : Finset (Fin n), (lo.coeffs S + hi.coeffs S) / 2 * chiS S x = (lo.coeffs S * chiS S x + hi.coeffs S * chiS S x) / 2 := fun S => by ring rw [Finset.sum_congr rfl fun S _ => hterm S, ← Finset.sum_div, Finset.sum_add_distrib] have hB : ∑ S : Finset (Fin n), (lo.coeffs S - hi.coeffs S) / 2 * chiS S x * boolToSign (x i) = ((∑ S : Finset (Fin n), lo.coeffs S * chiS S x) - ∑ S : Finset (Fin n), hi.coeffs S * chiS S x) / 2 * boolToSign (x i) := by rw [← Finset.sum_mul] congr 1 have hterm : ∀ S : Finset (Fin n), (lo.coeffs S - hi.coeffs S) / 2 * chiS S x = (lo.coeffs S * chiS S x - hi.coeffs S * chiS S x) / 2 := fun S => by ring rw [Finset.sum_congr rfl fun S _ => hterm S, ← Finset.sum_div, Finset.sum_sub_distrib] rw [step1, step2, hA, hB] rw [expand, ← ih_lo, ← ih_hi] simp only [signEval, DecisionTree.eval] cases hxi : x i <;> simp [boolToSign] <;> ring