Theorem 5.1 — (B1) holds iff the support function ψ° is "matroidal"
ProvedSteinitzExchange.LocalSupermod.baseSet_iff_support_matroidalLet be a finite nonempty set with , i.e. every integer point of the convex hull of belongs to . Let . Then
The theorem restates the exchange property of in terms of the support function of : supermodularity of 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 is stated as: every whose image lies in hull B belongs to (the reverse inclusion is automatic). It is a hypothesis of the paper and is not implied by finiteness. is positively homogeneous for every finite nonempty ; "matroidal" includes that property.
import Mathlib import Definitions.Def_SteinitzExchange_LocalSupermod_IntegralBaseSet import Definitions.Def_SteinitzExchange_LocalSupermod_Matroidal
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting.
- is a finite, nonempty type with decidable equality, and .
- is a finite set with .
- Closure hypothesis: every whose real image lies in the convex hull of belongs to .
Claim. is an integral base set if and only if the function
is matroidal.
Being an integral base set means: , and for all and every with , there is with and .
Being matroidal means all three of the following hold:
- (a) Positive homogeneity: for every .
- (b) (C1): is supermodular on subsets of . Here is the real indicator vector of .
- (c) (C2): for every and every enumeration of with ,
where . When has ties, this must hold for every admissible enumeration.
Degenerate cases.
- Empty and empty are excluded, so the minimum is genuine.
- If has one element, the closure hypothesis holds, and is vacuously an integral base set. The theorem then asserts that the linear function is matroidal.
- If , (C2) reads for every real , including negative values.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.