p. 486, proof of THEOREM 19 — pushing a path forward along ψ preserves its cost, so the lifted inequality is valid
ProvedGomory69.Lifting.pushForward_pathgroup-polyhedronhomomorphismliftingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a homomorphism of finite Abelian groups, with , and with . For let , .
- If , then and
- Consequently, for every : if for all , then for all .
This is the half of THEOREM 19 that says the lifted inequality is valid for ; the elements of the kernel drop out of because their cost is .
Formalization Note The paper argues with a path of value and derives a contradiction; the Lean states the underlying identity and the resulting implication directly. Paths are vectors , their value is . The hypothesis is from THEOREM 19; it ensures the pushed-forward path is nonzero and hence belongs to the paper's .
Preamble
import Mathlib import Definitions.Def_Gomory69_Lifting_GroupPolyhedron import Definitions.Def_Gomory69_Lifting_Lift
Formal statement
namespace Gomory69.Lifting
theorem pushForward_path {G H : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
[AddCommGroup H] [Fintype H] [DecidableEq H]
(ψ : G →+ H) (g₀ : G) (hg₀ : ψ g₀ ≠ 0) (π' : Plus H → ℝ) (π₀ : ℝ) :
(∀ t ∈ T G g₀, pushForward ψ t ∈ T H (ψ g₀) ∧
liftCoeff ψ π' ⬝ᵥ castVec t = π' ⬝ᵥ castVec (pushForward ψ t)) ∧
((∀ τ ∈ T H (ψ g₀), π₀ ≤ π' ⬝ᵥ castVec τ) →
∀ t ∈ T G g₀, π₀ ≤ liftCoeff ψ π' ⬝ᵥ castVec t) := by sorry
end Gomory69.Lifting
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 486, proof of THEOREM 19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.