Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.4 — (EXC) holds iff every argmax(ω[p]) is an integral base set

Proved
SteinitzExchange.LocalSupermod.exc_iff_argmax_isIntegralBaseSet

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

exchange-propertyintegral-base-setm-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. Then

ω satisfies (EXC)  ⟺  argmax⁡(ω[p]) satisfies (B1) for every p∈RV,\omega\ \text{satisfies (EXC)}\iff\operatorname{argmax}(\omega[p])\ \text{satisfies (B1) for every}\ p\in\mathbb R^V,ω satisfies (EXC)⟺argmax(ω[p]) satisfies (B1) for every p∈RV,

where ω[p](x)=ω(x)+⟨p,x⟩\omega[p](x)=\omega(x)+\langle p,x\rangleω[p](x)=ω(x)+⟨p,x⟩. (Each argmax⁡(ω[p])\operatorname{argmax}(\omega[p])argmax(ω[p]) is finite and nonempty.)

The theorem characterizes M-concavity by the combinatorial shape of the maximizer sets of all linear perturbations; combined with Theorem 5.1 it links (EXC) to "matroidal" localizations.

Formalization Note. The paper phrases the condition as "argmax⁡(ω[p])‾\overline{\operatorname{argmax}(\omega[p])}argmax(ω[p])​ is an integral base polytope". This is formalized as "argmax⁡(ω[p])\operatorname{argmax}(\omega[p])argmax(ω[p]) is a finite integral base set", the reading fixed by the paper's Lemma 4.3 ("argmax(ω) is an integral base set, that is, …") and used in the proof of Theorem 5.3. The literal convex-hull reading makes the "if" direction false (e.g. B={(2,0),(1,1),(0,2)}B=\{(2,0),(1,1),(0,2)\}B={(2,0),(1,1),(0,2)}, ω=(0,−10,0)\omega=(0,-10,0)ω=(0,−10,0): every convex hull of a maximizer set is an integral base polytope, yet (EXC) fails). The same statement appears in the first mission of this series.

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

/-- Murota 1996, p. 286, Theorem 4.4, in the reading of Lemma 4.3 ("argmax(ω) is an integral base
set, that is, conv(argmax(ω)) is an integral base polytope"): on a finite integral base set `B`,
`ω` satisfies (EXC) iff `argmax(ω[p])` is an integral base set for every `p : V → ℝ`. -/
theorem exc_iff_argmax_isIntegralBaseSet {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
    (B : Finset (V → ℤ)) (hB : IsIntegralBaseSet B) (ω : (V → ℤ) → ℝ) :
    SatisfiesEXC B ω ↔ ∀ p : V → ℝ, IsIntegralBaseSet (argmaxB B (perturb ω p)) := by sorry

end SteinitzExchange.LocalSupermod
Source
Murota, Convexity and Steinitz's Exchange Property, Adv. Math. 124 (1996), p. 286, Theorem 4.4 (reading from Lemma 4.3, p. 285)
Read-back

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

Setting.

  • VVV is a finite, nonempty type with decidable equality.
  • B⊆ZVB \subseteq \mathbb{Z}^VB⊆ZV is a finite set, assumed to be an integral base set. That means B≠∅B \neq \emptysetB=∅, and for all x,y∈Bx, y \in Bx,y∈B and every uuu with (x−y)(u)>0(x-y)(u) > 0(x−y)(u)>0, there is vvv with (x−y)(v)<0(x-y)(v) < 0(x−y)(v)<0 and x−χu+χv∈Bx - \chi_u + \chi_v \in Bx−χu​+χv​∈B.
  • ω:ZV→R\omega : \mathbb{Z}^V \to \mathbb{R}ω:ZV→R is an arbitrary function. Its values outside BBB play no role.

Claim. The following two conditions are equivalent.

  1. (EXC): for all x,y∈Bx, y \in Bx,y∈B and every uuu with (x−y)(u)>0(x-y)(u) > 0(x−y)(u)>0, there is vvv with (x−y)(v)<0(x-y)(v) < 0(x−y)(v)<0 such that x−χu+χv∈Bx - \chi_u + \chi_v \in Bx−χu​+χv​∈B, y+χu−χv∈By + \chi_u - \chi_v \in By+χu​−χv​∈B, and
ω(x)+ω(y)≤ω(x−χu+χv)+ω(y+χu−χv).\omega(x) + \omega(y) \le \omega(x - \chi_u + \chi_v) + \omega(y + \chi_u - \chi_v).ω(x)+ω(y)≤ω(x−χu​+χv​)+ω(y+χu​−χv​).
  1. For every p∈RVp \in \mathbb{R}^Vp∈RV, the set
argmax⁡Bω[p]={x∈B:ω[p](y)≤ω[p](x) for all y∈B}\operatorname{argmax}_B \omega[p] = \{x \in B : \omega[p](y) \le \omega[p](x) \text{ for all } y \in B\}argmaxB​ω[p]={x∈B:ω[p](y)≤ω[p](x) for all y∈B}

is an integral base set. Here ω[p](x)=ω(x)+∑vp(v) x(v)\omega[p](x) = \omega(x) + \sum_{v} p(v)\, x(v)ω[p](x)=ω(x)+∑v​p(v)x(v).

The set in condition 2 is always nonempty, because BBB is finite and nonempty. So condition 2 amounts to the one-sided exchange property within each such argmax set.

Degenerate cases. Empty VVV and empty BBB are excluded. If BBB has one element, (EXC) holds vacuously, every argmax⁡Bω[p]\operatorname{argmax}_B \omega[p]argmaxB​ω[p] equals BBB, and both sides are true. The case p=0p = 0p=0 is included, giving argmax⁡Bω\operatorname{argmax}_B \omegaargmaxB​ω itself.

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