Theorem 5.9 -- discrete separation for L-convex sets
ProvedDiscreteConvex.LConvexSets.discrete_separation_lconvexTheorem 5.9 (p.126). Let be L-convex sets. If they are disjoint, there exists such that
An ordinary separating hyperplane exists for any two disjoint convex sets; the content here is that the separator can always be forced into — three values per coordinate — independent of how large or awkwardly shaped are. A formalization proving only the classical real-valued separation (any ) would state nothing specific to discrete convexity.
Formalization Note. The conclusion is stated as (addition) rather than (subtraction), an equivalent reformulation that avoids EReal subtraction's ⊤ - ⊤ ambiguity; the infimum and supremum are taken in EReal (a complete lattice) so that both are total even though may be unbounded (L-convex sets are always translation-invariant along the all-ones direction, hence typically infinite).
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.126, Theorem 5.9.)
import Mathlib import Definitions.Def_DiscreteConvex_LConvexSets_LConvexSet
namespace DiscreteConvex.LConvexSets
/-- Theorem 5.9 (discrete separation for L-convex sets; Murota, *Discrete Convex Analysis*,
SIAM 2003, p.126). Let `D1, D2 ⊆ Zⱽ` be L-convex sets. If they are disjoint, there exists
`x* ∈ {-1,0,1}ⱽ` such that `inf{⟨p,x*⟩ : p ∈ D1} - sup{⟨p,x*⟩ : p ∈ D2} ≥ 1`. -/
theorem discrete_separation_lconvex {V : Type*} [Fintype V] [DecidableEq V]
(D1 D2 : Set (V → ℤ)) (hD1 : LConvexSet D1) (hD2 : LConvexSet D2)
(hdisj : D1 ∩ D2 = ∅) :
∃ x : V → ℤ, (∀ v, x v = -1 ∨ x v = 0 ∨ x v = 1) ∧
sSup ((fun p : V → ℤ => ((∑ v, (x v : ℝ) * (p v : ℝ) : ℝ) : EReal)) '' D2) + 1 ≤
sInf ((fun p : V → ℤ => ((∑ v, (x v : ℝ) * (p v : ℝ) : ℝ) : EReal)) '' D1) := by sorry
end DiscreteConvex.LConvexSets
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.