Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.4 — Fenchel-type min-max duality with primal and dual integrality for M-concave ω\omegaω and M-convex ζ\zetaζ

Proved
SteinitzExchange.Duality.fenchel_min_max

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

discrete-convex-analysisfenchel-dualityintegralitym-concavemin-maxp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let B1,B2⊆ZVB_1,B_2\subseteq\mathbb Z^VB1​,B2​⊆ZV be finite integral base sets and let ω:B1→R\omega:B_1\to\mathbb Rω:B1​→R and ζ:B2→R\zeta:B_2\to\mathbb Rζ:B2​→R be such that ω\omegaω and −ζ-\zeta−ζ satisfy (EXC). Take ω∘,ω^\omega^\circ,\hat\omegaω∘,ω^ with respect to B1B_1B1​ and ζ∙,ζˇ\zeta^\bullet,\check\zetaζ∙,ζˇ​ with respect to B2B_2B2​.

  1. Primal integrality.
max⁡{ω(x)−ζ(x)∣x∈B1∩B2}=max⁡{ω^(b)−ζˇ(b)∣b∈B1‾∩B2‾}=inf⁡{ζ∙(p)−ω∘(p)∣p∈RV}.\max\{\omega(x)-\zeta(x)\mid x\in B_1\cap B_2\}=\max\{\hat\omega(b)-\check\zeta(b)\mid b\in\overline{B_1}\cap\overline{B_2}\}=\inf\{\zeta^\bullet(p)-\omega^\circ(p)\mid p\in\mathbb R^V\}.max{ω(x)−ζ(x)∣x∈B1​∩B2​}=max{ω^(b)−ζˇ​(b)∣b∈B1​​∩B2​​}=inf{ζ∙(p)−ω∘(p)∣p∈RV}.

More precisely:

  • (P1) if inf⁡{ζ∙(p)−ω∘(p)∣p∈RV}≠−∞\inf\{\zeta^\bullet(p)-\omega^\circ(p)\mid p\in\mathbb R^V\}\neq-\inftyinf{ζ∙(p)−ω∘(p)∣p∈RV}=−∞, then B1∩B2≠∅B_1\cap B_2\neq\emptysetB1​∩B2​=∅;
  • (P2) if B1∩B2≠∅B_1\cap B_2\neq\emptysetB1​∩B2​=∅, all these values are finite and equal, and the infimum is attained by some p∈RVp\in\mathbb R^Vp∈RV.
  1. Dual integrality. If ω\omegaω and ζ\zetaζ are integer-valued, the infimum can be taken over integral vectors:
max⁡{ω(x)−ζ(x)∣x∈B1∩B2}=inf⁡{ζ∙(p)−ω∘(p)∣p∈ZV},\max\{\omega(x)-\zeta(x)\mid x\in B_1\cap B_2\}=\inf\{\zeta^\bullet(p)-\omega^\circ(p)\mid p\in\mathbb Z^V\},max{ω(x)−ζ(x)∣x∈B1​∩B2​}=inf{ζ∙(p)−ω∘(p)∣p∈ZV},

and the infimum is attained by some p∈ZVp\in\mathbb Z^Vp∈ZV if it is finite.

A maximum over an empty family is −∞-\infty−∞. According to the paper, the formula unifies Edmonds' polymatroid intersection theorem, Fujishige's Fenchel-type duality theorem and Frank's discrete separation theorem with Iri–Tomizawa's potential characterization for the independent assignment problem and its extensions by Fujishige and Frank (weight splitting).

Formalization Note. The three values are EReal (primalValue, relaxedValue, dualValue, and dualValueInt over ZV\mathbb Z^VZV), with ⊥ the paper's −∞-\infty−∞ and the supremum of the empty family equal to ⊥. (P2) is stated as the existence of x∈B1∩B2x\in B_1\cap B_2x∈B1​∩B2​, b∈B1‾∩B2‾b\in\overline{B_1}\cap\overline{B_2}b∈B1​​∩B2​​ and p∈RVp\in\mathbb R^Vp∈RV at which the three values are attained, as equal real numbers ("max" includes attainment of both maxima). M-convexity of ζ\zetaζ is (EXC) for −ζ-\zeta−ζ. Integer-valued means ω(x)∈Z\omega(x)\in\mathbb Zω(x)∈Z for x∈B1x\in B_1x∈B1​ and ζ(x)∈Z\zeta(x)\in\mathbb Zζ(x)∈Z for x∈B2x\in B_2x∈B2​; "finite" for the integral infimum is ≠ ⊥.

Preamble
import Mathlib
import Definitions.Def_SteinitzExchange_Duality_IntegralBaseSet
import Definitions.Def_SteinitzExchange_Duality_Exchange
import Definitions.Def_SteinitzExchange_Duality_Conjugate
import Definitions.Def_SteinitzExchange_Duality_Problems
Formal statement
namespace SteinitzExchange.Duality

/-- Murota 1996, p. 295, Theorem 6.4 (Fenchel-type min-max duality). Let `B₁, B₂ ⊆ ℤ^V` be finite
integral base sets and `ω : B₁ → ℝ`, `ζ : B₂ → ℝ` such that `ω` and `−ζ` satisfy (EXC).
(1) [Primal integrality]
`max{ω(x) − ζ(x) | x ∈ B₁ ∩ B₂} = max{ω̂(b) − ζ̌(b) | b ∈ B̄₁ ∩ B̄₂} = inf{ζ•(p) − ω°(p) | p ∈ ℝ^V}`
(in `EReal`, `max ∅ = −∞`); more precisely
(P1) if the infimum is `≠ −∞` then `B₁ ∩ B₂ ≠ ∅`;
(P2) if `B₁ ∩ B₂ ≠ ∅`, all three values are finite and equal, both maxima are attained, and the
infimum is attained by some `p ∈ ℝ^V`.
(2) [Dual integrality] If `ω` and `ζ` are integer-valued, the infimum may be taken over `ℤ^V`:
`max{ω(x) − ζ(x) | x ∈ B₁ ∩ B₂} = inf{ζ•(p) − ω°(p) | p ∈ ℤ^V}`, and it is attained by some
`p ∈ ℤ^V` if it is finite. -/
theorem fenchel_min_max {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
    (B₁ B₂ : Finset (V → ℤ)) (hB₁ : IsIntegralBaseSet B₁) (hB₂ : IsIntegralBaseSet B₂)
    (ω ζ : (V → ℤ) → ℝ) (hω : SatisfiesEXC B₁ ω) (hζ : SatisfiesEXC B₂ (fun x => -ζ x)) :
    -- (1)
    (primalValue B₁ B₂ ω ζ = relaxedValue B₁ B₂ ω ζ ∧
      relaxedValue B₁ B₂ ω ζ = dualValue B₁ B₂ ω ζ) ∧
    -- (P1)
    (dualValue B₁ B₂ ω ζ ≠ ⊥ → (B₁ ∩ B₂).Nonempty) ∧
    -- (P2)
    ((B₁ ∩ B₂).Nonempty →
      ∃ x ∈ B₁ ∩ B₂, ∃ b ∈ hull B₁ ∩ hull B₂, ∃ p : V → ℝ,
        primalValue B₁ B₂ ω ζ = ((ω x - ζ x : ℝ) : EReal) ∧
        relaxedValue B₁ B₂ ω ζ =
          ((concaveClosure B₁ ω b - convexClosure B₂ ζ b : ℝ) : EReal) ∧
        dualValue B₁ B₂ ω ζ = ((convexConj B₂ ζ p - concaveConj B₁ ω p : ℝ) : EReal) ∧
        ω x - ζ x = concaveClosure B₁ ω b - convexClosure B₂ ζ b ∧
        ω x - ζ x = convexConj B₂ ζ p - concaveConj B₁ ω p) ∧
    -- (2)
    ((∀ x ∈ B₁, ∃ k : ℤ, ω x = k) → (∀ x ∈ B₂, ∃ k : ℤ, ζ x = k) →
      primalValue B₁ B₂ ω ζ = dualValueInt B₁ B₂ ω ζ ∧
      (dualValueInt B₁ B₂ ω ζ ≠ ⊥ →
        ∃ p : V → ℤ, dualValueInt B₁ B₂ ω ζ =
          ((convexConj B₂ ζ (toReal p) - concaveConj B₁ ω (toReal p) : ℝ) : EReal))) := by sorry

end SteinitzExchange.Duality
Source
Murota, Convexity and Steinitz's Exchange Property, Adv. Math. 124 (1996), p. 295, Theorem 6.4
Read-back

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

Let VVV be a finite, nonempty set with decidable equality, and write ZV\mathbb{Z}^VZV and RV\mathbb{R}^VRV for the functions V→ZV \to \mathbb{Z}V→Z and V→RV \to \mathbb{R}V→R. The data are:

  • two finite sets B1,B2⊆ZVB_1, B_2 \subseteq \mathbb{Z}^VB1​,B2​⊆ZV;
  • two real-valued functions ω,ζ:ZV→R\omega, \zeta : \mathbb{Z}^V \to \mathbb{R}ω,ζ:ZV→R. Both are defined on all of ZV\mathbb{Z}^VZV, not only on B1B_1B1​ or B2B_2B2​.

The hypotheses are:

  • B1B_1B1​ and B2B_2B2​ each satisfy the predicate IsIntegralBaseSet;
  • the pair (B1,ω)(B_1, \omega)(B1​,ω) satisfies the predicate SatisfiesEXC;
  • the pair (B2,−ζ)(B_2, -\zeta)(B2​,−ζ) satisfies SatisfiesEXC, where −ζ-\zeta−ζ is the pointwise negation x↦−ζ(x)x \mapsto -\zeta(x)x↦−ζ(x).

Several notions come from imported definition files whose code is not shown here, so this read-back cannot spell them out. They are only named below. The docstring's wording (maxima, infima, "(EXC)", ω^\hat\omegaω^, ζˇ\check\zetaζˇ​, ζ∙\zeta^\bulletζ∙, ω∘\omega^\circω∘) is the author's comment, not something the code checks. The notation is:

  • IsIntegralBaseSet and SatisfiesEXC: the two predicates in the hypotheses.
  • B‾\overline{B}B = hull BBB: a set of real vectors attached to BBB.
  • ω^B1(b)\hat\omega_{B_1}(b)ω^B1​​(b) = concaveClosure B1 ω bB_1\,\omega\,bB1​ωb and ζˇB2(b)\check\zeta_{B_2}(b)ζˇ​B2​​(b) = convexClosure B2 ζ bB_2\,\zeta\,bB2​ζb: real numbers depending on a point bbb.
  • ζB2∙(p)\zeta^\bullet_{B_2}(p)ζB2​∙​(p) = convexConj B2 ζ pB_2\,\zeta\,pB2​ζp and ωB1∘(p)\omega^\circ_{B_1}(p)ωB1​∘​(p) = concaveConj B1 ω pB_1\,\omega\,pB1​ωp: real numbers depending on p∈RVp \in \mathbb{R}^Vp∈RV.
  • toReal: sends p∈ZVp \in \mathbb{Z}^Vp∈ZV to a vector in RV\mathbb{R}^VRV, written pˉ\bar ppˉ​ below.
  • Four quantities P\mathrm{P}P (primalValue), R\mathrm{R}R (relaxedValue), D\mathrm{D}D (dualValue) and DZ\mathrm{D}_{\mathbb{Z}}DZ​ (dualValueInt), each depending on (B1,B2,ω,ζ)(B_1, B_2, \omega, \zeta)(B1​,B2​,ω,ζ). Each is compared with −∞-\infty−∞ and with coerced reals, so each lies in the extended reals R‾=[−∞,+∞]\overline{\mathbb{R}} = [-\infty, +\infty]R=[−∞,+∞].

Under these hypotheses the statement asserts four things together.

(1) The three values are equal in R‾\overline{\mathbb{R}}R:

P=RandR=D.\mathrm{P} = \mathrm{R} \quad\text{and}\quad \mathrm{R} = \mathrm{D}.P=RandR=D.

(P1) If D≠−∞\mathrm{D} \neq -\inftyD=−∞, then B1∩B2B_1 \cap B_2B1​∩B2​ is nonempty.

(P2) If B1∩B2B_1 \cap B_2B1​∩B2​ is nonempty, then there exist a lattice point x∈B1∩B2x \in B_1 \cap B_2x∈B1​∩B2​, a point b∈B1‾∩B2‾b \in \overline{B_1} \cap \overline{B_2}b∈B1​​∩B2​​ and a real vector p∈RVp \in \mathbb{R}^Vp∈RV such that:

P=ω(x)−ζ(x),R=ω^B1(b)−ζˇB2(b),D=ζB2∙(p)−ωB1∘(p),\mathrm{P} = \omega(x) - \zeta(x),\qquad \mathrm{R} = \hat\omega_{B_1}(b) - \check\zeta_{B_2}(b),\qquad \mathrm{D} = \zeta^\bullet_{B_2}(p) - \omega^\circ_{B_1}(p),P=ω(x)−ζ(x),R=ω^B1​​(b)−ζˇ​B2​​(b),D=ζB2​∙​(p)−ωB1​∘​(p),

where each right-hand side is a real number embedded in R‾\overline{\mathbb{R}}R. In particular, all three values are finite. Also, as real numbers,

ω(x)−ζ(x)=ω^B1(b)−ζˇB2(b)andω(x)−ζ(x)=ζB2∙(p)−ωB1∘(p).\omega(x) - \zeta(x) = \hat\omega_{B_1}(b) - \check\zeta_{B_2}(b) \quad\text{and}\quad \omega(x) - \zeta(x) = \zeta^\bullet_{B_2}(p) - \omega^\circ_{B_1}(p).ω(x)−ζ(x)=ω^B1​​(b)−ζˇ​B2​​(b)andω(x)−ζ(x)=ζB2​∙​(p)−ωB1​∘​(p).

The code does not use the word "attained". What it gives is that each value equals the objective at one specific witness. Whether that means a maximum or infimum is attained depends on how P\mathrm{P}P, R\mathrm{R}R and D\mathrm{D}D are defined, which is not shown.

(2) Suppose ω(x)∈Z\omega(x) \in \mathbb{Z}ω(x)∈Z for every x∈B1x \in B_1x∈B1​ and ζ(x)∈Z\zeta(x) \in \mathbb{Z}ζ(x)∈Z for every x∈B2x \in B_2x∈B2​. Nothing is assumed about values outside these sets. Then:

  • P=DZ\mathrm{P} = \mathrm{D}_{\mathbb{Z}}P=DZ​ in R‾\overline{\mathbb{R}}R;
  • if DZ≠−∞\mathrm{D}_{\mathbb{Z}} \neq -\inftyDZ​=−∞, there is an integer vector p∈ZVp \in \mathbb{Z}^Vp∈ZV with
DZ=ζB2∙(pˉ)−ωB1∘(pˉ),\mathrm{D}_{\mathbb{Z}} = \zeta^\bullet_{B_2}(\bar p) - \omega^\circ_{B_1}(\bar p),DZ​=ζB2​∙​(pˉ​)−ωB1​∘​(pˉ​),

a real number. So the premise DZ≠−∞\mathrm{D}_{\mathbb{Z}} \neq -\inftyDZ​=−∞ also forces DZ≠+∞\mathrm{D}_{\mathbb{Z}} \neq +\inftyDZ​=+∞.

Degenerate cases. VVV must be nonempty, so the smallest case is ∣V∣=1|V| = 1∣V∣=1, where ZV\mathbb{Z}^VZV is a copy of Z\mathbb{Z}Z. Whether B1B_1B1​ or B2B_2B2​ can be empty, and whether the IsIntegralBaseSet and SatisfiesEXC hypotheses can be satisfied at all, depends on definitions not shown here. If they can never hold together, the theorem is vacuous. When B1∩B2=∅B_1 \cap B_2 = \emptysetB1​∩B2​=∅, (P2) says nothing, and (P1) read in reverse gives D=−∞\mathrm{D} = -\inftyD=−∞. By (1) this makes P=R=−∞\mathrm{P} = \mathrm{R} = -\inftyP=R=−∞ as well, whatever value the definition of P\mathrm{P}P gives an empty intersection. In the conclusions themselves, every subtraction is done in R\mathbb{R}R and only then embedded in R‾\overline{\mathbb{R}}R, so no ∞−∞\infty - \infty∞−∞ appears there. How the unseen definitions handle empty or unbounded suprema and infima, conjugates over an empty BBB, an empty hull, and the values of ω\omegaω and ζ\zetaζ outside B1B_1B1​ and B2B_2B2​ is fixed by the imported code and cannot be read off this declaration. (2) only requires ω\omegaω to be integer-valued on B1B_1B1​ and ζ\zetaζ on B2B_2B2​. Its attainment clause is conditioned on DZ≠−∞\mathrm{D}_{\mathbb{Z}} \neq -\inftyDZ​=−∞, not on DZ\mathrm{D}_{\mathbb{Z}}DZ​ being finite.

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