Theorem 2.1 — (B1) characterizes integer points of integral submodular/supermodular base polytopes
ProvedSteinitzExchange.Duality.baseSet_iff_submodular_systemLet be finite and nonempty. The following are equivalent:
- satisfies (B1);
- there is an integer-valued submodular with such that
- there is an integer-valued supermodular with such that
Moreover, the functions and are given by and .
This folklore result identifies finite integral base sets with the integer points of integral base polytopes; in the duality theorem it provides the supermodular function describing and the submodular function describing .
Formalization Note. The page writes ; it is read as all subsets (the paper uses for here, and is covered by the equality constraint anyway). The "Moreover" clause is stated as: every (resp. ) as in 2 (resp. 3) equals the max (resp. min) formula.
import Mathlib import Definitions.Def_SteinitzExchange_Duality_IntegralBaseSet import Definitions.Def_SteinitzExchange_Duality_SetFunction
namespace SteinitzExchange.Duality
/-- Murota 1996, p. 277, Theorem 2.1. For a finite nonempty `B ⊆ ℤ^V`:
(a) (B1) ⇔ (b) `B = {x ∈ ℤ^V | x(X) ≤ f(X) ∀ X ⊆ V, x(V) = f(V)}` for an integer-valued
submodular `f` with `f(∅) = 0`; (a) ⇔ (c) the same with a supermodular `g` and `≥`.
Moreover any such `f` is `X ↦ max{x(X) | x ∈ B}` and any such `g` is `X ↦ min{x(X) | x ∈ B}`.
The page's "∀X ⊂ V" is read as all `X ⊆ V`. -/
theorem baseSet_iff_submodular_system {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
(B : Finset (V → ℤ)) (hne : B.Nonempty) :
(IsIntegralBaseSet B ↔
∃ f : Finset V → ℤ, IsSubmodular f ∧ f ∅ = 0 ∧
∀ x : V → ℤ, x ∈ B ↔
(∀ X : Finset V, sumOn x X ≤ f X) ∧ sumOn x Finset.univ = f Finset.univ) ∧
(IsIntegralBaseSet B ↔
∃ g : Finset V → ℤ, IsSupermodular g ∧ g ∅ = 0 ∧
∀ x : V → ℤ, x ∈ B ↔
(∀ X : Finset V, g X ≤ sumOn x X) ∧ sumOn x Finset.univ = g Finset.univ) ∧
(∀ f : Finset V → ℤ, IsSubmodular f → f ∅ = 0 →
(∀ x : V → ℤ, x ∈ B ↔
(∀ X : Finset V, sumOn x X ≤ f X) ∧ sumOn x Finset.univ = f Finset.univ) →
∀ X : Finset V, f X = B.sup' hne (fun x => sumOn x X)) ∧
(∀ g : Finset V → ℤ, IsSupermodular g → g ∅ = 0 →
(∀ x : V → ℤ, x ∈ B ↔
(∀ X : Finset V, g X ≤ sumOn x X) ∧ sumOn x Finset.univ = g Finset.univ) →
∀ X : Finset V, g X = B.inf' hne (fun x => sumOn x X)) := by sorry
end SteinitzExchange.Duality
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 nonempty finite set.
Write for .
- Submodular: for all .
- Supermodular: the reverse inequality, .
- Integral base set: is nonempty, and for and every with there is with and .
Claim. The theorem asserts all four of the following:
- is an integral base set iff there is an integer-valued submodular with such that, for every :
- is an integral base set iff there is an integer-valued supermodular with such that, for every :
- Every integer-valued submodular with that describes in the sense of part 1 satisfies
- Every integer-valued supermodular with that describes in the sense of part 2 satisfies
Parts 3 and 4 do not assume that is an integral base set.
Degenerate cases. The set on the right of parts 1 and 2 ranges over all integer vectors. Equality with therefore also asserts that this integer set is finite, since is a finite set. If no such (or ) exists, parts 3 and 4 are vacuous. If has one element , the only subsets are and , and the conditions pin down to the single value (respectively ). Empty and empty are excluded.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.