Proposition 5.3 -- induced_gamma_triangle_and_recovery
ProvedDiscreteConvex.LConvexSetsB.induced_gamma_triangle_and_recoverycombinatoricsdiscrete-convex-analysisdiscrete-geometry
Proposition 5.3 (p.124), Eq. (5.8). For nonempty , define . Then (1) satisfies the triangle inequality, i.e. , and (2) if is an L-convex set, .
Formalization Note. As in Theorem 5.2 (chunk 05-lconvex-sets), the book's "" in part (2) denotes the convex hull (the surrounding text introduces here as the polyhedral description of the convex hull of an L-convex set), formalized as convexHull ℝ (IntEmbed D).
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.124, Proposition 5.3, Eq. (5.8).)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexSetsB_TriangleInequality import Definitions.Def_DiscreteConvex_LConvexSetsB_InducedGamma import Definitions.Def_DiscreteConvex_LConvexSetsB_LConvexSet import Definitions.Def_DiscreteConvex_LConvexSetsB_IntEmbed import Definitions.Def_DiscreteConvex_LConvexSetsB_AdmissiblePotentials
Formal statement
/-!
Murota, *Discrete Convex Analysis*, SIAM 2003, p.124, Proposition 5.3, in `DiscreteConvex.LConvexSetsB`.
-/
namespace DiscreteConvex.LConvexSetsB
/-- Proposition 5.3 (Murota, *Discrete Convex Analysis*, SIAM 2003, p.124). See the item's
`natural_language_statement` for the full statement. -/
theorem induced_gamma_triangle_and_recovery {V : Type*} [Fintype V] [DecidableEq V]
(D : Set (V → ℤ)) (hDne : D.Nonempty) :
TriangleInequality (InducedGamma D) ∧
(LConvexSet D → convexHull ℝ (IntEmbed D) = AdmissiblePotentials (InducedGamma D)) := by sorry
end DiscreteConvex.LConvexSetsB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.124, Proposition 5.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.