THEOREM 1, p. 459 — an irreducible t satisfies ∏(1 + t(g)) ≤ |G|
ProvedGomory69.Asymptotic.theorem_1group-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
where is the number of elements of the group.
The bound limits the size of every irreducible point, and hence (by THEOREM 2) of every vertex of ; it is the source of the bound in THEOREM 4.
Formalization Note The vector need not solve the group equation. is the paper's .
Preamble
import Mathlib import Definitions.Def_Gomory69_Asymptotic_GroupPolyhedron
Formal statement
namespace Gomory69.Asymptotic
/-- THEOREM 1 (p. 459): an irreducible nonnegative integer vector `t` on a set `𝒩` of
nonzero elements of a finite Abelian group `𝒢` satisfies `∏_{g ∈ 𝒩} (1 + t(g)) ≤ |𝒢|`. -/
theorem theorem_1 {G : Type*} [AddCommGroup G] [Fintype G] (𝒩 : Finset G)
(h𝒩 : (0 : G) ∉ 𝒩) (t : ↥𝒩 → ℕ) (ht : IsIrreducible 𝒩 t) :
∏ g : ↥𝒩, (1 + t g) ≤ Fintype.card G := by sorry
end Gomory69.Asymptotic
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 459, THEOREM 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.