four_vertex_cycle_cost_potential
If every closed four-step walk on four vertices has nonnegative cost and loops cost zero, a real vertex potential makes every reduced edge cost nonnegative.
Statement
theorem four_vertex_cycle_cost_potential (c : Fin 4 → Fin 4 → ℝ)
(hd : ∀ i, c i i = 0)
(hc : ∀ i j k l, 0 ≤ c i j + c j k + c k l + c l i) :
∃ p : Fin 4 → ℝ, ∀ i j, p j ≤ p i + c i j- Source
- Sector-bound formalization for IN-166; arXiv:math/0508176, Theorem 5.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- four_vertex_balanced_cost_nonnegOn four vertices, a balanced edge weighting, nonnegative away from the diagonal, assigns nonnegative total cost whenever every closed…
The proof, explained
The proof constructs a vertex potential $p$ on the four-vertex complete directed graph by fixing $p_0 = 0$ and defining each remaining $p_v$ as the shortest-path distance from vertex 0 to $v$, expressed as the explicit minimum over all five simple paths from 0 to $v$. Because every four-step closed walk has nonnegative cost and loops cost zero, all cycles of lengths 2, 3, and 4 have nonnegative cost as well. To verify the triangle inequality $p_j \le p_i + c(i, j)$, appending the edge $(i, j)$ to any simple path to $i$ produces either a simple path to $j$ (bounded by $p_j$) or a cycle plus a subpath to $j$ (whose cost is at least $p_j$ because cycles are nonnegative). Finally, an exhaustive verification over all sixteen vertex pairs confirms that this potential satisfies the required condition for all edges.
Candidate potential values $p_1, p_2, p_3$ are defined as the shortest simple paths from vertex 0, and bounded by each path cost.
For each vertex $v \in \{1, 2, 3\}$, there are five simple directed paths from vertex 0 to $v$ in the complete graph on 4 vertices: the single edge $0 \to v$, two 2-edge paths, and two 3-edge paths. We define $p_v$ as the nested minimum of the costs of these five paths. By applying the standard properties of the binary minimum (`min_le_left`, `min_le_right`, `le_trans`, and `le_rfl`), we record explicit inequalities ($hp1_0$ through $hp3_4$) stating that $p_v$ is bounded above by the cost of each individual path.
uses
min_le_left,le_trans,min_le_right,le_rfllet p1 : ℝ := min (c 0 1) (min (c 0 2 + c 2 1) (min (c 0 3 + c 3 1) (min (c 0 2 + c 2 3 + c 3 1) (c 0 3 + c 3 2 + c 2 1)))) have hp1_0 : p1 ≤ c 0 1 := min_le_left _ _ have hp1_1 : p1 ≤ c 0 2 + c 2 1 := le_trans (min_le_right _ _) (min_le_left _ _) have hp1_2 : p1 ≤ c 0 3 + c 3 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)) have hp1_3 : p1 ≤ c 0 2 + c 2 3 + c 3 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))) have hp1_4 : p1 ≤ c 0 3 + c 3 2 + c 2 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl)))) let p2 : ℝ := min (c 0 2) (min (c 0 1 + c 1 2) (min (c 0 3 + c 3 2) (min (c 0 1 + c 1 3 + c 3 2) (c 0 3 + c 3 1 + c 1 2)))) have hp2_0 : p2 ≤ c 0 2 := min_le_left _ _ have hp2_1 : p2 ≤ c 0 1 + c 1 2 := le_trans (min_le_right _ _) (min_le_left _ _) have hp2_2 : p2 ≤ c 0 3 + c 3 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)) have hp2_3 : p2 ≤ c 0 1 + c 1 3 + c 3 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))) have hp2_4 : p2 ≤ c 0 3 + c 3 1 + c 1 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl)))) let p3 : ℝ := min (c 0 3) (min (c 0 1 + c 1 3) (min (c 0 2 + c 2 3) (min (c 0 1 + c 1 2 + c 2 3) (c 0 2 + c 2 1 + c 1 3)))) have hp3_0 : p3 ≤ c 0 3 := min_le_left _ _ have hp3_1 : p3 ≤ c 0 1 + c 1 3 := le_trans (min_le_right _ _) (min_le_left _ _) have hp3_2 : p3 ≤ c 0 2 + c 2 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)) have hp3_3 : p3 ≤ c 0 1 + c 1 2 + c 2 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))) have hp3_4 : p3 ≤ c 0 2 + c 2 1 + c 1 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl))))
Every directed cycle of length 2, 3, or 4 has nonnegative total cost.
The theorem hypothesis states that every 4-step closed walk $i \to j \to k \to l \to i$ has nonnegative total cost. Because self-loops have zero cost ($c(i, i) = 0$), setting repeated vertices specializes this hypothesis to shorter cycles: setting three vertices identical yields the nonnegativity of all six 2-cycles ($hc0$–$hc5$); setting two vertices identical yields the nonnegativity of all eight 3-cycles ($hc6$–$hc13$); and distinct vertices yield all six 4-cycles ($hc14$–$hc19$). Each identity is simplified by removing zero loop costs using `add_zero` and `zero_add`.
uses
add_zero,zero_addhave hc0 : 0 ≤ c 0 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 1 1 have hc1 : 0 ≤ c 0 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 2 2 have hc2 : 0 ≤ c 0 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 3 3 have hc3 : 0 ≤ c 1 2 + c 2 1 := by simpa only [hd, add_zero, zero_add] using hc 1 2 2 2 have hc4 : 0 ≤ c 1 3 + c 3 1 := by simpa only [hd, add_zero, zero_add] using hc 1 3 3 3 have hc5 : 0 ≤ c 2 3 + c 3 2 := by simpa only [hd, add_zero, zero_add] using hc 2 3 3 3 have hc6 : 0 ≤ c 0 1 + c 1 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 2 2 have hc7 : 0 ≤ c 0 1 + c 1 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 3 3 have hc8 : 0 ≤ c 0 2 + c 2 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 1 1 have hc9 : 0 ≤ c 0 2 + c 2 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 3 3 have hc10 : 0 ≤ c 0 3 + c 3 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 1 1 have hc11 : 0 ≤ c 0 3 + c 3 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 2 2 have hc12 : 0 ≤ c 1 2 + c 2 3 + c 3 1 := by simpa only [hd, add_zero, zero_add] using hc 1 2 3 3 have hc13 : 0 ≤ c 1 3 + c 3 2 + c 2 1 := by simpa only [hd, add_zero, zero_add] using hc 1 3 2 2 have hc14 : 0 ≤ c 0 1 + c 1 2 + c 2 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 2 3 have hc15 : 0 ≤ c 0 1 + c 1 3 + c 3 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 3 2 have hc16 : 0 ≤ c 0 2 + c 2 1 + c 1 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 1 3 have hc17 : 0 ≤ c 0 2 + c 2 3 + c 3 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 3 1 have hc18 : 0 ≤ c 0 3 + c 3 1 + c 1 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 1 2 have hc19 : 0 ≤ c 0 3 + c 3 2 + c 2 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 2 1
The reduced cost inequality $p_j \le p_0 + c(0, j)$ holds for edges outgoing from the source vertex 0.
Setting the source potential $p_0 = 0$, the requirement $p_j \le 0 + c(0, j)$ simplifies to $p_j \le c(0, j)$ via `zero_add`. This inequality holds directly because $c(0, j)$, the cost of the direct edge $0 \to j$, is the first term in the minimum defining $p_j$.
uses
zero_addhave h01 : p1 ≤ 0 + c 0 1 := by simpa only [zero_add] using hp1_0 have h02 : p2 ≤ 0 + c 0 2 := by simpa only [zero_add] using hp2_0 have h03 : p3 ≤ 0 + c 0 3 := by simpa only [zero_add] using hp3_0
The reduced cost inequality $p_j \le p_i + c(i, j)$ holds for all remaining directed edges between distinct vertices.
For each of the remaining 9 directed edges $i \to j$ (with $i \ne 0$ and $i \ne j$, setting $p_0 = 0$): distributing addition by $c(i, j)$ across the nested minimum defining $p_i$ via `min_add_add_right` and splitting with `le_min_iff` reduces the goal $p_j \le p_i + c(i, j)$ to five separate subgoals, one for each simple path $P$ from 0 to $i$. If $j = 0$, appending $i \to 0$ to $P$ forms a cycle whose cost is nonnegative by Step 2. If $j \ne 0$ and $P$ does not visit $j$, $P$ followed by $i \to j$ is a simple path from 0 to $j$, so its cost is bounded below by $p_j$ by definition. If $P$ already visits $j$, the walk decomposes into a simple path from 0 to $j$ plus a cycle containing $(i, j)$; since cycles have nonnegative cost, the total cost is at least the path cost to $j$, which is at least $p_j$. In each branch, linear arithmetic (`linarith`) completes the check using the precomputed cycle nonnegativities and path bounds.
uses
min_add_add_right,le_min_iffhave h10 : 0 ≤ p1 + c 1 0 := by dsimp only [p1] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hc0] · linarith only [hc8] · linarith only [hc10] · linarith only [hc17] · linarith only [hc19] have h12 : p2 ≤ p1 + c 1 2 := by dsimp only [p1] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp2_1] · linarith only [hp2_0, hc3] · linarith only [hp2_4] · linarith only [hp2_0, hc12] · linarith only [hp2_2, hc3] have h13 : p3 ≤ p1 + c 1 3 := by dsimp only [p1] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp3_1] · linarith only [hp3_4] · linarith only [hp3_0, hc4] · linarith only [hp3_2, hc4] · linarith only [hp3_0, hc13] have h20 : 0 ≤ p2 + c 2 0 := by dsimp only [p2] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hc1] · linarith only [hc6] · linarith only [hc11] · linarith only [hc15] · linarith only [hc18] have h21 : p1 ≤ p2 + c 2 1 := by dsimp only [p2] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp1_1] · linarith only [hp1_0, hc3] · linarith only [hp1_4] · linarith only [hp1_0, hc13] · linarith only [hp1_2, hc3] have h23 : p3 ≤ p2 + c 2 3 := by dsimp only [p2] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp3_2] · linarith only [hp3_3] · linarith only [hp3_0, hc5] · linarith only [hp3_1, hc5] · linarith only [hp3_0, hc12] have h30 : 0 ≤ p3 + c 3 0 := by dsimp only [p3] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hc2] · linarith only [hc7] · linarith only [hc9] · linarith only [hc14] · linarith only [hc16] have h31 : p1 ≤ p3 + c 3 1 := by dsimp only [p3] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp1_2] · linarith only [hp1_0, hc4] · linarith only [hp1_3] · linarith only [hp1_0, hc12] · linarith only [hp1_1, hc4] have h32 : p2 ≤ p3 + c 3 2 := by dsimp only [p3] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp2_2] · linarith only [hp2_3] · linarith only [hp2_0, hc5] · linarith only [hp2_1, hc5] · linarith only [hp2_0, hc13]
The potential vector $p = (0, p_1, p_2, p_3)$ satisfies $p_j \le p_i + c(i, j)$ for all $i, j \in \{0, 1, 2, 3\}$.
We provide $p = ![0, p_1, p_2, p_3]$ as the witness potential. An exhaustive case split (`fin_cases`) over all 16 pairs $(i, j) \in \operatorname{Fin} 4 \times \operatorname{Fin} 4$ reduces each case: the four diagonal cases $i = j$ reduce to $p_i \le p_i + 0$ since loops cost zero, solved by simplification with `Matrix.cons_val_zero`, `Matrix.cons_val_succ`, `add_zero`, and reflexivity `le_refl`; while the twelve off-diagonal cases match the inequalities established in steps 3 and 4.
uses
Matrix.cons_val_zero,Matrix.cons_val_succ,add_zero,le_reflrefine ⟨![0, p1, p2, p3], ?_⟩ intro i j fin_cases i <;> fin_cases j · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl] · exact h01 · exact h02 · exact h03 · exact h10 · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl] · exact h12 · exact h13 · exact h20 · exact h21 · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl] · exact h23 · exact h30 · exact h31 · exact h32 · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]
min_le_left- The minimum of two elements is less than or equal to the first: $\min(a, b) \le a$.
min_le_right- The minimum of two elements is less than or equal to the second: $\min(a, b) \le b$.
le_trans- Order is transitive: if $a \le b$ and $b \le c$, then $a \le c$.
le_rfl- Order is reflexive: $a \le a$.
le_refl- Order is reflexive: $a \le a$.
add_zero- Adding zero on the right leaves an element unchanged: $a + 0 = a$.
zero_add- Adding zero on the left leaves an element unchanged: $0 + a = a$.
min_add_add_right- Addition distributes over minimum on the right: $\min(a, b) + c = \min(a + c, b + c)$.
le_min_iff- An element is bounded above by a minimum if and only if it is bounded by both operands: $c \le \min(a, b) \iff c \le a \land c \le b$.
Matrix.cons_val_zero- The 0-th entry of a vector constructed by prepending an element $x$ is $x$.
Matrix.cons_val_succ- The $(i + 1)$-th entry of a vector constructed by prepending an element is the $i$-th entry of the original vector.
- In step 4, the graph-theoretic distinction between extending a path to a longer simple path versus creating a cycle is verified mechanically: distributing addition over the minimum generates 5 linear inequalities for each edge, each closed by linear arithmetic (`linarith`).
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_cycle_cost_potential (c : Fin 4 → Fin 4 → ℝ) (hd : ∀ i, c i i = 0) (hc : ∀ i j k l, 0 ≤ c i j + c j k + c k l + c l i) : ∃ p : Fin 4 → ℝ, ∀ i j, p j ≤ p i + c i j := by let p1 : ℝ := min (c 0 1) (min (c 0 2 + c 2 1) (min (c 0 3 + c 3 1) (min (c 0 2 + c 2 3 + c 3 1) (c 0 3 + c 3 2 + c 2 1)))) have hp1_0 : p1 ≤ c 0 1 := min_le_left _ _ have hp1_1 : p1 ≤ c 0 2 + c 2 1 := le_trans (min_le_right _ _) (min_le_left _ _) have hp1_2 : p1 ≤ c 0 3 + c 3 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)) have hp1_3 : p1 ≤ c 0 2 + c 2 3 + c 3 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))) have hp1_4 : p1 ≤ c 0 3 + c 3 2 + c 2 1 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl)))) let p2 : ℝ := min (c 0 2) (min (c 0 1 + c 1 2) (min (c 0 3 + c 3 2) (min (c 0 1 + c 1 3 + c 3 2) (c 0 3 + c 3 1 + c 1 2)))) have hp2_0 : p2 ≤ c 0 2 := min_le_left _ _ have hp2_1 : p2 ≤ c 0 1 + c 1 2 := le_trans (min_le_right _ _) (min_le_left _ _) have hp2_2 : p2 ≤ c 0 3 + c 3 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)) have hp2_3 : p2 ≤ c 0 1 + c 1 3 + c 3 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))) have hp2_4 : p2 ≤ c 0 3 + c 3 1 + c 1 2 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl)))) let p3 : ℝ := min (c 0 3) (min (c 0 1 + c 1 3) (min (c 0 2 + c 2 3) (min (c 0 1 + c 1 2 + c 2 3) (c 0 2 + c 2 1 + c 1 3)))) have hp3_0 : p3 ≤ c 0 3 := min_le_left _ _ have hp3_1 : p3 ≤ c 0 1 + c 1 3 := le_trans (min_le_right _ _) (min_le_left _ _) have hp3_2 : p3 ≤ c 0 2 + c 2 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _)) have hp3_3 : p3 ≤ c 0 1 + c 1 2 + c 2 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (min_le_left _ _))) have hp3_4 : p3 ≤ c 0 2 + c 2 1 + c 1 3 := le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_trans (min_le_right _ _) (le_rfl)))) have hc0 : 0 ≤ c 0 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 1 1 have hc1 : 0 ≤ c 0 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 2 2 have hc2 : 0 ≤ c 0 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 3 3 have hc3 : 0 ≤ c 1 2 + c 2 1 := by simpa only [hd, add_zero, zero_add] using hc 1 2 2 2 have hc4 : 0 ≤ c 1 3 + c 3 1 := by simpa only [hd, add_zero, zero_add] using hc 1 3 3 3 have hc5 : 0 ≤ c 2 3 + c 3 2 := by simpa only [hd, add_zero, zero_add] using hc 2 3 3 3 have hc6 : 0 ≤ c 0 1 + c 1 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 2 2 have hc7 : 0 ≤ c 0 1 + c 1 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 3 3 have hc8 : 0 ≤ c 0 2 + c 2 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 1 1 have hc9 : 0 ≤ c 0 2 + c 2 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 3 3 have hc10 : 0 ≤ c 0 3 + c 3 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 1 1 have hc11 : 0 ≤ c 0 3 + c 3 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 2 2 have hc12 : 0 ≤ c 1 2 + c 2 3 + c 3 1 := by simpa only [hd, add_zero, zero_add] using hc 1 2 3 3 have hc13 : 0 ≤ c 1 3 + c 3 2 + c 2 1 := by simpa only [hd, add_zero, zero_add] using hc 1 3 2 2 have hc14 : 0 ≤ c 0 1 + c 1 2 + c 2 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 2 3 have hc15 : 0 ≤ c 0 1 + c 1 3 + c 3 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 1 3 2 have hc16 : 0 ≤ c 0 2 + c 2 1 + c 1 3 + c 3 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 1 3 have hc17 : 0 ≤ c 0 2 + c 2 3 + c 3 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 2 3 1 have hc18 : 0 ≤ c 0 3 + c 3 1 + c 1 2 + c 2 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 1 2 have hc19 : 0 ≤ c 0 3 + c 3 2 + c 2 1 + c 1 0 := by simpa only [hd, add_zero, zero_add] using hc 0 3 2 1 have h01 : p1 ≤ 0 + c 0 1 := by simpa only [zero_add] using hp1_0 have h02 : p2 ≤ 0 + c 0 2 := by simpa only [zero_add] using hp2_0 have h03 : p3 ≤ 0 + c 0 3 := by simpa only [zero_add] using hp3_0 have h10 : 0 ≤ p1 + c 1 0 := by dsimp only [p1] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hc0] · linarith only [hc8] · linarith only [hc10] · linarith only [hc17] · linarith only [hc19] have h12 : p2 ≤ p1 + c 1 2 := by dsimp only [p1] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp2_1] · linarith only [hp2_0, hc3] · linarith only [hp2_4] · linarith only [hp2_0, hc12] · linarith only [hp2_2, hc3] have h13 : p3 ≤ p1 + c 1 3 := by dsimp only [p1] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp3_1] · linarith only [hp3_4] · linarith only [hp3_0, hc4] · linarith only [hp3_2, hc4] · linarith only [hp3_0, hc13] have h20 : 0 ≤ p2 + c 2 0 := by dsimp only [p2] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hc1] · linarith only [hc6] · linarith only [hc11] · linarith only [hc15] · linarith only [hc18] have h21 : p1 ≤ p2 + c 2 1 := by dsimp only [p2] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp1_1] · linarith only [hp1_0, hc3] · linarith only [hp1_4] · linarith only [hp1_0, hc13] · linarith only [hp1_2, hc3] have h23 : p3 ≤ p2 + c 2 3 := by dsimp only [p2] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp3_2] · linarith only [hp3_3] · linarith only [hp3_0, hc5] · linarith only [hp3_1, hc5] · linarith only [hp3_0, hc12] have h30 : 0 ≤ p3 + c 3 0 := by dsimp only [p3] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hc2] · linarith only [hc7] · linarith only [hc9] · linarith only [hc14] · linarith only [hc16] have h31 : p1 ≤ p3 + c 3 1 := by dsimp only [p3] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp1_2] · linarith only [hp1_0, hc4] · linarith only [hp1_3] · linarith only [hp1_0, hc12] · linarith only [hp1_1, hc4] have h32 : p2 ≤ p3 + c 3 2 := by dsimp only [p3] simp only [← min_add_add_right, le_min_iff] refine ⟨?_, ?_, ?_, ?_, ?_⟩ · linarith only [hp2_2] · linarith only [hp2_3] · linarith only [hp2_0, hc5] · linarith only [hp2_1, hc5] · linarith only [hp2_0, hc13] refine ⟨![0, p1, p2, p3], ?_⟩ intro i j fin_cases i <;> fin_cases j · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl] · exact h01 · exact h02 · exact h03 · exact h10 · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl] · exact h12 · exact h13 · exact h20 · exact h21 · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl] · exact h23 · exact h30 · exact h31 · exact h32 · simp only [Matrix.cons_val_zero, Matrix.cons_val_succ, hd, add_zero, le_refl]