ArrowTheorem.degree_one_implies_dictator
theoremverifiedimported Lean
Degree-one unanimous voting rules are dictatorships. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function that is odd, is $\pm 1$-valued, and is unanimous. Suppose further that $f$ has degree one, in the sense that its Fourier--Walsh coefficient $\hat f(S)$ vanishes for every set $S\subseteq[n]$ with $\abs{S}\neq 1$. Then $f$ is a dictatorship: there is a coordinate $i$ with $f=\mathrm{dict}_i$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in set_option maxHeartbeats 800000 in open scoped BigOperators in open BooleanAnalysis in variable {n : ℕ} in lemma ArrowTheorem.degree_one_implies_dictator (f : BooleanFunc n) (_hodd : isOddFunc f) (hpm : isPmOne f) (huniv : unanimity f) (hdeg1 : ∀ S : Finset (Fin n), S.card ≠ 1 → fourierCoeff f S = 0) : isDictator f
- Source
- TCSlib, `ArrowTheorem.degree_one_implies_dictator`
- Lean proof
- By Mina, Allan Li, 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.ArrowTheorem.degree_one_implies_dictator← ArrowTheorem.degree_one_implies_dictator (TCSlib/BooleanAnalysis/ArrowTheorem.lean:572): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 21
- BooleanAnalysis.walsh_expansionWalsh–Fourier expansion of a Boolean function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of arity $n$. Then at every point…
- 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$:…
- 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.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- 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$…
- 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.isOddFuncA Boolean function $f$ is odd if $f(\lnot x) = -f(x)$ for all $x$. This models antisymmetry of pairwise preferences in social choice.
- BooleanAnalysis.innerProduct_chi_selfWalsh characters have unit norm. Let $n$ be a natural number and let $S \subseteq [n]$. Under the uniform measure on the Boolean hypercube…
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- BooleanAnalysis.parseval_pm_oneParseval's identity for $\pm 1$-valued functions. Let $f \colon \{0,1\}^n \to \bbr$ be a Boolean function that is $\pm 1$-valued, meaning…
- 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$;…
- ArrowTheorem.unanimityA social welfare function $f:\{0,1\}^n\to\bbr$ is unanimous if $f(\texttt{false},\dots,\texttt{false}) = 1$: when all voters prefer…
- BooleanAnalysis.isPmOne$f$ is $\pm 1$-valued if $f(x)\in\{-1,1\}$ for all $x$.
- 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.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…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- BooleanAnalysis.flipBit_flipBitBit-flip is an involution. For a point $x$ in the Boolean hypercube $\{0,1\}^n$ and a coordinate $i$, flipping the $i$-th coordinate of…
- Used by 1
- ArrowTheorem.arrow_theoremArrow's impossibility theorem. Let $n$ be a natural number and let $f:\{0,1\}^n\to\bbr$ be a social welfare function that aggregates the…
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 800000 inopen scoped BigOperators inopen BooleanAnalysis invariable {n : ℕ} in/-- A ±1-valued odd unanimous function with all Fourier weight on level 1 is a dictator. Proof: f = ∑_i a_i · χ_{i} with ∑_i a_i² = 1 (Parseval). - Unanimity: f(false,...,false) = ∑_i a_i = 1. - For each j: f(only-j-true) = 1 - 2·a_j ∈ {-1,1}, so a_j ∈ {0,1}. - From a_j ∈ {0,1} and ∑ a_j² = ∑ a_j = 1: exactly one a_{j₀} = 1. - Hence f = χ_{{j₀}} = dictator j₀. **Source:** [OD14, Ch. 2]. -/lemma ArrowTheorem.degree_one_implies_dictator (f : BooleanFunc n) (_hodd : isOddFunc f) (hpm : isPmOne f) (huniv : unanimity f) (hdeg1 : ∀ S : Finset (Fin n), S.card ≠ 1 → fourierCoeff f S = 0) : isDictator f := by -- Step 1: Parseval gives ∑_i f̂({i})² = 1 -- All non-singleton Fourier coefficients are 0 by hdeg1. have hpars : ∑ i : Fin n, fourierCoeff f {i} ^ 2 = 1 := by have hparseval := parseval_pm_one f hpm -- Reindex via Finset.sum_image: ∑_i f({i})² = ∑_{S ∈ image} f(S)² = ∑_S f(S)² have hexpand : ∑ i : Fin n, fourierCoeff f ({i} : Finset (Fin n)) ^ 2 = ∑ S : Finset (Fin n), fourierCoeff f S ^ 2 := by rw [← Finset.sum_image (f := fun S => fourierCoeff f S ^ 2) (fun i _ j _ h => Finset.singleton_injective h)] apply Finset.sum_subset (Finset.subset_univ _) intro S _ hS have hcard : S.card ≠ 1 := by intro hc obtain ⟨i, hi⟩ := Finset.card_eq_one.mp hc exact hS (Finset.mem_image.mpr ⟨i, Finset.mem_univ i, hi.symm⟩) simp [hdeg1 S hcard] rw [hexpand, hparseval] -- Step 2: Walsh expansion restricted to level 1 -- f(x) = ∑_i f̂({i}) · boolToSign(x i) have hfourier : ∀ x : BoolCube n, f x = ∑ i : Fin n, fourierCoeff f {i} * boolToSign (x i) := by intro x rw [walsh_expansion f x] -- Reduce full sum to singleton terms (non-singletons vanish) have step1 : ∑ S : Finset (Fin n), fourierCoeff f S * chiS S x = ∑ S ∈ (Finset.univ : Finset (Fin n)).image (fun i => ({i} : Finset (Fin n))), fourierCoeff f S * chiS S x := by symm apply Finset.sum_subset (Finset.subset_univ _) intro S _ hS have hcard : S.card ≠ 1 := by intro hc obtain ⟨i, hi⟩ := Finset.card_eq_one.mp hc exact hS (Finset.mem_image.mpr ⟨i, Finset.mem_univ i, hi.symm⟩) simp [hdeg1 S hcard] -- Reindex image sum over Fin n have step2 : ∑ S ∈ (Finset.univ : Finset (Fin n)).image (fun i => ({i} : Finset (Fin n))), fourierCoeff f S * chiS S x = ∑ i : Fin n, fourierCoeff f {i} * boolToSign (x i) := by rw [Finset.sum_image (fun i _ j _ h => Finset.singleton_injective h)] congr 1; ext i; rw [chiS_singleton] rw [step1, step2] -- Step 3: Unanimity gives ∑_i a_i = 1 have huniv' : ∑ i : Fin n, fourierCoeff f {i} = 1 := by have h := huniv rw [unanimity] at h rw [hfourier] at h simp only [boolToSign_false, mul_one] at h exact h -- Step 4: For each i, f(only-i-true) ∈ {-1,1} gives a_i ∈ {0,1} have hai_range : ∀ i : Fin n, fourierCoeff f {i} = 0 ∨ fourierCoeff f {i} = 1 := by intro i -- f at x with only bit i = true equals 1 - 2·a_i have hval : f (Function.update (fun _ => false) i true) = 1 - 2 * fourierCoeff f {i} := by rw [hfourier] have key : ∑ j : Fin n, fourierCoeff f {j} * boolToSign ((Function.update (fun _ => false) i true) j) = -(fourierCoeff f {i}) + ∑ j ∈ Finset.univ.erase i, fourierCoeff f {j} := by rw [← Finset.add_sum_erase Finset.univ (fun j => fourierCoeff f {j} * boolToSign ((Function.update (fun _ => false) i true) j)) (Finset.mem_univ i)] simp only [Function.update_apply, ↓reduceIte, boolToSign_true, mul_neg, mul_one] congr 1 apply Finset.sum_congr rfl intro j hj have hjni : j ≠ i := (Finset.mem_erase.mp hj).1 simp only [if_neg hjni, boolToSign_false, mul_one] rw [key] have herase := Finset.add_sum_erase Finset.univ (fun j => fourierCoeff f {j}) (Finset.mem_univ i) linarith [huniv'] have hpm_val := hpm (Function.update (fun _ => false) i true) rw [hval] at hpm_val rcases hpm_val with h | h · left; linarith · right; linarith -- Step 5: Exactly one a_{j₀} = 1, the rest are 0 -- Using |{i | a_i = 1}| = ∑_{i∈J} 1 = ∑_i a_i = 1 have hexists : ∃ j : Fin n, fourierCoeff f {j} = 1 ∧ ∀ i : Fin n, i ≠ j → fourierCoeff f {i} = 0 := by let J := Finset.univ.filter (fun i : Fin n => fourierCoeff f {i} = 1) have hJ_card : J.card = 1 := by have hcard_real : (J.card : ℝ) = 1 := by have h0 : ∀ i : Fin n, i ∉ J → fourierCoeff f {i} = 0 := by intro i hi simp only [J, Finset.mem_filter, Finset.mem_univ, true_and] at hi push_neg at hi rcases hai_range i with h | h · exact h · exact absurd h hi calc (J.card : ℝ) = ∑ i ∈ J, (1 : ℝ) := by simp _ = ∑ i ∈ J, fourierCoeff f {i} := by apply Finset.sum_congr rfl intro i hi exact ((Finset.mem_filter.mp hi).2).symm _ = ∑ i : Fin n, fourierCoeff f {i} := by apply Finset.sum_subset (Finset.filter_subset _ _) intro i _ hi exact h0 i hi _ = 1 := huniv' exact_mod_cast hcard_real obtain ⟨j, hj⟩ := Finset.card_eq_one.mp hJ_card have hj_mem : j ∈ J := by rw [hj]; exact Finset.mem_singleton_self j refine ⟨j, (Finset.mem_filter.mp hj_mem).2, fun i hi => ?_⟩ rcases hai_range i with h | h · exact h · exfalso have hi_mem : i ∈ J := Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩ rw [hj] at hi_mem exact hi (Finset.mem_singleton.mp hi_mem) obtain ⟨j₀, hj₀, hothers⟩ := hexists -- Step 6: f = χ_{{j₀}} = dictator j₀ use j₀ ext x rw [hfourier x, dictator_eq_chi, chiS_singleton] -- ∑_i a_i * boolToSign(x i) = boolToSign(x j₀) since a_{j₀}=1 and a_i=0 for i≠j₀ conv_lhs => rw [← Finset.add_sum_erase _ _ (Finset.mem_univ j₀)] simp only [hj₀, one_mul] suffices h : ∑ i ∈ Finset.univ.erase j₀, fourierCoeff f {i} * boolToSign (x i) = 0 by linarith apply Finset.sum_eq_zero intro i hi simp [hothers i (Finset.mem_erase.mp hi).1]