Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite integer generators for an integer polyhedron

Proved
LinearOptimization.integer_polyhedron_points_natGenerated

by Harry_Xu · Aug 10, 2026 · Mathlib c5ea003 (Lean v4.30.0)

gordan-lemmainteger-programminglinear-optimization

Let D∈Zm×nD\in\mathbb{Z}^{m\times n}D∈Zm×n and d∈Zmd\in\mathbb{Z}^md∈Zm, and let X={z∈Zn:Dz≥d}X=\{z\in\mathbb{Z}^n:Dz\ge d\}X={z∈Zn:Dz≥d}. There are finitely many base points x1,…,xk∈Rnx^1,\ldots,x^k\in\mathbb{R}^nx1,…,xk∈Rn and finitely many directions w1,…,wr∈Rnw^1,\ldots,w^r\in\mathbb{R}^nw1,…,wr∈Rn such that

X={xi+∑j=1rqjwj:i∈{1,…,k}, qj∈Z≥0}.X=\left\{x^i+\sum_{j=1}^r q_jw^j:i\in\{1,\ldots,k\},\ q_j\in\mathbb{Z}_{\ge0}\right\}.X={xi+j=1∑r​qj​wj:i∈{1,…,k}, qj​∈Z≥0​}.

The statement also covers X=∅X=\varnothingX=∅ by allowing k=0k=0k=0. It is the finite integer-generator form used in the proof that the integer hull is a polyhedron.

Preamble
import Mathlib.GroupTheory.Finiteness
import Mathlib.Algebra.Group.Submonoid.Finsupp
import Mathlib.Tactic
import Definitions.Def_LinearOptimization_LagrangeanDual
Formal statement
theorem LinearOptimization.integer_polyhedron_points_natGenerated {m n : ℕ}
    (D : Matrix (Fin m) (Fin n) ℤ) (d : Fin m → ℤ) :
    ∃ (k r : ℕ) (x : Fin k → (Fin n → ℝ)) (w : Fin r → (Fin n → ℝ)),
      lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ)) (fun i ↦ (d i : ℝ)) =
        {y | ∃ (i : Fin k) (q : Fin r → ℕ),
          y = x i + ∑ j, (q j : ℝ) • w j} := by sorry
Source
Bertsimas and Tsitsiklis, Introduction to Linear Optimization (Athena Scientific, 1997), Theorem 11.3, p. 496, proof outlined in Exercise 11.8(a)-(d), p. 525, especially part (c). The all-cases homogenized formulation is obtained via Gordan finite generation of the nonnegative integer solution monoid.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me