Lemma 6.7 (with dim aff_ℤ(I) ≥ 1 added), p. 26 — slicing an index set in a slab into finitely many pieces of lower rational dimension
ProvedMICPRep.Periodic.lemma_6_7geometry-of-numbersmixed-integer-convex-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rational-affine-hull
Let and let be convex with ,
Then there are invertible rational affine maps , , such that
The slices replace the naive slices , which need not stay rationally unbounded, in the induction step of Lemma 6.1.
Formalization Note The hypothesis is added: when the dimension is , (6.13a) forces , some must then contain an integer point, so its rational affine hull has dimension and (6.14a) fails. Lemma 6.1 uses the lemma only when this dimension is at least . Dimensions are integers with (slices without integer points have dimension ). The maps are indexed by all of and constrained only on .
Preamble
import Mathlib import Definitions.Def_MICPRep_Periodic_Setting
Formal statement
namespace MICPRep.Periodic
open scoped ENNReal Matrix
/-- Lemma 6.7, p. 26, with `dim aff_ℤ(I) ≥ 1` added. -/
theorem lemma_6_7 {d : ℕ} (l u : ℤ) (I : Set (Fin d → ℝ)) (hI : Convex ℝ I)
(h613a : (affZ I : Set (Fin d → ℝ)) = coordSubspace d (affDim (affZ I)))
(h613b : IZ I ⊆ slab d l u) (hdim : 1 ≤ affDim (affZ I)) :
∃ (A : ℤ → Matrix (Fin d) (Fin d) ℚ) (b : ℤ → Fin d → ℚ),
(∀ i ∈ Set.Icc l u, IsUnit (A i)) ∧
(∀ i ∈ Set.Icc l u, affDim (affZ (ratAff (A i) (b i) '' I)) ≤ affDim (affZ I) - 1) ∧
(⋃ i ∈ Set.Icc l u, ratAff (A i) (b i) '' I ∩ intLattice d) = I ∩ intLattice d ∧
∀ i ∈ Set.Icc l u, ∀ z ∈ ratAff (A i) (b i) '' I ∩ intLattice d,
ratAffInv (A i) (b i) z = z := by sorry
end MICPRep.Periodic
Source
Lubin, Vielma, Zadik, Mixed-integer convex representability, arXiv:1706.05135v3, p. 26, Lemma 6.7 (with the hypothesis dim aff_ℤ(I) ≥ 1 added)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.