Theorem 4.4 — (EXC) holds iff every argmax(ω[p]) is an integral base set
ProvedSteinitzExchange.LocalSupermod.exc_iff_argmax_isIntegralBaseSetLet be a finite integral base set and . Then
where . (Each 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 " is an integral base polytope". This is formalized as " 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. , : 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.
import Mathlib import Definitions.Def_SteinitzExchange_LocalSupermod_IntegralBaseSet import Definitions.Def_SteinitzExchange_LocalSupermod_Exchange
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting.
- is a finite, nonempty type with decidable equality.
- is a finite set, assumed to be an integral base set. That means , and for all and every with , there is with and .
- is an arbitrary function. Its values outside play no role.
Claim. The following two conditions are equivalent.
- (EXC): for all and every with , there is with such that , , and
- For every , the set
is an integral base set. Here .
The set in condition 2 is always nonempty, because is finite and nonempty. So condition 2 amounts to the one-sided exchange property within each such argmax set.
Degenerate cases. Empty and empty are excluded. If has one element, (EXC) holds vacuously, every equals , and both sides are true. The case is included, giving itself.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.