Proof of THEOREM 4, p. 462 — an irreducible t has Σ t(g) ≤ |G| − 1
ProvedGomory69.Asymptotic.sum_le_card_sub_onegroup-polyhedronirreducibilityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite Abelian group and a set of nonzero elements of . If the nonnegative integer vector is irreducible, then
This is the first step of the proof of THEOREM 4, applied there to a minimizing vertex .
Formalization Note The page writes ". Expanding shows ..."; the inequality it expands is THEOREM 1's product , and the sum is a printing slip. The subtraction is in , which is exact because .
Preamble
import Mathlib import Definitions.Def_Gomory69_Asymptotic_GroupPolyhedron
Formal statement
namespace Gomory69.Asymptotic
/-- Proof of THEOREM 4 (p. 462), first step: an irreducible nonnegative integer vector `t`
satisfies `∑_{g ∈ 𝒩} t(g) ≤ |𝒢| − 1` (natural-number subtraction is exact here, as
`|𝒢| ≥ 1`). -/
theorem sum_le_card_sub_one {G : Type*} [AddCommGroup G] [Fintype G] (𝒩 : Finset G)
(h𝒩 : (0 : G) ∉ 𝒩) (t : ↥𝒩 → ℕ) (ht : IsIrreducible 𝒩 t) :
∑ g : ↥𝒩, t g ≤ Fintype.card G - 1 := by sorry
end Gomory69.Asymptotic
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 462, proof of THEOREM 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.