Theorem 5.8 -- lconvex_minkowski_sum
ProvedDiscreteConvex.LConvexSetsB.lconvex_minkowski_sumcombinatoricsconvex-optimizationdiscrete-convex-analysis
Theorem 5.8 (p.126). For L-convex sets , : the convex hull of the Minkowski sum equals the Minkowski sum of the convex hulls ("convexity in Minkowski sum"). Unlike the M-convex case (Theorem 4.23(3)), the Minkowski sum of two L-convex sets need not itself be L-convex (Note 5.11 gives an explicit counterexample), so this theorem states only the closure identity, not L-convexity of .
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.126, Theorem 5.8.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexSetsB_LConvexSet import Definitions.Def_DiscreteConvex_LConvexSetsB_IntEmbed open scoped Pointwise
Formal statement
/-!
Murota, *Discrete Convex Analysis*, SIAM 2003, p.126, Theorem 5.8, in `DiscreteConvex.LConvexSetsB`.
-/
namespace DiscreteConvex.LConvexSetsB
/-- Theorem 5.8 (Murota, *Discrete Convex Analysis*, SIAM 2003, p.126). See the item's
`natural_language_statement` for the full statement. -/
theorem lconvex_minkowski_sum {V : Type*} [Fintype V] [DecidableEq V] (D1 D2 : Set (V → ℤ))
(hD1 : LConvexSet D1) (hD2 : LConvexSet D2) :
convexHull ℝ (IntEmbed (D1 + D2)) = convexHull ℝ (IntEmbed D1) + convexHull ℝ (IntEmbed D2) := by sorry
end DiscreteConvex.LConvexSetsB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.126, Theorem 5.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.