Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.6 — the M-concave intersection theorem (optimality via a potential p∗p^*p∗)

Proved
SteinitzExchange.Duality.mconcave_intersection_optimality

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

intersectionm-concaveoptimality-criterionp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1valuated-matroid

Let B1,B2⊆ZVB_1,B_2\subseteq\mathbb Z^VB1​,B2​⊆ZV be finite integral base sets, let ω1:B1→R\omega_1:B_1\to\mathbb Rω1​:B1​→R and ω2:B2→R\omega_2:B_2\to\mathbb Rω2​:B2​→R satisfy (EXC), and let x∗∈B1∩B2x^*\in B_1\cap B_2x∗∈B1​∩B2​. Then

ω1(x∗)+ω2(x∗)≥ω1(x)+ω2(x)∀x∈B1∩B2\omega_1(x^*)+\omega_2(x^*)\ge\omega_1(x)+\omega_2(x)\qquad\forall x\in B_1\cap B_2ω1​(x∗)+ω2​(x∗)≥ω1​(x)+ω2​(x)∀x∈B1​∩B2​

if and only if there exists p∗∈RVp^*\in\mathbb R^Vp∗∈RV such that

ω1[−p∗](x∗)≥ω1[−p∗](x)  ∀x∈B1,ω2[p∗](x∗)≥ω2[p∗](x)  ∀x∈B2,\omega_1[-p^*](x^*)\ge\omega_1[-p^*](x)\ \ \forall x\in B_1,\qquad \omega_2[p^*](x^*)\ge\omega_2[p^*](x)\ \ \forall x\in B_2,ω1​[−p∗](x∗)≥ω1​[−p∗](x)  ∀x∈B1​,ω2​[p∗](x∗)≥ω2​[p∗](x)  ∀x∈B2​,

where ω[p](x)=ω(x)+⟨p,x⟩\omega[p](x)=\omega(x)+\langle p,x\rangleω[p](x)=ω(x)+⟨p,x⟩. Moreover, if ω1\omega_1ω1​ and ω2\omega_2ω2​ are integer-valued, there exists such a p∗p^*p∗ in ZV\mathbb Z^VZV.

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 ω1,ω2\omega_1,\omega_2ω1​,ω2​ are integer-valued on B1,B2B_1,B_2B1​,B2​ and x∗x^*x∗ is optimal, some integral p∗p^*p∗ satisfies both inequalities (the "such a p∗p^*p∗" of the page).

Preamble
import Mathlib
import Definitions.Def_SteinitzExchange_Duality_IntegralBaseSet
import Definitions.Def_SteinitzExchange_Duality_Exchange
Formal statement
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
Source
Murota, Convexity and Steinitz's Exchange Property, Adv. Math. 124 (1996), p. 296, Theorem 6.6 (citing [32, Theorem 4.1] = K. Murota, Submodular flow problem with a nonseparable cost function, Report 95843-OR, Univ. Bonn, 1995; proofs in [32], [28] (Valuated matroid intersection I, SIAM J. Discrete Math. 9 (1996)) or [35])
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.
  • ω1\omega_1ω1​ satisfies (EXC) on B1B_1B1​ and ω2\omega_2ω2​ satisfies (EXC) on B2B_2B2​. For ω\omegaω on BBB this means: for all x,y∈Bx,y\in Bx,y∈B and every uuu with (x−y)(u)>0(x-y)(u)>0(x−y)(u)>0, there is vvv with (x−y)(v)<0(x-y)(v)<0(x−y)(v)<0 such that x−χu+χv∈Bx-\chi_u+\chi_v\in Bx−χu​+χv​∈B, y+χu−χv∈By+\chi_u-\chi_v\in By+χu​−χv​∈B, and
ω(x)+ω(y)≤ω(x−χu+χv)+ω(y+χu−χv).\omega(x)+\omega(y)\le\omega(x-\chi_u+\chi_v)+\omega(y+\chi_u-\chi_v).ω(x)+ω(y)≤ω(x−χu​+χv​)+ω(y+χu​−χv​).
  • x∗∈B1∩B2x^* \in B_1\cap B_2x∗∈B1​∩B2​.

Claim. The theorem asserts both of the following.

  1. The following are equivalent:
    • (a) For every x∈B1∩B2x\in B_1\cap B_2x∈B1​∩B2​:
ω1(x)+ω2(x)≤ω1(x∗)+ω2(x∗).\omega_1(x)+\omega_2(x)\le\omega_1(x^*)+\omega_2(x^*).ω1​(x)+ω2​(x)≤ω1​(x∗)+ω2​(x∗).
  • (b) There is p∗∈RVp^*\in\mathbb{R}^Vp∗∈RV such that
ω1(x)−⟨p∗,x⟩≤ω1(x∗)−⟨p∗,x∗⟩∀x∈B1,\omega_1(x) - \langle p^*,x\rangle \le \omega_1(x^*) - \langle p^*,x^*\rangle \quad \forall x\in B_1,ω1​(x)−⟨p∗,x⟩≤ω1​(x∗)−⟨p∗,x∗⟩∀x∈B1​, ω2(x)+⟨p∗,x⟩≤ω2(x∗)+⟨p∗,x∗⟩∀x∈B2.\omega_2(x) + \langle p^*,x\rangle \le \omega_2(x^*) + \langle p^*,x^*\rangle \quad \forall x\in B_2.ω2​(x)+⟨p∗,x⟩≤ω2​(x∗)+⟨p∗,x∗⟩∀x∈B2​.

Here ⟨p,x⟩=∑vp(v)x(v)\langle p,x\rangle=\sum_v p(v)x(v)⟨p,x⟩=∑v​p(v)x(v); these are the perturbed functions ω1[−p∗]\omega_1[-p^*]ω1​[−p∗] and ω2[p∗]\omega_2[p^*]ω2​[p∗]. 2. Suppose ω1\omega_1ω1​ takes integer values on B1B_1B1​, ω2\omega_2ω2​ takes integer values on B2B_2B2​, and (a) holds. Then a vector p∗p^*p∗ satisfying (b) exists with integer entries, p∗∈ZVp^*\in\mathbb{Z}^Vp∗∈ZV.

Degenerate cases. If B1∩B2={x∗}B_1\cap B_2 = \{x^*\}B1​∩B2​={x∗}, condition (a) holds trivially. Part 1 then asserts that a separating p∗p^*p∗ as in (b) always exists. If B1B_1B1​ or B2B_2B2​ is a singleton, the corresponding inequality in (b) holds for every p∗p^*p∗. 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