Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.8: ωμ≥1/(4nLf,2)\omega_\mu \ge 1/(4nL_{f,2})ωμ​≥1/(4nLf,2​)

Proved
GeomRescale.lemma_3_8

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm

Let fff be an integer valued submodular function with f(∅)=0f(\emptyset) = 0f(∅)=0, and let μ∈Z\mu \in \mathbb{Z}μ∈Z satisfy min⁡S⊆Vf(S)<−μ≤min⁡{0,f(V)}\min_{S \subseteq V} f(S) < -\mu \le \min\{0, f(V)\}minS⊆V​f(S)<−μ≤min{0,f(V)}. Then width⁡Fμ(x)≥1/n\operatorname{width}_{F_\mu}(x) \ge 1/\sqrt{n}widthFμ​​(x)≥1/n​ for every x∈B(fμ)x \in B(f_\mu)x∈B(fμ​), and

ωμ≥14nLf,2.\omega_\mu \ge \frac{1}{4nL_{f,2}}.ωμ​≥4nLf,2​1​.

This is the place where integrality of fff enters the analysis.

Differences from the source:

  • generalization: the conclusion ωμ≥1/(4nLf,2)\omega_\mu \ge 1/(4nL_{f,2})ωμ​≥1/(4nLf,2​) → also the bound (12) of the proof; reason: an added conjunct; dropping it gives the printed lemma
  • encoding: min⁡S⊆Vf(S)<−μ\min_{S \subseteq V} f(S) < -\muminS⊆V​f(S)<−μ → ∃S, f(S)<−μ\exists S,\ f(S) < -\mu∃S, f(S)<−μ; reason: same condition on a finite family
  • encoding: ωμ\omega_\muωμ​, width as min and max → sInf and sSup; reason: under these hypotheses B(fμ)∖{0}=B(fμ)B(f_\mu) \setminus \{0\} = B(f_\mu)B(fμ​)∖{0}=B(fμ​) is compact, so they are attained
Preamble
import Mathlib
import Definitions.Def_NonmonotoneSubmod_Shared_Submodular
import Definitions.Def_SchrijverSFM_Alg_Setting
import Definitions.Def_GeomRescale_fR
import Definitions.Def_GeomRescale_enlarge
import Definitions.Def_GeomRescale_Ltwo
import Definitions.Def_GeomRescale_Fmu
import Definitions.Def_GeomRescale_width
import Definitions.Def_GeomRescale_omega

open NonmonotoneSubmod.Shared
open SchrijverSFM.Alg
Formal statement
namespace GeomRescale

/-- Lemma 3.8 (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.8, p.11, with display (12)): if `f` is an integer valued submodular
function and `μ ∈ ℤ` satisfies `min_{S ⊆ V} f(S) < −μ ≤ min {0, f(V)}`, then
`width_{F_μ}(x) ≥ 1/√n` for every `x ∈ B(f_μ)`, and `ω_μ ≥ 1/(4nL_{f,2})`.

**Formalization Note.** `min_S f(S) < −μ` is written `∃ S, f S < −μ`. The bound (12) is a step of the
proof, kept as a conjunct. -/
theorem lemma_3_8 {n : ℕ} (f : Finset (Fin n) → ℤ) (hsub : Submodular (fR f)) (hf0 : f ∅ = 0)
    (μ : ℤ) (hmin : ∃ S, f S < -μ) (hμ : -μ ≤ min 0 (f Finset.univ)) :
    (∀ x ∈ baseB (enlarge (fR f) (μ : ℝ)), 1 / √(n : ℝ) ≤ width (Fmu (fR f) (μ : ℝ)) x) ∧
      1 / (4 * (n : ℝ) * Ltwo (fR f)) ≤ omega (fR f) (μ : ℝ) := by sorry

end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.8, p.11, and display (12)
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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