Theorem 5.5 -- L-convex sets correspond to integer distance functions
ProvedDiscreteConvex.LConvexSets.lconvex_set_iff_distance_functioncombinatoricsdiscrete-convex-analysis
Theorem 5.5 (p.125). A nonempty set is L-convex if and only if for some integer-valued distance function satisfying the triangle inequality, establishing a one-to-one correspondence between L-convex sets and integer-valued distance functions with the triangle inequality.
Formalization Note. As with chunk 04's Theorem 4.15, the book additionally names the mutually inverse maps (Eq. (5.8)) and realizing this correspondence; this mission states the iff itself (an existential ) and does not construct as a separate object.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.125, Theorem 5.5.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexSets_LConvexSet import Definitions.Def_DiscreteConvex_LConvexSets_DistanceFunction import Definitions.Def_DiscreteConvex_LConvexSets_TriangleInequality import Definitions.Def_DiscreteConvex_LConvexSets_AdmissiblePotentials import Definitions.Def_DiscreteConvex_LConvexSets_IsIntegerValuedDist
Formal statement
namespace DiscreteConvex.LConvexSets
/-- Theorem 5.5 (Murota, *Discrete Convex Analysis*, SIAM 2003, p.125). A nonempty set
`D ⊆ Zⱽ` is L-convex if and only if `D = D(γ) ∩ Zⱽ` for some integer-valued distance function
`γ` satisfying the triangle inequality, establishing a one-to-one correspondence between
L-convex sets and integer-valued distance functions with the triangle inequality. -/
theorem lconvex_set_iff_distance_function {V : Type*} [Fintype V] [DecidableEq V]
(D : Set (V → ℤ)) (hD : D.Nonempty) :
LConvexSet D ↔
∃ γ : V → V → WithTop ℝ, DistanceFunction γ ∧ TriangleInequality γ ∧
IsIntegerValuedDist γ ∧
D = {p : V → ℤ | (fun v => (p v : ℝ)) ∈ AdmissiblePotentials γ} := by sorry
end DiscreteConvex.LConvexSets
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.125, Theorem 5.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.