Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.3 (Local Supermodularity Theorem, corrected) — (EXC) iff ω = ω̂ on B and every localization of ω° is "matroidal"

Proved
SteinitzExchange.LocalSupermod.exc_iff_localization_matroidal

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

concave-conjugatediscrete-convex-analysislocal-supermodularitym-concavep2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let B⊆ZVB\subseteq\mathbb Z^VB⊆ZV be a finite integral base set and ω:B→R\omega:B\to\mathbb Rω:B→R. Let ω∘(p)=min⁡{⟨p,x⟩−ω(x)∣x∈B}\omega^\circ(p)=\min\{\langle p,x\rangle-\omega(x)\mid x\in B\}ω∘(p)=min{⟨p,x⟩−ω(x)∣x∈B} be the concave conjugate, ω^\hat\omegaω^ the concave closure, and L^(ω∘,p0)(p)=inf⁡{⟨p,b⟩∣b∈∂ω∘(p0)}\hat L(\omega^\circ,p_0)(p)=\inf\{\langle p,b\rangle\mid b\in\partial\omega^\circ(p_0)\}L^(ω∘,p0​)(p)=inf{⟨p,b⟩∣b∈∂ω∘(p0​)} the localization of ω∘\omega^\circω∘ at p0p_0p0​. Then ω\omegaω satisfies (EXC) if and only if

  1. ω(x)=ω^(x)\omega(x)=\hat\omega(x)ω(x)=ω^(x) for every x∈Bx\in Bx∈B, and
  2. L^(ω∘,p0)\hat L(\omega^\circ,p_0)L^(ω∘,p0​) is "matroidal" (satisfies (C1) and (C2)) at every point p0∈RVp_0\in\mathbb R^Vp0​∈RV.

In short,

ω is M-concave  ⟺  ω=ω^ on B and ω∘ is "locally matroidal" everywhere.\omega\ \text{is M-concave}\iff\omega=\hat\omega\ \text{on}\ B\ \text{and}\ \omega^\circ\ \text{is "locally matroidal" everywhere}.ω is M-concave⟺ω=ω^ on B and ω∘ is "locally matroidal" everywhere.

Since (C1) is a supermodularity condition, the theorem says that the exchange property (EXC) is "a collection of local supermodularity" of the conjugate, just as (B1) for a set corresponds to supermodularity of its support function (Theorem 5.1).

Formalization Note. The paper's statement has only condition 2. The "only if" direction holds as printed, but the "if" direction fails without condition 1: see localization_matroidal_not_sufficient, where B={(2,0),(1,1),(0,2)}B=\{(2,0),(1,1),(0,2)\}B={(2,0),(1,1),(0,2)} and ω=(0,−10,0)\omega=(0,-10,0)ω=(0,−10,0). The paper's proof applies Theorem 5.1 to argmax⁡(ω[−p0])\operatorname{argmax}(\omega[-p_0])argmax(ω[−p0​]), which requires every integer point of its convex hull to be a maximizer; condition 1 (ω extends to a concave function, which the paper proves for M-concave ω in Section 4) supplies this. The localization is defined by (5.8)–(5.9), not by formula (5.12). "Matroidal" includes positive homogeneity, and (C2) is required for every non-increasing indexing of VVV.

Preamble
import Mathlib
import Definitions.Def_SteinitzExchange_LocalSupermod_IntegralBaseSet
import Definitions.Def_SteinitzExchange_LocalSupermod_Exchange
import Definitions.Def_SteinitzExchange_LocalSupermod_Matroidal
import Definitions.Def_SteinitzExchange_LocalSupermod_Localization
Formal statement
namespace SteinitzExchange.LocalSupermod

/-- Murota 1996, p. 292, Theorem 5.3 (Local Supermodularity Theorem), corrected. For `ω` on a
finite integral base set `B`: `ω` satisfies (EXC) iff `ω` coincides on `B` with its concave
closure `ω̂` (4.2) and the localization `L̂(ω°, p₀)` of the concave conjugate `ω°` (5.6) at
`p₀` ((5.8)–(5.9)) is "matroidal" at every `p₀ ∈ ℝ^V`. The printed statement omits the
concave-closure clause; without it the "if" direction fails
(see `localization_matroidal_not_sufficient`). -/
theorem exc_iff_localization_matroidal {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
    (B : Finset (V → ℤ)) (hB : IsIntegralBaseSet B) (ω : (V → ℤ) → ℝ) :
    SatisfiesEXC B ω ↔
      ((∀ x ∈ B, concaveClosure B ω (toReal x) = ω x) ∧
        ∀ p₀ : V → ℝ, IsMatroidal (localization (concaveConj B ω) p₀)) := by sorry

end SteinitzExchange.LocalSupermod
Source
Murota, Convexity and Steinitz's Exchange Property, Adv. Math. 124 (1996), p. 292, Theorem 5.3 (corrected by the concave-closure condition; concave closure from p. 284, Eq. (4.2))
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let VVV be a type that is finite, has decidable equality and is nonempty. Write ZV\mathbb{Z}^VZV for the functions V→ZV \to \mathbb{Z}V→Z (integer vectors indexed by VVV) and RV\mathbb{R}^VRV for the functions V→RV \to \mathbb{R}V→R. The statement takes three explicit inputs:

  • BBB, a finite set of integer vectors, B⊆ZVB \subseteq \mathbb{Z}^VB⊆ZV;
  • a hypothesis hBh_BhB​ that BBB satisfies the bundle predicate IsIntegralBaseSet(B)\mathrm{IsIntegralBaseSet}(B)IsIntegralBaseSet(B);
  • a function ω:ZV→R\omega : \mathbb{Z}^V \to \mathbb{R}ω:ZV→R. It is defined on all of ZV\mathbb{Z}^VZV, not only on BBB, and takes finite real values everywhere.

Under these assumptions the theorem asserts this equivalence:

SatisfiesEXC(B,ω)  ⟺  (∀x∈B: ω^B(ι(x))=ω(x)) ∧ (∀p0∈RV: IsMatroidal(L(ωB∘, p0))).\mathrm{SatisfiesEXC}(B,\omega) \iff \Big( \forall x \in B:\ \hat\omega_B(\iota(x)) = \omega(x) \Big) \ \wedge\ \Big( \forall p_0 \in \mathbb{R}^V:\ \mathrm{IsMatroidal}\big(\mathcal{L}(\omega^{\circ}_B,\, p_0)\big) \Big).SatisfiesEXC(B,ω)⟺(∀x∈B: ω^B​(ι(x))=ω(x)) ∧ (∀p0​∈RV: IsMatroidal(L(ωB∘​,p0​))).

The symbols are:

  • ι(x)∈RV\iota(x) \in \mathbb{R}^Vι(x)∈RV is the integer vector xxx viewed as a real vector (the bundle's toReal).
  • ω^B=concaveClosure(B,ω)\hat\omega_B = \mathrm{concaveClosure}(B,\omega)ω^B​=concaveClosure(B,ω) is a real-valued function on RV\mathbb{R}^VRV built from BBB and ω\omegaω.
  • ωB∘=concaveConj(B,ω)\omega^{\circ}_B = \mathrm{concaveConj}(B,\omega)ωB∘​=concaveConj(B,ω) is an object built from BBB and ω\omegaω.
  • L(ωB∘,p0)=localization(ωB∘,p0)\mathcal{L}(\omega^{\circ}_B, p_0) = \mathrm{localization}(\omega^{\circ}_B, p_0)L(ωB∘​,p0​)=localization(ωB∘​,p0​) is that object localized at the real vector p0p_0p0​.
  • SatisfiesEXC\mathrm{SatisfiesEXC}SatisfiesEXC, IsIntegralBaseSet\mathrm{IsIntegralBaseSet}IsIntegralBaseSet and IsMatroidal\mathrm{IsMatroidal}IsMatroidal are predicates.

All six of these (toReal, concaveClosure, concaveConj, localization, SatisfiesEXC, IsIntegralBaseSet, IsMatroidal) are defined in the imported bundle files. Their code is not part of what was supplied, so this read-back cannot unfold them. The names suggest a concave closure, a concave conjugate, a localization, an exchange axiom, an integral base set and a matroid condition, but the formal content of each is exactly its bundle definition and nothing more. The documentation comment attached to the theorem is not part of the formal assertion.

The equivalence has two directions:

  • "Only if": whenever ω\omegaω satisfies SatisfiesEXC\mathrm{SatisfiesEXC}SatisfiesEXC on BBB, two things hold. First, ω^B\hat\omega_Bω^B​ agrees with ω\omegaω at every point of BBB. Second, for every real vector p0∈RVp_0 \in \mathbb{R}^Vp0​∈RV (not only integer ones), the localization of ωB∘\omega^{\circ}_BωB∘​ at p0p_0p0​ satisfies IsMatroidal\mathrm{IsMatroidal}IsMatroidal.
  • "If": the conjunction of both conditions implies SatisfiesEXC(B,ω)\mathrm{SatisfiesEXC}(B,\omega)SatisfiesEXC(B,ω).

The first condition only asks for agreement at points of BBB. It says nothing about points of ZV\mathbb{Z}^VZV outside BBB. Whether the values ω(x)\omega(x)ω(x) for x∉Bx \notin Bx∈/B affect any of the three predicates depends on the bundle definitions and cannot be read from this statement.

Degenerate cases. Because VVV must be nonempty, the empty index type is excluded. The smallest allowed case is a one-element VVV, where ZV≅Z\mathbb{Z}^V \cong \mathbb{Z}ZV≅Z and RV≅R\mathbb{R}^V \cong \mathbb{R}RV≅R; the equivalence is still asserted there, in the same form. Nothing in the statement itself excludes B=∅B = \emptysetB=∅ or a one-element BBB. Whether those are allowed depends entirely on IsIntegralBaseSet\mathrm{IsIntegralBaseSet}IsIntegralBaseSet. If B=∅B = \emptysetB=∅ is allowed:

  • the condition "∀x∈B\forall x \in B∀x∈B" is vacuously true;
  • the theorem then reduces to SatisfiesEXC(∅,ω)  ⟺  ∀p0, IsMatroidal(L(ω∅∘,p0))\mathrm{SatisfiesEXC}(\emptyset,\omega) \iff \forall p_0,\ \mathrm{IsMatroidal}(\mathcal{L}(\omega^{\circ}_\emptyset,p_0))SatisfiesEXC(∅,ω)⟺∀p0​, IsMatroidal(L(ω∅∘​,p0​)), and what each side means there is again fixed by the unseen definitions.

If IsIntegralBaseSet\mathrm{IsIntegralBaseSet}IsIntegralBaseSet cannot be satisfied at all, the theorem is vacuously true. Its satisfiability cannot be checked from the supplied code.

ω^B\hat\omega_Bω^B​ is real-valued rather than extended-real-valued. So wherever its underlying construction (for example an infimum or supremum) is unbounded, empty or not attained, Lean returns whatever default value the bundle definition gives, and the equation ω^B(ι(x))=ω(x)\hat\omega_B(\iota(x)) = \omega(x)ω^B​(ι(x))=ω(x) is a statement about that value. The statement itself shows no division, natural-number subtraction or integral.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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