AFTD Auto-Formalizing Theoretical Domains

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

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