condorcet_qr23_selector_local
The potential satisfies 23 + 3 p(i) <= 45 [challenger below the minimum] + the sum of p over the three transitions, for every triple.
Statement
theorem condorcet_qr23_selector_local : ∀ i : Fin 1771, 23 + 3 * condorcet_qr23_selector_potential i ≤ 45 * (if condorcet_qr23_selector_challenger i < condorcet_qr23_selector_member i 0 then 1 else 0) + ∑ k : Fin 3, condorcet_qr23_selector_potential (condorcet_qr23_selector_next i k)
- Source
- Certificate data for condorcet_tournament_stationary_restriction_obstruction (restriction diagnostic for OP-19 on the quadratic-residue tournament modulo 23; potential from experiment 8584, recomputed by CP-SAT). Related definition from Condorcet winning sets, Social Choice and Welfare 44(3):493-517 (2015).
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- condorcet_qr23_selector_memberThe k-th smallest member of the i-th three-element subset of Fin 23 in lexicographic order (stored as lookup tables).
- condorcet_qr23_selector_challengerThe outside challenger of the i-th triple: the first candidate cyclically before its minimum that beats all three members in the…
- condorcet_qr23_selector_nextThe index of the triple obtained from the i-th triple by evicting its k-th smallest member and inserting its challenger.
- condorcet_qr23_selector_potentialAn integer potential on the 1771 triples certifying the local inequality 23 + 3 p(i) <= 45 score(i) + sum over the three transitions of p.
- Used by 1
- condorcet_tournament_stationary_restriction_obstructionThere is a complete outside-challenger selector on all1771 three-element subsets of23 candidates such that every challenger dominates…
The proof, explained
The theorem asserts a local potential decrease condition across each of the 1,771 states in the Condorcet selector model on the Paley tournament of order 23. Because the domain is finite and all functions are given by computable tables, the proof proceeds by exhaustive finite verification using Lean's kernel evaluator.
For every state $i \in \mathrm{Fin}(1771)$, the potential inequality $23 + 3 \cdot p(i) \le 45 \cdot \mathbf{1}_{\{c(i) < m(i, 0)\}} + \sum_{k=0}^2 p(n(i, k))$ holds. automation
The claim is a universally quantified statement over the finite domain $\mathrm{Fin}(1771)$, and all quantities involved (the potential function, challenger, member, and transition states) are defined via explicit computational lookup tables. The `decide +kernel` tactic delegates the exhaustive evaluation of all 1,771 instances directly to Lean's trusted kernel.
decide +kernel
- The proof is entirely computational: Lean's kernel evaluates the arithmetic inequality exhaustively across all 1,771 states of the finite type Fin 1771 without any intermediate symbolic steps.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem condorcet_qr23_selector_local : ∀ i : Fin 1771, 23 + 3 * condorcet_qr23_selector_potential i ≤ 45 * (if condorcet_qr23_selector_challenger i < condorcet_qr23_selector_member i 0 then 1 else 0) + ∑ k : Fin 3, condorcet_qr23_selector_potential (condorcet_qr23_selector_next i k) := by decide +kernel