Flatness theorem (Lenstra; Grötschel–Lovász–Schrijver) — a lattice-free rational polyhedron has width in some integral direction
ProvedCookSensitivity.ChvatalRank.exists_flat_direction_of_no_integer_pointThis is the flatness theorem for lattice-free rational polyhedra, in the form used by Cook, Gerards, Schrijver and Tardos.
Let and let be a rational polyhedron (possibly unbounded, possibly empty) that contains no integral vector, . Then there is a nonzero integral vector such that
In words: a lattice-free rational polyhedron is flat in some integral direction — its lattice width in direction is bounded by a number depending only on the dimension. For bounded the existence of such a direction is due to Lenstra; the version for arbitrary rational polyhedra, with this bound, is due to Grötschel, Lovász and Schrijver. It is the geometric input to the proof of the Cook–Coullard–Turán theorem that lattice-free polyhedra have Chvátal rank at most : one cuts the polyhedron down along the flat direction , one hyperplane at a time, using induction on the dimension on each hyperplane.
Formalization Note Points are Fin n → ℚ and "polyhedron" is IsPolyhedron (finitely many rational inequalities). The hypothesis is needed because has no nonzero vector (in dimension every lattice-free polyhedron is empty anyway). The width is computed in and compared in with the bound , where the power is the real power Real.rpow. The paper prints the inequality as strict in one place; the non-strict form stated here is the weaker one and is all that the proof of Theorem 8 uses.
import Mathlib import Definitions.Def_CookSensitivity_ChvatalRank_IntegerProgram
namespace CookSensitivity.ChvatalRank
open Matrix
theorem exists_flat_direction_of_no_integer_point {n : ℕ} (hn : 1 ≤ n) (P : Set (Fin n → ℚ))
(hP : IsPolyhedron P) (hPZ : ∀ x ∈ P, ¬ IsIntegral x) :
∃ w : Fin n → ℤ, w ≠ 0 ∧ ∀ x ∈ P, ∀ x' ∈ P,
|((((fun i => (w i : ℚ)) ⬝ᵥ (x - x') : ℚ)) : ℝ)| ≤
((n * (n + 1) : ℕ) : ℝ) * (2 : ℝ) ^ ((n : ℝ) ^ 2 / 2) := by sorry
end CookSensitivity.ChvatalRank