Lemma 6.7 — four equivalent forms of boundedness of the dual problem
ProvedSteinitzExchange.Duality.dual_bounded_iffLet be finite integral base sets and , arbitrary functions. Let be the supermodular function describing , the submodular function describing , and
Then the following four conditions are equivalent:
- (6.7) ;
- (6.8) ;
- (6.9) for all ;
- (6.10) for all , and .
Together with Frank's discrete separation theorem, this gives part (P1) of the duality theorem.
Formalization Note. The two infima are dualValueInt and dualValue in EReal; "" is ≠ ⊥, i.e. boundedness below. The four-way equivalence is stated as the chain (6.7)⇔(6.8), (6.8)⇔(6.9), (6.9)⇔(6.10).
import Mathlib import Definitions.Def_SteinitzExchange_Duality_IntegralBaseSet import Definitions.Def_SteinitzExchange_Duality_Conjugate import Definitions.Def_SteinitzExchange_Duality_SetFunction import Definitions.Def_SteinitzExchange_Duality_Problems
namespace SteinitzExchange.Duality
/-- Murota 1996, p. 297, Lemma 6.7. Let `B₁, B₂ ⊆ ℤ^V` be finite integral base sets,
`ω : B₁ → ℝ`, `ζ : B₂ → ℝ` arbitrary, `g₁(X) = min{x(X) | x ∈ B₁}`,
`f₂(X) = max{x(X) | x ∈ B₂}`, `ψ₁°(p) = min{⟨p, x⟩ | x ∈ B₁}`, `ψ₂•(p) = max{⟨p, x⟩ | x ∈ B₂}`.
The following are equivalent:
(6.7) `inf{ζ•(p) − ω°(p) | p ∈ ℤ^V} ≠ −∞`;
(6.8) `inf{ζ•(p) − ω°(p) | p ∈ ℝ^V} ≠ −∞`;
(6.9) `ψ₂•(p) ≥ ψ₁°(p)` for all `p ∈ ℝ^V`;
(6.10) `f₂(X) ≥ g₁(X)` for all `X ⊆ V`, and `f₂(V) = g₁(V)`. -/
theorem dual_bounded_iff {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
(B₁ B₂ : Finset (V → ℤ)) (hB₁ : IsIntegralBaseSet B₁) (hB₂ : IsIntegralBaseSet B₂)
(ω ζ : (V → ℤ) → ℝ) :
(dualValueInt B₁ B₂ ω ζ ≠ ⊥ ↔ dualValue B₁ B₂ ω ζ ≠ ⊥) ∧
(dualValue B₁ B₂ ω ζ ≠ ⊥ ↔ ∀ p : V → ℝ, supportMin B₁ p ≤ supportMax B₂ p) ∧
((∀ p : V → ℝ, supportMin B₁ p ≤ supportMax B₂ p) ↔
(∀ X : Finset V, setMin B₁ X ≤ setMax B₂ X) ∧
setMax B₂ Finset.univ = setMin B₁ Finset.univ) := 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.
- are integral base sets: each is nonempty, and for in it and every with , some with has back in the set.
- are arbitrary.
Notation. With :
- and , both taken in the extended reals.
- and .
- and .
Claim.
- .
- for all .
- and .
and are never , so "" means the value is finite. and appear only in and ; the conditions in parts 2 and 3 do not involve them.
Degenerate cases. Both sets are nonempty, so every min and max above is genuine and no junk value enters. For , . Empty is excluded by hypothesis.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.