condorcet_optimized_private_policy_lower_bound
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
- condorcet_stationary_action_dual_acyclic_massFor nonnegative occupations of arbitrary finite families of rooted finite-set actions, let each vertex weight equal the sum of occupations…
- 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…
- Used by 1
- condorcet_stationary_policy_strict_unrestricted_gapFor 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…
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.
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.
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
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`).
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
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`.
uses
measure,condorcet_policy_gap_private_order_checktheorem 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
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`.
uses
condorcet_policy_gap_private_dual_checkhave 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
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).
uses
condorcet_stationary_action_dual_acyclic_mass,Nat.cast_nonnegobtain ⟨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
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.
uses
condorcet_policy_gap_private_acyclichave 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
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_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⟩