AFTD Auto-Formalizing Theoretical Domains

four_vertex_balanced_cost_nonneg

theoremverified

On four vertices, a balanced edge weighting, nonnegative away from the diagonal, assigns nonnegative total cost whenever every closed four-step walk has nonnegative cost and loops cost zero.

Statement

theorem four_vertex_balanced_cost_nonneg (w c : Fin 4 → Fin 4 → ℝ)
    (hw : ∀ i j, i ≠ j → 0 ≤ w i j)
    (hb : ∀ i, ∑ j, w i j = ∑ j, w j i)
    (hd : ∀ i, c i i = 0)
    (hc : ∀ i j k l, 0 ≤ c i j + c j k + c k l + c l i) :
    0 ≤ ∑ i, ∑ j, w i j * c i j
Source
Sector-bound formalization for IN-166; arXiv:math/0508176, Theorem 5.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • four_vertex_cycle_cost_potentialIf every closed four-step walk on four vertices has nonnegative cost and loops cost zero, a real vertex potential makes every reduced edge…
Used by 1

The proof, explained

The argument introduces a vertex potential p to adjust edge costs into nonnegative reduced costs without altering the total circulation cost. By four_vertex_cycle_cost_potential, the nonnegativity of four-step cycles and the vanishing of loop costs guarantee that such a potential exists, ensuring c i j + p i - p j ≥ 0 for all edges. Because the edge weighting w is balanced at every vertex, the weighted sum of potential differences vanishes globally. Consequently, the total weighted cost equals the sum of the nonnegative reduced costs weighted by w, which is therefore nonnegative.

  1. There exists a vertex potential p on Fin 4 such that p j ≤ p i + c i j for all vertices i and j.

    Because loops cost zero (hd) and all four-step closed walks have nonnegative total cost (hc), the helper theorem four_vertex_cycle_cost_potential provides a potential function p : Fin 4 → ℝ satisfying p j ≤ p i + c i j for every pair of vertices.

    line 7

    uses four_vertex_cycle_cost_potential

      obtain ⟨p, hp⟩ := four_vertex_cycle_cost_potential c hd hc
  2. The total weighted potential difference vanishes: ∑ i, ∑ j, w i j * (p i - p j) = 0.

    Distributing the multiplication with mul_sub and splitting the sum with Finset.sum_sub_distrib, sub_eq_zero reduces the claim to showing that ∑ i, ∑ j, w i j * p i = ∑ i, ∑ j, w i j * p j. Factoring out p i via Finset.sum_mul gives ∑ i, (∑ j, w i j) * p i. By the balance condition (hb), each row sum ∑ j, w i j equals the corresponding column sum ∑ j, w j i. Multiplying back through with Finset.sum_mul and interchanging the two sums with Finset.sum_comm yields ∑ i, ∑ j, w i j * p j, which completes the equality.

    lines 8–16

    uses mul_sub, Finset.sum_sub_distrib, sub_eq_zero, Finset.sum_mul, Finset.sum_comm

      have hcancel : (∑ i, ∑ j, w i j * (p i - p j)) = 0 := by
        simp_rw [mul_sub, Finset.sum_sub_distrib]
        rw [sub_eq_zero]
        calc
          (∑ i, ∑ j, w i j * p i) = ∑ i, (∑ j, w i j) * p i := by
            simp_rw [Finset.sum_mul]
          _ = ∑ i, (∑ j, w j i) * p i := by simp_rw [hb]
          _ = ∑ i, ∑ j, w j i * p i := by simp_rw [Finset.sum_mul]
          _ = ∑ i, ∑ j, w i j * p j := Finset.sum_comm
  3. The weighted sum of reduced costs is nonnegative: 0 ≤ ∑ i, ∑ j, w i j * (c i j + (p i - p j)).

    By Finset.sum_nonneg, it suffices to check that each term w i j * (c i j + (p i - p j)) is nonnegative. We distinguish two cases: when i = j, the term is zero since c i i = 0 (by hd) and p i - p i = 0 (by sub_self), which is nonnegative by le_refl; when i ≠ j, the weight w i j is nonnegative by hw, and the reduced cost c i j + (p i - p j) is nonnegative by the potential condition (hp), so their product is nonnegative by mul_nonneg.

    lines 17–21

    uses Finset.sum_nonneg, sub_self, add_zero, mul_zero, le_refl, mul_nonneg

      have hnn : 0 ≤ ∑ i, ∑ j, w i j * (c i j + (p i - p j)) :=
        Finset.sum_nonneg fun i _ => Finset.sum_nonneg fun j _ => by
          by_cases hij : i = j
          · subst j; simp only [hd, sub_self, add_zero, mul_zero, le_refl]
          · exact mul_nonneg (hw i j hij) (by linarith only [hp i j])
  4. The total weighted cost is nonnegative: 0 ≤ ∑ i, ∑ j, w i j * c i j.

    Distributing the product with mul_add and splitting the sum using Finset.sum_add_distrib, the previous inequality becomes 0 ≤ ∑ i, ∑ j, w i j * c i j + ∑ i, ∑ j, w i j * (p i - p j). Since the second sum vanishes by hcancel, adding zero leaves only 0 ≤ ∑ i, ∑ j, w i j * c i j.

    lines 22–23

    uses mul_add, Finset.sum_add_distrib, add_zero

      simp_rw [mul_add, Finset.sum_add_distrib] at hnn
      simpa only [hcancel, add_zero] using hnn
four_vertex_cycle_cost_potential
If a cost matrix on four vertices has zero diagonal and all four-step closed walks have nonnegative total cost, then there exists a vertex potential p such that p j ≤ p i + c i j for all i, j.
mul_sub
Multiplication distributes over subtraction on the left: a * (b - c) = a * b - a * c.
Finset.sum_sub_distrib
A finite sum of differences equals the difference of the sums: ∑ (f x - g x) = ∑ f x - ∑ g x.
sub_eq_zero
A difference a - b is zero if and only if a = b.
Finset.sum_mul
Right-distributivity of multiplication over finite sums: (∑ f i) * a = ∑ (f i * a).
Finset.sum_comm
The order of summation in a finite double sum can be swapped: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
Finset.sum_nonneg
A finite sum of nonnegative terms is nonnegative.
sub_self
Subtracting any element from itself gives zero: a - a = 0.
add_zero
Adding zero to an element leaves it unchanged: a + 0 = a.
mul_zero
Multiplying any element by zero yields zero: a * 0 = 0.
le_refl
The ordering relation is reflexive: a ≤ a.
mul_nonneg
The product of two nonnegative elements is nonnegative.
mul_add
Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.
Finset.sum_add_distrib
A finite sum of sums equals the sum of the individual sums: ∑ (f x + g x) = ∑ f x + ∑ g x.

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

theorem four_vertex_balanced_cost_nonneg (w c : Fin 4 → Fin 4 → ℝ)    (hw : ∀ i j, i ≠ j → 0 ≤ w i j)    (hb : ∀ i, ∑ j, w i j = ∑ j, w j i)    (hd : ∀ i, c i i = 0)    (hc : ∀ i j k l, 0 ≤ c i j + c j k + c k l + c l i) :    0 ≤ ∑ i, ∑ j, w i j * c i j := by  obtain ⟨p, hp⟩ := four_vertex_cycle_cost_potential c hd hc  have hcancel : (∑ i, ∑ j, w i j * (p i - p j)) = 0 := by    simp_rw [mul_sub, Finset.sum_sub_distrib]    rw [sub_eq_zero]    calc      (∑ i, ∑ j, w i j * p i) = ∑ i, (∑ j, w i j) * p i := by        simp_rw [Finset.sum_mul]      _ = ∑ i, (∑ j, w j i) * p i := by simp_rw [hb]      _ = ∑ i, ∑ j, w j i * p i := by simp_rw [Finset.sum_mul]      _ = ∑ i, ∑ j, w i j * p j := Finset.sum_comm  have hnn : 0 ≤ ∑ i, ∑ j, w i j * (c i j + (p i - p j)) :=    Finset.sum_nonneg fun i _ => Finset.sum_nonneg fun j _ => by      by_cases hij : i = j      · subst j; simp only [hd, sub_self, add_zero, mul_zero, le_refl]      · exact mul_nonneg (hw i j hij) (by linarith only [hp i j])  simp_rw [mul_add, Finset.sum_add_distrib] at hnn  simpa only [hcancel, add_zero] using hnn
See it in the graphDiscuss this resultChallenge it