ArrowTheorem.expected_product_eq_corrFunc
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.ArrowTheorem.expected_product_eq_corrFunc← ArrowTheorem.expected_product_eq_corrFunc (TCSlib/BooleanAnalysis/ArrowTheorem.lean:489): verbatim
- 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
- ArrowTheorem.acyclic_implies_corrFuncAcyclicity 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…
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