p. 506, proof of THEOREM 23 — solutions vanishing off the support of t agree with t modulo p and dominate it
ProvedGomory69.SpecialGroups.solution_on_supportgroup-polyhedronirreducibilityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite Abelian group in which every nonzero element has order , , and let be an irreducible nonnegative integer solution of the group equation . If is any nonnegative integer solution of the same equation with whenever , then for every
In particular is the only such solution whose components are all smaller than .
Formalization Note The page asserts that is the only solution with components zero outside its support. Literally this fails: in with , is irreducible and is another solution with the same support. The page's argument (with , , and independence of the support) proves ; since an irreducible has , this gives . The statement records that corrected conclusion.
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, then every solution
`u` vanishing wherever `t` vanishes satisfies `u(g) ≡ t(g) (mod p)` and `u(g) ≥ t(g)` for every
`g`; in particular `t` is the only such solution with all components below `p`. (The page asserts
that `t` is the only such solution outright, which fails, e.g. `𝒢 = ℤ₂`, `t = (1)`, `u = (3)`.) -/
theorem solution_on_support {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)
(u : {g : G // g ≠ 0} → ℕ) (hu : u ∈ solutionSet g₀) (hsupp : ∀ g, t g = 0 → u g = 0) :
∀ g, u g ≡ t g [MOD p] ∧ t g ≤ u 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.