BooleanAnalysis.sum_chiS_mul_eq
theoremverifiedimported Lean
Completeness kernel for the Walsh basis. Let $x, y \in \{0,1\}^n$ be points of the Boolean hypercube. Then the sum of the products of Walsh--Fourier characters over all subsets of $[n]$ satisfies \[ \sum_{S \subseteq [n]} \chi_S(x)\,\chi_S(y) \;=\; \begin{cases} 2^n & \text{if } x = y,\\[2pt] 0 & \text{if } x \neq y. \end{cases} \]
Statement
set_option maxHeartbeats 400000 in open scoped BigOperators in variable {n : ℕ} in lemma BooleanAnalysis.sum_chiS_mul_eq (x y : BoolCube n) : ∑ S : Finset (Fin n), chiS S x * chiS S y = if x = y then (2 : ℝ) ^ n else 0
- Source
- TCSlib, `BooleanAnalysis.sum_chiS_mul_eq`
- 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.sum_chiS_mul_eq← BooleanAnalysis.sum_chiS_mul_eq (TCSlib/BooleanAnalysis/Basic.lean:262): 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.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.sum_prod_subset_eq_prod_one_addSum over subsets equals a product of one plus each term. For any real numbers $c_0,\dots,c_{n-1}$, indexed by $i \in \mathrm{Fin}\,n$,…
- BooleanAnalysis.chiSThe Walsh--Fourier character associated to $S\subseteq[n]$ is…
- Used by 1
- BooleanAnalysis.walsh_expansionWalsh–Fourier expansion of a Boolean function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of arity $n$. Then at every point…
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 sum of `χ_S(x) * χ_S(y)` over all `S ⊆ [n]` equals `2ⁿ` if `x = y`, else `0`. This is the completeness kernel for the Walsh basis. -/lemma BooleanAnalysis.sum_chiS_mul_eq (x y : BoolCube n) : ∑ S : Finset (Fin n), chiS S x * chiS S y = if x = y then (2 : ℝ) ^ n else 0 := by simp only [chiS, ← Finset.prod_mul_distrib] rw [sum_prod_subset_eq_prod_one_add] split_ifs with hxy · subst hxy; simp only [boolToSign_mul_self] simp only [Finset.prod_const, Finset.card_univ, Fintype.card_fin] norm_num · obtain ⟨i, hi⟩ := Function.ne_iff.mp hxy apply Finset.prod_eq_zero (Finset.mem_univ i) have : boolToSign (x i) * boolToSign (y i) = -1 := by cases hxi : x i <;> cases hyi : y i <;> simp_all [boolToSign] simp [this]