Lemma 6.3, p. 24 — aff_ℤ(I) is a rational affine subspace, I_ℤ keeps the integer points of I, and lattice-preserving rational maps commute with aff_ℤ and (·)_ℤ
ProvedMICPRep.Periodic.lemma_6_3geometry-of-numbersmixed-integer-convex-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rational-affine-hull
Let be convex with . Then
- is a rational affine subspace;
- ;
- ;
- if is an invertible rational affine map with , then
The lemma lets the proof of Lemma 6.1 replace an index set by its rational part and change integer coordinates without losing integer points.
Formalization Note A rational affine subspace is a nonempty affine subspace spanned by its rational points. is ratAff A b with invertible; , the image of under , is written as the preimage of under .
Preamble
import Mathlib import Definitions.Def_MICPRep_Periodic_Setting
Formal statement
namespace MICPRep.Periodic
open scoped ENNReal Matrix
/-- Lemma 6.3, p. 24. -/
theorem lemma_6_3 {d : ℕ} (I : Set (Fin d → ℝ)) (hI : Convex ℝ I)
(hZ : (I ∩ intLattice d).Nonempty) :
IsRationalAffineSubspace (affZ I) ∧
IZ I ∩ intLattice d = I ∩ intLattice d ∧
affZ (IZ I) = affZ I ∧ affZ I = affineSpan ℝ (IZ I) ∧
∀ (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 →
ratAff A b '' IZ I = IZ (ratAff A b '' I) ∧
ratAff A b '' (affZ I : Set (Fin d → ℝ)) = (affZ (ratAff A b '' I) : Set (Fin d → ℝ)) := by sorry
end MICPRep.Periodic
Source
Lubin, Vielma, Zadik, Mixed-integer convex representability, arXiv:1706.05135v3, p. 24, Lemma 6.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.