Proof of THEOREM 4, p. 462 — ‖Nx_N*‖ ≤ l_max(D − 1)
ProvedGomory69.Asymptotic.norm_le_lmaxgroup-polyhedroninteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a nonsingular integer matrix, an integer matrix, , , the set of nonzero , and the largest Euclidean length of a column . If is a vertex of and is the nonbasic part of a vertex of corresponding to (Remark 1), then
where is the Euclidean length.
This is the quantitative core of THEOREM 4: the nonbasic correction moves by at most .
Formalization Note No cost or optimality hypothesis is needed for this step; only the vertex property of and conditions (i)–(iii) of Remark 1 enter.
Preamble
import Mathlib import Definitions.Def_Gomory69_Asymptotic_GroupPolyhedron import Definitions.Def_Gomory69_Asymptotic_IntegerProgram
Formal statement
namespace Gomory69.Asymptotic
/-- Proof of THEOREM 4 (p. 462): if `t*` is a vertex of `P(𝒢, 𝒩, f b)` and `x_N*` the
nonbasic part of a corresponding vertex (Remark 1), then
`‖N x_N*‖ ≤ l_max (D − 1)`, `D = |det B|`, `‖·‖` the Euclidean length. -/
theorem norm_le_lmax {m n : ℕ} (B : Matrix (Fin m) (Fin m) ℤ) (N : Matrix (Fin m) (Fin n) ℤ)
(b : Fin m → ℤ) (hdet : B.det ≠ 0) (tstar : ↥(groupColumnSet B N) → ℝ)
(ht : tstar ∈ Set.extremePoints ℝ (groupPolyhedron (groupColumnSet B N) (toGroup B b)))
(xN : Fin n → ℕ) (hx : IsVertexLift B N tstar xN) :
euclNorm (fun k => ∑ i, (N k i : ℝ) * (xN i : ℝ)) ≤ lmax N * ((detAbs B : ℝ) - 1) := by sorry
end Gomory69.Asymptotic
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 462, proof of THEOREM 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.