condorcet_qr23_selector_chk
Each indexed triple is listed in increasing order, its challenger is outside it, and the challenger beats every member in the quadratic-residue tournament modulo 23.
Statement
theorem condorcet_qr23_selector_chk : ∀ i : Fin 1771,
condorcet_qr23_selector_member i 0 < condorcet_qr23_selector_member i 1 ∧ condorcet_qr23_selector_member i 1 < condorcet_qr23_selector_member i 2 ∧
condorcet_qr23_selector_challenger i ≠ condorcet_qr23_selector_member i 0 ∧ condorcet_qr23_selector_challenger i ≠ condorcet_qr23_selector_member i 1 ∧ condorcet_qr23_selector_challenger i ≠ condorcet_qr23_selector_member i 2 ∧
∀ k : Fin 3, ((condorcet_qr23_selector_member i k).val + 23 - (condorcet_qr23_selector_challenger i).val) % 23 ∈ [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18]- 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
Quot.soundpropext- Built on 2
- 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…
- 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 establishes that a precomputed table of 1,771 triples from ℤ/23ℤ and their associated challengers satisfies three properties: each triple is strictly increasing, the challenger is not in the triple, and the challenger beats every member of the triple in the Paley tournament on ℤ/23ℤ (meaning the difference is a non-zero quadratic residue). Because the claim is a bounded universal quantification over finite types involving decidable arithmetic relations, it reduces entirely to finite computation. Lean's kernel verifies this directly via `decide +kernel` by exhaustively evaluating the condition for all 1,771 triples.
All 1,771 candidate triples and challengers satisfy the required ordering, disjointness, and tournament edge conditions. automation
Because the types Fin 1771 and Fin 3 are finite, and all inequalities, disequalities, and modular arithmetic operations are computable, the entire universal statement is decidable. The tactic `decide +kernel` delegates the exhaustive evaluation of all 1,771 triples directly to Lean's kernel, reducing the proposition to true.
decide +kernel
- The proof relies entirely on Lean's kernel evaluating the decidable proposition across all 1,771 cases, with no intermediate manual derivation 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_chk : ∀ i : Fin 1771, condorcet_qr23_selector_member i 0 < condorcet_qr23_selector_member i 1 ∧ condorcet_qr23_selector_member i 1 < condorcet_qr23_selector_member i 2 ∧ condorcet_qr23_selector_challenger i ≠ condorcet_qr23_selector_member i 0 ∧ condorcet_qr23_selector_challenger i ≠ condorcet_qr23_selector_member i 1 ∧ condorcet_qr23_selector_challenger i ≠ condorcet_qr23_selector_member i 2 ∧ ∀ k : Fin 3, ((condorcet_qr23_selector_member i k).val + 23 - (condorcet_qr23_selector_challenger i).val) % 23 ∈ [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] := by decide +kernel