Theorem 5.3 (Local Supermodularity Theorem, corrected) — (EXC) iff ω = ω̂ on B and every localization of ω° is "matroidal"
ProvedSteinitzExchange.LocalSupermod.exc_iff_localization_matroidalLet be a finite integral base set and . Let be the concave conjugate, the concave closure, and the localization of at . Then satisfies (EXC) if and only if
- for every , and
- is "matroidal" (satisfies (C1) and (C2)) at every point .
In short,
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 and . The paper's proof applies Theorem 5.1 to , 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 .
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
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a type that is finite, has decidable equality and is nonempty. Write for the functions (integer vectors indexed by ) and for the functions . The statement takes three explicit inputs:
- , a finite set of integer vectors, ;
- a hypothesis that satisfies the bundle predicate ;
- a function . It is defined on all of , not only on , and takes finite real values everywhere.
Under these assumptions the theorem asserts this equivalence:
The symbols are:
- is the integer vector viewed as a real vector (the bundle's
toReal). - is a real-valued function on built from and .
- is an object built from and .
- is that object localized at the real vector .
- , and 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 satisfies on , two things hold. First, agrees with at every point of . Second, for every real vector (not only integer ones), the localization of at satisfies .
- "If": the conjunction of both conditions implies .
The first condition only asks for agreement at points of . It says nothing about points of outside . Whether the values for affect any of the three predicates depends on the bundle definitions and cannot be read from this statement.
Degenerate cases. Because must be nonempty, the empty index type is excluded. The smallest allowed case is a one-element , where and ; the equivalence is still asserted there, in the same form. Nothing in the statement itself excludes or a one-element . Whether those are allowed depends entirely on . If is allowed:
- the condition "" is vacuously true;
- the theorem then reduces to , and what each side means there is again fixed by the unseen definitions.
If cannot be satisfied at all, the theorem is vacuously true. Its satisfiability cannot be checked from the supplied code.
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 is a statement about that value. The statement itself shows no division, natural-number subtraction or integral.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.