condorcet_stationary_telescoping_bound
On any 3-regular directed transition graph on 56 vertices, if a potential vector p and positive bound K satisfy K + 3 * p i <= C * score i + sum_k p(next i k) for all i, and C <= 2 * K, then every nonnegative integer stationary weighting w satisfies sum w <= 2 * sum (score i * w i).
Statement
theorem condorcet_stationary_telescoping_bound (C K : ℕ) (hK : 0 < K) (hCK : C ≤ 2 * K) (next : Fin 56 → Fin 3 → Fin 56) (p : Fin 56 → ℕ) (score : Fin 56 → ℕ) (hlocal : ∀ i, K + 3 * p i ≤ C * score i + ∑ k : Fin 3, p (next i k)) (w : Fin 56 → ℕ) (hw : ∀ j, 3 * w j = ∑ i, ∑ k : Fin 3, if next i k = j then w i else 0) : (∑ i, w i) ≤ 2 * ∑ i, score i * w i
- Source
- step towards condorcet_stationary_weight_restriction_obstruction
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- condorcet_stationary_weight_restriction_obstructionThere exist an enumeration of all56 three-candidate subsets of eight candidates, an outside challenger for every triple, bijective member…
The proof, explained
The proof establishes that the total weighted potential ∑ i, 3 * p i * w i equals the total successor potential ∑ i, k, p (next i k) * w i under any stationary weighting w, by swapping summation order in the in-flow representation. Multiplying the local inequality K + 3 * p i ≤ C * score i + ∑ k, p (next i k) by w i and summing over all vertices i allows these identical potential terms to cancel from both sides, leaving K * ∑ w ≤ C * ∑ score * w. Finally, bounding C ≤ 2 * K and cancelling the strictly positive constant K produces the desired inequality ∑ w ≤ 2 * ∑ score * w.
The triple sum is rewritten so that the sums over i and k are on the outside and the sum over j is on the inside.
Using distributivity (`mul_sum`), the potential factor p j is moved inside the double summation over i and k. Swapping the summation order twice (`Finset.sum_comm`) moves the summation over j to the inside. By congruence (`Finset.sum_congr`), it suffices to evaluate the resulting inner sum over j for arbitrary fixed i and k.
uses
mul_sum,Finset.sum_comm,Finset.sum_congropen Finset in simp_rw [mul_sum] rw [Finset.sum_comm] refine Finset.sum_congr rfl fun i _ => ?_ rw [Finset.sum_comm] refine Finset.sum_congr rfl fun k _ => ?_
For fixed i and k, the summand p j * (if next i k = j then w i else 0) equals if next i k = j then p (next i k) * w i else 0 for every j.
We case-split on whether next i k = j. When next i k = j, substituting j into p j gives p (next i k) * w i. When next i k ≠ j, the term is p j * 0, which equals 0 by `mul_zero`.
uses
mul_zerohave : (fun j => p j * (if next i k = j then w i else 0)) = (fun j => if next i k = j then p (next i k) * w i else 0) := by funext j split_ifs with h · subst h; rfl · rw [mul_zero]
The inner sum over j evaluates to p (next i k) * w i, completing the proof of `condorcet_stationary_telescoping_bound_swap`.
Substituting the rewritten summand into the sum over all j in Fin 56, `Finset.sum_ite_eq` reduces the sum over the indicator for next i k = j to the single non-zero value p (next i k) * w i. Simplification closes the goal.
uses
Finset.sum_ite_eqrw [this] rw [Finset.sum_ite_eq] simp
Under the stationarity condition, the total weighted potential equals the total successor potential: ∑ i, 3 * p i * w i = ∑ i, ∑ k, p (next i k) * w i.
Rewriting 3 * p i * w i as p i * (3 * w i) and substituting the stationarity condition `hw`, the left-hand side becomes the sum over j of p j times the total in-flow to j. Applying `condorcet_stationary_telescoping_bound_swap` exchanges this for the sum over all edges (i, k) of p (next i k) * w i.
uses
sum_congr,condorcet_stationary_telescoping_bound_swapopen Finset in have h_pot : (∑ i, 3 * p i * w i) = ∑ i, ∑ k : Fin 3, p (next i k) * w i := by have h1 : (∑ i, 3 * p i * w i) = ∑ i, p i * (3 * w i) := by refine sum_congr rfl fun i _ => by ring rw [h1] simp_rw [hw] exact condorcet_stationary_telescoping_bound_swap next p w
Weighting the local inequality by w i and summing over all vertices i yields ∑ i, (K + 3 * p i) * w i ≤ ∑ i, (C * score i + ∑ k, p (next i k)) * w i.
For each vertex i, multiplying both sides of the local hypothesis K + 3 * p i ≤ C * score i + ∑ k, p (next i k) by w i preserves the inequality via `Nat.mul_le_mul_right`. Summing these inequalities over all vertices i using `Finset.sum_le_sum` gives the weighted sum inequality.
uses
Finset.sum_le_sum,Nat.mul_le_mul_righthave h_sum_le : (∑ i, (K + 3 * p i) * w i) ≤ ∑ i, (C * score i + ∑ k : Fin 3, p (next i k)) * w i := by refine Finset.sum_le_sum fun i _ => Nat.mul_le_mul_right (w i) (hlocal i)
The left-hand side expands to K * (∑ i, w i) + ∑ i, 3 * p i * w i and the right-hand side expands to C * (∑ i, score i * w i) + ∑ i, ∑ k, p (next i k) * w i.
Distributing multiplication over addition and sums (`add_mul`, `sum_add_distrib`, `sum_mul`, `mul_assoc`, `mul_sum`) isolates the primary terms from the potential terms on both sides of the inequality.
uses
add_mul,sum_add_distrib,mul_sum,sum_mul,mul_assochave h_lhs : (∑ i, (K + 3 * p i) * w i) = K * (∑ i, w i) + ∑ i, 3 * p i * w i := by open Finset in simp_rw [add_mul, sum_add_distrib, mul_sum] have h_rhs : (∑ i, (C * score i + ∑ k : Fin 3, p (next i k)) * w i) = C * (∑ i, score i * w i) + ∑ i, ∑ k : Fin 3, p (next i k) * w i := by open Finset in simp_rw [add_mul, sum_add_distrib, sum_mul, mul_assoc, mul_sum]
Cancelling the common potential sum from both sides leaves K * (∑ i, w i) ≤ C * (∑ i, score i * w i).
Substituting the expanded forms of the left- and right-hand sides into the weighted inequality, the potential terms ∑ i, 3 * p i * w i and ∑ i, ∑ k, p (next i k) * w i are equal by `h_pot`. Cancelling this identical additive term from both sides using `Nat.le_of_add_le_add_right` yields the simplified inequality.
uses
Nat.le_of_add_le_add_rightrw [h_lhs, h_rhs, h_pot] at h_sum_le have hKC : K * (∑ i, w i) ≤ C * (∑ i, score i * w i) := Nat.le_of_add_le_add_right h_sum_le
Using C ≤ 2 * K and K > 0, we conclude ∑ i, w i ≤ 2 * ∑ i, score i * w i.
Multiplying C ≤ 2 * K by ∑ i, score i * w i via `Nat.mul_le_mul_right` yields C * (∑ i, score i * w i) ≤ (2 * K) * (∑ i, score i * w i). Transitivity gives K * (∑ i, w i) ≤ K * (2 * ∑ i, score i * w i). Since K > 0, cancelling the multiplier K using `Nat.le_of_mul_le_mul_left` completes the proof.
uses
Nat.mul_le_mul_right,Nat.le_of_mul_le_mul_lefthave h1 : C * (∑ i, score i * w i) ≤ (2 * K) * (∑ i, score i * w i) := Nat.mul_le_mul_right (∑ i, score i * w i) hCK have h2 : K * (∑ i, w i) ≤ (2 * K) * (∑ i, score i * w i) := hKC.trans h1 have h3 : (2 * K) * (∑ i, score i * w i) = K * (2 * ∑ i, score i * w i) := by ring rw [h3] at h2 exact Nat.le_of_mul_le_mul_left h2 hK
mul_sum- Multiplication on the left distributes over a finite sum: a * ∑ i, f i = ∑ i, a * f i.
Finset.sum_comm- Fubini's theorem for finite sums: interchanging the order of summation in a double sum preserves the value.
Finset.sum_congr- Two finite sums are equal if their index sets are identical and their summands are equal at every element.
sum_congr- Two finite sums are equal if their index sets are identical and their summands are equal at every element.
mul_zero- Multiplying any number by zero gives zero: a * 0 = 0.
Finset.sum_ite_eq- Summing an indicator that tests equality to a fixed element a over a finite set evaluates to the value at a if a is in the set, and 0 otherwise.
condorcet_stationary_telescoping_bound_swap- Summing potential values over target vertices weighted by in-flows equals summing successor potentials weighted by source vertex weights.
Finset.sum_le_sum- If f i ≤ g i for all indices i in a finite set, then ∑ i, f i ≤ ∑ i, g i.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers on the right by a factor preserves the inequality: n ≤ m → n * k ≤ m * k.
add_mul- Multiplication on the right distributes over addition: (a + b) * c = a * c + b * c.
sum_add_distrib- The sum of a pointwise sum of two functions equals the sum of the first plus the sum of the second.
sum_mul- Multiplication on the right distributes over a finite sum: (∑ i, f i) * a = ∑ i, f i * a.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
Nat.le_of_add_le_add_right- Additive cancellation for inequalities on natural numbers: a + b ≤ c + b implies a ≤ c.
Nat.le_of_mul_le_mul_left- Cancellation of a strictly positive multiplier on natural numbers: c * a ≤ c * b and 0 < c imply a ≤ b.
- The proof begins with a helper lemma, `condorcet_stationary_telescoping_bound_swap`, which establishes that the double sum over in-flows weighted by target potentials equals the double sum over edges of target potentials weighted by source weights.
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.
lemma condorcet_stationary_telescoping_bound_swap (next : Fin 56 → Fin 3 → Fin 56) (p : Fin 56 → ℕ) (w : Fin 56 → ℕ) : (∑ j : Fin 56, p j * (∑ i : Fin 56, ∑ k : Fin 3, if next i k = j then w i else 0)) = ∑ i : Fin 56, ∑ k : Fin 3, p (next i k) * w i := by open Finset in simp_rw [mul_sum] rw [Finset.sum_comm] refine Finset.sum_congr rfl fun i _ => ?_ rw [Finset.sum_comm] refine Finset.sum_congr rfl fun k _ => ?_ have : (fun j => p j * (if next i k = j then w i else 0)) = (fun j => if next i k = j then p (next i k) * w i else 0) := by funext j split_ifs with h · subst h; rfl · rw [mul_zero] rw [this] rw [Finset.sum_ite_eq] simp/-- Telescoping conservation bound for stationary weights on a 3-regular graph. -/theorem condorcet_stationary_telescoping_bound (C K : ℕ) (hK : 0 < K) (hCK : C ≤ 2 * K) (next : Fin 56 → Fin 3 → Fin 56) (p : Fin 56 → ℕ) (score : Fin 56 → ℕ) (hlocal : ∀ i, K + 3 * p i ≤ C * score i + ∑ k : Fin 3, p (next i k)) (w : Fin 56 → ℕ) (hw : ∀ j, 3 * w j = ∑ i, ∑ k : Fin 3, if next i k = j then w i else 0) : (∑ i, w i) ≤ 2 * ∑ i, score i * w i := by open Finset in have h_pot : (∑ i, 3 * p i * w i) = ∑ i, ∑ k : Fin 3, p (next i k) * w i := by have h1 : (∑ i, 3 * p i * w i) = ∑ i, p i * (3 * w i) := by refine sum_congr rfl fun i _ => by ring rw [h1] simp_rw [hw] exact condorcet_stationary_telescoping_bound_swap next p w have h_sum_le : (∑ i, (K + 3 * p i) * w i) ≤ ∑ i, (C * score i + ∑ k : Fin 3, p (next i k)) * w i := by refine Finset.sum_le_sum fun i _ => Nat.mul_le_mul_right (w i) (hlocal i) have h_lhs : (∑ i, (K + 3 * p i) * w i) = K * (∑ i, w i) + ∑ i, 3 * p i * w i := by open Finset in simp_rw [add_mul, sum_add_distrib, mul_sum] have h_rhs : (∑ i, (C * score i + ∑ k : Fin 3, p (next i k)) * w i) = C * (∑ i, score i * w i) + ∑ i, ∑ k : Fin 3, p (next i k) * w i := by open Finset in simp_rw [add_mul, sum_add_distrib, sum_mul, mul_assoc, mul_sum] rw [h_lhs, h_rhs, h_pot] at h_sum_le have hKC : K * (∑ i, w i) ≤ C * (∑ i, score i * w i) := Nat.le_of_add_le_add_right h_sum_le have h1 : C * (∑ i, score i * w i) ≤ (2 * K) * (∑ i, score i * w i) := Nat.mul_le_mul_right (∑ i, score i * w i) hCK have h2 : K * (∑ i, w i) ≤ (2 * K) * (∑ i, score i * w i) := hKC.trans h1 have h3 : (2 * K) * (∑ i, score i * w i) = K * (2 * ∑ i, score i * w i) := by ring rw [h3] at h2 exact Nat.le_of_mul_le_mul_left h2 hK