BooleanAnalysis.chiS_mul_chiS
theoremverifiedimported Lean
Walsh 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 associated Walsh--Fourier character. Then for all subsets $S,T\subseteq[n]$ and every point $x\in\{0,1\}^n$, \[ \chi_S(x)\,\chi_T(x) \;=\; \chi_{S\,\triangle\,T}(x), \] where $S\,\triangle\,T$ is the symmetric difference of $S$ and $T$.
Statement
set_option maxHeartbeats 400000 in open scoped BigOperators in variable {n : ℕ} in lemma BooleanAnalysis.chiS_mul_chiS (S T : Finset (Fin n)) (x : BoolCube n) : (BooleanAnalysis.chiS S) x * (BooleanAnalysis.chiS T) x = (BooleanAnalysis.chiS (symmDiff S T)) x
- Source
- TCSlib, `BooleanAnalysis.chiS_mul_chiS`
- Lean proof
- By Jingzhen Sha, Allan Li, Hydroxyi, Mina, Owen McGinty (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.BooleanAnalysis.chiS_mul_chiS← BooleanAnalysis.chiS_mul_chiS (TCSlib/BooleanAnalysis/Basic.lean:198): adapted
What was changed in
BooleanAnalysis.chiS_mul_chiS--- TCSlib/BooleanAnalysis/Basic.lean:198 (BooleanAnalysis.chiS_mul_chiS) +++ as compiled here @@ -1,5 +1,6 @@ -/-- The pointwise product of two Walsh characters is another Walsh character (up to sign), - specifically `χ_S · χ_T = χ_{S Δ T}` where `Δ` denotes symmetric difference. -/ -lemma chiS_mul_chiS (S T : Finset (Fin n)) (x : BoolCube n) : - χ_[S] x * χ_[T] x = χ_[symmDiff S T] x := by +set_option maxHeartbeats 400000 in +open scoped BigOperators in +variable {n : ℕ} in +lemma BooleanAnalysis.chiS_mul_chiS (S T : Finset (Fin n)) (x : BoolCube n) : + (BooleanAnalysis.chiS S) x * (BooleanAnalysis.chiS T) x = (BooleanAnalysis.chiS (symmDiff S T)) x := by simp only [chiS] - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- BooleanAnalysis.boolToSignThe sign encoding maps $\mathrm{Bool}$ to $\{-1,1\}\subset\bbr$:…
- BooleanAnalysis.boolToSign_mul_selfSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- 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 2
- 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.fourier_coeff_chiOrthonormality of Walsh characters. For any two subsets $S, T \subseteq [n]$, the $L^2$ inner product of the Walsh--Fourier characters…
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.
set_option maxHeartbeats 400000 inopen scoped BigOperators invariable {n : ℕ} in/-- The pointwise product of two Walsh characters is another Walsh character (up to sign), specifically `χ_S · χ_T = χ_{S Δ T}` where `Δ` denotes symmetric difference. -/lemma BooleanAnalysis.chiS_mul_chiS (S T : Finset (Fin n)) (x : BoolCube n) : (BooleanAnalysis.chiS S) x * (BooleanAnalysis.chiS T) x = (BooleanAnalysis.chiS (symmDiff S T)) x := by simp only [chiS] -- Decompose: S = (S \ T) ∪ (S ∩ T), T = (T \ S) ∪ (T ∩ S) have hS : ∏ i ∈ S, boolToSign (x i) = (∏ i ∈ S \ T, boolToSign (x i)) * ∏ i ∈ S ∩ T, boolToSign (x i) := by conv_lhs => rw [← Finset.sdiff_union_inter S T] apply Finset.prod_union simp only [Finset.disjoint_left, Finset.mem_sdiff, Finset.mem_inter, not_and] tauto have hT : ∏ i ∈ T, boolToSign (x i) = (∏ i ∈ T \ S, boolToSign (x i)) * ∏ i ∈ S ∩ T, boolToSign (x i) := by conv_lhs => rw [← Finset.sdiff_union_inter T S] rw [Finset.inter_comm T S] apply Finset.prod_union simp only [Finset.disjoint_left, Finset.mem_sdiff, Finset.mem_inter, not_and] tauto -- The intersection product squares to 1 have hcancel : (∏ i ∈ S ∩ T, boolToSign (x i)) * ∏ i ∈ S ∩ T, boolToSign (x i) = 1 := by rw [← Finset.prod_mul_distrib]; simp [boolToSign_mul_self] rw [hS, hT, symmDiff_def, Finset.sup_eq_union, Finset.prod_union disjoint_sdiff_sdiff] -- Goal: (A * P) * (B * P) = A * B where P² = 1 set P := ∏ i ∈ S ∩ T, boolToSign (x i) set A := ∏ i ∈ S \ T, boolToSign (x i) set B := ∏ i ∈ T \ S, boolToSign (x i) calc A * P * (B * P) = A * B * (P * P) := by ring _ = A * B * 1 := by rw [hcancel] _ = A * B := by ring