AFTD Auto-Formalizing Theoretical Domains

condorcet_one_child_circulation_unrestricted_gap

theoremverified

For the explicit seven-vertex oriented relation with predecessor masks [16,4,65,36,72,3,32], every induced acyclic subset has at most five vertices, so uniform weights have acyclic mass at most 5/7. Every nonnegative stationary occupation on its outgoing singleton actions has an induced acyclic subset of at least 3/4 of total vertex mass, expressed homogeneously. Since 5/7 < 3/4, equality between unrestricted acyclic minimax and the one-child circulation restriction fails in general, even for oriented relations. This graph does not have the S3 predecessor property, which is explicitly certified. It does not refute equality restricted to S3 cores, the strict-half separator goal, or the original election statement.

Statement

theorem condorcet_one_child_circulation_unrestricted_gap :
    (∀ a b : Fin 7, condorcet_one_child_gap_relation a b → ¬condorcet_one_child_gap_relation b a) ∧
    (¬∀ J : Finset (Fin 7), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, condorcet_one_child_gap_relation a b) ∧
    (∀ A : Finset (Fin 7), WellFounded (fun a b : {a : Fin 7 // a ∈ A} => condorcet_one_child_gap_relation a.val b.val) → A.card ≤ 5) ∧
    (∀ (x : Fin 7 → Finset (Fin 7) → ℝ) (w : Fin 7 → ℝ),
      (∀ a, ∀ J ∈ condorcet_one_child_gap_actions a, 0 ≤ x a J) →
      (∀ a, w a = ∑ J ∈ condorcet_one_child_gap_actions a, x a J) →
      (∀ b, w b = ∑ a, ∑ J ∈ condorcet_one_child_gap_actions a, if b ∈ J then x a J else 0) →
      ∃ A : Finset (Fin 7), WellFounded (fun a b : {a : Fin 7 // a ∈ A} => condorcet_one_child_gap_relation a.val b.val) ∧
        3 * (∑ a, w a) ≤ 4 * (∑ a ∈ A, w a)) ∧
    (5 / 7 : ℚ) < 3 / 4
Source
IN-372 final method obstruction for OP-19. Exact rational SMT experiment9339 supplied the graph; optimization9340 reconstructed the simple rational certificate; exact integer audit9343 checks the complete certificate. No novelty, election bound or campaign research advance is claimed. Earlier random tests missed this sparse graph. The S3-specific reduction remains unproved.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Lean source view module on GitHub

open Finset
open scoped BigOperators
set_option maxHeartbeats 4000000
set_option maxRecDepth 10000

theorem condorcet_one_child_action_dual_bound
    (m : ℕ) (F : Fin m → Finset (Finset (Fin m)))
    (x : Fin m → Finset (Fin m) → ℝ) (w p h : Fin m → ℝ) (c : ℝ)
    (hx : ∀ a, ∀ J ∈ F a, 0 ≤ x a J)
    (hw : ∀ a, w a = ∑ J ∈ F a, x a J)
    (hflow : ∀ b, w b = ∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0)
    (hdual : ∀ a, ∀ J ∈ F a, c + (∑ b ∈ J, h b) ≤ p a + h a) :
    c * (∑ a, w a) ≤ ∑ a, w a * p a := by
  classical
  have hchildren : (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) =
      ∑ b, w b * h b := by
    calc
      (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) =
          ∑ a, ∑ J ∈ F a, ∑ b : Fin m, if b ∈ J then x a J * h b else 0 := by
        simp [mul_sum]
      _ = ∑ b : Fin m, ∑ a, ∑ J ∈ F a, if b ∈ J then x a J * h b else 0 := by
        simp_rw [sum_comm (s := F _)]
        rw [sum_comm]
      _ = ∑ b, (∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0) * h b := by
        simp [sum_mul, ite_mul]
      _ = _ := by simp_rw [← hflow]
  have hsum : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) ≤
      ∑ a, ∑ J ∈ F a, x a J * (p a + h a) := by
    apply sum_le_sum
    intro a ha
    apply sum_le_sum
    intro J hJ
    exact mul_le_mul_of_nonneg_left (hdual a J hJ) (hx a J hJ)
  have hleft : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) =
      c * (∑ a, w a) + ∑ a, w a * h a := by
    simp_rw [mul_add, sum_add_distrib]
    rw [hchildren]
    congr 1
    rw [mul_sum]
    apply sum_congr rfl
    intro a ha
    rw [← sum_mul, ← hw]
    ring
  have hright : (∑ a, ∑ J ∈ F a, x a J * (p a + h a)) =
      (∑ a, w a * p a) + ∑ a, w a * h a := by
    simp_rw [← sum_mul, ← hw, mul_add]
    rw [sum_add_distrib]
  rw [hleft, hright] at hsum
  linarith

theorem condorcet_one_child_action_dual_acyclic_mass
    (m k : ℕ) (hk : 0 < k)
    (F : Fin m → Finset (Finset (Fin m)))
    (x : Fin m → Finset (Fin m) → ℝ) (w h : Fin m → ℝ)
    (A : Fin k → Finset (Fin m)) (d : Fin k → ℝ) (c : ℝ)
    (hd : ∀ j, 0 ≤ d j)
    (hx : ∀ a, ∀ J ∈ F a, 0 ≤ x a J)
    (hw : ∀ a, w a = ∑ J ∈ F a, x a J)
    (hflow : ∀ b, w b = ∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0)
    (hdual : ∀ a, ∀ J ∈ F a,
      c + (∑ b ∈ J, h b) ≤ (∑ j, if a ∈ A j then d j else 0) + h a) :
    ∃ j, c * (∑ a, w a) ≤ (∑ i, d i) * (∑ a ∈ A j, w a) := by
  classical
  have hbound := condorcet_one_child_action_dual_bound m F x w
    (fun a => ∑ j, if a ∈ A j then d j else 0) h c hx hw hflow hdual
  have hswap : (∑ a, w a * (∑ j, if a ∈ A j then d j else 0)) =
      ∑ j, d j * (∑ a ∈ A j, w a) := by
    simp_rw [mul_sum]
    rw [sum_comm]
    apply sum_congr rfl
    intro j hj
    simp [mul_ite, mul_comm]
  rw [hswap] at hbound
  obtain ⟨j, hj, hmax⟩ := exists_max_image univ (fun j : Fin k => ∑ a ∈ A j, w a)
    ⟨⟨0,hk⟩, mem_univ _⟩
  refine ⟨j, hbound.trans ?_⟩
  rw [sum_mul]
  exact sum_le_sum (fun i hi => mul_le_mul_of_nonneg_left (hmax i hi) (hd i))


def condorcet_one_child_gap_pred : Fin 7 → Finset (Fin 7) :=
  ![{4},{2},{0,6},{2,5},{3,6},{0,1},{5}]
def condorcet_one_child_gap_relation (a b : Fin 7) : Prop := a ∈ condorcet_one_child_gap_pred b
instance (a b : Fin 7) : Decidable (condorcet_one_child_gap_relation a b) := inferInstanceAs (Decidable (a ∈ condorcet_one_child_gap_pred b))
def condorcet_one_child_gap_actions (a : Fin 7) : Finset (Finset (Fin 7)) :=
  (univ.powersetCard 1).filter (fun J => ∀ b ∈ J, condorcet_one_child_gap_relation a b)
def condorcet_one_child_gap_sets : Fin 2 → Finset (Fin 7) := ![{0,1,2,4,5},{0,2,3,5,6}]
def condorcet_one_child_gap_potential : Fin 7 → ℕ := ![0,2,1,2,1,1,2]
def condorcet_one_child_gap_orders : Fin 2 → Fin 7 → ℕ := ![![1,3,2,0,0,4,0],![0,0,3,4,0,1,2]]
def condorcet_one_child_gap_forbidden : Finset (Finset (Fin 7)) := {{0,2,3,4},{0,3,4,5},{1,2,5,6},{0,4,5,6}}

theorem condorcet_one_child_gap_forbidden_check : ∀ B ∈ condorcet_one_child_gap_forbidden,
    B.Nonempty ∧ ∀ a ∈ B, ∃ b ∈ B, condorcet_one_child_gap_relation b a := by decide
theorem condorcet_one_child_gap_card_check : ∀ A : Finset (Fin 7),
    (∀ B ∈ condorcet_one_child_gap_forbidden, ¬B ⊆ A) → A.card ≤ 5 := by decide
theorem condorcet_one_child_gap_card (A : Finset (Fin 7))
    (hA : WellFounded (fun a b : {a : Fin 7 // a ∈ A} => condorcet_one_child_gap_relation a.val b.val)) : A.card ≤ 5 := by
  apply condorcet_one_child_gap_card_check A
  intro B hB hsub
  obtain ⟨hne,hpred⟩ := condorcet_one_child_gap_forbidden_check B hB
  obtain ⟨b,hb⟩ := hne
  obtain ⟨a,ha,hmin⟩ := hA.has_min {a : {a : Fin 7 // a ∈ A} | a.val ∈ B} ⟨⟨b,hsub hb⟩,hb⟩
  obtain ⟨c,hc,hca⟩ := hpred a.val ha
  exact hmin ⟨c,hsub hc⟩ hc hca
theorem condorcet_one_child_gap_order_check : ∀ j : Fin 2, ∀ a b : Fin 7,
    a ∈ condorcet_one_child_gap_sets j → b ∈ condorcet_one_child_gap_sets j →
    condorcet_one_child_gap_relation a b →
    condorcet_one_child_gap_orders j a < condorcet_one_child_gap_orders j b := by decide
theorem condorcet_one_child_gap_acyclic (j : Fin 2) :
    WellFounded (fun a b : {a : Fin 7 // a ∈ condorcet_one_child_gap_sets j} => condorcet_one_child_gap_relation a.val b.val) := by
  refine (measure (fun a : {a : Fin 7 // a ∈ condorcet_one_child_gap_sets j} => condorcet_one_child_gap_orders j a.val)).wf.mono ?_
  intro a b hab
  exact condorcet_one_child_gap_order_check j a b a.property b.property hab
theorem condorcet_one_child_gap_dual_check : ∀ a : Fin 7, ∀ J ∈ condorcet_one_child_gap_actions a,
    3 + (∑ b ∈ J, condorcet_one_child_gap_potential b) ≤
      (∑ j : Fin 2, if a ∈ condorcet_one_child_gap_sets j then 2 else 0) + condorcet_one_child_gap_potential a := by decide
theorem condorcet_one_child_gap_bound
    (x : Fin 7 → Finset (Fin 7) → ℝ) (w : Fin 7 → ℝ)
    (hx : ∀ a, ∀ J ∈ condorcet_one_child_gap_actions a, 0 ≤ x a J)
    (hw : ∀ a, w a = ∑ J ∈ condorcet_one_child_gap_actions a, x a J)
    (hflow : ∀ b, w b = ∑ a, ∑ J ∈ condorcet_one_child_gap_actions a, if b ∈ J then x a J else 0) :
    ∃ A : Finset (Fin 7), WellFounded (fun a b : {a : Fin 7 // a ∈ A} => condorcet_one_child_gap_relation a.val b.val) ∧
      3 * (∑ a, w a) ≤ 4 * (∑ a ∈ A, w a) := by
  have hdual : ∀ a : Fin 7, ∀ J ∈ condorcet_one_child_gap_actions a,
      (3 : ℝ) + (∑ b ∈ J, (condorcet_one_child_gap_potential b : ℝ)) ≤
        (∑ j : Fin 2, if a ∈ condorcet_one_child_gap_sets j then (2 : ℝ) else 0) + (condorcet_one_child_gap_potential a : ℝ) := by
    intro a J hJ
    exact_mod_cast condorcet_one_child_gap_dual_check a J hJ
  obtain ⟨j,hj⟩ := condorcet_one_child_action_dual_acyclic_mass 7 2 (by decide)
    condorcet_one_child_gap_actions x w (fun a => (condorcet_one_child_gap_potential a : ℝ))
    condorcet_one_child_gap_sets (fun _ => 2) 3 (by intro j; norm_num) hx hw hflow hdual
  norm_num at hj
  exact ⟨_,condorcet_one_child_gap_acyclic j,hj⟩

def condorcet_one_child_gap_cycle_weight : Fin 7 → ℕ := ![1,0,1,1,1,0,0]
def condorcet_one_child_gap_cycle_next : Fin 7 → Fin 7 := ![2,0,3,4,0,0,0]
def condorcet_one_child_gap_cycle_x (a : Fin 7) (J : Finset (Fin 7)) : ℕ :=
  if J = {condorcet_one_child_gap_cycle_next a} then condorcet_one_child_gap_cycle_weight a else 0
theorem condorcet_one_child_gap_cycle_check :
    (∑ a : Fin 7, condorcet_one_child_gap_cycle_weight a) = 4 ∧
    (∀ a, condorcet_one_child_gap_cycle_weight a = ∑ J ∈ condorcet_one_child_gap_actions a, condorcet_one_child_gap_cycle_x a J) ∧
    (∀ b, condorcet_one_child_gap_cycle_weight b = ∑ a, ∑ J ∈ condorcet_one_child_gap_actions a,
      if b ∈ J then condorcet_one_child_gap_cycle_x a J else 0) := by decide

theorem condorcet_one_child_circulation_unrestricted_gap :
    (∀ a b : Fin 7, condorcet_one_child_gap_relation a b → ¬condorcet_one_child_gap_relation b a) ∧
    (¬∀ J : Finset (Fin 7), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, condorcet_one_child_gap_relation a b) ∧
    (∀ A : Finset (Fin 7), WellFounded (fun a b : {a : Fin 7 // a ∈ A} => condorcet_one_child_gap_relation a.val b.val) → A.card ≤ 5) ∧
    (∀ (x : Fin 7 → Finset (Fin 7) → ℝ) (w : Fin 7 → ℝ),
      (∀ a, ∀ J ∈ condorcet_one_child_gap_actions a, 0 ≤ x a J) →
      (∀ a, w a = ∑ J ∈ condorcet_one_child_gap_actions a, x a J) →
      (∀ b, w b = ∑ a, ∑ J ∈ condorcet_one_child_gap_actions a, if b ∈ J then x a J else 0) →
      ∃ A : Finset (Fin 7), WellFounded (fun a b : {a : Fin 7 // a ∈ A} => condorcet_one_child_gap_relation a.val b.val) ∧
        3 * (∑ a, w a) ≤ 4 * (∑ a ∈ A, w a)) ∧
    (5 / 7 : ℚ) < 3 / 4 := by
  exact ⟨by decide,by decide,condorcet_one_child_gap_card,condorcet_one_child_gap_bound,by norm_num⟩
See it in the graphDiscuss this resultChallenge it