p. 506, proof of THEOREM 23 — an irreducible solution minimizes π and is a vertex
ProvedGomory69.SpecialGroups.minimizer_vertexgroup-polyhedronp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1vertices
Let be a finite Abelian group in which every nonzero element has order , , and let be an irreducible nonnegative integer solution of , with support . Define
Then
- minimizes over the nonnegative integer solutions of the group equation;
- every minimizing solution satisfies componentwise;
- is a vertex of .
This is the step "irreducible vertex" of THEOREM 23.
Formalization Note The page says that is the unique minimizer of this . That fails literally (in , : and every solution minimizes), for the reason recorded in the item on solutions vanishing off the support; clause 2 is the corrected form, and clause 3 is the page's conclusion "So is a vertex".
Preamble
import Mathlib import Definitions.Def_Gomory69_SpecialGroups_GroupPolyhedron
Formal statement
namespace Gomory69.SpecialGroups
/-- Proof of THEOREM 23 (Gomory 1969, p. 506), corrected: if every nonzero element of `𝒢` has
order `p ∈ {2, 3}` and `t` is an irreducible solution of the group equation, put `π(g) = 0` where
`t(g) > 0` and `π(g) = 1` where `t(g) = 0`. Then `t` minimizes `π · u` over the solutions `u`,
every minimizer `u` satisfies `u ≥ t` componentwise, and `t` is a vertex of `P(𝒢, g₀)`. -/
theorem minimizer_vertex {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
(p : ℕ) (hp : p = 2 ∨ p = 3) (hG : AllNonzeroOfOrder G p)
(g₀ : G) (t : {g : G // g ≠ 0} → ℕ) (ht : t ∈ solutionSet g₀) (hirr : IsIrreducible t) :
let π : {g : G // g ≠ 0} → ℕ := fun g => if t g = 0 then 1 else 0
(∀ u ∈ solutionSet g₀, ∑ g, π g * t g ≤ ∑ g, π g * u g) ∧
(∀ u ∈ solutionSet g₀, ∑ g, π g * u g = ∑ g, π g * t g → t ≤ u) ∧
toReal t ∈ Set.extremePoints ℝ (masterPolyhedron g₀) := by sorry
end Gomory69.SpecialGroups
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 506, proof of THEOREM 23 (corrected; see the Formalization Note)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.