AFTD Auto-Formalizing Theoretical Domains

condorcet_heavy_pair_acyclic_cover_potential_break

theoremverified

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

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.

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

    lines 18–24

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

    lines 25–34

    uses Fintype.sum_ite_mem, sum_add_distrib, sum_le_sum

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

    lines 35–69

    uses condorcet_nonpositive_potential_acyclic, mem_insert, mem_singleton, sum_pair

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

    lines 70–76

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

    lines 77–79

    uses condorcet_acyclic_three_sources_omit, And.intro

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

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