p. 487, proof of THEOREM 19 — each lifted path T_k(τ) solves the group equation and has cost π₀
ProvedGomory69.Lifting.liftedPath_minimalgroup-polyhedronhomomorphismliftingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a homomorphism of finite Abelian groups with kernel , and a section, for every . Let , , with , and . Let with and . Then the closing element lies in , and the lifted path satisfies
Each minimal path of the quotient problem thus yields minimal paths of the original problem, one for each ; these are the rows of the matrix of Fig. 6.
Formalization Note is the vector liftedPath ψ φ g₀ k τ of the definition file; its kernel entry is a single on when and nothing when . The page writes " with and "; the Lean places the on itself (the two agree when ). "Minimal" is stated as cost exactly .
Preamble
import Mathlib import Definitions.Def_Gomory69_Lifting_GroupPolyhedron import Definitions.Def_Gomory69_Lifting_Lift
Formal statement
namespace Gomory69.Lifting
theorem liftedPath_minimal {G H : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
[AddCommGroup H] [Fintype H] [DecidableEq H]
(ψ : G →+ H) (φ : H → G) (hφ : ∀ h, ψ (φ h) = h) (g₀ : G)
(π' : Plus H → ℝ) (π₀ : ℝ) (τ : Plus H → ℕ) (hτ : τ ∈ T H (ψ g₀))
(hτπ : π' ⬝ᵥ castVec τ = π₀) (k : G) (hk : ψ k = 0) :
ψ (closingElement ψ φ g₀ k τ) = 0 ∧
liftedPath ψ φ g₀ k τ ∈ T G g₀ ∧
liftCoeff ψ π' ⬝ᵥ castVec (liftedPath ψ φ g₀ k τ) = π₀ := by sorry
end Gomory69.Lifting
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 487, proof of THEOREM 19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.