BooleanAnalysis.chiS_neg
theoremverifiedimported Lean
Walsh character under global bit flip. Let $n$ be a natural number, let $S \subseteq [n]$, and let $x \in \{0,1\}^n$. Writing $\lnot x$ for the point obtained by flipping every coordinate of $x$, the Walsh--Fourier character $\chi_S$ satisfies \[ \chi_S(\lnot x) \;=\; (-1)^{\abs{S}}\,\chi_S(x), \] where $\abs{S}$ is the number of elements of $S$.
Statement
set_option maxHeartbeats 400000 in open scoped BigOperators in variable {n : ℕ} in lemma BooleanAnalysis.chiS_neg (S : Finset (Fin n)) (x : BoolCube n) : chiS S (fun i => !x i) = (-1 : ℝ) ^ S.card * chiS S x
- Source
- TCSlib, `BooleanAnalysis.chiS_neg`
- 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_neg← BooleanAnalysis.chiS_neg (TCSlib/BooleanAnalysis/Basic.lean:1023): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- BooleanAnalysis.boolToSign_notSign 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.fourierCoeff_odd_evenVanishing of even-level Fourier coefficients of odd functions. Let $f : \{0,1\}^n \to \bbr$ be an odd Boolean function, meaning…
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/-- Flipping all bits of `x` multiplies `χ_S(x)` by `(-1)^|S|`. -/lemma BooleanAnalysis.chiS_neg (S : Finset (Fin n)) (x : BoolCube n) : chiS S (fun i => !x i) = (-1 : ℝ) ^ S.card * chiS S x := by simp only [chiS] simp_rw [boolToSign_not] -- ∏_{i∈S} (-boolToSign (x i)) = (-1)^|S| * ∏_{i∈S} boolToSign (x i) induction S using Finset.induction with | empty => simp | insert a s ha ih => rw [Finset.prod_insert ha, Finset.card_insert_of_notMem ha, Finset.prod_insert ha, ih] ring