DecisionTree.chiS_symmDiff_singleton
theoremverifiedimported Lean
Symmetric 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 Walsh--Fourier character indexed by the symmetric difference $S\mathbin{\triangle}\{i\}$ satisfies \[ \chi_{S\,\triangle\,\{i\}}(x) \;=\; \chi_S(x)\,\sigma(x_i), \] where $\sigma$ is the sign encoding $\sigma(x_i)=(-1)^{x_i}$.
Statement
open BooleanAnalysis in variable {n : ℕ} in lemma DecisionTree.chiS_symmDiff_singleton (S : Finset (Fin n)) (i : Fin n) (x : BoolCube n) : chiS (symmDiff S {i}) x = chiS S x * boolToSign (x i)
- Source
- TCSlib, `DecisionTree.chiS_symmDiff_singleton`
- 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.chiS_symmDiff_singleton← DecisionTree.chiS_symmDiff_singleton (TCSlib/BooleanAnalysis/LMN/DecisionTreeFourier.lean:73): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- BooleanAnalysis.boolToSignThe sign encoding maps $\mathrm{Bool}$ to $\{-1,1\}\subset\bbr$:…
- BooleanAnalysis.chiS_mul_chiSWalsh characters multiply by symmetric difference. Fix $n$, and for a subset $S\subseteq[n]$ let $\chi_S\colon\{0,1\}^n\to\bbr$ denote the…
- BooleanAnalysis.chiS_singletonValue of a singleton Walsh character. Fix a dimension $n$, a coordinate $i \in [n]$, and a point $x$ of the Boolean hypercube $\{0,1\}^n$.…
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- BooleanAnalysis.chiSThe Walsh--Fourier character associated to $S\subseteq[n]$ is…
- Used by 1
- 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
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 : ℕ} inlemma DecisionTree.chiS_symmDiff_singleton (S : Finset (Fin n)) (i : Fin n) (x : BoolCube n) : chiS (symmDiff S {i}) x = chiS S x * boolToSign (x i) := by rw [← chiS_mul_chiS, chiS_singleton]