Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.7 — four equivalent forms of boundedness of the dual problem

Proved
SteinitzExchange.Duality.dual_bounded_iff

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

base-polytopefenchel-dualityp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-function

Let B1,B2⊆ZVB_1,B_2\subseteq\mathbb Z^VB1​,B2​⊆ZV be finite integral base sets and ω:B1→R\omega:B_1\to\mathbb Rω:B1​→R, ζ:B2→R\zeta:B_2\to\mathbb Rζ:B2​→R arbitrary functions. Let g1(X)=min⁡{x(X)∣x∈B1}g_1(X)=\min\{x(X)\mid x\in B_1\}g1​(X)=min{x(X)∣x∈B1​} be the supermodular function describing B1B_1B1​, f2(X)=max⁡{x(X)∣x∈B2}f_2(X)=\max\{x(X)\mid x\in B_2\}f2​(X)=max{x(X)∣x∈B2​} the submodular function describing B2B_2B2​, and

ψ1∘(p)=min⁡{⟨p,x⟩∣x∈B1},ψ2∙(p)=max⁡{⟨p,x⟩∣x∈B2}.\psi_1^\circ(p)=\min\{\langle p,x\rangle\mid x\in B_1\},\qquad \psi_2^\bullet(p)=\max\{\langle p,x\rangle\mid x\in B_2\}.ψ1∘​(p)=min{⟨p,x⟩∣x∈B1​},ψ2∙​(p)=max{⟨p,x⟩∣x∈B2​}.

Then the following four conditions are equivalent:

  1. (6.7) inf⁡{ζ∙(p)−ω∘(p)∣p∈ZV}≠−∞\inf\{\zeta^\bullet(p)-\omega^\circ(p)\mid p\in\mathbb Z^V\}\neq-\inftyinf{ζ∙(p)−ω∘(p)∣p∈ZV}=−∞;
  2. (6.8) inf⁡{ζ∙(p)−ω∘(p)∣p∈RV}≠−∞\inf\{\zeta^\bullet(p)-\omega^\circ(p)\mid p\in\mathbb R^V\}\neq-\inftyinf{ζ∙(p)−ω∘(p)∣p∈RV}=−∞;
  3. (6.9) ψ2∙(p)≥ψ1∘(p)\psi_2^\bullet(p)\ge\psi_1^\circ(p)ψ2∙​(p)≥ψ1∘​(p) for all p∈RVp\in\mathbb R^Vp∈RV;
  4. (6.10) f2(X)≥g1(X)f_2(X)\ge g_1(X)f2​(X)≥g1​(X) for all X⊆VX\subseteq VX⊆V, and f2(V)=g1(V)f_2(V)=g_1(V)f2​(V)=g1​(V).

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; "≠−∞\neq-\infty=−∞" 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).

Preamble
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
Formal statement
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
Source
Murota, Convexity and Steinitz's Exchange Property, Adv. Math. 124 (1996), p. 297, Lemma 6.7 (Eqs. (6.7)-(6.10))
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting.

  • VVV is a finite, nonempty type with decidable equality.
  • B1,B2⊆ZVB_1, B_2 \subseteq \mathbb{Z}^VB1​,B2​⊆ZV are integral base sets: each is nonempty, and for x,yx, yx,y in it and every uuu with (x−y)(u)>0(x-y)(u)>0(x−y)(u)>0, some vvv with (x−y)(v)<0(x-y)(v)<0(x−y)(v)<0 has x−χu+χvx-\chi_u+\chi_vx−χu​+χv​ back in the set.
  • ω,ζ:ZV→R\omega, \zeta : \mathbb{Z}^V\to\mathbb{R}ω,ζ:ZV→R are arbitrary.

Notation. With ⟨p,x⟩=∑vp(v)x(v)\langle p,x\rangle = \sum_v p(v)x(v)⟨p,x⟩=∑v​p(v)x(v):

  • ω∘(p)=min⁡x∈B1(⟨p,x⟩−ω(x))\omega^\circ(p) = \min_{x\in B_1}(\langle p,x\rangle - \omega(x))ω∘(p)=minx∈B1​​(⟨p,x⟩−ω(x))
  • ζ∙(p)=max⁡x∈B2(⟨p,x⟩−ζ(x))\zeta^\bullet(p) = \max_{x\in B_2}(\langle p,x\rangle - \zeta(x))ζ∙(p)=maxx∈B2​​(⟨p,x⟩−ζ(x))
  • D=inf⁡p∈RV(ζ∙(p)−ω∘(p))\mathrm{D} = \inf_{p\in\mathbb{R}^V}(\zeta^\bullet(p)-\omega^\circ(p))D=infp∈RV​(ζ∙(p)−ω∘(p)) and DZ=inf⁡p∈ZV(ζ∙(p)−ω∘(p))\mathrm{D}_\mathbb{Z} = \inf_{p\in\mathbb{Z}^V}(\zeta^\bullet(p)-\omega^\circ(p))DZ​=infp∈ZV​(ζ∙(p)−ω∘(p)), both taken in the extended reals.
  • ψ1∘(p)=min⁡x∈B1⟨p,x⟩\psi_1^\circ(p) = \min_{x\in B_1}\langle p,x\rangleψ1∘​(p)=minx∈B1​​⟨p,x⟩ and ψ2∙(p)=max⁡x∈B2⟨p,x⟩\psi_2^\bullet(p) = \max_{x\in B_2}\langle p,x\rangleψ2∙​(p)=maxx∈B2​​⟨p,x⟩.
  • g1(X)=min⁡x∈B1x(X)g_1(X) = \min_{x\in B_1}x(X)g1​(X)=minx∈B1​​x(X) and f2(X)=max⁡x∈B2x(X)f_2(X) = \max_{x\in B_2}x(X)f2​(X)=maxx∈B2​​x(X).

Claim.

  1. DZ≠−∞  ⟺  D≠−∞\mathrm{D}_\mathbb{Z} \ne -\infty \iff \mathrm{D} \ne -\inftyDZ​=−∞⟺D=−∞.
  2. D≠−∞  ⟺  ψ1∘(p)≤ψ2∙(p)\mathrm{D}\neq -\infty \iff \psi_1^\circ(p) \le \psi_2^\bullet(p)D=−∞⟺ψ1∘​(p)≤ψ2∙​(p) for all p∈RVp\in\mathbb{R}^Vp∈RV.
  3. (ψ1∘(p)≤ψ2∙(p) ∀p)  ⟺  (g1(X)≤f2(X) ∀X⊆V)\bigl(\psi_1^\circ(p)\le\psi_2^\bullet(p)\ \forall p\bigr) \iff \bigl(g_1(X) \le f_2(X)\ \forall X\subseteq V\bigr)(ψ1∘​(p)≤ψ2∙​(p) ∀p)⟺(g1​(X)≤f2​(X) ∀X⊆V) and f2(V)=g1(V)f_2(V) = g_1(V)f2​(V)=g1​(V).

D\mathrm{D}D and DZ\mathrm{D}_\mathbb{Z}DZ​ are never +∞+\infty+∞, so "≠−∞\neq -\infty=−∞" means the value is finite. ω\omegaω and ζ\zetaζ appear only in D\mathrm{D}D and DZ\mathrm{D}_\mathbb{Z}DZ​; 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 000 enters. For X=∅X=\emptysetX=∅, g1(∅)=f2(∅)=0g_1(\emptyset) = f_2(\emptyset) = 0g1​(∅)=f2​(∅)=0. Empty VVV is excluded by hypothesis.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me