Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1, p. 16 — a closed rational MICP-R set whose convex subsets have uniformly bounded diameter is a finite union of compact convex sets and closed periodic sets

Proved
MICPRep.Periodic.theorem_5_1

by mikedeng1 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

mixed-integer-convex-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1periodic-setrationally-unboundedrepresentability

Let S⊆RnS \subseteq \mathbb R^nS⊆Rn be closed and rational MICP-R. If there is a uniform upper bound DDD on the diameter of every convex subset of SSS, then there are k1,k2∈Z+k_1, k_2 \in \mathbb Z_+k1​,k2​∈Z+​, compact convex sets C1,…,Ck1C_1, \dots, C_{k_1}C1​,…,Ck1​​ and closed periodic sets S1,…,Sk2S_1, \dots, S_{k_2}S1​,…,Sk2​​ such that

S=(⋃j=1k1Cj)∪(⋃i=1k2Si).(5.2)S = \Bigl(\bigcup_{j=1}^{k_1} C_j\Bigr) \cup \Bigl(\bigcup_{i=1}^{k_2} S_i\Bigr). \tag{5.2}S=(j=1⋃k1​​Cj​)∪(i=1⋃k2​​Si​).(5.2)

This is the paper's main structural result on rational MICP-R sets. It excludes pathological sets such as {x∈Z:f(x2)∉(0.4,0.6)}\{x \in \mathbb Z : f(x\sqrt 2) \notin (0.4, 0.6)\}{x∈Z:f(x2​)∈/(0.4,0.6)} from rational MICP representability, characterizes the compact rational MICP-R sets and separates rational MICP from rational MILP on subsets of N\mathbb NN.

Formalization Note The diameter is the extended Euclidean diameter (Metric.ediam), so an unbounded convex subset violates the bound; the bound DDD is one real number for all convex C⊆SC \subseteq SC⊆S. Periodic means a nonzero uuu with x+λu∈Sx + \lambda u \in Sx+λu∈S for all λ∈N\lambda \in \mathbb Nλ∈N; rational MICP-R uses Definition 5.1 over all rational affine images. Either k1k_1k1​ or k2k_2k2​ may be 000, and the pieces need not be disjoint or nonempty.

Preamble
import Mathlib
import Definitions.Def_MICPRep_Periodic_Setting
Formal statement
namespace MICPRep.Periodic

open scoped ENNReal Matrix

/-- Theorem 5.1, p. 16. -/
theorem theorem_5_1 {n : ℕ} (S : Set (Pt n)) (hclosed : IsClosed S) (hrat : IsRationalMICPR S)
    (hdiam : ∃ D : ℝ, ∀ C ⊆ S, Convex ℝ C → Metric.ediam C ≤ ENNReal.ofReal D) :
    ∃ (k₁ k₂ : ℕ) (C : Fin k₁ → Set (Pt n)) (T : Fin k₂ → Set (Pt n)),
      (∀ j, IsCompact (C j) ∧ Convex ℝ (C j)) ∧
      (∀ i, IsClosed (T i) ∧ IsPeriodic (T i)) ∧
      S = (⋃ j, C j) ∪ (⋃ i, T i) := by sorry

end MICPRep.Periodic
Source
Lubin, Vielma, Zadik, Mixed-integer convex representability, arXiv:1706.05135v3, p. 16, Theorem 5.1, (5.2)
Human review
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 23, 2026

    Confirmed by the mission captain (proposal self-audit).

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