condorcet_heavy_pair_acyclic_cover_potential_break
For any finite S3 relation, any nonnegative weighted family of induced acyclic sets and real vertex potential has an arrow violating the half-cover potential inequality whenever two distinct coefficients carry at least half the total weight and a third distinct coefficient is positive.
Statement
theorem condorcet_heavy_pair_acyclic_cover_potential_break (m n : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (d : Fin n → ℝ) (q : Fin m → ℝ) (i j k : Fin n) (hij : i ≠ j) (hik : i ≠ k) (hjk : j ≠ k) (hd : ∀ v, 0 ≤ d v) (hk : 0 < d k) (hheavy : (∑ v, d v) ≤ 2*(d i+d j)) (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)) : ∃ a b, R a b ∧ 2 * (∑ v, if a ∈ U v then d v else 0) + q a < (∑ v, d v) + q b
- Source
- IN-380, OP-19 campaign session8, 2026-10-30. FourCoverPotential.lean. Structural support constraint on the new equivalent main route. No new election bound or research novelty is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- condorcet_nonpositive_potential_acyclicOn a finite directed relation, a vertex set with nonpositive costs is acyclic if a potential drops along arrows by at least the source…
- 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…
- Used by 1
- condorcet_four_acyclic_sets_potential_breakFor every finite S3 relation, every four induced acyclic sets with arbitrary strictly positive real coefficients and every real vertex…
The proof, explained
We argue by contradiction, assuming that no arrow violates the half-cover potential inequality, so that the potential q acts as a Lyapunov-like function with drift c(a) = 2 p(a) - T. Because the heavy pair {i, j} carries at least half the total weight, the drift is nonpositive on the complement A = univ \ (U i ∪ U j), and any point where the drift vanishes must belong to U k because d k > 0. The acyclicity criterion condorcet_nonpositive_potential_acyclic then implies that A is acyclic under R. Finally, the S3 property applied to the three acyclic sets U i, U j, and A yields a vertex omitted by all three, which contradicts the definition of A as the complement of U i ∪ U j.
Assume for contradiction that no arrow violates the potential inequality, and define the cover weight, total weight, complement set, and drift function.
We assume for contradiction that for every arrow a → b (R a b), the inequality fails, meaning (∑ v, d v) + q b ≤ 2 p(a) + q a, or q b ≤ q a + (2 p(a) - T). We set up the cover weight p(a) = ∑_{v : a ∈ U v} d v, the total weight T = ∑ v, d v, the complement set A = univ \ (U i ∪ U j), and the drift function c(a) = 2 p(a) - T.
classical by_contra hbad push_neg at hbad let p : Fin m → ℝ := fun a => ∑ v, if a ∈ U v then d v else 0 let T : ℝ := ∑ v, d v let A := univ \ (U i ∪ U j) let c : Fin m → ℝ := fun a => 2*p a-T
For any vertex a and index set I disjoint from the sets containing a, p(a) + ∑_{v ∈ I} d v ≤ T.
We prove the accounting lemma hmass. Using Fintype.sum_ite_mem to write the sum over I as a full sum with an indicator function and sum_add_distrib to combine the two sums, it suffices by sum_le_sum to verify the inequality term-by-term for each index v. For v ∈ I, the vertex a cannot belong to U v by hypothesis, so the summand is 0 + d v ≤ d v. For v ∉ I, the second indicator is 0, and the first is at most d v since d v ≥ 0.
uses
Fintype.sum_ite_mem,sum_add_distrib,sum_le_sumhave hmass (a : Fin m) (I : Finset (Fin n)) (hI : ∀ v ∈ I, a ∉ U v) : p a + (∑ v ∈ I, d v) ≤ T := by rw [← Fintype.sum_ite_mem I d] change (∑ v, if a ∈ U v then d v else 0) + (∑ v, if v ∈ I then d v else 0) ≤ ∑ v, d v rw [← sum_add_distrib] apply sum_le_sum intro v hv by_cases hvI : v ∈ I · simp [hvI,hI v hvI] · by_cases ha : a ∈ U v <;> simp [hvI,ha,hd v]
The induced subgraph on the complement A = univ \ (U i ∪ U j) is acyclic (well-founded under R).
We apply condorcet_nonpositive_potential_acyclic with set A, helper set U k, drift c, and potential q. This requires four conditions: 1. Nonpositive drift on A: every a ∈ A lies outside U i and U j. Applying hmass to {i, j} via mem_insert, mem_singleton, and sum_pair gives p(a) + d i + d j ≤ T. Since T ≤ 2 (d i + d j) by hheavy, linear arithmetic shows c(a) = 2 p(a) - T ≤ 0. 2. Zero drift implies membership in U k: if a ∈ A satisfies c(a) = 0 and we assume for contradiction a ∉ U k, then a lies outside {i, j, k}. Applying hmass to {i, j, k} gives p(a) + d i + d j + d k ≤ T. Together with 2 p(a) = T, T ≤ 2 (d i + d j), and d k > 0, linear arithmetic yields a contradiction. 3. Edge drift condition: for any arrow R a b with a, b ∈ A, the contradiction hypothesis rearranges to q b ≤ q a + c(a). 4. Helper set acyclicity: U k is acyclic by assumption hU k. These four facts together imply that A is well-founded under R.
uses
condorcet_nonpositive_potential_acyclic,mem_insert,mem_singleton,sum_pairhave hA : WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) := by apply condorcet_nonpositive_potential_acyclic m R A (U k) c q · intro a ha have hnot : a ∉ U i ∧ a ∉ U j := by simpa [A] using ha have hp := hmass a {i,j} (by intro v hv simp only [mem_insert,mem_singleton] at hv rcases hv with rfl|rfl · exact hnot.1 · exact hnot.2) simp only [sum_pair hij] at hp change 2*p a-T ≤ 0 change T ≤ 2*(d i+d j) at hheavy linarith · intro a ha hz by_contra hak have hnot : a ∉ U i ∧ a ∉ U j := by simpa [A] using ha have hp := hmass a {i,j,k} (by intro v hv simp only [mem_insert,mem_singleton] at hv rcases hv with rfl|rfl|rfl · exact hnot.1 · exact hnot.2 · exact hak) simp [hij,hik,hjk] at hp change 2*p a-T = 0 at hz change T ≤ 2*(d i+d j) at hheavy linarith · intro a b ha hb hab have hh := hbad a b hab change (∑ v, d v) + q b ≤ 2*p a+q a at hh change q b ≤ q a+(2*p a-T) dsimp only [T] linarith · exact hU k
The three-element family V = ![U i, U j, A] consists entirely of acyclic sets.
We define the three-element family V with V(0) = U i, V(1) = U j, and V(2) = A. A case split on v ∈ Fin 3 shows that every set in V is acyclic under R: the first two by hypotheses hU i and hU j, and the third by the lemma hA proved in the previous step.
let V : Fin 3 → Finset (Fin m) := ![U i,U j,A] have hV : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ V v} => R a.val b.val) := by intro v fin_cases v · exact hU i · exact hU j · exact hA
Contradiction: the S3 property provides a vertex outside U i, U j, and A, but any vertex outside U i ∪ U j belongs to A.
Applying condorcet_acyclic_three_sources_omit to the three acyclic sets in V yields a vertex a that belongs to none of them. Because a ∉ U i and a ∉ U j (combined with And.intro), by definition a ∈ univ \ (U i ∪ U j) = A. This contradicts a ∉ A and concludes the proof.
uses
condorcet_acyclic_three_sources_omit,And.introobtain ⟨a,ha0,ha1,ha2⟩ := condorcet_acyclic_three_sources_omit m 3 R V hroot hV 0 1 2 have haA : a ∈ A := by simpa [A,V] using And.intro ha0 ha1 exact ha2 haA
And.intro- Given proofs of two propositions, constructs a proof of their conjunction.
condorcet_acyclic_three_sources_omit- In an S3 relation, given any family of acyclic sets, any three sets in the family omit at least one common vertex.
condorcet_nonpositive_potential_acyclic- An induced subgraph on A is acyclic if there is a function c ≤ 0 on A whose zeros lie in an acyclic set B, and along every arrow in A the potential q satisfies q(b) ≤ q(a) + c(a).
Fintype.sum_ite_mem- For a finite type and a subset s, the sum over all elements of the indicator function of s equals the sum restricted to s.
mem_insert- An element belongs to the insertion of an element into a set if and only if it equals the inserted element or already belongs to the set.
mem_singleton- An element belongs to a singleton set if and only if it is equal to the single element.
sum_add_distrib- The sum of a sum of two functions over a finite set equals the sum of the first plus the sum of the second.
sum_le_sum- A sum of terms is less than or equal to another sum if the inequality holds term-by-term.
sum_pair- The sum of a function over an unordered pair of distinct elements is the sum of the values at those two elements.
- Linear inequalities over the weights, drift, and potentials are discharged using `linarith`.
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_heavy_pair_acyclic_cover_potential_break (m n : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (d : Fin n → ℝ) (q : Fin m → ℝ) (i j k : Fin n) (hij : i ≠ j) (hik : i ≠ k) (hjk : j ≠ k) (hd : ∀ v, 0 ≤ d v) (hk : 0 < d k) (hheavy : (∑ v, d v) ≤ 2*(d i+d j)) (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)) : ∃ a b, R a b ∧ 2 * (∑ v, if a ∈ U v then d v else 0) + q a < (∑ v, d v) + q b := by classical by_contra hbad push_neg at hbad let p : Fin m → ℝ := fun a => ∑ v, if a ∈ U v then d v else 0 let T : ℝ := ∑ v, d v let A := univ \ (U i ∪ U j) let c : Fin m → ℝ := fun a => 2*p a-T have hmass (a : Fin m) (I : Finset (Fin n)) (hI : ∀ v ∈ I, a ∉ U v) : p a + (∑ v ∈ I, d v) ≤ T := by rw [← Fintype.sum_ite_mem I d] change (∑ v, if a ∈ U v then d v else 0) + (∑ v, if v ∈ I then d v else 0) ≤ ∑ v, d v rw [← sum_add_distrib] apply sum_le_sum intro v hv by_cases hvI : v ∈ I · simp [hvI,hI v hvI] · by_cases ha : a ∈ U v <;> simp [hvI,ha,hd v] have hA : WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) := by apply condorcet_nonpositive_potential_acyclic m R A (U k) c q · intro a ha have hnot : a ∉ U i ∧ a ∉ U j := by simpa [A] using ha have hp := hmass a {i,j} (by intro v hv simp only [mem_insert,mem_singleton] at hv rcases hv with rfl|rfl · exact hnot.1 · exact hnot.2) simp only [sum_pair hij] at hp change 2*p a-T ≤ 0 change T ≤ 2*(d i+d j) at hheavy linarith · intro a ha hz by_contra hak have hnot : a ∉ U i ∧ a ∉ U j := by simpa [A] using ha have hp := hmass a {i,j,k} (by intro v hv simp only [mem_insert,mem_singleton] at hv rcases hv with rfl|rfl|rfl · exact hnot.1 · exact hnot.2 · exact hak) simp [hij,hik,hjk] at hp change 2*p a-T = 0 at hz change T ≤ 2*(d i+d j) at hheavy linarith · intro a b ha hb hab have hh := hbad a b hab change (∑ v, d v) + q b ≤ 2*p a+q a at hh change q b ≤ q a+(2*p a-T) dsimp only [T] linarith · exact hU k let V : Fin 3 → Finset (Fin m) := ![U i,U j,A] have hV : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ V v} => R a.val b.val) := by intro v fin_cases v · exact hU i · exact hU j · exact hA obtain ⟨a,ha0,ha1,ha2⟩ := condorcet_acyclic_three_sources_omit m 3 R V hroot hV 0 1 2 have haA : a ∈ A := by simpa [A,V] using And.intro ha0 ha1 exact ha2 haA