AFTD Auto-Formalizing Theoretical Domains

ArrowTheorem.profile_kernel_abca

theoremverifiedimported Lean

Kernel of the ab–ca vote correlation. Fix a natural number $n$ and consider profiles $p$ of $n$ voters, each of whom reports one of the six strict orderings of the three alternatives $a, b, c$; there are $6^n$ such profiles. For a profile $p$, let $x^{ab}(p) \in \{0,1\}^n$ be the vector recording each voter's preference in the $a$-vs-$b$ comparison, and $x^{ca}(p) \in \{0,1\}^n$ the vector recording each voter's preference in the $c$-vs-$a$ comparison. Then for any two subsets $S, T \subseteq \{1,\dots,n\}$, the averaged product of the corresponding Walsh–Fourier characters satisfies \[ \left(\tfrac{1}{6}\right)^{\!n} \sum_{p} \chi_S\bigl(x^{ab}(p)\bigr)\,\chi_T\bigl(x^{ca}(p)\bigr) \;=\; \begin{cases} \left(-\tfrac{1}{3}\right)^{|S|} & \text{if } S = T,\\[2pt] 0 & \text{if } S \neq T, \end{cases} \] where the sum ranges over all $6^n$ profiles.

Statement

set_option maxHeartbeats 800000 in
open scoped BigOperators in
open BooleanAnalysis in
variable {n : ℕ} in
lemma ArrowTheorem.profile_kernel_abca (S T : Finset (Fin n)) :
    (1/6 : ℝ)^n * ∑ p : Profile n,
      chiS S (abVotes p) * chiS T (caVotes p) =
    if S = T then (-1/3 : ℝ)^S.card else 0
Source
TCSlib, `ArrowTheorem.profile_kernel_abca`
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 8
  • ArrowTheorem.sum_abPref_caPrefSum of paired preference signs. Label the six strict orderings of three alternatives $a,b,c$ by $k\in\{0,\dots,5\}$. For each ordering let…
  • ArrowTheorem.profile_kernel_genGeneral profile kernel for paired preference assignments. Let $x, y : \mathrm{Fin}\,6 \to \mathrm{Bool}$ be two preference assignments…
  • ArrowTheorem.sum_caPref_signVanishing sum of signed $c$-vs-$a$ preferences. For each of the six strict orderings $k\in\{0,1,\dots,5\}$ of three alternatives, let…
  • 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.ProfileA profile assigns each of the $n$ voters one of the 6 orderings: $p : \mathrm{Fin}\,n \to \mathrm{Fin}\,6$.
  • ArrowTheorem.sum_abPref_signBalance of the a-vs-b preference signs. There are six strict orderings $k \in \{0,1,\dots,5\}$ of the three alternatives $a,b,c$. For each…
  • BooleanAnalysis.chiSThe Walsh--Fourier character associated to $S\subseteq[n]$ is…
Used by 1
  • 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…

Lean source view module on GitHub

set_option maxHeartbeats 800000 in
open scoped BigOperators in
open BooleanAnalysis in
variable {n : ℕ} in
/-- Kernel lemma for the ab–ca pair. -/
lemma ArrowTheorem.profile_kernel_abca (S T : Finset (Fin n)) :
    (1/6 : ℝ)^n * ∑ p : Profile n,
      chiS S (abVotes p) * chiS T (caVotes p) =
    if S = T then (-1/3 : ℝ)^S.card else 0 :=
  profile_kernel_gen sum_abPref_sign sum_caPref_sign sum_abPref_caPref S T
See it in the graphDiscuss this resultChallenge it