condorcet_acyclic_half_cover_reciprocal_roots_ge_seven
Suppose an S3 finite directed relation has a positive integer acyclic half-cover. If every vertex is connected by reciprocal arrows to one of c designated roots, and each designated root has a reciprocal neighbor, then c is at least seven. Roots and labels need not be injective. The reciprocal-neighbor hypothesis is explicit; isolated reciprocal vertices are not covered by this representation.
Statement
theorem condorcet_acyclic_half_cover_reciprocal_roots_ge_seven (m n c : ℕ) (hn : 0 < n) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hhalf : ∀ a, n ≤ 2 * (univ.filter fun v => a ∈ U v).card) (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)) : 7 ≤ c
- 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_signature_pairs_ge_sevenLet a relation on Fin m have an outside common predecessor for every set of at most three vertices, and let a positive finite family of…
- condorcet_half_coalitions_partition_of_incompatibleFor two incompatible voter events in a finite electorate, if each has at least half of the voter support, the electorate size is even, the…
- Used by 1
- condorcet_reciprocal_roots_le_six_acyclic_weight_separationAn S3 finite relation has nonnegative real weights putting every induced acyclic subset strictly below half if all vertices are connected…
The proof, explained
The proof proceeds by reduction to an established lower bound, `condorcet_acyclic_half_cover_signature_pairs_ge_seven`, which shows that at least seven roots are required whenever an acyclic half-cover admits a balanced signed representation. Because each coalition induces an acyclic subrelation, vertices connected by reciprocal arrows cannot belong to the same coalition; since each belongs to at least half of the coalitions, reciprocal neighbors must partition the coalitions into two equal halves of size n / 2. Propagating this along reciprocal paths establishes that every vertex's coalition membership is either identically equal to or the exact complement of that of its designated root, yielding a balanced signed representation with c roots and concluding that 7 ≤ c.
If two vertices have reciprocal arrows between them, then for every coalition U v, exactly one of them is an element of U v.
Suppose R a b and R b a. Within each coalition U v, R is well-founded and therefore asymmetric, so a and b cannot both belong to U v. Since each vertex belongs to at least half of the coalitions by hypothesis, the incompatible pair of half-coalitions must partition the set of voters, meaning a ∈ U v ↔ b ∉ U v for every voter v.
uses
condorcet_half_coalitions_partition_of_incompatibleclassical have hedge : ∀ a b, R a b → R b a → ∀ v, a ∈ U v ↔ b ∉ U v := by intro a b hab hba exact (condorcet_half_coalitions_partition_of_incompatible n (fun v => a ∈ U v) (fun v => b ∈ U v) (hhalf a) (hhalf b) (by intro v ⟨ha,hb⟩ exact (hU v).asymmetric (a := ⟨a,ha⟩) (b := ⟨b,hb⟩) hab hba)).2.2
Along any path of reciprocal edges, an element's membership across all coalitions is either everywhere identical to or everywhere complementary to that of the starting element.
We induct on the reflexive-transitive closure of the reciprocal edge relation. In the base case of an empty path, membership is identical across all coalitions. For the inductive step extending a path by one reciprocal step from b to d, d belongs to U v if and only if b does not. Combining this negation with the induction hypothesis that b is either universally equivalent or universally complementary to a implies that d is either universally complementary or universally equivalent to a.
uses
Or.inl,Iff.rflhave hprop : ∀ a b, Relation.ReflTransGen (fun x y => R x y ∧ R y x) a b → (∀ v, b ∈ U v ↔ a ∈ U v) ∨ (∀ v, b ∈ U v ↔ a ∉ U v) := by intro a b hp induction hp with | refl => exact Or.inl (fun _ => Iff.rfl) | @tail b d hp hbd ih => rcases ih with hs|hs · right intro v have hh := hedge d b hbd.2 hbd.1 v have hi := hs v tauto · left intro v have hh := hedge d b hbd.2 hbd.1 v have hi := hs v tauto
Every vertex a has a sign in {true, false} indicating whether its coalition membership matches or opposes that of its designated root.
We define a boolean table B where B v j indicates whether root r j belongs to coalition U v. Because every vertex a is connected to root r (label a) by a path of reciprocal arrows, its membership in U v is either always equal to B v (label a) (sign true) or always equal to its negation (sign false). Applying the axiom of choice yields the signing function.
uses
decide_eq_true_eq,decide_eq_false_iff_notlet B : Fin n → Fin c → Bool := fun v j => decide (r j ∈ U v) have hsign : ∀ a, ∃ b : Bool, ∀ v, a ∈ U v ↔ B v (label a) = b := by intro a rcases hprop _ _ (hpath a) with hs|hs · exact ⟨true,fun v => by simpa only [B, decide_eq_true_eq] using hs v⟩ · exact ⟨false,fun v => by simpa only [B, decide_eq_false_iff_not] using hs v⟩ choose sign hsign using hsign
To prove 7 ≤ c, it suffices to show that each root column of the boolean table B is balanced and that the signature equation holds.
We apply the previously established theorem `condorcet_acyclic_half_cover_signature_pairs_ge_seven`, which proves that any S3 relation admitting an acyclic half-cover with a signed representation over c roots and balanced columns satisfies 7 ≤ c.
uses
condorcet_acyclic_half_cover_signature_pairs_ge_sevenapply condorcet_acyclic_half_cover_signature_pairs_ge_seven m n c hn R U hroot hU B label signFor every root r j and any reciprocal neighbor t, exactly half of the coalitions contain r j and exactly half contain t.
By hypothesis, root r j has a reciprocal neighbor t. Let X be the coalitions containing r j and Y those containing t. Since reciprocal neighbors cannot co-occur in any coalition, X and Y are disjoint, which gives |X| + |Y| ≤ n. Because each element appears in at least n / 2 coalitions, linear integer arithmetic forces 2 * |X| = n and 2 * |Y| = n.
uses
disjoint_left.mpr,card_union_of_disjoint,card_univ,Fintype.card_fin,card_le_univ· intro j b obtain ⟨t,hrt,htr⟩ := hne j let X : Finset (Fin n) := univ.filter fun v => r j ∈ U v let Y : Finset (Fin n) := univ.filter fun v => t ∈ U v have hd : Disjoint X Y := by apply disjoint_left.mpr intro v hx hy exact (hedge _ _ hrt htr v).mp (mem_filter.mp hx).2 (mem_filter.mp hy).2 have hle : X.card + Y.card ≤ n := by rw [← card_union_of_disjoint hd] simpa only [card_univ,Fintype.card_fin] using card_le_univ (X ∪ Y) have hX : n ≤ 2 * X.card := hhalf _ have hY : n ≤ 2 * Y.card := hhalf _ have hXeq : 2 * X.card = n := by omega have hYeq : 2 * Y.card = n := by omega
Each column of the boolean profile B is balanced: exactly n / 2 entries are true and exactly n / 2 are false.
For a boolean b, we check cases. When b is false, the coalitions where B v j = false are those not containing r j, which by the reciprocal edge partition property is precisely the set Y of coalitions containing the neighbor t, so twice its size is n. When b is true, the set is X, whose size multiplied by 2 is also n.
uses
mem_filter,mem_univ,true_and,decide_eq_false_iff_not,decide_eq_true_eqcases b · have heq : (univ.filter fun v => B v j = false) = Y := by ext v simp only [Y,mem_filter,mem_univ,true_and,B,decide_eq_false_iff_not] have hh := hedge _ _ hrt htr v tauto rw [heq] exact hYeq · simpa only [B,decide_eq_true_eq] using hXeq
The membership equation a ∈ U v ↔ B v (label a) = sign a holds for all vertices and coalitions.
This is the second obligation required by the signature lower-bound theorem, which holds immediately by the definition of the sign function.
· exact hsign
condorcet_half_coalitions_partition_of_incompatible- If two predicates on n voters each hold for at least n / 2 voters and are mutually exclusive in every coalition, then each holds for exactly n / 2 voters and they partition the universe into exact complements.
Or.inl- Injects a proof of the left proposition into a disjunction A ∨ B.
Iff.rfl- Reflexivity of logical equivalence: A ↔ A.
decide_eq_true_eq- The boolean decision `decide p` equals true if and only if p holds.
decide_eq_false_iff_not- The boolean decision `decide p` equals false if and only if ¬p holds.
condorcet_acyclic_half_cover_signature_pairs_ge_seven- In an S3 tournament, if an acyclic half-cover factors through a signed representation over c roots whose boolean evaluation columns are all balanced, then c ≥ 7.
disjoint_left.mpr- If no element of a finite set s belongs to t, then s and t are disjoint.
card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
card_univ- The cardinality of the universal finset on a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
card_le_univ- The cardinality of any finset of a finite type is at most the cardinality of the type itself.
mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
mem_univ- Every element of a finite type belongs to the universal finset `univ`.
true_and- Conjunction with True simplifies to the proposition itself: True ∧ p = p.
- The balance equations 2 * |X| = n and 2 * |Y| = n are deduced automatically by the `omega` tactic using linear arithmetic on the inequalities |X| + |Y| ≤ n, n ≤ 2 * |X|, and n ≤ 2 * |Y|.
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_acyclic_half_cover_reciprocal_roots_ge_seven (m n c : ℕ) (hn : 0 < n) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hhalf : ∀ a, n ≤ 2 * (univ.filter fun v => a ∈ U v).card) (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)) : 7 ≤ c := by classical have hedge : ∀ a b, R a b → R b a → ∀ v, a ∈ U v ↔ b ∉ U v := by intro a b hab hba exact (condorcet_half_coalitions_partition_of_incompatible n (fun v => a ∈ U v) (fun v => b ∈ U v) (hhalf a) (hhalf b) (by intro v ⟨ha,hb⟩ exact (hU v).asymmetric (a := ⟨a,ha⟩) (b := ⟨b,hb⟩) hab hba)).2.2 have hprop : ∀ a b, Relation.ReflTransGen (fun x y => R x y ∧ R y x) a b → (∀ v, b ∈ U v ↔ a ∈ U v) ∨ (∀ v, b ∈ U v ↔ a ∉ U v) := by intro a b hp induction hp with | refl => exact Or.inl (fun _ => Iff.rfl) | @tail b d hp hbd ih => rcases ih with hs|hs · right intro v have hh := hedge d b hbd.2 hbd.1 v have hi := hs v tauto · left intro v have hh := hedge d b hbd.2 hbd.1 v have hi := hs v tauto let B : Fin n → Fin c → Bool := fun v j => decide (r j ∈ U v) have hsign : ∀ a, ∃ b : Bool, ∀ v, a ∈ U v ↔ B v (label a) = b := by intro a rcases hprop _ _ (hpath a) with hs|hs · exact ⟨true,fun v => by simpa only [B, decide_eq_true_eq] using hs v⟩ · exact ⟨false,fun v => by simpa only [B, decide_eq_false_iff_not] using hs v⟩ choose sign hsign using hsign apply condorcet_acyclic_half_cover_signature_pairs_ge_seven m n c hn R U hroot hU B label sign · intro j b obtain ⟨t,hrt,htr⟩ := hne j let X : Finset (Fin n) := univ.filter fun v => r j ∈ U v let Y : Finset (Fin n) := univ.filter fun v => t ∈ U v have hd : Disjoint X Y := by apply disjoint_left.mpr intro v hx hy exact (hedge _ _ hrt htr v).mp (mem_filter.mp hx).2 (mem_filter.mp hy).2 have hle : X.card + Y.card ≤ n := by rw [← card_union_of_disjoint hd] simpa only [card_univ,Fintype.card_fin] using card_le_univ (X ∪ Y) have hX : n ≤ 2 * X.card := hhalf _ have hY : n ≤ 2 * Y.card := hhalf _ have hXeq : 2 * X.card = n := by omega have hYeq : 2 * Y.card = n := by omega cases b · have heq : (univ.filter fun v => B v j = false) = Y := by ext v simp only [Y,mem_filter,mem_univ,true_and,B,decide_eq_false_iff_not] have hh := hedge _ _ hrt htr v tauto rw [heq] exact hYeq · simpa only [B,decide_eq_true_eq] using hXeq · exact hsign