p. 469, proof of THEOREM 7 — for π₀ > 0, a face is a valid inequality with n′ linearly independent tight points of T
ProvedGomory69.Lifting.face_iff_independent_tightLet be a finite nontrivial Abelian group, , the nonzero nonnegative integer solutions of the group equation, and . Let and . Then is a face of the master polyhedron if and only if
The criterion turns the affine condition "the tight points generate the hyperplane" into a rank condition. It is the step that makes a count of independent minimal paths prove that an inequality is a face, and it is how THEOREM 19 is established.
Formalization Note This is THEOREM 7 of p. 469 with "basic feasible solution of " unfolded: rows of rank satisfied with equality are linearly independent tight . It is stated for the master polyhedron (), the case this mission needs; the page states it for any . The hypothesis is THEOREM 7's. Nontriviality makes the ambient T-space have positive dimension, as the paper's facet convention requires.
import Mathlib import Definitions.Def_Gomory69_Lifting_GroupPolyhedron
namespace Gomory69.Lifting
theorem face_iff_independent_tight {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
[Nontrivial G]
(g₀ : G) (π : Plus G → ℝ) (π₀ : ℝ) (hπ₀ : 0 < π₀) :
IsFace G g₀ π π₀ ↔
(∀ t ∈ T G g₀, π₀ ≤ π ⬝ᵥ castVec t) ∧
∃ s : Fin (Fintype.card (Plus G)) → (Plus G → ℕ),
(∀ i, s i ∈ T G g₀ ∧ π ⬝ᵥ 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.