AFTD Auto-Formalizing Theoretical Domains

ArrowTheorem.expected_product_bcca

theoremverifiedimported Lean

Expected product of the $bc$ and $ca$ vote vectors. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function, and for each profile $p:\mathrm{Fin}\,n\to\{0,\dots,5\}$ write $x_{bc}(p),\,x_{ca}(p)\in\{0,1\}^n$ for the $b$-vs-$c$ and $c$-vs-$a$ vote vectors it induces. Then the average of the product $f\bigl(x_{bc}(p)\bigr)\,f\bigl(x_{ca}(p)\bigr)$ over all $6^n$ profiles equals the Fourier correlation function of $f$: \[ \Bigl(\tfrac16\Bigr)^{n}\sum_{p} f\bigl(x_{bc}(p)\bigr)\,f\bigl(x_{ca}(p)\bigr) \;=\; \mathrm{corr}(f) \;=\; \sum_{S\subseteq[n]} \hat f(S)^2\,(-1/3)^{|S|}. \]

Statement

set_option maxHeartbeats 800000 in
open scoped BigOperators in
open BooleanAnalysis in
variable {n : ℕ} in
lemma ArrowTheorem.expected_product_bcca (f : BooleanFunc n) :
    (1/6 : ℝ)^n * ∑ p : Profile n, f (bcVotes p) * f (caVotes p) = corrFunc f
Source
TCSlib, `ArrowTheorem.expected_product_bcca`
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.caVotesGiven 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.profile_kernel_bccaThe $bc$–$ca$ profile kernel. Let $S, T \subseteq [n]$, and for a profile $p \colon \mathrm{Fin}\,n \to \mathrm{Fin}\,6$ write $x(p)$ for…
  • 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.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(bc)·f(ca)] = corrFunc f. -/
lemma ArrowTheorem.expected_product_bcca (f : BooleanFunc n) :
    (1/6 : ℝ)^n * ∑ p : Profile n, f (bcVotes p) * f (caVotes p) = corrFunc f :=
  expected_product_helper f bcVotes caVotes profile_kernel_bcca
See it in the graphDiscuss this resultChallenge it