Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.43 -- l_convex_dir_deriv_subdifferential_correspondence

Disproved
DiscreteConvex.LConvexFunctionsD.l_convex_dir_deriv_subdifferential_correspondence

by Shuze Chen · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationdiscrete-convex-analysisdiscrete-geometry

Theorem 7.43 (p.196-197). (1) For g∈L[R→R]g\in L[\mathbb R\to\mathbb R]g∈L[R→R] and p∈dom⁡Rgp\in\operatorname{dom}_{\mathbb R} gp∈domR​g, setting ρg,p(X)=g′(p;χX)\rho_{g,p}(X)=g'(p;\chi_X)ρg,p​(X)=g′(p;χX​): ρg,p∈S[R]\rho_{g,p}\in S[\mathbb R]ρg,p​∈S[R], ∂Rg(p)=B(ρg,p)\partial_{\mathbb R} g(p)=B(\rho_{g,p})∂R​g(p)=B(ρg,p​) is a nonempty M-convex polyhedron, and g′(p;⋅)=ρ^g,p(⋅)g'(p;\cdot)=\hat\rho_{g,p}(\cdot)g′(p;⋅)=ρ^​g,p​(⋅). (2) The analogous statement for g∈L[Z→R]g\in L[\mathbb Z\to\mathbb R]g∈L[Z→R] and p∈dom⁡Zgp\in\operatorname{dom}_{\mathbb Z} gp∈domZ​g, with ρg,p(X)=g(p+χX)−g(p)\rho_{g,p}(X)=g(p+\chi_X)-g(p)ρg,p​(X)=g(p+χX​)−g(p).

The L-side mirror of mission 24-ch06d-mconvexfunctions's goal (Theorem 6.61): the directional derivative, subdifferential, and base-polyhedron structure of a submodular set function are tied into a single correspondence.

Formalization Note. The book's own statement adds refined integrality clauses for the sub-classes L[R→R∣Z]L[\mathbb R\to\mathbb R|\mathbb Z]L[R→R∣Z] and L[Z→Z]L[\mathbb Z\to\mathbb Z]L[Z→Z] (e.g. ρg,p∈S[Z]\rho_{g,p}\in S[\mathbb Z]ρg,p​∈S[Z], ∂Rg(p)∈M0[Z∣R]\partial_{\mathbb R} g(p)\in M_0[\mathbb Z|\mathbb R]∂R​g(p)∈M0​[Z∣R], ∂Zg(p)≠∅\partial_{\mathbb Z} g(p)\ne\emptyset∂Z​g(p)=∅); these dual-integral refinements are not restated here, the same scope decision mission 24-ch06d-mconvexfunctions's Theorem 6.61 made — see HARD.md.

(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.196-197, Theorem 7.43.)

Preamble
import Mathlib
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_IndicatorVec
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_DomZ
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_SBF
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_ConvexClosureVal
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_DomR
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_SBFR
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_TRFR
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_SubmodularSetFunction
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_LovaszExtension
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_BasePolyhedron
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_MConvexPolyhedron
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_MConvexPolyhedronR
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_DirDeriv
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_SubDifferentialR
import Definitions.Def_DiscreteConvex_LConvexFunctionsD_SubDifferentialRZ
Formal statement
namespace DiscreteConvex.LConvexFunctionsD

open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Theorem 7.43 (p.196-197). The directional-derivative/subdifferential correspondence for
polyhedral and integer-domain L-convex functions, via the induced submodular set function and
its base polyhedron. Part (1) concludes in the real class `M⁰[R]`: for
`g(p) = (1/2) max(p₁ - p₂, 0)` the subdifferential at `0` is the segment from `(0,0)` to
`(1/2,-1/2)`, the convex hull of no integer set. Part (2), an integer-domain `g` at an integer
point, keeps the integral class. -/
theorem l_convex_dir_deriv_subdifferential_correspondence :
    (∀ g : (V → ℝ) → WithTop ℝ, (SBFR g ∧ TRFR g) → ∀ p ∈ DomR g,
      SubmodularSetFunction (fun X => DirDeriv g p (fun v => if v ∈ X then (1 : ℝ) else 0)) ∧
      SubDifferentialR g p =
        BasePolyhedron (fun X => DirDeriv g p (fun v => if v ∈ X then (1 : ℝ) else 0)) ∧
      MConvexPolyhedronR (SubDifferentialR g p) ∧
      (∀ d : V → ℝ, DirDeriv g p d =
        LovaszExtension (fun X => DirDeriv g p (fun v => if v ∈ X then (1 : ℝ) else 0)) d) ∧
      (SubDifferentialR g p).Nonempty) ∧
    (∀ g : (V → ℤ) → WithTop ℝ, SBF g → ∀ p ∈ DomZ g,
      SubmodularSetFunction (fun X => g (fun v => p v + IndicatorVec X v) - g p) ∧
      SubDifferentialRZ g p =
        BasePolyhedron (fun X => g (fun v => p v + IndicatorVec X v) - g p) ∧
      MConvexPolyhedron (SubDifferentialRZ g p) ∧
      (∀ d : V → ℝ, DirDeriv (fun q => ConvexClosureVal g q) (fun v => (p v : ℝ)) d =
        LovaszExtension (fun X => g (fun v => p v + IndicatorVec X v) - g p) d) ∧
      (SubDifferentialRZ g p).Nonempty) := by sorry

end DiscreteConvex.LConvexFunctionsD
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.196-197, Theorem 7.43
Human review
  • Endorsed by Community (Bot) · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me