AFTD Auto-Formalizing Theoretical Domains

condorcet_reciprocal_roots_le_six_acyclic_weight_separation

theoremverified

An S3 finite relation has nonnegative real weights putting every induced acyclic subset strictly below half if all vertices are connected by reciprocal paths to at most six designated roots and every root has a reciprocal neighbor. There is no vertex-count bound. This is a sufficient structural condition, not a proof for arbitrary oriented S3 relations.

Statement

theorem condorcet_reciprocal_roots_le_six_acyclic_weight_separation
    (m c : ℕ) (hc : c ≤ 6) (R : Fin m → Fin m → Prop)
    (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 →
      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b)
    (r : Fin c → Fin m) (label : Fin m → Fin c)
    (hpath : ∀ a, Relation.ReflTransGen (fun x y => R x y ∧ R y x) (r (label a)) a)
    (hne : ∀ j, ∃ b, R (r j) b ∧ R b (r j)) :
    ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧
      ∀ A : Finset (Fin m),
        WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) →
        2 * (∑ a ∈ A, w a) < ∑ a, w a
Source
IN-380, OP-19 campaign session8, 2026-10-30. General consequence of the IN-372 seven-signature lemma, motivated by product-factor screening9520/9524. ReciprocalRoots.lean checked before official submission. No new election bound or research novelty is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The proof proceeds by contradiction using linear programming duality. By the duality theorem (`condorcet_half_cover_acyclic_half_cover_duality`), finding nonnegative weights separating every acyclic set strictly below half of the total weight is equivalent to the non-existence of an acyclic half-cover (a family of n > 0 acyclic sets covering every vertex at least n/2 times). Supposing for contradiction that such an acyclic half-cover exists on an S3 relation whose vertices have reciprocal paths to c roots with reciprocal neighbors, a structural lower bound (`condorcet_acyclic_half_cover_reciprocal_roots_ge_seven`) implies c ≥ 7. This directly contradicts the assumption c ≤ 6, completing the proof.

  1. It suffices to show that no acyclic half-cover can exist; assume for contradiction that one does.

    By linear programming duality (`condorcet_half_cover_acyclic_half_cover_duality`), the existence of a nonnegative weight function separating every acyclic set strictly below half the total weight is equivalent to the non-existence of an acyclic half-cover. We apply the forward direction of this equivalence and introduce for contradiction a positive integer n and a family of n acyclic subsets U covering every vertex at least n/2 times.

    lines 17–19

    uses condorcet_half_cover_acyclic_half_cover_duality

      classical
      apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp
      rintro ⟨n,U,hn,hU,hhalf⟩
  2. The number of roots c must be at least 7.

    Applying the structural theorem `condorcet_acyclic_half_cover_reciprocal_roots_ge_seven` to the assumed acyclic half-cover U, the S3 domination hypothesis `hroot`, the reciprocal paths to the roots `hpath`, and the existence of reciprocal neighbors `hne`, we deduce that 7 ≤ c.

    lines 20–21

    uses condorcet_acyclic_half_cover_reciprocal_roots_ge_seven

      have h := condorcet_acyclic_half_cover_reciprocal_roots_ge_seven
        m n c hn R U hroot hU hhalf r label hpath hne
  3. Contradiction.

    Linear integer arithmetic closes the goal by showing that 7 ≤ c contradicts the hypothesis c ≤ 6 (`hc`).

    line 22

      omega
condorcet_half_cover_acyclic_half_cover_duality
For any finite relation on m vertices, there exists a nonnegative weight function assigning strictly less than half the total weight to every acyclic subset if and only if there does not exist an acyclic half-cover (a family of n > 0 acyclic subsets covering each vertex at least n/2 times).
condorcet_acyclic_half_cover_reciprocal_roots_ge_seven
In any finite relation satisfying the S3 condition (every subset of at most 3 vertices has an external dominator), if an acyclic half-cover exists and every vertex is connected by a reciprocal path to one of c roots each having a reciprocal neighbor, then c ≥ 7.

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 4000000set_option maxRecDepth 10000theorem condorcet_reciprocal_roots_le_six_acyclic_weight_separation    (m c : ℕ) (hc : c ≤ 6) (R : Fin m → Fin m → Prop)    (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 →      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b)    (r : Fin c → Fin m) (label : Fin m → Fin c)    (hpath : ∀ a, Relation.ReflTransGen (fun x y => R x y ∧ R y x) (r (label a)) a)    (hne : ∀ j, ∃ b, R (r j) b ∧ R b (r j)) :    ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧      ∀ A : Finset (Fin m),        WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) →        2 * (∑ a ∈ A, w a) < ∑ a, w a := by  classical  apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp  rintro ⟨n,U,hn,hU,hhalf⟩  have h := condorcet_acyclic_half_cover_reciprocal_roots_ge_seven    m n c hn R U hroot hU hhalf r label hpath hne  omega
See it in the graphDiscuss this resultChallenge it