Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Flatness theorem (Lenstra; Grötschel–Lovász–Schrijver) — a lattice-free rational polyhedron has width ≤n(n+1)2n2/2\le n(n+1)2^{n^2/2}≤n(n+1)2n2/2 in some integral direction

Proved
CookSensitivity.ChvatalRank.exists_flat_direction_of_no_integer_point

by tianyipeng · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

chvatal-rankcutting-planesflatnessgeometry-of-numbersinteger-programming

This is the flatness theorem for lattice-free rational polyhedra, in the form used by Cook, Gerards, Schrijver and Tardos.

Let n≥1n \ge 1n≥1 and let P={x∈Qn:Dx≤d}P = \{x \in \mathbb{Q}^n : Dx \le d\}P={x∈Qn:Dx≤d} be a rational polyhedron (possibly unbounded, possibly empty) that contains no integral vector, P∩Zn=∅P \cap \mathbb{Z}^n = \emptysetP∩Zn=∅. Then there is a nonzero integral vector w∈Znw \in \mathbb{Z}^nw∈Zn such that

∣w(x−x′)∣  ≤  n(n+1) 212n2for all x,x′∈P.|w(x - x')| \;\le\; n(n+1)\,2^{\frac12 n^2} \qquad \text{for all } x, x' \in P.∣w(x−x′)∣≤n(n+1)221​n2for all x,x′∈P.

In words: a lattice-free rational polyhedron is flat in some integral direction www — its lattice width in direction www is bounded by a number depending only on the dimension. For bounded PPP 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 n2n2n3n^{2n}2^{n^3}n2n2n3: one cuts the polyhedron down along the flat direction www, one hyperplane wx=βwx = \betawx=β 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 n≥1n \ge 1n≥1 is needed because Z0\mathbb{Z}^0Z0 has no nonzero vector (in dimension 000 every lattice-free polyhedron is empty anyway). The width w(x−x′)w(x-x')w(x−x′) is computed in Q\mathbb{Q}Q and compared in R\mathbb{R}R with the bound n(n+1)⋅2n2/2n(n+1)\cdot 2^{n^2/2}n(n+1)⋅2n2/2, 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.

Preamble
import Mathlib
import Definitions.Def_CookSensitivity_ChvatalRank_IntegerProgram
Formal statement
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
Source
Cook, Gerards, Schrijver, Tardos, Sensitivity theorems in integer linear programming, Math. Programming 34 (1986), p. 259, proof of Theorem 9 [cited as Theorem 8], citing Grötschel, Lovász, Schrijver [18] (Geometric Algorithms and Combinatorial Optimization, Springer 1988) and, for bounded P, Lenstra [22] (Integer programming with a fixed number of variables, Math. Oper. Res. 8 (1983))

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