THEOREM 19, p. 486 — a face of P(H, ψg₀) lifts through a homomorphism ψ of G onto H to a face of P(G, g₀)
ProvedGomory69.Lifting.theorem_19Let and be finite Abelian groups and a homomorphism of onto with kernel , and let with . Let be a face of the master polyhedron with . Define on by
Then is a face of .
Faces of the master polyhedron of a small group thus produce faces of the master polyhedra of all groups mapping onto it. For example, the face of lifts through reduction mod to the face of (p. 488). THEOREM 20 gives the converse for faces with a zero coefficient.
Formalization Note The hypothesis is added: the page does not state it, and without it the theorem is false under the paper's own definition of face. With , , reduction mod 3 and , the inequality is a face of (THEOREM 16), but its lift is not a face of : its tight solutions all have and span only a 3-dimensional subspace of the 4-dimensional hyperplane. The proof's " independent minimal paths" (p. 487) requires . Surjectivity is the page's "onto"; is written .
import Mathlib import Definitions.Def_Gomory69_Lifting_GroupPolyhedron import Definitions.Def_Gomory69_Lifting_Lift
namespace Gomory69.Lifting
theorem theorem_19 {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₀) π' π₀) :
IsFace G g₀ (liftCoeff ψ π') π₀ := by sorry
end Gomory69.Lifting
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.