AFTD Auto-Formalizing Theoretical Domains

ArrowTheorem.expected_product_eq_corrFunc

theoremverifiedimported Lean

Expected pairwise vote product equals the Fourier correlation function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function. Suppose each of the $n$ voters chooses, independently and uniformly, one of the six strict orderings of three candidates $a,b,c$; for such a profile $p$ write $x_p\in\{0,1\}^n$ for the vector whose $i$-th entry records voter $i$'s preference in the $a$-versus-$b$ comparison, and $y_p\in\{0,1\}^n$ for the vector recording each voter's preference in the $b$-versus-$c$ comparison. Then, averaging the product of the values of $f$ on these two vectors over all $6^n$ profiles, \[ \frac{1}{6^{\,n}}\sum_{p}\, f(x_p)\,f(y_p) \;=\; \sum_{S\subseteq[n]} \hat f(S)^2\,(-1/3)^{|S|}, \] where $\hat f(S)$ denotes the Fourier--Walsh coefficient of $f$ at frequency $S$.

Statement

set_option maxHeartbeats 800000 in
open scoped BigOperators in
open BooleanAnalysis in
variable {n : ℕ} in
lemma ArrowTheorem.expected_product_eq_corrFunc (f : BooleanFunc n) :
    (1/6 : ℝ)^n * ∑ p : Profile n, f (abVotes p) * f (bcVotes p) = corrFunc f
Source
TCSlib, `ArrowTheorem.expected_product_eq_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 7
  • ArrowTheorem.abVotesGiven a profile $p$, the vote vectors $\mathrm{abVotes}(p)$, $\mathrm{bcVotes}(p)$, $\mathrm{caVotes}(p) \in \{0,1\}^n$ record each…
  • ArrowTheorem.bcVotesGiven a profile $p$, the vote vectors $\mathrm{abVotes}(p)$, $\mathrm{bcVotes}(p)$, $\mathrm{caVotes}(p) \in \{0,1\}^n$ record each…
  • ArrowTheorem.ProfileA profile assigns each of the $n$ voters one of the 6 orderings: $p : \mathrm{Fin}\,n \to \mathrm{Fin}\,6$.
  • ArrowTheorem.expected_product_helperExpected product from the character kernel. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function, and let $\mathrm{votes}_1,\mathrm{votes}_2$…
  • BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
  • ArrowTheorem.profile_inner_product_kernelOrthogonality kernel for the $ab$–$bc$ vote pair. Fix $n$, and for each profile $p \in \{0,\dots,5\}^n$ let…
  • 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

Lean source view module on GitHub

set_option maxHeartbeats 800000 in
open scoped BigOperators in
open BooleanAnalysis in
variable {n : ℕ} in
/-- E[f(ab)·f(bc)] = corrFunc f. -/
lemma ArrowTheorem.expected_product_eq_corrFunc (f : BooleanFunc n) :
    (1/6 : ℝ)^n * ∑ p : Profile n, f (abVotes p) * f (bcVotes p) = corrFunc f :=
  expected_product_helper f abVotes bcVotes profile_inner_product_kernel
See it in the graphDiscuss this resultChallenge it