AFTD Auto-Formalizing Theoretical Domains

condorcet_permutation_negative_closed_walk

theoremverified

For a permutation of a finite type and real costs with strictly negative total, some point has a nonempty periodic orbit segment of strictly negative summed cost. Repetition of an orbit is allowed; no simple-cycle claim is made.

Statement

theorem condorcet_permutation_negative_closed_walk
    {V : Type*} [Fintype V] (e : Equiv.Perm V) (c : V → ℝ)
    (hc : (∑ x, c x) < 0) :
    ∃ l : ℕ, 0 < l ∧ ∃ x : V,
      (e^l) x = x ∧ (∑ i ∈ range l, c ((e^i) x)) < 0
Source
IN-380, OP-19 campaign session8, 2026-10-30. Supporting reduction from the proved strict-half circulation bridge. Scratch ClosedWalk.lean passed trusted-axiom checking. Standard finite matching and orbit averaging; no research novelty or new election bound is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof chooses $l$ to be the group-theoretic order of the permutation $e$ on the finite set $V$. Exchanging the order of summation and using the fact that each power $e^i$ is a bijection shows that the sum of the $l$-step trajectory costs over all vertices equals $l$ times the total vertex cost. Since $l > 0$ and the total vertex cost is negative, the grand sum is negative, so by an averaging argument, at least one vertex $x$ must have a strictly negative trajectory cost. Because $l$ is the order of $e$, $e^l(x) = x$, producing the desired negative closed walk.

  1. Let $l$ be the order of $e$ in the permutation group of $V$; then $l > 0$.

    Because $V$ is a finite type, its permutation group is finite. In any finite group, every element has a strictly positive finite order, so setting $l = \operatorname{orderOf}(e)$ gives $l > 0$ by `orderOf_pos`.

    lines 11–13

    uses orderOf_pos

      classical
      let l := orderOf e
      have hl : 0 < l := orderOf_pos e
  2. The sum over all vertices of the $l$-step trajectory cost, $\sum_{x \in V} \sum_{i=0}^{l-1} c(e^i(x))$, equals $l \sum_{x \in V} c(x)$.

    Flipping the order of summation using `sum_comm` rewrites the expression as $\sum_{i=0}^{l-1} \sum_{x \in V} c(e^i(x))$. Since each power $e^i$ is a permutation of $V$, reindexing the inner sum by $e^i$ via `Equiv.sum_comp` leaves it equal to $\sum_{x \in V} c(x)$ for each $i$. Summing this identical value over the $l$ terms of the range $\{0, \dots, l-1\}$ simplifies to $l \sum_{x \in V} c(x)$.

    lines 14–17

    uses sum_comm, Equiv.sum_comp

      have hsum : (∑ x, ∑ i ∈ range l, c ((e^i) x)) = (l : ℝ) * ∑ x, c x := by
        rw [sum_comm]
        simp only [Equiv.sum_comp]
        simp
  3. The total trajectory sum $\sum_{x \in V} \sum_{i=0}^{l-1} c(e^i(x))$ is strictly negative.

    Substituting the identity from the previous step reduces the sum to $l \cdot \sum_{x \in V} c(x)$. Since $l > 0$ and the total cost $\sum_{x \in V} c(x) < 0$ by hypothesis, their product is strictly negative by `mul_neg_of_pos_of_neg`.

    lines 18–20

    uses mul_neg_of_pos_of_neg

      have hneg : (∑ x, ∑ i ∈ range l, c ((e^i) x)) < 0 := by
        rw [hsum]
        exact mul_neg_of_pos_of_neg (by exact_mod_cast hl) hc
  4. There exists a vertex $x \in V$ with strictly negative trajectory cost $\sum_{i=0}^{l-1} c(e^i(x)) < 0$.

    We argue by contradiction: if every vertex $x \in V$ satisfied $\sum_{i=0}^{l-1} c(e^i(x)) \ge 0$, then summing these non-negative quantities over all $x \in V$ would yield a non-negative total by `sum_nonneg`. But the total sum was already proven to be strictly negative; linear arithmetic (`linarith`) derives the contradiction.

    lines 21–25

    uses sum_nonneg

      obtain ⟨x,hx⟩ : ∃ x, (∑ i ∈ range l, c ((e^i) x)) < 0 := by
        by_contra hbad
        push_neg at hbad
        have hnon : 0 ≤ ∑ x, ∑ i ∈ range l, c ((e^i) x) := sum_nonneg (fun x _ => hbad x)
        linarith
  5. The witnesses $l$ and $x$ satisfy $l > 0$, $(e^l)(x) = x$, and $\sum_{i=0}^{l-1} c(e^i(x)) < 0$.

    We provide $l$, the positivity proof $hl$, the witness vertex $x$, and its negative trajectory cost $hx$. It remains only to check $(e^l)(x) = x$. Because $l = \operatorname{orderOf}(e)$, we have $e^l = 1$ by `pow_orderOf_eq_one`, so $e^l$ fixes every element of $V$, including $x$.

    lines 26–27

    uses pow_orderOf_eq_one

      refine ⟨l,hl,x,?_,hx⟩
      simp [l,pow_orderOf_eq_one]
orderOf_pos
In a finite cancellative monoid, every element has strictly positive order.
sum_comm
The order of summation in a double finite sum can be exchanged without changing the result.
Equiv.sum_comp
Summing a function over a finite type is invariant under reindexing by an equivalence (permutation).
mul_neg_of_pos_of_neg
The product of a strictly positive element and a strictly negative element is strictly negative.
sum_nonneg
A finite sum whose terms are all non-negative is non-negative.
pow_orderOf_eq_one
Raising a monoid element to the power of its order yields the identity element.

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_permutation_negative_closed_walk    {V : Type*} [Fintype V] (e : Equiv.Perm V) (c : V → ℝ)    (hc : (∑ x, c x) < 0) :    ∃ l : ℕ, 0 < l ∧ ∃ x : V,      (e^l) x = x ∧ (∑ i ∈ range l, c ((e^i) x)) < 0 := by  classical  let l := orderOf e  have hl : 0 < l := orderOf_pos e  have hsum : (∑ x, ∑ i ∈ range l, c ((e^i) x)) = (l : ℝ) * ∑ x, c x := by    rw [sum_comm]    simp only [Equiv.sum_comp]    simp  have hneg : (∑ x, ∑ i ∈ range l, c ((e^i) x)) < 0 := by    rw [hsum]    exact mul_neg_of_pos_of_neg (by exact_mod_cast hl) hc  obtain ⟨x,hx⟩ : ∃ x, (∑ i ∈ range l, c ((e^i) x)) < 0 := by    by_contra hbad    push_neg at hbad    have hnon : 0 ≤ ∑ x, ∑ i ∈ range l, c ((e^i) x) := sum_nonneg (fun x _ => hbad x)    linarith  refine ⟨l,hl,x,?_,hx⟩  simp [l,pow_orderOf_eq_one]
See it in the graphDiscuss this resultChallenge it