Theorem 6.6 — the M-concave intersection theorem (optimality via a potential )
ProvedSteinitzExchange.Duality.mconcave_intersection_optimalityLet be finite integral base sets, let and satisfy (EXC), and let . Then
if and only if there exists such that
where . Moreover, if and are integer-valued, there exists such a in .
This is the optimality criterion for the M-concave intersection problem, which the paper cites from Murota's earlier work without proof; it gives part (P2) and the dual integrality of the duality theorem.
Formalization Note. The integral clause is stated as: if are integer-valued on and is optimal, some integral satisfies both inequalities (the "such a " of the page).
import Mathlib import Definitions.Def_SteinitzExchange_Duality_IntegralBaseSet import Definitions.Def_SteinitzExchange_Duality_Exchange
namespace SteinitzExchange.Duality
/-- Murota 1996, p. 296, Theorem 6.6 (the M-concave intersection theorem, [32, Theorem 4.1]).
Let `B₁, B₂ ⊆ ℤ^V` be finite integral base sets, `ω₁ : B₁ → ℝ` and `ω₂ : B₂ → ℝ` satisfy (EXC),
and `x* ∈ B₁ ∩ B₂`. Then `ω₁(x*) + ω₂(x*) ≥ ω₁(x) + ω₂(x)` for all `x ∈ B₁ ∩ B₂` iff there is
`p* ∈ ℝ^V` with `ω₁[−p*](x*) ≥ ω₁[−p*](x)` for all `x ∈ B₁` and `ω₂[p*](x*) ≥ ω₂[p*](x)` for all
`x ∈ B₂`. Moreover, if `ω₁` and `ω₂` are integer-valued (and `x*` is optimal), such a `p*`
exists in `ℤ^V`. -/
theorem mconcave_intersection_optimality {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₂ ω₂)
(xs : V → ℤ) (hx₁ : xs ∈ B₁) (hx₂ : xs ∈ B₂) :
((∀ x ∈ B₁, x ∈ B₂ → ω₁ x + ω₂ x ≤ ω₁ xs + ω₂ xs) ↔
∃ p : V → ℝ, (∀ x ∈ B₁, perturb ω₁ (-p) x ≤ perturb ω₁ (-p) xs) ∧
(∀ x ∈ B₂, perturb ω₂ p x ≤ perturb ω₂ p xs)) ∧
((∀ x ∈ B₁, ∃ k : ℤ, ω₁ x = k) → (∀ x ∈ B₂, ∃ k : ℤ, ω₂ x = k) →
(∀ x ∈ B₁, x ∈ B₂ → ω₁ x + ω₂ x ≤ ω₁ xs + ω₂ xs) →
∃ p : V → ℤ, (∀ x ∈ B₁, perturb ω₁ (-toReal p) x ≤ perturb ω₁ (-toReal p) xs) ∧
(∀ x ∈ B₂, perturb ω₂ (toReal p) x ≤ perturb ω₂ (toReal p) xs)) := 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.
- satisfies (EXC) on and satisfies (EXC) on . For on this means: for all and every with , there is with such that , , and
- .
Claim. The theorem asserts both of the following.
- The following are equivalent:
- (a) For every :
- (b) There is such that
Here ; these are the perturbed functions and . 2. Suppose takes integer values on , takes integer values on , and (a) holds. Then a vector satisfying (b) exists with integer entries, .
Degenerate cases. If , condition (a) holds trivially. Part 1 then asserts that a separating as in (b) always exists. If or is a singleton, the corresponding inequality in (b) holds for every . Empty is excluded by hypothesis.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.