condorcet_four_acyclic_sets_potential_break
For every finite S3 relation, every four induced acyclic sets with arbitrary strictly positive real coefficients and every real vertex potential have an arrow violating the weighted half-cover potential inequality. This excludes four positive support sets in this certificate format, without bounding the support needed in the main conjecture.
Statement
theorem condorcet_four_acyclic_sets_potential_break (m : ℕ) (R : Fin m → Fin m → Prop) (U : Fin 4 → Finset (Fin m)) (d : Fin 4 → ℝ) (h : Fin m → ℝ) (hd : ∀ v, 0 < d v) (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) + h a < (∑ v, d v) + h 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 1
- 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…
The proof, explained
The proof partitions the four acyclic sets into two pairs, $\{0, 1\}$ and $\{2, 3\}$. By comparing their weights, at least one pair must be 'heavy'—meaning its weight sum is at least half of the total weight across all four sets. In either case, the result follows by applying `condorcet_heavy_pair_acyclic_cover_potential_break` with the heavy pair and a third distinct index with positive weight.
It suffices to prove the existence of a violating arrow in two cases: either $d(2) + d(3) \le d(0) + d(1)$ or $d(0) + d(1) < d(2) + d(3)$.
Using classical logic, we split into cases depending on whether the pair $\{0, 1\}$ has at least as much total weight as the pair $\{2, 3\}$.
classical by_cases hpair : d 2+d 3 ≤ d 0+d 1A violating arrow exists when $d(2) + d(3) \le d(0) + d(1)$.
Since $d(2) + d(3) \le d(0) + d(1)$, the pair $\{0, 1\}$ carries at least half the total weight: $d(0) + d(1) + d(2) + d(3) \le 2(d(0) + d(1))$. We invoke `condorcet_heavy_pair_acyclic_cover_potential_break` with heavy pair $i = 0, j = 1$ and a third index $k = 2$. The index distinctness conditions ($0 \neq 1$, $0 \neq 2$, $1 \neq 2$) are checked by computation, the positivity and acyclicity hypotheses are supplied directly, and the heavy-pair inequality is verified by expanding the sum over `Fin 4` with `Fin.sum_univ_four` followed by linear arithmetic.
uses
condorcet_heavy_pair_acyclic_cover_potential_break,Fin.sum_univ_four· refine condorcet_heavy_pair_acyclic_cover_potential_break m 4 R U d h 0 1 2 (by decide) (by decide) (by decide) (fun v => (hd v).le) (hd 2) ?_ hroot hU simp only [Fin.sum_univ_four] linarith
A violating arrow exists when $d(0) + d(1) < d(2) + d(3)$.
When $d(2) + d(3) > d(0) + d(1)$, the pair $\{2, 3\}$ instead carries at least half the total weight: $d(0) + d(1) + d(2) + d(3) \le 2(d(2) + d(3))$. Symmetrically, we invoke `condorcet_heavy_pair_acyclic_cover_potential_break` with heavy pair $i = 2, j = 3$ and third index $k = 0$. The distinctness conditions ($2 \neq 3$, $2 \neq 0$, $3 \neq 0$) are checked by computation, the remaining hypotheses come from the assumptions, and the heavy-pair inequality is closed by expanding the sum with `Fin.sum_univ_four` and linear arithmetic.
uses
condorcet_heavy_pair_acyclic_cover_potential_break,Fin.sum_univ_four· refine condorcet_heavy_pair_acyclic_cover_potential_break m 4 R U d h 2 3 0 (by decide) (by decide) (by decide) (fun v => (hd v).le) (hd 0) ?_ hroot hU simp only [Fin.sum_univ_four] linarith
condorcet_heavy_pair_acyclic_cover_potential_break- In a tournament relation where every subset of at most 3 vertices has an in-dominating root, if a family of acyclic sets has a 'heavy pair' of indices whose combined weight is at least half the total weight, and another distinct index has positive weight, then there exists an arrow violating the potential inequality.
Fin.sum_univ_four- The sum of a function $f$ over the four-element type `Fin 4` is equal to $f(0) + f(1) + f(2) + f(3)$.
- The distinctness checks between indices in `Fin 4` (such as $0 \ne 1$ and $2 \ne 3$) are discharged automatically via `decide` as finite computational checks.
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_four_acyclic_sets_potential_break (m : ℕ) (R : Fin m → Fin m → Prop) (U : Fin 4 → Finset (Fin m)) (d : Fin 4 → ℝ) (h : Fin m → ℝ) (hd : ∀ v, 0 < d v) (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) + h a < (∑ v, d v) + h b := by classical by_cases hpair : d 2+d 3 ≤ d 0+d 1 · refine condorcet_heavy_pair_acyclic_cover_potential_break m 4 R U d h 0 1 2 (by decide) (by decide) (by decide) (fun v => (hd v).le) (hd 2) ?_ hroot hU simp only [Fin.sum_univ_four] linarith · refine condorcet_heavy_pair_acyclic_cover_potential_break m 4 R U d h 2 3 0 (by decide) (by decide) (by decide) (fun v => (hd v).le) (hd 0) ?_ hroot hU simp only [Fin.sum_univ_four] linarith