Theorem 10 — Lovász's characterization of maximal -free convex sets of
ProvedMaxLatticeFree.Geometry.lovasz_maxLambdaFree_iffLet be a lattice of a linear space with . A set is a maximal -free convex set of if and only if one of the following holds:
- is a polyhedron in of the form where is a polytope, is a -subspace of ,
no point of lies in , and every facet of has a point of in its relative interior; 2. is an affine hyperplane of of the form , where , is a linear subspace of with , and is not a -subspace of .
For this is Lovász's theorem (Theorem 2 of the paper): maximal lattice-free convex sets are cylinders over polytopes with a lattice point in the relative interior of every facet, or irrational hyperplanes.
Formalization Note The page does not state ; it is added because for the only maximal -free set is (), which satisfies neither case. " is a polyhedron" is read as a polyhedron in , because a maximal -free set of lies in . "Its interior" is , as fixed on p. 10. is the Minkowski sum.
import Mathlib import Definitions.Def_MaxLatticeFree_Geometry_IsLatticeOf import Definitions.Def_MaxLatticeFree_Geometry_IsLambdaSubspace import Definitions.Def_MaxLatticeFree_Geometry_intW import Definitions.Def_MaxLatticeFree_Geometry_IsLambdaFree import Definitions.Def_MaxLatticeFree_Geometry_affDim import Definitions.Def_MaxLatticeFree_Geometry_Polyhedron open Pointwise
namespace MaxLatticeFree.Geometry
theorem lovasz_maxLambdaFree_iff {n : ℕ} (Λ : AddSubgroup (EuclideanSpace ℝ (Fin n)))
(V : Submodule ℝ (EuclideanSpace ℝ (Fin n))) (hΛ : IsLatticeOf Λ V) (hV : 0 < Module.finrank ℝ V)
(S : Set (EuclideanSpace ℝ (Fin n))) :
IsMaxLambdaFree Λ V S ↔
(IsPolyhedronIn V S ∧
∃ (P : Set (EuclideanSpace ℝ (Fin n))) (L : Submodule ℝ (EuclideanSpace ℝ (Fin n))),
IsPolytope P ∧ IsLambdaSubspace Λ V L ∧ S = P + (L : Set (EuclideanSpace ℝ (Fin n))) ∧
affDim S = affDim P + (Module.finrank ℝ L : ℤ) ∧
affDim P + (Module.finrank ℝ L : ℤ) = (Module.finrank ℝ V : ℤ) ∧
(Λ : Set (EuclideanSpace ℝ (Fin n))) ∩ intW (V : Set (EuclideanSpace ℝ (Fin n))) S = ∅ ∧
∀ F : Set (EuclideanSpace ℝ (Fin n)), IsFacet S F → ∃ x ∈ Λ, x ∈ relint F) ∨
(∃ v ∈ V, ∃ L : Submodule ℝ (EuclideanSpace ℝ (Fin n)), L ≤ V ∧
Module.finrank ℝ L + 1 = Module.finrank ℝ V ∧
S = v +ᵥ (L : Set (EuclideanSpace ℝ (Fin n))) ∧ ¬ IsLambdaSubspace Λ V L) := by sorry
end MaxLatticeFree.Geometry
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.