AFTD Auto-Formalizing Theoretical Domains

condorcet_stationary_policy_strict_unrestricted_gap

theoremverified

For the existing integer weights [1,1,1,1,4,1,3,4] of total16 on the explicit eight-vertex relation, every induced acyclic subset has at most5/16 of the total weight. Moreover5/16<32/101<77/227, separating this unrestricted upper bound from the two stationary-policy lower bounds proved by the dependencies. This is a method diagnostic on an already studied core, not an election counterexample or a research advance.

Statement

theorem condorcet_stationary_policy_strict_unrestricted_gap :
    (∀ A : Finset (Fin 8),
      WellFounded (fun a b : {a : Fin 8 // a ∈ A} =>
        condorcet_minimal_private_relation a.val b.val) →
      16 * (∑ a ∈ A, condorcet_minimal_private_separator_weight a) ≤
        5 * (∑ a : Fin 8, condorcet_minimal_private_separator_weight a)) ∧
    (5 / 16 : ℚ) < 32 / 101 ∧ (32 / 101 : ℚ) < 77 / 227
Source
IN-372 supporting method diagnostic for OP-19. Integer audit experiment9221 and exploratory LP9219. Standard finite LP weak duality; no novelty or research advance is claimed. The original strict election statement remains unchanged.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

Every acyclic subset of vertices in the 8-vertex relation has total weight at most 5 out of 16, which strictly separates the unrestricted bound 5/16 from the policy bounds 32/101 and 77/227. The bound is established by identifying 14 small cyclic forbidden subsets that cannot appear in any well-founded subset, and verifying by finite exhaustion that any subset avoiding all 14 has weight at most 5. Together with the total weight of 16 and arithmetic checks, this yields the strict separation.

  1. Every forbidden subset of vertices is nonempty and has no minimal element with respect to the relation. automation

    The decider exhaustively checks the 14 candidate forbidden subsets; each is nonempty and every vertex in it has an incoming edge from within the set.

    line 11

          ∀ a ∈ B, ∃ b ∈ B, condorcet_minimal_private_relation b a := by decide
  2. Any subset of vertices that avoids all 14 forbidden subsets has total weight at most 5. automation

    The decider exhaustively checks all 256 subsets of Fin 8, confirming that every subset avoiding all forbidden subsets has sum of weights at most 5.

    line 15

        (∑ a ∈ A, condorcet_minimal_private_separator_weight a) ≤ 5 := by decide
  3. To bound the weight of an acyclic subset A, it suffices to show that A does not contain any forbidden subset B.

    We apply the exhaustive check `condorcet_policy_gap_weight_check` to A, reducing the goal to showing that no forbidden subset B can be a subset of A. We then assume for contradiction that some forbidden B is contained in A.

    lines 21–22

    uses condorcet_policy_gap_weight_check

      apply condorcet_policy_gap_weight_check A
      intro B hB hsub
  4. No acyclic subset A can contain a forbidden subset B.

    By `condorcet_policy_gap_forbidden_check`, B is nonempty, so well-foundedness of the relation on A guarantees a minimal element a in B. However, the forbidden check also provides an element c in B with an edge to a, contradicting the minimality of a.

    lines 23–28

    uses condorcet_policy_gap_forbidden_check

      obtain ⟨hBne,hpred⟩ := condorcet_policy_gap_forbidden_check B hB
      obtain ⟨b,hb⟩ := hBne
      obtain ⟨a,ha,hmin⟩ := hA.has_min {a : {a : Fin 8 // a ∈ A} | a.val ∈ B}
        ⟨⟨b,hsub hb⟩,hb⟩
      obtain ⟨c,hc,hca⟩ := hpred a.val ha
      exact hmin ⟨c,hsub hc⟩ hc hca
  5. The main theorem splits into the weight bound for acyclic sets and the strict numerical inequalities 5/16 < 32/101 < 77/227. automation

    We split the goal into the universal weight bound and two rational inequalities, which norm_num verifies directly.

    line 37

      refine ⟨?_, by norm_num, by norm_num⟩
  6. For any acyclic subset A, 16 times its weight is at most 5 times the total weight of Fin 8. automation

    For any acyclic subset A, `condorcet_policy_gap_unrestricted_weight_bound` gives ∑_{a ∈ A} w(a) ≤ 5. Exhaustive evaluation by decide establishes that the total weight ∑_{a : Fin 8} w(a) is 16. Rewriting with this total, integer arithmetic (omega) closes the inequality 16 * (∑_{a ∈ A} w(a)) ≤ 5 * 16.

    lines 38–43

    uses condorcet_policy_gap_unrestricted_weight_bound

      intro A hA
      have h := condorcet_policy_gap_unrestricted_weight_bound A hA
      have htotal : (∑ a : Fin 8, condorcet_minimal_private_separator_weight a) = 16 := by
        decide
      rw [htotal]
      omega
condorcet_policy_gap_forbidden_check
Every forbidden subset of vertices is nonempty and contains an incoming edge to each of its vertices.
condorcet_policy_gap_weight_check
Any subset of vertices containing none of the forbidden subsets has total separator weight at most 5.
condorcet_policy_gap_unrestricted_weight_bound
Any subset of vertices on which the relation is well-founded (acyclic) has total weight at most 5.

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

open Finsetopen scoped BigOperatorsset_option maxHeartbeats 20000000set_option maxRecDepth 20000def condorcet_policy_gap_forbidden : Finset (Finset (Fin 8)) :=  {{0,4},{1,4},{2,4},{0,6},{3,6},{4,6},{2,7},{3,7},{4,7},{5,7},{6,7},    {3,4,5},{0,1,7},{1,2,5,6}}theorem condorcet_policy_gap_forbidden_check :    ∀ B ∈ condorcet_policy_gap_forbidden, B.Nonempty ∧      ∀ a ∈ B, ∃ b ∈ B, condorcet_minimal_private_relation b a := by decidetheorem condorcet_policy_gap_weight_check : ∀ A : Finset (Fin 8),    (∀ B ∈ condorcet_policy_gap_forbidden, ¬B ⊆ A) →    (∑ a ∈ A, condorcet_minimal_private_separator_weight a) ≤ 5 := by decidetheorem condorcet_policy_gap_unrestricted_weight_bound (A : Finset (Fin 8))    (hA : WellFounded (fun a b : {a : Fin 8 // a ∈ A} =>      condorcet_minimal_private_relation a.val b.val)) :    (∑ a ∈ A, condorcet_minimal_private_separator_weight a) ≤ 5 := by  apply condorcet_policy_gap_weight_check A  intro B hB hsub  obtain ⟨hBne,hpred⟩ := condorcet_policy_gap_forbidden_check B hB  obtain ⟨b,hb⟩ := hBne  obtain ⟨a,ha,hmin⟩ := hA.has_min {a : {a : Fin 8 // a ∈ A} | a.val ∈ B}    ⟨⟨b,hsub hb⟩,hb⟩  obtain ⟨c,hc,hca⟩ := hpred a.val ha  exact hmin ⟨c,hsub hc⟩ hc hcatheorem condorcet_stationary_policy_strict_unrestricted_gap :    (∀ A : Finset (Fin 8),      WellFounded (fun a b : {a : Fin 8 // a ∈ A} =>        condorcet_minimal_private_relation a.val b.val) →      16 * (∑ a ∈ A, condorcet_minimal_private_separator_weight a) ≤        5 * (∑ a : Fin 8, condorcet_minimal_private_separator_weight a)) ∧    (5 / 16 : ℚ) < 32 / 101 ∧ (32 / 101 : ℚ) < 77 / 227 := by  refine ⟨?_, by norm_num, by norm_num⟩  intro A hA  have h := condorcet_policy_gap_unrestricted_weight_bound A hA  have htotal : (∑ a : Fin 8, condorcet_minimal_private_separator_weight a) = 16 := by    decide  rw [htotal]  omega
See it in the graphDiscuss this resultChallenge it