AFTD Auto-Formalizing Theoretical Domains

condorcet_acyclic_half_cover_reciprocal_roots_ge_seven

theoremverified

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
Used by 1

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.

  1. 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.

    lines 17–23

    uses condorcet_half_coalitions_partition_of_incompatible

      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
  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.

    lines 24–40

    uses Or.inl, Iff.rfl

      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
  3. 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.

    lines 41–47

    uses decide_eq_true_eq, decide_eq_false_iff_not

      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
  4. 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.

    line 48

    uses condorcet_acyclic_half_cover_signature_pairs_ge_seven

      apply condorcet_acyclic_half_cover_signature_pairs_ge_seven m n c hn R U hroot hU B label sign
  5. For 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.

    lines 49–63

    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
  6. 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.

    lines 64–72

    uses mem_filter, mem_univ, true_and, decide_eq_false_iff_not, decide_eq_true_eq

        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
  7. 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.

    line 73

      · 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.

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_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
See it in the graphDiscuss this resultChallenge it