AFTD Auto-Formalizing Theoretical Domains

condorcet_stationary_telescoping_general

theoremverified

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

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

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

    lines 1–16

    uses mul_sum, sum_comm, sum_congr, sum_ite_eq

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

    lines 17–30

    uses sum_congr, condorcet_stationary_telescoping_general_swap

    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 := 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
  3. 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.

    lines 31–33

    uses Finset.sum_le_sum, Nat.mul_le_mul_right

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

    lines 34–38

    uses add_mul, sum_add_distrib, mul_sum, sum_mul, mul_assoc

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

    lines 39–41

    uses Nat.le_of_add_le_add_right

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

    lines 42–47

    uses Nat.mul_le_mul_right, Nat.le_of_mul_le_mul_left

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

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

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