AFTD Auto-Formalizing Theoretical Domains

condorcet_optimized_private_policy_lower_bound

theoremverified

On the explicit eight-vertex globally minimal, arc-minimal S3 relation from condorcet_minimal_private_averaging_obstruction, every choice of nonnegative occupations on the complete private-triple families satisfying triple stationarity has an induced acyclic subset of at least77/227 of its total vertex weight, in the displayed homogeneous form. This lower bound concerns the best possible private stationary policy; it is below one half and does not refute the election conjecture or the strict-half policy conjecture.

Statement

theorem condorcet_optimized_private_policy_lower_bound
    (x : Fin 8 → Finset (Fin 8) → ℝ) (w : Fin 8 → ℝ)
    (hx : ∀ a, ∀ J ∈ condorcet_minimal_private_family a, 0 ≤ x a J)
    (hw : ∀ a, w a = ∑ J ∈ condorcet_minimal_private_family a, x a J)
    (hflow : ∀ b, 3 * w b = ∑ a, ∑ J ∈ condorcet_minimal_private_family a,
      if b ∈ J then x a J else 0) :
    ∃ A : Finset (Fin 8),
      WellFounded (fun a b : {a : Fin 8 // a ∈ A} =>
        condorcet_minimal_private_relation a.val b.val) ∧
      77 * (∑ a, w a) ≤ 227 * (∑ a ∈ A, w a)
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 2
Used by 1

The proof, explained

The proof establishes a lower bound of 77/227 on the maximum relative weight of an acyclic sub-tournament by linear programming duality via a stationary averaging principle (`condorcet_stationary_action_dual_acyclic_mass`). Five explicit candidate subsets of vertices are shown to be acyclic by exhibiting integer rankings that strictly increase along all directed edges within each subset. An integer potential vector on the 8 vertices is verified by finite exhaustive computation to satisfy the dual slack inequality with constant 77 and subset coefficients summing to 227; the averaging principle then guarantees that at least one of these acyclic sets carries at least 77/227 of the total vertex weight.

  1. The integer dual slack inequality holds for every vertex and every triple in its private family. automation

    For each vertex a and private triple J, the inequality 77 + ∑_{b ∈ J} h(b) ≤ (∑_{j : a ∈ A_j} d_j) + 3 h(a) is verified by exhaustive finite computation (`decide`) over all 8 vertices and their private triple families.

    lines 14–20

    theorem condorcet_policy_gap_private_dual_check : ∀ a : Fin 8,
        ∀ J ∈ condorcet_minimal_private_family a,
          77 + (∑ b ∈ J, condorcet_policy_gap_private_potential b) ≤
            (∑ j : Fin 5, if a ∈ condorcet_policy_gap_private_sets j then
              condorcet_policy_gap_private_coeff j else 0) +
            3 * condorcet_policy_gap_private_potential a := by decide
    
  2. Within each candidate subset, the ordering function strictly increases along all directed edges of the minimal private relation. automation

    For each of the 5 candidate subsets A_j and each directed edge a → b with both endpoints in A_j, the strict inequality between their assigned integer ranks is verified by exhaustive finite computation (`decide`).

    lines 21–26

    theorem condorcet_policy_gap_private_order_check : ∀ j : Fin 5, ∀ a b : Fin 8,
        a ∈ condorcet_policy_gap_private_sets j → b ∈ condorcet_policy_gap_private_sets j →
        condorcet_minimal_private_relation a b →
        condorcet_policy_gap_private_orders j a < condorcet_policy_gap_private_orders j b := by
      decide
    
  3. Each of the five candidate subsets induces an acyclic (well-founded) sub-relation.

    The induced relation on the j-th candidate set is proven well-founded by mapping vertices to ℕ via their ranking function (`measure`), because directed edges strictly increase this ranking according to `condorcet_policy_gap_private_order_check`.

    lines 27–34

    uses measure, condorcet_policy_gap_private_order_check

    theorem condorcet_policy_gap_private_acyclic (j : Fin 5) :
        WellFounded (fun a b : {a : Fin 8 // a ∈ condorcet_policy_gap_private_sets j} =>
          condorcet_minimal_private_relation a.val b.val) := by
      refine (measure (fun a : {a : Fin 8 // a ∈ condorcet_policy_gap_private_sets j} =>
        condorcet_policy_gap_private_orders j a.val)).wf.mono ?_
      intro a b hab
      exact condorcet_policy_gap_private_order_check j a b a.property b.property hab
    
  4. The dual slack inequality holds over the real numbers for all vertices and private triples.

    The integer dual inequality established in `condorcet_policy_gap_private_dual_check` is cast from ℕ to ℝ using `exact_mod_cast`.

    lines 45–51

    uses condorcet_policy_gap_private_dual_check

      have hdual : ∀ a : Fin 8, ∀ J ∈ condorcet_minimal_private_family a,
          (77 : ℝ) + (∑ b ∈ J, (condorcet_policy_gap_private_potential b : ℝ)) ≤
            (∑ j : Fin 5, if a ∈ condorcet_policy_gap_private_sets j then
              (condorcet_policy_gap_private_coeff j : ℝ) else 0) +
            3 * (condorcet_policy_gap_private_potential a : ℝ) := by
        intro a J hJ
        exact_mod_cast condorcet_policy_gap_private_dual_check a J hJ
  5. There exists a candidate subset carrying at least a 77 / (∑ d_j) fraction of the total vertex weight.

    We apply the stationary action dual averaging theorem `condorcet_stationary_action_dual_acyclic_mass` with the 5 candidate subsets, coefficients d_j, potential h, and constant c = 77. Given nonnegativity of d (via `Nat.cast_nonneg`), nonnegativity of occupations x, definition of weights w, flow stationarity, and the real dual inequality `hdual`, the lemma produces an index j whose subset satisfies 77 ∑ w ≤ (∑ d_i) ∑_{a ∈ A_j} w(a).

    lines 52–57

    uses condorcet_stationary_action_dual_acyclic_mass, Nat.cast_nonneg

      obtain ⟨j,hj⟩ := condorcet_stationary_action_dual_acyclic_mass 8 5 (by decide)
        condorcet_minimal_private_family x w
        (fun a => (condorcet_policy_gap_private_potential a : ℝ))
        condorcet_policy_gap_private_sets
        (fun j => (condorcet_policy_gap_private_coeff j : ℝ)) 77
        (fun j => Nat.cast_nonneg _) hx hw hflow hdual
  6. There exists an acyclic subset A satisfying 77 ∑_a w(a) ≤ 227 ∑_{a ∈ A} w(a).

    The sum of the coefficients 68 + 39 + 39 + 39 + 42 = 227 is computed by `decide` in ℕ and cast to ℝ. Rewriting the mass bound with this sum and pairing it with the acyclicity of A_j from `condorcet_policy_gap_private_acyclic` witnesses the existential claim.

    lines 58–62

    uses condorcet_policy_gap_private_acyclic

      have hsumN : (∑ j : Fin 5, condorcet_policy_gap_private_coeff j) = 227 := by decide
      have hsumR : (∑ j : Fin 5, (condorcet_policy_gap_private_coeff j : ℝ)) = 227 := by
        exact_mod_cast hsumN
      rw [hsumR] at hj
      exact ⟨_, condorcet_policy_gap_private_acyclic j, hj⟩
measure
Constructs a well-founded relation on a type α by pulling back the standard strict less-than relation on ℕ along a given ranking function from α to ℕ.
condorcet_policy_gap_private_order_check
Within each of the five candidate subsets, every directed edge in the minimal private relation points from a vertex of strictly lower ranking to one of strictly higher ranking.
condorcet_policy_gap_private_acyclic
For each of the five candidate subsets, the tournament relation induced on that subset is well-founded, and hence contains no directed cycles.
condorcet_policy_gap_private_dual_check
For every vertex a and every private triple J in its family, the integer dual slack inequality holds with constant 77 and the given private potential vector and subset coefficients.
condorcet_stationary_action_dual_acyclic_mass
In a system satisfying triple stationarity and nonnegativity, if a potential vector and family of subsets satisfy the dual slack inequality with constant c and coefficients d, then some subset in the family carries at least a c / (∑ d_i) fraction of the total vertex weight.
Nat.cast_nonneg
The coercion of any natural number into an ordered semiring, such as the real numbers, is nonnegative.

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_private_sets : Fin 5 → Finset (Fin 8) :=  ![{3,4},{0,1,2,3,5},{1,2,6},{1,5,6},{2,5,6}]def condorcet_policy_gap_private_coeff : Fin 5 → ℕ := ![68,39,39,39,42]def condorcet_policy_gap_private_potential : Fin 8 → ℕ := ![27,0,0,0,13,0,0,30]def condorcet_policy_gap_private_orders : Fin 5 → Fin 8 → ℕ :=  ![![0,0,0,1,0,0,0,0], ![4,3,2,0,0,1,0,0], ![0,1,0,0,0,0,2,0],    ![0,0,0,0,0,2,1,0], ![0,0,2,0,0,1,0,0]]theorem condorcet_policy_gap_private_dual_check : ∀ a : Fin 8,    ∀ J ∈ condorcet_minimal_private_family a,      77 + (∑ b ∈ J, condorcet_policy_gap_private_potential b) ≤        (∑ j : Fin 5, if a ∈ condorcet_policy_gap_private_sets j then          condorcet_policy_gap_private_coeff j else 0) +        3 * condorcet_policy_gap_private_potential a := by decidetheorem condorcet_policy_gap_private_order_check : ∀ j : Fin 5, ∀ a b : Fin 8,    a ∈ condorcet_policy_gap_private_sets j → b ∈ condorcet_policy_gap_private_sets j →    condorcet_minimal_private_relation a b →    condorcet_policy_gap_private_orders j a < condorcet_policy_gap_private_orders j b := by  decidetheorem condorcet_policy_gap_private_acyclic (j : Fin 5) :    WellFounded (fun a b : {a : Fin 8 // a ∈ condorcet_policy_gap_private_sets j} =>      condorcet_minimal_private_relation a.val b.val) := by  refine (measure (fun a : {a : Fin 8 // a ∈ condorcet_policy_gap_private_sets j} =>    condorcet_policy_gap_private_orders j a.val)).wf.mono ?_  intro a b hab  exact condorcet_policy_gap_private_order_check j a b a.property b.property habtheorem condorcet_optimized_private_policy_lower_bound    (x : Fin 8 → Finset (Fin 8) → ℝ) (w : Fin 8 → ℝ)    (hx : ∀ a, ∀ J ∈ condorcet_minimal_private_family a, 0 ≤ x a J)    (hw : ∀ a, w a = ∑ J ∈ condorcet_minimal_private_family a, x a J)    (hflow : ∀ b, 3 * w b = ∑ a, ∑ J ∈ condorcet_minimal_private_family a,      if b ∈ J then x a J else 0) :    ∃ A : Finset (Fin 8),      WellFounded (fun a b : {a : Fin 8 // a ∈ A} =>        condorcet_minimal_private_relation a.val b.val) ∧      77 * (∑ a, w a) ≤ 227 * (∑ a ∈ A, w a) := by  have hdual : ∀ a : Fin 8, ∀ J ∈ condorcet_minimal_private_family a,      (77 : ℝ) + (∑ b ∈ J, (condorcet_policy_gap_private_potential b : ℝ)) ≤        (∑ j : Fin 5, if a ∈ condorcet_policy_gap_private_sets j then          (condorcet_policy_gap_private_coeff j : ℝ) else 0) +        3 * (condorcet_policy_gap_private_potential a : ℝ) := by    intro a J hJ    exact_mod_cast condorcet_policy_gap_private_dual_check a J hJ  obtain ⟨j,hj⟩ := condorcet_stationary_action_dual_acyclic_mass 8 5 (by decide)    condorcet_minimal_private_family x w    (fun a => (condorcet_policy_gap_private_potential a : ℝ))    condorcet_policy_gap_private_sets    (fun j => (condorcet_policy_gap_private_coeff j : ℝ)) 77    (fun j => Nat.cast_nonneg _) hx hw hflow hdual  have hsumN : (∑ j : Fin 5, condorcet_policy_gap_private_coeff j) = 227 := by decide  have hsumR : (∑ j : Fin 5, (condorcet_policy_gap_private_coeff j : ℝ)) = 227 := by    exact_mod_cast hsumN  rw [hsumR] at hj  exact ⟨_, condorcet_policy_gap_private_acyclic j, hj⟩
See it in the graphDiscuss this resultChallenge it