Theorem 6.48 -- polyhedral_mconvex_iff_mnat_with_domain
DisprovedDiscreteConvex.MConvexFunctionsD.polyhedral_mconvex_iff_mnat_with_domainconvex-optimizationdiscrete-convex-analysis
Theorem 6.48 (p.162). A polyhedral M-convex function is polyhedral M-convex. Conversely, a polyhedral M-convex function is polyhedral M-convex if and only if its effective domain is contained in for some .
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.162, Theorem 6.48.)
Retired (2026-10-07). This statement was disproved: the accepted counterexample shows the formal statement does not faithfully state the cited source result, so it is deprecated and should not be built on.
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MConvexFunctionsD_DomR import Definitions.Def_DiscreteConvex_MConvexFunctionsD_MExchangeAxiomR import Definitions.Def_DiscreteConvex_MConvexFunctionsD_MNaturalConvexR
Formal statement
namespace DiscreteConvex.MConvexFunctionsD
open scoped Pointwise
open Classical
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Theorem 6.48 (p.181). -/
theorem polyhedral_mconvex_iff_mnat_with_domain (g : (V → ℝ) → WithTop ℝ) :
(MExchangeAxiomR g → MNaturalConvexR g) ∧
(MNaturalConvexR g → (MExchangeAxiomR g ↔ ∃ r : ℝ, ∀ x ∈ DomR g, ∑ v, x v = r)) := by sorry
end DiscreteConvex.MConvexFunctionsD
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.162, Theorem 6.48
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.