Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.5 — Frank's discrete separation theorem for a submodular/supermodular pair

Proved
SteinitzExchange.Duality.frank_discrete_separation

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

discrete-separationintegralityp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-function

Let f:2V→Rf:2^V\to\mathbb Rf:2V→R be submodular and g:2V→Rg:2^V\to\mathbb Rg:2V→R supermodular with f(∅)=g(∅)=0f(\emptyset)=g(\emptyset)=0f(∅)=g(∅)=0. If g(X)≤f(X)g(X)\le f(X)g(X)≤f(X) for all X⊆VX\subseteq VX⊆V, then there exists x∗∈RVx^*\in\mathbb R^Vx∗∈RV such that

g(X)≤x∗(X)≤f(X)(X⊆V).g(X)\le x^*(X)\le f(X)\qquad(X\subseteq V).g(X)≤x∗(X)≤f(X)(X⊆V).

Moreover, if fff and ggg are integer-valued, there exists such an x∗x^*x∗ in ZV\mathbb Z^VZV.

This is Frank's discrete separation theorem (1982), stated in the paper with a citation and no proof. In the duality theorem it yields a common point of B1B_1B1​ and B2B_2B2​ whenever the dual problem is bounded.

Preamble
import Mathlib
import Definitions.Def_SteinitzExchange_Duality_IntegralBaseSet
import Definitions.Def_SteinitzExchange_Duality_SetFunction
Formal statement
namespace SteinitzExchange.Duality

/-- Murota 1996, p. 296, Theorem 6.5 (Frank's discrete separation theorem [14]). Let
`f : 2^V → ℝ` be submodular and `g : 2^V → ℝ` supermodular with `f(∅) = g(∅) = 0`. If
`g(X) ≤ f(X)` for all `X ⊆ V`, there is `x* ∈ ℝ^V` with `g(X) ≤ x*(X) ≤ f(X)` for all `X ⊆ V`
(Eq. (6.6)). Moreover, if `f` and `g` are integer-valued, such an `x*` exists in `ℤ^V`. -/
theorem frank_discrete_separation {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
    (f g : Finset V → ℝ) (hf : IsSubmodular f) (hg : IsSupermodular g)
    (hf0 : f ∅ = 0) (hg0 : g ∅ = 0) (hgf : ∀ X : Finset V, g X ≤ f X) :
    (∃ xs : V → ℝ, ∀ X : Finset V, g X ≤ ∑ v ∈ X, xs v ∧ ∑ v ∈ X, xs v ≤ f X) ∧
    ((∀ X : Finset V, ∃ k : ℤ, f X = k) → (∀ X : Finset V, ∃ k : ℤ, g X = k) →
      ∃ xs : V → ℤ, ∀ X : Finset V,
        g X ≤ ((sumOn xs X : ℤ) : ℝ) ∧ ((sumOn xs X : ℤ) : ℝ) ≤ f X) := by sorry

end SteinitzExchange.Duality
Source
Murota, Convexity and Steinitz's Exchange Property, Adv. Math. 124 (1996), p. 296, Theorem 6.5 (citing [14] = A. Frank, An algorithm for submodular functions on graphs, Ann. Discrete Math. 16 (1982) 97-120)
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.
  • f,g:2V→Rf, g : 2^V \to \mathbb{R}f,g:2V→R are functions on all subsets of VVV.

Hypotheses.

  • fff is submodular: f(X∪Y)+f(X∩Y)≤f(X)+f(Y)f(X\cup Y)+f(X\cap Y)\le f(X)+f(Y)f(X∪Y)+f(X∩Y)≤f(X)+f(Y) for all X,YX, YX,Y.
  • ggg is supermodular: g(X)+g(Y)≤g(X∪Y)+g(X∩Y)g(X)+g(Y)\le g(X\cup Y)+g(X\cap Y)g(X)+g(Y)≤g(X∪Y)+g(X∩Y) for all X,YX, YX,Y.
  • f(∅)=g(∅)=0f(\emptyset) = g(\emptyset) = 0f(∅)=g(∅)=0.
  • g(X)≤f(X)g(X) \le f(X)g(X)≤f(X) for every X⊆VX \subseteq VX⊆V.

Claim.

  1. There is a real vector x∗∈RVx^* \in \mathbb{R}^Vx∗∈RV such that for every X⊆VX\subseteq VX⊆V:
g(X)≤∑v∈Xx∗(v)≤f(X).g(X) \le \sum_{v\in X} x^*(v) \le f(X).g(X)≤v∈X∑​x∗(v)≤f(X).
  1. If additionally every value f(X)f(X)f(X) and every value g(X)g(X)g(X) is an integer, then there is an integer vector x∗∈ZVx^* \in \mathbb{Z}^Vx∗∈ZV with the same two-sided bound for every X⊆VX \subseteq VX⊆V.

Degenerate cases. For X=∅X = \emptysetX=∅ the bound reads 0≤0≤00 \le 0 \le 00≤0≤0. No equality f(V)=g(V)f(V) = g(V)f(V)=g(V) is assumed or asserted. If VVV has a single element uuu, the claim reduces to the existence of a real (respectively integer) number between g({u})g(\{u\})g({u}) and f({u})f(\{u\})f({u}). 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