condorcet_stationary_policy_strict_unrestricted_gap
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
- condorcet_minimal_private_obstruction_no_half_coverThe explicit eight-vertex globally minimal averaging obstruction has no integer acyclic half-cover with a positive number of sets. Its…
- condorcet_optimized_private_policy_lower_boundOn the explicit eight-vertex globally minimal, arc-minimal S3 relation from condorcet_minimal_private_averaging_obstruction, every choice…
- condorcet_optimized_all_triple_policy_lower_boundOn the same explicit eight-vertex relation, allow every three-element subset of each root's out-neighborhood, including nonprivate…
- condorcet_minimal_private_averaging_obstructionThere exist an irreflexive directed relation R on eight vertices, nonempty complete families F(a) of private three-element sets at each…
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.
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.
∀ a ∈ B, ∃ b ∈ B, condorcet_minimal_private_relation b a := by decide
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.
(∑ a ∈ A, condorcet_minimal_private_separator_weight a) ≤ 5 := by decide
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.
uses
condorcet_policy_gap_weight_checkapply condorcet_policy_gap_weight_check A intro B hB hsub
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.
uses
condorcet_policy_gap_forbidden_checkobtain ⟨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
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.
refine ⟨?_, by norm_num, by norm_num⟩
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.
uses
condorcet_policy_gap_unrestricted_weight_boundintro 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
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.
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