condorcet_acyclic_half_cover_signature_pairs_ge_seven
Let 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 vertex subsets each induce a well-founded relation. Suppose their membership is represented by c Boolean activity columns and a label and sign for each vertex, where each column is exactly balanced across the n subsets for each Boolean value. Then c is at least seven. Labels need not be distinct or surjective. This is a necessary condition for a half-cover encoded by complementary activity signatures, with no bound on the number of vertices or signature multiplicities.
Statement
theorem condorcet_acyclic_half_cover_signature_pairs_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)) (B : Fin n → Fin c → Bool) (label : Fin m → Fin c) (sign : Fin m → Bool) (hbal : ∀ j b, 2 * (univ.filter fun v => B v j = b).card = n) (hmem : ∀ a v, a ∈ U v ↔ B v (label a) = sign a) : 7 ≤ c
- Source
- IN-372 supporting structural diagnostic for OP-19, 2026-10-30. Exact finite certificates and source/counting arguments documented in In372Oct30/ResearchNotes.txt. No novelty or research advance is claimed; the main election statement remains unchanged.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 3
- condorcet_heavy_pair_acyclic_cover_potential_breakFor any finite S3 relation, any nonnegative weighted family of induced acyclic sets and real vertex potential has an arrow violating the…
- condorcet_acyclic_cover_realizes_critical_signaturesSuppose n=k+q induced acyclic vertex sets cover each vertex at least q times, and every set of at most k vertices has an outside common…
- 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…
The proof, explained
To show c ≥ 7, we first show that any three well-founded subsets omit a common element, which gives a coordinate where any three rows agree because of the Boolean encoding. Then we show that this 3-agreement condition combined with column balance forces any two rows to agree on at least 3 coordinates. Finally, double counting the agreement scores against a fixed row shows that the total score exceeds 3n, which forces c ≥ 7.
Pair agreement is at least 3
By contradiction, analyzing cases |S| = 1 and |S| = 2.
classical let S := univ.filter fun j => B v j = B w j change 3 ≤ S.card by_contra h have hsmall : S.card ≤ 2 := by omega have hne : S.Nonempty := by obtain ⟨j,hj,_⟩ := hthree v w v exact ⟨j,mem_filter.mpr ⟨mem_univ _,hj⟩⟩ have hcpos := card_pos.mpr hne have hcover : ∀ z, ∃ j ∈ S, B z j = B v j := by intro z obtain ⟨j,hvw,hwz⟩ := hthree v w z exact ⟨j,mem_filter.mpr ⟨mem_univ _,hvw⟩,(hvw.trans hwz).symm⟩ by_cases hone : S.card = 1 · obtain ⟨j,hj⟩ := card_eq_one.mp hone have hall : (univ.filter fun z => B z j = B v j) = univ := by ext z simp only [mem_filter, mem_univ, true_and, iff_true] obtain ⟨i,hi,hiz⟩ := hcover z rw [hj] at hi simpa only [mem_singleton.mp hi] using hiz have hh := hbal j (B v j) rw [hall] at hh simp only [card_univ, Fintype.card_fin] at hh omega · have htwo : S.card = 2 := by omega obtain ⟨j,k,hjk,hS⟩ := card_eq_two.mp htwo let X := univ.filter fun z => B z j = B v j let Y := univ.filter fun z => B z k = B v k have hfull : X ∪ Y = univ := by ext z simp only [mem_union, mem_univ, iff_true] obtain ⟨i,hi,hiz⟩ := hcover z rw [hS] at hi simp only [mem_insert, mem_singleton] at hi rcases hi with rfl | rfl · exact Or.inl (mem_filter.mpr ⟨mem_univ _,hiz⟩) · exact Or.inr (mem_filter.mpr ⟨mem_univ _,hiz⟩) have hinter : 0 < (X ∩ Y).card := by apply card_pos.mpr exact ⟨v,mem_inter.mpr ⟨mem_filter.mpr ⟨mem_univ _,rfl⟩, mem_filter.mpr ⟨mem_univ _,rfl⟩⟩⟩ have hcount := card_union_add_card_inter X Y rw [hfull] at hcount simp only [card_univ, Fintype.card_fin] at hcount have hX : 2 * X.card = n := hbal j (B v j) have hY : 2 * Y.card = n := hbal k (B v k) omega
At least 7 coordinates
Double counting pairwise agreements.
classical let v : Fin n := ⟨0,hn⟩ let f : Fin n → ℕ := fun w => (univ.filter fun j => B v j = B w j).card have hmin : ∀ w, 3 ≤ f w := fun w => condorcet_balanced_signature_pair_agreement n c hn B hbal hthree v w have hself : f v = c := by simp [f] have hswap : (∑ w, f w) = ∑ j : Fin c, (univ.filter fun w => B v j = B w j).card := by simp only [f, card_eq_sum_ones, sum_filter] exact sum_comm have hcount : 2 * (∑ w, f w) = c * n := by rw [hswap, mul_sum] have heach : ∀ j : Fin c, 2 * (univ.filter fun w => B v j = B w j).card = n := by intro j simpa only [eq_comm] using hbal j (B v j) simp_rw [heach] simp have hle : 3 * n ≤ ∑ w, f w := by have h := sum_le_sum (s := (univ : Finset (Fin n))) (fun w _ => hmin w) simpa [Nat.mul_comm] using h have hsix : 6 ≤ c := by by_contra h have hc : c ≤ 5 := by omega nlinarith have hlt : 3 * n < ∑ w, f w := by have h := sum_lt_sum (s := (univ : Finset (Fin n))) (fun w _ => hmin w) ⟨v,mem_univ _,by rw [hself]; omega⟩ simpa [Nat.mul_comm] using h by_contra h have hc : c ≤ 6 := by omega nlinarith
Three sets omit a common element
Finding minimal sources and an outside predecessor.
classical obtain ⟨r,_,_⟩ := hroot ∅ (by simp) have hsources : ∀ v, ∃ b, ∀ a ∈ U v, ¬R a b := by intro v by_cases hne : (U v).Nonempty · obtain ⟨a,ha⟩ := hne obtain ⟨b,_,hmin⟩ := (hU v).has_min Set.univ ⟨⟨a,ha⟩,Set.mem_univ _⟩ exact ⟨b.val,fun a ha hab => hmin ⟨a,ha⟩ (Set.mem_univ _) hab⟩ · exact ⟨r,fun a ha => False.elim (hne ⟨a,ha⟩)⟩ choose b hb using hsources intro v w z obtain ⟨a,_,ha⟩ := hroot {b v,b w,b z} (by have h := card_insert_le (b v) ({b w,b z} : Finset (Fin m)) have h2 : ({b w,b z} : Finset (Fin m)).card ≤ 2 := card_le_two omega) exact ⟨a,fun hv => hb v a hv (ha _ (by simp)), fun hw => hb w a hw (ha _ (by simp)),fun hz => hb z a hz (ha _ (by simp))⟩
Main theorem: c is at least 7
Combining the omitted element with the coordinate bound.
apply condorcet_balanced_three_agree_seven_coordinates n c hn B hbal intro v w z obtain ⟨a,hv,hw,hz⟩ := condorcet_acyclic_three_sources_omit m n R U hroot hU v w z have hv' : B v (label a) ≠ sign a := fun h => hv ((hmem a v).mpr h) have hw' : B w (label a) ≠ sign a := fun h => hw ((hmem a w).mpr h) have hz' : B z (label a) ≠ sign a := fun h => hz ((hmem a z).mpr h) have hbool : ∀ x y b : Bool, x ≠ b → y ≠ b → x = y := by decide exact ⟨label a,hbool _ _ _ hv' hw',hbool _ _ _ hw' hz'⟩
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_balanced_signature_pair_agreement (n c : ℕ) (hn : 0 < n) (B : Fin n → Fin c → Bool) (hbal : ∀ j b, 2 * (univ.filter fun v => B v j = b).card = n) (hthree : ∀ v w z, ∃ j, B v j = B w j ∧ B w j = B z j) (v w : Fin n) : 3 ≤ (univ.filter fun j => B v j = B w j).card := by classical let S := univ.filter fun j => B v j = B w j change 3 ≤ S.card by_contra h have hsmall : S.card ≤ 2 := by omega have hne : S.Nonempty := by obtain ⟨j,hj,_⟩ := hthree v w v exact ⟨j,mem_filter.mpr ⟨mem_univ _,hj⟩⟩ have hcpos := card_pos.mpr hne have hcover : ∀ z, ∃ j ∈ S, B z j = B v j := by intro z obtain ⟨j,hvw,hwz⟩ := hthree v w z exact ⟨j,mem_filter.mpr ⟨mem_univ _,hvw⟩,(hvw.trans hwz).symm⟩ by_cases hone : S.card = 1 · obtain ⟨j,hj⟩ := card_eq_one.mp hone have hall : (univ.filter fun z => B z j = B v j) = univ := by ext z simp only [mem_filter, mem_univ, true_and, iff_true] obtain ⟨i,hi,hiz⟩ := hcover z rw [hj] at hi simpa only [mem_singleton.mp hi] using hiz have hh := hbal j (B v j) rw [hall] at hh simp only [card_univ, Fintype.card_fin] at hh omega · have htwo : S.card = 2 := by omega obtain ⟨j,k,hjk,hS⟩ := card_eq_two.mp htwo let X := univ.filter fun z => B z j = B v j let Y := univ.filter fun z => B z k = B v k have hfull : X ∪ Y = univ := by ext z simp only [mem_union, mem_univ, iff_true] obtain ⟨i,hi,hiz⟩ := hcover z rw [hS] at hi simp only [mem_insert, mem_singleton] at hi rcases hi with rfl | rfl · exact Or.inl (mem_filter.mpr ⟨mem_univ _,hiz⟩) · exact Or.inr (mem_filter.mpr ⟨mem_univ _,hiz⟩) have hinter : 0 < (X ∩ Y).card := by apply card_pos.mpr exact ⟨v,mem_inter.mpr ⟨mem_filter.mpr ⟨mem_univ _,rfl⟩, mem_filter.mpr ⟨mem_univ _,rfl⟩⟩⟩ have hcount := card_union_add_card_inter X Y rw [hfull] at hcount simp only [card_univ, Fintype.card_fin] at hcount have hX : 2 * X.card = n := hbal j (B v j) have hY : 2 * Y.card = n := hbal k (B v k) omegatheorem condorcet_balanced_three_agree_seven_coordinates (n c : ℕ) (hn : 0 < n) (B : Fin n → Fin c → Bool) (hbal : ∀ j b, 2 * (univ.filter fun v => B v j = b).card = n) (hthree : ∀ v w z, ∃ j, B v j = B w j ∧ B w j = B z j) : 7 ≤ c := by classical let v : Fin n := ⟨0,hn⟩ let f : Fin n → ℕ := fun w => (univ.filter fun j => B v j = B w j).card have hmin : ∀ w, 3 ≤ f w := fun w => condorcet_balanced_signature_pair_agreement n c hn B hbal hthree v w have hself : f v = c := by simp [f] have hswap : (∑ w, f w) = ∑ j : Fin c, (univ.filter fun w => B v j = B w j).card := by simp only [f, card_eq_sum_ones, sum_filter] exact sum_comm have hcount : 2 * (∑ w, f w) = c * n := by rw [hswap, mul_sum] have heach : ∀ j : Fin c, 2 * (univ.filter fun w => B v j = B w j).card = n := by intro j simpa only [eq_comm] using hbal j (B v j) simp_rw [heach] simp have hle : 3 * n ≤ ∑ w, f w := by have h := sum_le_sum (s := (univ : Finset (Fin n))) (fun w _ => hmin w) simpa [Nat.mul_comm] using h have hsix : 6 ≤ c := by by_contra h have hc : c ≤ 5 := by omega nlinarith have hlt : 3 * n < ∑ w, f w := by have h := sum_lt_sum (s := (univ : Finset (Fin n))) (fun w _ => hmin w) ⟨v,mem_univ _,by rw [hself]; omega⟩ simpa [Nat.mul_comm] using h by_contra h have hc : c ≤ 6 := by omega nlinariththeorem condorcet_acyclic_three_sources_omit (m 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)) : ∀ v w z, ∃ a, a ∉ U v ∧ a ∉ U w ∧ a ∉ U z := by classical obtain ⟨r,_,_⟩ := hroot ∅ (by simp) have hsources : ∀ v, ∃ b, ∀ a ∈ U v, ¬R a b := by intro v by_cases hne : (U v).Nonempty · obtain ⟨a,ha⟩ := hne obtain ⟨b,_,hmin⟩ := (hU v).has_min Set.univ ⟨⟨a,ha⟩,Set.mem_univ _⟩ exact ⟨b.val,fun a ha hab => hmin ⟨a,ha⟩ (Set.mem_univ _) hab⟩ · exact ⟨r,fun a ha => False.elim (hne ⟨a,ha⟩)⟩ choose b hb using hsources intro v w z obtain ⟨a,_,ha⟩ := hroot {b v,b w,b z} (by have h := card_insert_le (b v) ({b w,b z} : Finset (Fin m)) have h2 : ({b w,b z} : Finset (Fin m)).card ≤ 2 := card_le_two omega) exact ⟨a,fun hv => hb v a hv (ha _ (by simp)), fun hw => hb w a hw (ha _ (by simp)),fun hz => hb z a hz (ha _ (by simp))⟩theorem condorcet_acyclic_half_cover_signature_pairs_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)) (B : Fin n → Fin c → Bool) (label : Fin m → Fin c) (sign : Fin m → Bool) (hbal : ∀ j b, 2 * (univ.filter fun v => B v j = b).card = n) (hmem : ∀ a v, a ∈ U v ↔ B v (label a) = sign a) : 7 ≤ c := by apply condorcet_balanced_three_agree_seven_coordinates n c hn B hbal intro v w z obtain ⟨a,hv,hw,hz⟩ := condorcet_acyclic_three_sources_omit m n R U hroot hU v w z have hv' : B v (label a) ≠ sign a := fun h => hv ((hmem a v).mpr h) have hw' : B w (label a) ≠ sign a := fun h => hw ((hmem a w).mpr h) have hz' : B z (label a) ≠ sign a := fun h => hz ((hmem a z).mpr h) have hbool : ∀ x y b : Bool, x ≠ b → y ≠ b → x = y := by decide exact ⟨label a,hbool _ _ _ hv' hw',hbool _ _ _ hw' hz'⟩