Eqs. (2.13)–(2.17): shortest paths between the named nodes of
ProvedTSPHeuristics.NNLower.shortest_paths_F_succLet and let be the nodes of named in Fig. 1: , , the start, middle and right node of the left copy of , the new middle node, and , , the start, middle and right node of the right copy. Write for the length of a shortest path between and in . Then
These identities are the induction that establishes properties a) and b) of .
Formalization Note With the number of nodes of : , , , , , , . Distances are taken in (not ).
import Mathlib import Definitions.Def_TSPHeuristics_NNLower_ShortestPathMetric import Definitions.Def_TSPHeuristics_NNLower_LowerBoundFamily
namespace TSPHeuristics.NNLower
/-- Eqs. (2.13)–(2.17), p. 569: in `F_{i+1}` (for `i ≥ 1`), with the nodes of Fig. 1
`A = 0`, `B = middle i`, `C = s − 1`, `D = s`, `E = s + 1`, `F = s + 1 + middle i`, `G = 2 s`
(`s = numNodes i`), the shortest-path distances are
`AB = BC = EF = FG = l_i − 1`, `AC = EG = l_{i+1} − 2`, `BE = DF = l_i`,
`AD = DG = l_{i+1} − 1`, `AG = l_{i+2} − 2`. -/
theorem shortest_paths_F_succ (i : ℕ) (hi : 1 ≤ i) :
let s := numNodes i
let A := 0
let B := middle i
let C := s - 1
let D := s
let E := s + 1
let F := s + 1 + middle i
let G := 2 * s
let dF := spDist (edgesF (i + 1))
(dF A B = ell i - 1 ∧ dF B C = ell i - 1 ∧ dF E F = ell i - 1 ∧ dF F G = ell i - 1) ∧
(dF A C = ell (i + 1) - 2 ∧ dF E G = ell (i + 1) - 2) ∧
(dF B E = ell i ∧ dF D F = ell i) ∧
(dF A D = ell (i + 1) - 1 ∧ dF D G = ell (i + 1) - 1) ∧
dF A G = ell (i + 2) - 2 := by sorry
end TSPHeuristics.NNLower
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Fix a natural number and write . is the recursively defined edge list on nodes . It consists of:
- on nodes ;
- a copy of shifted by ;
- the edges , , and , where and .
Write for the shortest-path distance : the infimum of total weights of walks in , with edges in either direction. It is when no walk exists or costs are unbounded below.
Named nodes.
| Label | Node |
|---|---|
Claim. All of the following equalities hold simultaneously:
Each distance is taken in the order written. The claim concerns distances in , not in the augmented list .
Degenerate cases. The case is excluded. For we have , so involves no truncated subtraction, and the seven labels name seven distinct nodes.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.