condorcet_reciprocal_roots_le_six_acyclic_weight_separation
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
- condorcet_acyclic_half_cover_reciprocal_roots_ge_sevenSuppose an S3 finite directed relation has a positive integer acyclic half-cover. If every vertex is connected by reciprocal arrows to one…
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
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.
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.
uses
condorcet_half_cover_acyclic_half_cover_dualityclassical apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp rintro ⟨n,U,hn,hU,hhalf⟩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.
uses
condorcet_acyclic_half_cover_reciprocal_roots_ge_sevenhave h := condorcet_acyclic_half_cover_reciprocal_roots_ge_seven m n c hn R U hroot hU hhalf r label hpath hneContradiction.
Linear integer arithmetic closes the goal by showing that 7 ≤ c contradicts the hypothesis c ≤ 6 (`hc`).
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
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 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