condorcet_stationary_telescoping_general
On an arbitrary finite three-successor transition graph, suppose a natural potential has local conservation lower bound K against scale C times a natural score, with K positive and C at most twice K. Every natural stationary weighting then has total weight at most twice its weighted score. This generalizes the existing56-state helper to any number of states.
Statement
theorem condorcet_stationary_telescoping_general (q C K : ℕ) (hK : 0 < K) (hCK : C ≤ 2*K) (next : Fin q → Fin 3 → Fin q) (p score w : Fin q → ℕ) (hlocal : ∀ i, K+3*p i ≤ C*score i+∑ k : Fin 3, p (next i k)) (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
- IN-341 generic supporting algebra for the OP-19 tournament-consistent stationarity diagnostic. Generalizes condorcet_stationary_telescoping_bound from56 states to arbitrary q; no new election result or research advance.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- condorcet_tournament_stationary_restriction_obstructionThere is a complete outside-challenger selector on all1771 three-element subsets of23 candidates such that every challenger dominates…
The proof, explained
The theorem bounds the total stationary weight on any finite 3-regular transition graph by twice the weighted score when a local conservation lower bound holds. Taking the inner product of the local conservation inequality with the stationary weight vector w, the potential terms 3 * ∑ p(i) * w(i) and ∑ p(next(i, k)) * w(i) telescope and cancel each other out identically thanks to the stationarity of w. This leaves K * ∑ w(i) ≤ C * ∑ score(i) * w(i), from which the bound C ≤ 2 * K and the positivity K > 0 directly yield ∑ w(i) ≤ 2 * ∑ score(i) * w(i).
The sum over all states j of p(j) times the total weight entering j equals the sum over all transitions (i, k) of p(next(i, k)) * w(i).
Distribute p(j) into the inner sum using mul_sum, interchange the sum over j with the sums over i and k using sum_comm, and push p(j) inside the indicator. The sum over j of the indicator if next(i, k) = j then p(j) * w(i) else 0 collapses via sum_ite_eq to p(next(i, k)) * w(i).
uses
mul_sum,sum_comm,sum_congr,sum_ite_eqprivate theorem condorcet_stationary_telescoping_general_swap {q : ℕ} (next : Fin q → Fin 3 → Fin q) (p w : Fin q → ℕ) : (∑ j, p j * ∑ i, ∑ k : Fin 3, if next i k = j then w i else 0) = ∑ i, ∑ k : Fin 3, p (next i k) * w i := by open Finset in simp_rw [mul_sum] rw [sum_comm] refine sum_congr rfl fun i _ => ?_ rw [sum_comm] refine sum_congr rfl fun k _ => ?_ rw [show (∑ x, p x * (if next i k = x then w i else 0)) = ∑ x, (if next i k = x then p x * w i else 0) by refine sum_congr rfl fun x _ => ?_ by_cases h : next i k = x <;> simp [h]] rw [sum_ite_eq] simp
The weighted potential 3 * ∑ i, p(i) * w(i) equals the total outgoing potential sum ∑ i, ∑ k, p(next(i, k)) * w(i).
Rewrite 3 * p(i) * w(i) as p(i) * (3 * w(i)) by ring commutativity, substitute the stationarity condition 3 * w(i) = ∑ j, ∑ k, (if next(j, k) = i then w(j) else 0), and apply the swap lemma condorcet_stationary_telescoping_general_swap.
uses
sum_congr,condorcet_stationary_telescoping_general_swaptheorem condorcet_stationary_telescoping_general (q C K : ℕ) (hK : 0 < K) (hCK : C ≤ 2*K) (next : Fin q → Fin 3 → Fin q) (p score w : Fin q → ℕ) (hlocal : ∀ i, K+3*p i ≤ C*score i+∑ k : Fin 3, p (next i k)) (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_general_swap next p w
Summing the local conservation lower bound weighted by w(i) gives ∑ i, (K + 3 * p(i)) * w(i) ≤ ∑ i, (C * score(i) + ∑ k, p(next(i, k))) * w(i).
Multiply each side of the local bound hlocal(i) by w(i) on the right using Nat.mul_le_mul_right, and sum the resulting inequalities over all states i using Finset.sum_le_sum.
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)
Both sides of the weighted inequality expand into a primary term plus the potential term: the left-hand side is K * (∑ i, w(i)) + ∑ i, 3 * p(i) * w(i) and the right-hand side is C * (∑ i, score(i) * w(i)) + ∑ i, ∑ k, p(next(i, k)) * w(i).
Distribute multiplication over addition using add_mul, separate the sums with sum_add_distrib, and factor out constants K and C using mul_sum, sum_mul, and mul_assoc.
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]
Canceling the equal potential terms from both sides yields K * (∑ i, w(i)) ≤ C * (∑ i, score(i) * w(i)).
Substitute the expanded forms of the left- and right-hand sides and the potential telescoping identity h_pot into the weighted inequality. The potential terms on both sides match and are canceled by Nat.le_of_add_le_add_right.
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
The total stationary weight is at most twice the weighted score: ∑ i, w(i) ≤ 2 * ∑ i, score(i) * w(i).
Since C ≤ 2 * K, multiplying by the weighted score gives C * (∑ i, score(i) * w(i)) ≤ (2 * K) * (∑ i, score i * w(i)). Transitivity yields K * (∑ i, w(i)) ≤ K * (2 * ∑ i, score(i) * w(i)), and canceling the factor K > 0 on the left using Nat.le_of_mul_le_mul_left produces the desired bound.
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 distributes over finite sums from the left: a * ∑ i, f i = ∑ i, a * f i.
sum_comm- The order of two finite summations can be exchanged: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
sum_congr- Two finite sums over the same index set are equal if their summands are equal at every point.
sum_ite_eq- Summing an equality indicator over a finite set collapses to the value at that element if it belongs to the set, and 0 otherwise.
condorcet_stationary_telescoping_general_swap- For any transition function, weights, and potential, swapping the summation order equates the potential weighted by incoming flow to the sum over all transitions of outgoing potential times source weight.
Finset.sum_le_sum- If f i ≤ g i for all i in a finite set, then the sum of f is at most the sum of g.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers on the right by a natural number preserves the inequality: if n ≤ m then n * k ≤ m * k.
add_mul- Multiplication distributes over addition from the right: (a + b) * c = a * c + b * c.
sum_add_distrib- A finite sum of sums splits into the sum of the two sums: ∑ x, (f x + g x) = (∑ x, f x) + (∑ x, g x).
sum_mul- Multiplication distributes over finite sums from the right: (∑ 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- A common additive term can be canceled from the right of an inequality of natural numbers: if a + b ≤ c + b, then a ≤ c.
Nat.le_of_mul_le_mul_left- A strictly positive common factor can be canceled from the left of an inequality of natural numbers: if c * a ≤ c * b and 0 < c, then a ≤ b.
- The helper lemma `condorcet_stationary_telescoping_general_swap` is proved by interchanging finite sums and collapsing an indicator function using `sum_ite_eq`.
- Standard algebraic rearrangements such as associativity and commutativity of multiplication are handled by the `ring` tactic.
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.
private theorem condorcet_stationary_telescoping_general_swap {q : ℕ} (next : Fin q → Fin 3 → Fin q) (p w : Fin q → ℕ) : (∑ j, p j * ∑ i, ∑ k : Fin 3, if next i k = j then w i else 0) = ∑ i, ∑ k : Fin 3, p (next i k) * w i := by open Finset in simp_rw [mul_sum] rw [sum_comm] refine sum_congr rfl fun i _ => ?_ rw [sum_comm] refine sum_congr rfl fun k _ => ?_ rw [show (∑ x, p x * (if next i k = x then w i else 0)) = ∑ x, (if next i k = x then p x * w i else 0) by refine sum_congr rfl fun x _ => ?_ by_cases h : next i k = x <;> simp [h]] rw [sum_ite_eq] simptheorem condorcet_stationary_telescoping_general (q C K : ℕ) (hK : 0 < K) (hCK : C ≤ 2*K) (next : Fin q → Fin 3 → Fin q) (p score w : Fin q → ℕ) (hlocal : ∀ i, K+3*p i ≤ C*score i+∑ k : Fin 3, p (next i k)) (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_general_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