AFTD Auto-Formalizing Theoretical Domains

condorcet_qr23_selector_chk

theoremverified

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
Used by 1

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.

  1. 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.

    line 5

      decide +kernel

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

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
See it in the graphDiscuss this resultChallenge it