AFTD Auto-Formalizing Theoretical Domains

BooleanAnalysis.dictator

defimported Lean

The dictator function for coordinate $i$ outputs the sign of the $i$-th bit: $\mathrm{dict}_i(x) = (-1)^{x_i}$. Its unique nonzero Fourier coefficient is $\widehat{\mathrm{dict}_i}(\{i\}) = 1$.

Statement

set_option maxHeartbeats 400000 in
open scoped BigOperators in
variable {n : ℕ} in
noncomputable def BooleanAnalysis.dictator (i : Fin n) : BooleanFunc n
Defined in
TCSlib, `BooleanAnalysis.dictator`
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
none listed
Built on 2
Used by 2
  • ArrowTheorem.isDictator$f$ is a dictatorship if there exists a voter $i$ such that $f = \mathrm{dict}_i$, i.e.\ society's preference always equals voter…
  • BooleanAnalysis.dictator_eq_chiDictator function as a singleton character. For each coordinate $i \in [n]$, the dictator function on the Boolean hypercube $\{0,1\}^n$…

Lean source view module on GitHub

set_option maxHeartbeats 400000 in
open scoped BigOperators in
variable {n : ℕ} in
/-- The **dictator function** for coordinate `i`: `f(x) = (-1)^{x_i}`. Its only nonzero Fourier coefficient is `f̂({i}) = 1`. -/
noncomputable def BooleanAnalysis.dictator (i : Fin n) : BooleanFunc n :=
  fun x ↦ boolToSign (x i)
See it in the graphDiscuss this resultChallenge it