Theorem 7.1 -- L-natural-convexity equals the direct translation-submodularity axiom
ProvedDiscreteConvex.LConvexFunctions.lnat_convex_iff_sbf_natcombinatoricsdiscrete-convex-analysis
Theorem 7.1 (p.178). For with , is L-convex if and only if satisfies the direct translation-submodularity axiom (SBF[Z]). The direct analogue, for L-convexity, of chunk 06's Theorem 6.2 for M-convexity.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.178, Theorem 7.1.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexFunctions_LNaturalConvex import Definitions.Def_DiscreteConvex_LConvexFunctions_SBFNat import Definitions.Def_DiscreteConvex_LConvexFunctions_DomZ
Formal statement
namespace DiscreteConvex.LConvexFunctions
/-- Theorem 7.1 (Murota, *Discrete Convex Analysis*, SIAM 2003, p.178). For a function
`g : Zⱽ → R ∪ {+∞}` with `dom g ≠ ∅`, `g` is L♮-convex if and only if `g` satisfies the direct
translation-submodularity axiom (SBF♮[Z]). -/
theorem lnat_convex_iff_sbf_nat {V : Type*} [Fintype V] [DecidableEq V]
(g : (V → ℤ) → WithTop ℝ) (hg : (DomZ g).Nonempty) :
LNaturalConvex g ↔ SBFNat g := by sorry
end DiscreteConvex.LConvexFunctions
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.178, Theorem 7.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.