AFTD Auto-Formalizing Theoretical Domains

ArrowTheorem.acyclic_implies_corrFunc

theoremverifiedimported Lean

Acyclicity forces correlation $-1/3$. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function that is odd, $\pm 1$-valued, and acyclic. Then its Fourier correlation function satisfies \[ \mathrm{corr}(f)\;=\;\sum_{S\subseteq[n]}\hat f(S)^2\,(-1/3)^{|S|}\;=\;-\tfrac{1}{3}. \]

Statement

set_option maxHeartbeats 800000 in
open scoped BigOperators in
open BooleanAnalysis in
variable {n : ℕ} in
lemma ArrowTheorem.acyclic_implies_corrFunc (f : BooleanFunc n) (_hodd : isOddFunc f) (hpm : isPmOne f)
    (hacyc : acyclic f) : corrFunc f = -1/3
Source
TCSlib, `ArrowTheorem.acyclic_implies_corrFunc`
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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12
  • ArrowTheorem.acyclicA social welfare function $f$ is acyclic if no profile of transitive voter orderings produces a Condorcet cycle in society's…
  • ArrowTheorem.caVotesGiven a profile $p$, the vote vectors $\mathrm{abVotes}(p)$, $\mathrm{bcVotes}(p)$, $\mathrm{caVotes}(p) \in \{0,1\}^n$ record each…
  • ArrowTheorem.abVotesGiven a profile $p$, the vote vectors $\mathrm{abVotes}(p)$, $\mathrm{bcVotes}(p)$, $\mathrm{caVotes}(p) \in \{0,1\}^n$ record each…
  • ArrowTheorem.expected_product_abcaExpected product of the $ab$ and $ca$ votes. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function. For a profile $p$ that assigns each of the…
  • ArrowTheorem.bcVotesGiven a profile $p$, the vote vectors $\mathrm{abVotes}(p)$, $\mathrm{bcVotes}(p)$, $\mathrm{caVotes}(p) \in \{0,1\}^n$ record each…
  • ArrowTheorem.expected_product_eq_corrFuncExpected pairwise vote product equals the Fourier correlation function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function. Suppose each of…
  • 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.
  • ArrowTheorem.ProfileA profile assigns each of the $n$ voters one of the 6 orderings: $p : \mathrm{Fin}\,n \to \mathrm{Fin}\,6$.
  • BooleanAnalysis.isPmOne$f$ is $\pm 1$-valued if $f(x)\in\{-1,1\}$ for all $x$.
  • ArrowTheorem.expected_product_bccaExpected product of the $bc$ and $ca$ vote vectors. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function, and for each profile…
  • BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
  • ArrowTheorem.corrFuncThe Fourier correlation function of $f$ is \[ \mathrm{corr}(f) \;=\; \sum_{S\subseteq[n]} \hat f(S)^2\,(-1/3)^{|S|}. \] For odd…
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

set_option maxHeartbeats 800000 inopen scoped BigOperators inopen BooleanAnalysis invariable {n : ℕ} in/-- Acyclicity of f implies that the Fourier correlation function equals -1/3. Key steps: 1. For any ±1 triple (a,b,c) avoiding (1,1,1) and (-1,-1,-1), ab+bc+ac = -1. 2. Summing over all 6^n profiles: ∑_p (f(ab)f(bc)+f(bc)f(ca)+f(ab)f(ca)) = -6^n. 3. The three pairwise expectations each equal corrFunc f. 4. Combining: 3·corrFunc f = -1, so corrFunc f = -1/3. **Source:** [OD14, Ch. 2]. -/lemma ArrowTheorem.acyclic_implies_corrFunc (f : BooleanFunc n) (_hodd : isOddFunc f) (hpm : isPmOne f)    (hacyc : acyclic f) : corrFunc f = -1/3 := by  -- Step 1: per-profile, the three products sum to -1  have hprod : ∀ p : Profile n,      f (abVotes p) * f (bcVotes p) +      f (bcVotes p) * f (caVotes p) +      f (abVotes p) * f (caVotes p) = -1 := by    intro p    obtain ⟨hcyc1, hcyc2⟩ := hacyc p    rcases hpm (abVotes p) with ha | ha <;>    rcases hpm (bcVotes p) with hb | hb <;>    rcases hpm (caVotes p) with hc | hc    · exact absurd ⟨ha, hb, hc⟩ hcyc1    · rw [ha, hb, hc]; norm_num    · rw [ha, hb, hc]; norm_num    · rw [ha, hb, hc]; norm_num    · rw [ha, hb, hc]; norm_num    · rw [ha, hb, hc]; norm_num    · rw [ha, hb, hc]; norm_num    · exact absurd ⟨ha, hb, hc⟩ hcyc2  -- Step 2: (1/6)^n * ∑_p (sum of products) = 3 * corrFunc f  have hkey : (1/6 : ℝ)^n * ∑ p : Profile n,      (f (abVotes p) * f (bcVotes p) +       f (bcVotes p) * f (caVotes p) +       f (abVotes p) * f (caVotes p)) = 3 * corrFunc f := by    simp_rw [Finset.sum_add_distrib]    rw [mul_add, mul_add,        expected_product_eq_corrFunc f,        expected_product_bcca f,        expected_product_abca f]    ring  -- Step 3: (1/6)^n * ∑_p (sum of products) = -1 (from hprod)  have hval : (1/6 : ℝ)^n * ∑ p : Profile n,      (f (abVotes p) * f (bcVotes p) +       f (bcVotes p) * f (caVotes p) +       f (abVotes p) * f (caVotes p)) = -1 := by    simp_rw [hprod]    have hn : Fintype.card (Profile n) = 6^n := by      simp [Fintype.card_pi, Fintype.card_fin, Finset.prod_const, Finset.card_univ]    rw [Finset.sum_const, Finset.card_univ, hn, nsmul_eq_mul]    push_cast    have h : (1 / 6 : ℝ) ^ n * (6 : ℝ) ^ n = 1 := by rw [← mul_pow]; norm_num    linarith [mul_neg ((1 / 6 : ℝ) ^ n) ((6 : ℝ) ^ n)]  -- Combine  linarith
See it in the graphDiscuss this resultChallenge it