BooleanAnalysis.sum_chiS
theoremverifiedimported Lean
Sum of a Walsh character over the cube. Let $n$ be a natural number and let $S \subseteq [n]$. Summing the Walsh--Fourier character $\chi_S$ over the entire Boolean hypercube $\{0,1\}^n$ gives \[ \sum_{x \in \{0,1\}^n} \chi_S(x) \;=\; \begin{cases} 2^n & \text{if } S = \varnothing,\\ 0 & \text{if } S \ne \varnothing. \end{cases} \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in set_option maxHeartbeats 400000 in open scoped BigOperators in variable {n : ℕ} in lemma BooleanAnalysis.sum_chiS (S : Finset (Fin n)) : ∑ x : BoolCube n, chiS S x = if S = ∅ then 2 ^ n else 0
- Source
- TCSlib, `BooleanAnalysis.sum_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.sum_chiS← BooleanAnalysis.sum_chiS (TCSlib/BooleanAnalysis/Basic.lean:335): adapted
What was changed in
BooleanAnalysis.sum_chiS--- TCSlib/BooleanAnalysis/Basic.lean:335 (BooleanAnalysis.sum_chiS) +++ as compiled here @@ -1,3 +1,7 @@ -/-- Summing `χ_S` over the entire hypercube gives `2ⁿ` if `S = ∅`, else `0`. -/ -private lemma sum_chiS (S : Finset (Fin n)) : +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +set_option maxHeartbeats 400000 in +open scoped BigOperators in +variable {n : ℕ} in +lemma BooleanAnalysis.sum_chiS (S : Finset (Fin n)) : ∑ x : BoolCube n, chiS S x = if S = ∅ then 2 ^ n else 0 := by @@ -19,2 +23,2 @@ apply Finset.prod_eq_zero (Finset.mem_univ i) - simp [hi] + simp [hi, boolToSign] - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- BooleanAnalysis.sum_boolToSignSign encoding sums to zero over the Booleans. Let $\sigma\colon\mathrm{Bool}\to\{-1,1\}$ be the sign encoding, sending the value *false*…
- 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.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.boolToSign_trueSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- BooleanAnalysis.boolToSign_falseSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- BooleanAnalysis.boolToSign_sqSign encoding of false. Under the sign encoding $\sigma\colon\mathrm{Bool}\to\{-1,1\}$, the Boolean value $\mathrm{false}$ is sent to $1$;…
- BooleanAnalysis.chiSThe Walsh--Fourier character associated to $S\subseteq[n]$ is…
- Used by 1
- 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 autoImplicit true inset_option relaxedAutoImplicit true inset_option maxHeartbeats 400000 inopen scoped BigOperators invariable {n : ℕ} in/-- Summing `χ_S` over the entire hypercube gives `2ⁿ` if `S = ∅`, else `0`. -/lemma BooleanAnalysis.sum_chiS (S : Finset (Fin n)) : ∑ x : BoolCube n, chiS S x = if S = ∅ then 2 ^ n else 0 := by simp only [chiS] by_cases hS : S = ∅ · subst hS; simp [Fintype.card_pi, Fintype.card_bool] · simp only [hS, if_false] have factored : ∑ x : BoolCube n, ∏ i ∈ S, boolToSign (x i) = ∑ x : BoolCube n, ∏ i : Fin n, (if i ∈ S then boolToSign (x i) else 1) := by congr 1; ext x; rw [← Finset.prod_filter]; simp rw [factored] -- Goal: ∑ x : BoolCube n, ∏ i : Fin n, g i (x i) = 0 -- where g i b = if i ∈ S then boolToSign b else 1 -- Factor: = ∏ i : Fin n, ∑ b : Bool, g i b (by Fintype.prod_sum reversed) rw [show ∑ x : BoolCube n, ∏ i : Fin n, (if i ∈ S then boolToSign (x i) else 1) = ∏ i : Fin n, ∑ b : Bool, (if i ∈ S then boolToSign b else 1) from (Fintype.prod_sum (fun i b => if i ∈ S then boolToSign b else 1)).symm] obtain ⟨i, hi⟩ := Finset.nonempty_iff_ne_empty.mpr hS apply Finset.prod_eq_zero (Finset.mem_univ i) simp [hi, boolToSign]