AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
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

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