AFTD Auto-Formalizing Theoretical Domains

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

Lean source view module on GitHub

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