pp. 487–488, proof of THEOREM 19 — the lifted inequality has D − 1 linearly independent minimal paths
ProvedGomory69.Lifting.rank_D_sub_oneLet be a homomorphism of the finite Abelian group onto the finite Abelian group , with , let , and let be a face of with . Put , , with . Then there are solutions with
that are linearly independent in .
In the paper these are the lifted paths over all and all independent minimal paths of the quotient problem, together with one path for each nonzero obtained by adding copies of to a lifted path. Together with the validity of the lift, this is what THEOREM 19 asserts.
Formalization Note The page says "for each a row"; has no column, so the rows are added for , which is the count that gives . The hypothesis is not on the page; without it the statement fails (see the goal theorem).
import Mathlib import Definitions.Def_Gomory69_Lifting_GroupPolyhedron import Definitions.Def_Gomory69_Lifting_Lift
namespace Gomory69.Lifting
theorem rank_D_sub_one {G H : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
[AddCommGroup H] [Fintype H] [DecidableEq H]
(ψ : G →+ H) (hψ : Function.Surjective ψ) (g₀ : G) (hg₀ : ψ g₀ ≠ 0)
(π' : Plus H → ℝ) (π₀ : ℝ) (hπ₀ : 0 < π₀) (hface : IsFace H (ψ g₀) π' π₀) :
∃ s : Fin (Fintype.card (Plus G)) → (Plus G → ℕ),
(∀ i, s i ∈ T G g₀ ∧ liftCoeff ψ π' ⬝ᵥ castVec (s i) = π₀) ∧
LinearIndependent ℝ (fun i => castVec (s i)) := by sorry
end Gomory69.Lifting
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.