AFTD Auto-Formalizing Theoretical Domains

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

Lean source view module on GitHub

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