Proposition 7.9 -- univariate_and_pair_lconvexity
DisprovedDiscreteConvex.LConvexFunctionsB.univariate_and_pair_lconvexityconvex-optimizationdiscrete-convex-analysis
Proposition 7.9 (p.183). Let be univariate discrete convex. (1) is L-convex. (2) The function defined by is L-convex.
Formalization Note. Part (1) is stated with the ground set represented as Unit (a single coordinate); part (2) with the ground set Fin 2.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.183, Proposition 7.9.)
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_LConvexFunctionsB_SBF import Definitions.Def_DiscreteConvex_LConvexFunctionsB_TRF import Definitions.Def_DiscreteConvex_LConvexFunctionsB_LNaturalConvex import Definitions.Def_DiscreteConvex_LConvexFunctionsB_DiscreteConvexUnivariate
Formal statement
namespace DiscreteConvex.LConvexFunctionsB
open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Proposition 7.9 (p.183). A univariate discrete convex function is L♮-convex; the two-variable
difference function it induces is L-convex. -/
theorem univariate_and_pair_lconvexity (psi : ℤ → WithTop ℝ) (hpsi : DiscreteConvexUnivariate psi) :
LNaturalConvex (fun p : Unit → ℤ => psi (p ())) ∧
(SBF (fun p : Fin 2 → ℤ => psi (p 0 - p 1)) ∧ TRF (fun p : Fin 2 → ℤ => psi (p 0 - p 1))) := by sorry
end DiscreteConvex.LConvexFunctionsB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.183, Proposition 7.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.