Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1 — (B1) holds iff the support function ψ° is "matroidal"

Proved
SteinitzExchange.LocalSupermod.baseSet_iff_support_matroidal

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

greedy-algorithmintegral-base-setp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1supermodularsupport-function

Let B⊆ZVB\subseteq\mathbb Z^VB⊆ZV be a finite nonempty set with B=ZV∩B‾B=\mathbb Z^V\cap\overline BB=ZV∩B, i.e. every integer point of the convex hull of BBB belongs to BBB. Let ψ∘(p)=min⁡{⟨p,x⟩∣x∈B}\psi^\circ(p)=\min\{\langle p,x\rangle\mid x\in B\}ψ∘(p)=min{⟨p,x⟩∣x∈B}. Then

B satisfies (B1)  ⟺  ψ∘ is "matroidal" (satisfies (C1) and (C2)).B\ \text{satisfies (B1)}\iff\psi^\circ\ \text{is "matroidal" (satisfies (C1) and (C2))}.B satisfies (B1)⟺ψ∘ is "matroidal" (satisfies (C1) and (C2)).

The theorem restates the exchange property of BBB in terms of the support function of B‾\overline BB: supermodularity of X↦ψ∘(χX)X\mapsto\psi^\circ(\chi_X)X↦ψ∘(χX​) together with correctness of the greedy formula. It is the step that turns localizations into exchange properties in the Local Supermodularity Theorem.

Formalization Note. The hypothesis B=ZV∩B‾B=\mathbb Z^V\cap\overline BB=ZV∩B is stated as: every z∈ZVz\in\mathbb Z^Vz∈ZV whose image lies in hull B belongs to BBB (the reverse inclusion is automatic). It is a hypothesis of the paper and is not implied by finiteness. ψ∘\psi^\circψ∘ is positively homogeneous for every finite nonempty BBB; "matroidal" includes that property.

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

/-- Murota 1996, p. 291, Theorem 5.1. Let `B ⊆ ℤ^V` be finite, nonempty, with
`B = ℤ^V ∩ B̄` (every integer point of the convex hull of `B` lies in `B`). Then `B` satisfies
(B1) iff `ψ°(p) = min{⟨p, x⟩ | x ∈ B}` is "matroidal" (satisfies (C1) and (C2)). -/
theorem baseSet_iff_support_matroidal {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
    (B : Finset (V → ℤ)) (hne : B.Nonempty)
    (hconv : ∀ z : V → ℤ, toReal z ∈ hull B → z ∈ B) :
    IsIntegralBaseSet B ↔ IsMatroidal (supportMin B) := by sorry

end SteinitzExchange.LocalSupermod
Source
Murota, Convexity and Steinitz's Exchange Property, Adv. Math. 124 (1996), p. 291, Theorem 5.1 (with Eq. (5.1), p. 289)
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, and n=∣V∣n = |V|n=∣V∣.
  • B⊆ZVB \subseteq \mathbb{Z}^VB⊆ZV is a finite set with B≠∅B \neq \emptysetB=∅.
  • Closure hypothesis: every z∈ZVz \in \mathbb{Z}^Vz∈ZV whose real image lies in the convex hull B‾⊆RV\overline{B} \subseteq \mathbb{R}^VB⊆RV of BBB belongs to BBB.

Claim. BBB is an integral base set if and only if the function

ψ∘(p)=min⁡x∈B⟨p,x⟩=min⁡x∈B∑v∈Vp(v) x(v)(p∈RV)\psi^\circ(p) = \min_{x \in B} \langle p, x\rangle = \min_{x \in B} \sum_{v \in V} p(v)\, x(v) \qquad (p \in \mathbb{R}^V)ψ∘(p)=x∈Bmin​⟨p,x⟩=x∈Bmin​v∈V∑​p(v)x(v)(p∈RV)

is matroidal.

Being an integral base set 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.

Being matroidal means all three of the following hold:

  • (a) Positive homogeneity: ψ∘(cp)=c ψ∘(p)\psi^\circ(cp) = c\, \psi^\circ(p)ψ∘(cp)=cψ∘(p) for every c>0c > 0c>0.
  • (b) (C1): X↦ψ∘(χX)X \mapsto \psi^\circ(\chi_X)X↦ψ∘(χX​) is supermodular on subsets of VVV. Here χX\chi_XχX​ is the real indicator vector of XXX.
  • (c) (C2): for every p∈RVp \in \mathbb{R}^Vp∈RV and every enumeration v1,…,vnv_1, \dots, v_nv1​,…,vn​ of VVV with p(v1)≥⋯≥p(vn)p(v_1) \ge \cdots \ge p(v_n)p(v1​)≥⋯≥p(vn​),
ψ∘(p)=∑j=1n(p(vj)−p(vj+1)) ψ∘(χ{v1,…,vj}),\psi^\circ(p) = \sum_{j=1}^n \big(p(v_j) - p(v_{j+1})\big)\, \psi^\circ(\chi_{\{v_1, \dots, v_j\}}),ψ∘(p)=j=1∑n​(p(vj​)−p(vj+1​))ψ∘(χ{v1​,…,vj​}​),

where p(vn+1):=0p(v_{n+1}) := 0p(vn+1​):=0. When ppp has ties, this must hold for every admissible enumeration.

Degenerate cases.

  • Empty VVV and empty BBB are excluded, so the minimum is genuine.
  • If B={x0}B = \{x_0\}B={x0​} has one element, the closure hypothesis holds, and BBB is vacuously an integral base set. The theorem then asserts that the linear function p↦⟨p,x0⟩p \mapsto \langle p, x_0\ranglep↦⟨p,x0​⟩ is matroidal.
  • If ∣V∣=1|V| = 1∣V∣=1, (C2) reads ψ∘(p)=p(v) ψ∘(χV)\psi^\circ(p) = p(v)\,\psi^\circ(\chi_V)ψ∘(p)=p(v)ψ∘(χV​) for every real p(v)p(v)p(v), including negative values.
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