AFTD Auto-Formalizing Theoretical Domains

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

Lean source view module on GitHub

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