ArrowTheorem.profile_inner_product_kernel
theoremverifiedimported Lean
Orthogonality kernel for the $ab$–$bc$ vote pair. Fix $n$, and for each profile $p \in \{0,\dots,5\}^n$ let $v_{ab}(p), v_{bc}(p) \in \{0,1\}^n$ be the vote vectors recording, voter by voter, each voter's pairwise preference in the $a$-vs-$b$ and $b$-vs-$c$ comparisons, and for $S \subseteq [n]$ let $\chi_S$ be the associated Walsh–Fourier character. Then for all subsets $S, T \subseteq [n]$, the uniform average of the product $\chi_S(v_{ab}(p))\,\chi_T(v_{bc}(p))$ over the $6^n$ profiles satisfies \[ \Bigl(\tfrac{1}{6}\Bigr)^{\!n}\sum_{p} \chi_S\bigl(v_{ab}(p)\bigr)\,\chi_T\bigl(v_{bc}(p)\bigr) \;=\; \begin{cases} \left(-\tfrac{1}{3}\right)^{\abs{S}} & S = T,\\[2pt] 0 & S \ne T. \end{cases} \]
Statement
set_option maxHeartbeats 800000 in open scoped BigOperators in open BooleanAnalysis in variable {n : ℕ} in lemma ArrowTheorem.profile_inner_product_kernel (S T : Finset (Fin n)) : (1/6 : ℝ)^n * ∑ p : Profile n, chiS S (abVotes p) * chiS T (bcVotes p) = if S = T then (-1/3 : ℝ)^S.card else 0
- Source
- TCSlib, `ArrowTheorem.profile_inner_product_kernel`
- 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.profile_inner_product_kernel← ArrowTheorem.profile_inner_product_kernel (TCSlib/BooleanAnalysis/ArrowTheorem.lean:419): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- ArrowTheorem.sum_abPref_bcPrefSum 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.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.sum_bcPref_signBalanced b-versus-c preferences over the six orderings. Consider the six strict orderings of three alternatives $a$, $b$, and $c$, indexed…
- 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_eq_corrFuncExpected pairwise vote product equals the Fourier correlation function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function. Suppose each of…
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–bc pair. -/ lemma ArrowTheorem.profile_inner_product_kernel (S T : Finset (Fin n)) : (1/6 : ℝ)^n * ∑ p : Profile n, chiS S (abVotes p) * chiS T (bcVotes p) = if S = T then (-1/3 : ℝ)^S.card else 0 := profile_kernel_gen sum_abPref_sign sum_bcPref_sign sum_abPref_bcPref S T