Lemma 6.5, p. 25 — flatness dichotomy: an integer point in relint(I_ℤ), or after a lattice-preserving rational map I_ℤ lies in a slab l ≤ z₁ ≤ u
ProvedMICPRep.Periodic.lemma_6_5flatnessgeometry-of-numbersp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rational-affine-hull
Let be a (not necessarily full-dimensional) convex set with . Then either has an integer point in its relative interior, or there are an invertible rational affine map with and integers such that
It is a variant of Khintchine's flatness theorem and drives the induction on dimension in the proof of Lemma 6.1.
Formalization Note is the integer-valued dimension of ; the relative interior is Mathlib's intrinsicInterior. is the coordinate with -based index ; for the slab is all of , and the first alternative holds anyway.
Preamble
import Mathlib import Definitions.Def_MICPRep_Periodic_Setting
Formal statement
namespace MICPRep.Periodic
open scoped ENNReal Matrix
/-- Lemma 6.5, p. 25. -/
theorem lemma_6_5 {d : ℕ} (I : Set (Fin d → ℝ)) (hI : Convex ℝ I)
(hZ : (I ∩ intLattice d).Nonempty) :
(intrinsicInterior ℝ (IZ I) ∩ intLattice d).Nonempty ∨
∃ (A : Matrix (Fin d) (Fin d) ℚ) (b : Fin d → ℚ), IsUnit A ∧
ratAff A b '' intLattice d = intLattice d ∧
ratAff A b ⁻¹' intLattice d = intLattice d ∧
∃ l u : ℤ, IZ (ratAff A b '' I) ⊆ slab d l u ∧
(affZ (ratAff A b '' I) : Set (Fin d → ℝ)) = coordSubspace d (setDim (IZ I)) := by sorry
end MICPRep.Periodic
Source
Lubin, Vielma, Zadik, Mixed-integer convex representability, arXiv:1706.05135v3, p. 25, Lemma 6.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.