AFTD Auto-Formalizing Theoretical Domains

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.
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

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