DecisionTree.sum_symmDiff_reindex
theoremverifiedimported Lean
Invariance 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 let $g$ assign a real number to each subset of $\{0, 1, \dots, n-1\}$. Then summing $g$ over all subsets is unaffected by first toggling the membership of $i$; that is, \[ \sum_{S} g\big(S \mathbin{\triangle} \{i\}\big) = \sum_{S} g(S), \] where both sums range over all subsets $S \subseteq \{0, 1, \dots, n-1\}$ and $S \mathbin{\triangle} \{i\}$ denotes the symmetric difference of $S$ with the singleton $\{i\}$.
Statement
variable {n : ℕ} in lemma DecisionTree.sum_symmDiff_reindex (g : Finset (Fin n) → ℝ) (i : Fin n) : ∑ S : Finset (Fin n), g (symmDiff S {i}) = ∑ S : Finset (Fin n), g S
- Source
- TCSlib, `DecisionTree.sum_symmDiff_reindex`
- 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.sum_symmDiff_reindex← DecisionTree.sum_symmDiff_reindex (TCSlib/BooleanAnalysis/LMN/DecisionTreeFourier.lean:69): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- DecisionTree.symmDiff_singleton_involSymmetric difference with a singleton is an involution. Fix $n \in \bbn$ and an index $i \in \{0, 1, \dots, n-1\}$. The map on subsets of…
- 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
variable {n : ℕ} in /-- Reindexing a sum over all frequencies by the involution `S ↦ S ∆ {i}`. -/ lemma DecisionTree.sum_symmDiff_reindex (g : Finset (Fin n) → ℝ) (i : Fin n) : ∑ S : Finset (Fin n), g (symmDiff S {i}) = ∑ S : Finset (Fin n), g S := Fintype.sum_bijective _ ((symmDiff_singleton_invol i).bijective) _ _ (fun _ => rfl)