four_vertex_balanced_cost_nonneg
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
- laplacian_order_four_stationary_eigenvalue_one_sideFor a real order-four matrix with zero row sums, nonpositive off-diagonal entries, and a strictly positive left null vector, every complex…
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.
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.
uses
four_vertex_cycle_cost_potentialobtain ⟨p, hp⟩ := four_vertex_cycle_cost_potential c hd hcThe 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.
uses
mul_sub,Finset.sum_sub_distrib,sub_eq_zero,Finset.sum_mul,Finset.sum_commhave 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
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.
uses
Finset.sum_nonneg,sub_self,add_zero,mul_zero,le_refl,mul_nonneghave 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])
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.
uses
mul_add,Finset.sum_add_distrib,add_zerosimp_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
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.
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