Theorem 6.4 — Fenchel-type min-max duality with primal and dual integrality for M-concave and M-convex
ProvedSteinitzExchange.Duality.fenchel_min_maxLet be finite integral base sets and let and be such that and satisfy (EXC). Take with respect to and with respect to .
- Primal integrality.
More precisely:
- (P1) if , then ;
- (P2) if , all these values are finite and equal, and the infimum is attained by some .
- Dual integrality. If and are integer-valued, the infimum can be taken over integral vectors:
and the infimum is attained by some if it is finite.
A maximum over an empty family is . 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 ), with ⊥ the paper's and the supremum of the empty family equal to ⊥. (P2) is stated as the existence of , and at which the three values are attained, as equal real numbers ("max" includes attainment of both maxima). M-convexity of is (EXC) for . Integer-valued means for and for ; "finite" for the integral infimum is ≠ ⊥.
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
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a finite, nonempty set with decidable equality, and write and for the functions and . The data are:
- two finite sets ;
- two real-valued functions . Both are defined on all of , not only on or .
The hypotheses are:
- and each satisfy the predicate IsIntegralBaseSet;
- the pair satisfies the predicate SatisfiesEXC;
- the pair satisfies SatisfiesEXC, where is the pointwise negation .
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)", , , , ) is the author's comment, not something the code checks. The notation is:
- IsIntegralBaseSet and SatisfiesEXC: the two predicates in the hypotheses.
- = hull : a set of real vectors attached to .
- = concaveClosure and = convexClosure : real numbers depending on a point .
- = convexConj and = concaveConj : real numbers depending on .
- toReal: sends to a vector in , written below.
- Four quantities (primalValue), (relaxedValue), (dualValue) and (dualValueInt), each depending on . Each is compared with and with coerced reals, so each lies in the extended reals .
Under these hypotheses the statement asserts four things together.
(1) The three values are equal in :
(P1) If , then is nonempty.
(P2) If is nonempty, then there exist a lattice point , a point and a real vector such that:
where each right-hand side is a real number embedded in . In particular, all three values are finite. Also, as real numbers,
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 , and are defined, which is not shown.
(2) Suppose for every and for every . Nothing is assumed about values outside these sets. Then:
- in ;
- if , there is an integer vector with
a real number. So the premise also forces .
Degenerate cases. must be nonempty, so the smallest case is , where is a copy of . Whether or 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 , (P2) says nothing, and (P1) read in reverse gives . By (1) this makes as well, whatever value the definition of gives an empty intersection. In the conclusions themselves, every subtraction is done in and only then embedded in , so no appears there. How the unseen definitions handle empty or unbounded suprema and infima, conjugates over an empty , an empty hull, and the values of and outside and is fixed by the imported code and cannot be read off this declaration. (2) only requires to be integer-valued on and on . Its attainment clause is conditioned on , not on being finite.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.