§2.1, p. 4 — a function is M-convex if and only if it satisfies the exchange property (M-EXC)
ProvedMConvexL1.SD.m_exc_iffdiscrete-convex-analysisexchange-propertym-convex-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a finite set and . Call M-convex if it satisfies (M-EXC),
(with ), and lies in a hyperplane for some . Then is M-convex if and only if it satisfies
The paper defines M-convexity through (M-EXC) and the hyperplane condition, while every argument of Appendix A.2 applies (M-EXC); this equivalence is the bridge between the two.
Differences from the source:
- generalization: N = {1, …, n} with n ≥ 2 (§2, p. 4) → an arbitrary finite type V with decidable equality (any cardinality, including 0 and 1); reason: taking V = Fin n with n ≥ 2 gives the paper's setting; for |V| ≤ 1 the hypotheses force dom f to be at most one point and the statement still holds
- encoding: f : ℤⁿ → ℝ ∪ {+∞} → f : (V → ℤ) → WithTop ℝ, dom f = {x | f x ≠ ⊤}; reason: Lean convention for ℝ ∪ {+∞}; same instances
- encoding: M-convex: (M♮-EXC) with ∃ j ∈ supp⁻(x − y) ∪ {0}, χ₀ = 0, and dom f in a hyperplane {x(N) = θ} (p. 4) → MConvex f := MNatExchangeAxiom f ∧ ∃ θ, ∀ x ∈ dom f, Σ x = θ, where MNatExchangeAxiom states f(x) + f(y) ≥ min(f(x − χ_i) + f(y + χ_i), min_{j ∈ supp⁻(x−y)} (f(x − χ_i + χ_j) + f(y + χ_i − χ_j))); reason: a minimum over a finite set in the linear order WithTop ℝ is attained, so the min form is the existential with j = 0 meaning χ₀ = 0
Preamble
import Mathlib import Definitions.Def_MConvexL1_SD_Basic import Definitions.Def_DiscreteConvex_MConvexFunctions_MExchangeAxiom import Definitions.Def_DiscreteConvex_MConvexFunctions_ArgMin open DiscreteConvex.MConvexFunctions DiscreteConvex.Algorithms
Formal statement
namespace MConvexL1.SD
theorem m_exc_iff {V : Type*} [Fintype V] [DecidableEq V] (f : (V → ℤ) → WithTop ℝ) :
MConvex f ↔ MExchangeAxiom f := by sorry
end MConvexL1.SD
Source
Shioura, M-convex Function Minimization Under L1-Distance Constraint, arXiv:1809.03126v3, p. 4, §2.1, "It is known that a function f is M-convex if and only if it satisfies the following exchange property: (M-EXC)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.