Theorem 9 — maximal -free convex sets of a subspace
ProvedMaxLatticeFree.Geometry.maxLambdaFree_in_W_iffLet be a lattice of a linear space and let be a linear space of containing , with . A set is a maximal -free convex set of if and only if one of the following holds:
- is a polyhedron in with , is a maximal -free convex set of , and the map
is a bijection from the facets of onto the facets of ; 2. is an affine hyperplane of of the form , where and is a linear hyperplane of , such that is a hyperplane of () that is not a -subspace of ; 3. is a half-space of , with not orthogonal to , that contains on its boundary: for all .
Here may span a proper subspace of , as happens for when is an irrational subspace (for example , whose integer points span ). The theorem reduces the classification in to Lovász's classification in (Theorem 10) and adds the two genuinely new cases (ii) and (iii). It is the geometric input for the characterization of minimal valid inequalities of the multi-row relaxation .
Formalization Note The page does not state ; it is added because for the only maximal -free set is , which satisfies none of the three cases (the theorem as stated is true when ). "One-to-one correspondence, with the facet corresponding to " is stated as: is a facet of for every facet of , the map is injective, and every facet of is of this form. Dimensions are integer valued with ; hyperplane conditions are written in natural numbers.
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 maxLambdaFree_in_W_iff {n : ℕ} (Λ : AddSubgroup (EuclideanSpace ℝ (Fin n)))
(V W : Submodule ℝ (EuclideanSpace ℝ (Fin n))) (hΛ : IsLatticeOf Λ V) (hVW : V ≤ W)
(hW : 0 < Module.finrank ℝ W) (S : Set (EuclideanSpace ℝ (Fin n))) :
IsMaxLambdaFree Λ W S ↔
(IsPolyhedronIn W S ∧ affDim S = (Module.finrank ℝ W : ℤ) ∧
IsMaxLambdaFree Λ V (S ∩ (V : Set (EuclideanSpace ℝ (Fin n)))) ∧
(∀ F : Set (EuclideanSpace ℝ (Fin n)), IsFacet S F → IsFacet (S ∩ (V : Set (EuclideanSpace ℝ (Fin n)))) (F ∩ (V : Set (EuclideanSpace ℝ (Fin n))))) ∧
(∀ F G : Set (EuclideanSpace ℝ (Fin n)), IsFacet S F → IsFacet S G →
F ∩ (V : Set (EuclideanSpace ℝ (Fin n))) = G ∩ (V : Set (EuclideanSpace ℝ (Fin n))) → F = G) ∧
(∀ G : Set (EuclideanSpace ℝ (Fin n)), IsFacet (S ∩ (V : Set (EuclideanSpace ℝ (Fin n)))) G →
∃ F : Set (EuclideanSpace ℝ (Fin n)), IsFacet S F ∧ F ∩ (V : Set (EuclideanSpace ℝ (Fin n))) = G)) ∨
(∃ v ∈ W, ∃ L : Submodule ℝ (EuclideanSpace ℝ (Fin n)), L ≤ W ∧
Module.finrank ℝ L + 1 = Module.finrank ℝ W ∧
S = v +ᵥ (L : Set (EuclideanSpace ℝ (Fin n))) ∧
Module.finrank ℝ (L ⊓ V : Submodule ℝ (EuclideanSpace ℝ (Fin n))) + 1 = Module.finrank ℝ V ∧
¬ IsLambdaSubspace Λ V (L ⊓ V)) ∨
(∃ (a : EuclideanSpace ℝ (Fin n)) (b : ℝ), (∃ w ∈ W, inner ℝ a w ≠ 0) ∧
S = (W : Set (EuclideanSpace ℝ (Fin n))) ∩ {x | inner ℝ a x ≤ b} ∧
(V : Set (EuclideanSpace ℝ (Fin n))) ⊆ {x | inner ℝ a x = b}) := by sorry
end MaxLatticeFree.Geometry
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.