Proof of THEOREM 4, p. 462 — y ∈ K_B(d) and ‖v‖ ≤ d imply y − v ∈ K_B
ProvedGomory69.Asymptotic.sub_mem_basisConeconesinteger-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a nonsingular integer matrix, , and the set of points of at Euclidean distance at least from the frontier of . If and has Euclidean length , then
In the proof of THEOREM 4 this is applied with , and , giving .
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 `y ∈ K_B(d)` and `v` has Euclidean length at most `d`,
then `y − v ∈ K_B`. -/
theorem sub_mem_basisCone {m : ℕ} (B : Matrix (Fin m) (Fin m) ℤ) (hdet : B.det ≠ 0)
(d : ℝ) (y v : Fin m → ℝ) (hy : y ∈ deepCone B d) (hv : euclNorm v ≤ d) :
y - v ∈ basisCone B := 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.