Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1 (iii), p. 8, part (iii) of 3 ((i), (ii) are theorem_4_1_i, theorem_4_1_ii) — every y ∈ M_{k+1} has a neighbour y − χ_i + χ_j in M_k moving towards x_c

Proved
MConvexL1.SD.theorem_4_1_iii

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

l1-distance-constraintm-convex-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1proximity

Throughout, VVV is a finite ground set (the paper's N={1,…,n}N = \{1,\dots,n\}N={1,…,n}), vectors are integer vectors x∈ZVx \in \mathbb Z^Vx∈ZV, x(V)=∑vx(v)x(V) = \sum_{v} x(v)x(V)=∑v​x(v), χi\chi_iχi​ is the iii-th unit vector, supp+(z)={v∣z(v)>0}\mathrm{supp}^+(z) = \{v \mid z(v) > 0\}supp+(z)={v∣z(v)>0}, supp−(z)={v∣z(v)<0}\mathrm{supp}^-(z) = \{v \mid z(v) < 0\}supp−(z)={v∣z(v)<0} and ∥z∥1=∑v∣z(v)∣\|z\|_1 = \sum_v |z(v)|∥z∥1​=∑v​∣z(v)∣. The function f:ZV→R∪{+∞}f : \mathbb Z^V \to \mathbb R \cup \{+\infty\}f:ZV→R∪{+∞} is M-convex (in the paper's sense, p. 4), its effective domain dom⁡f\operatorname{dom} fdomf is bounded, and the center xc∈ZVx_c \in \mathbb Z^Vxc​∈ZV satisfies xc(V)=θx_c(V) = \thetaxc​(V)=θ where dom⁡f⊆{x∣x(V)=θ}\operatorname{dom} f \subseteq \{x \mid x(V) = \theta\}domf⊆{x∣x(V)=θ}; the center need not lie in dom⁡f\operatorname{dom} fdomf. For k∈Z+k \in \mathbb Z_+k∈Z+​, MkM_kMk​ is the set of optimal solutions of

(MML1(k))min⁡{f(x)∣x∈dom⁡f, ∥x−xc∥1≤2k},(\mathrm{MML1}(k))\qquad \min\{ f(x) \mid x \in \operatorname{dom} f,\ \|x - x_c\|_1 \le 2k\},(MML1(k))min{f(x)∣x∈domf, ∥x−xc​∥1​≤2k},

and σ,τ∈Z+\sigma, \tau \in \mathbb Z_+σ,τ∈Z+​ are defined by (4.1): 2σ=min⁡{∥x−xc∥1∣x∈dom⁡f}2\sigma = \min\{\|x - x_c\|_1 \mid x \in \operatorname{dom} f\}2σ=min{∥x−xc​∥1​∣x∈domf} and 2τ=min⁡{∥x−xc∥1∣x∈arg⁡min⁡f}2\tau = \min\{\|x - x_c\|_1 \mid x \in \arg\min f\}2τ=min{∥x−xc​∥1​∣x∈argminf}.

Then for every integer k∈[σ,τ−1]k \in [\sigma, \tau - 1]k∈[σ,τ−1] and every y∈Mk+1y \in M_{k+1}y∈Mk+1​ there is some y′∈Mky' \in M_ky′∈Mk​ of the form

y′=y−χi+χjfor some i∈supp+(y−xc), j∈supp−(y−xc).y' = y - \chi_i + \chi_j \qquad\text{for some } i \in \mathrm{supp}^+(y - x_c),\ j \in \mathrm{supp}^-(y - x_c).y′=y−χi​+χj​for some i∈supp+(y−xc​), j∈supp−(y−xc​).

Part (iii) of Theorem 4.1; parts (i) and (ii) are separate items. It is the converse direction of (ii) and underlies the variant of steepest descent that starts from a nearest minimizer and approaches the center.

Differences from the source:

  • generalization: N = {1, …, n} with n ≥ 2 (§2, p. 4) → an arbitrary finite type V with decidable equality (any cardinality, including 0 and 1); reason: taking V = Fin n with n ≥ 2 gives the paper's setting; for |V| ≤ 1 the hypotheses force dom f to be at most one point and the statement still holds
  • encoding: f : ℤⁿ → ℝ ∪ {+∞} → f : (V → ℤ) → WithTop ℝ, dom f = {x | f x ≠ ⊤}; reason: Lean convention for ℝ ∪ {+∞}; same instances
  • encoding: ‖x − y‖₁ = Σ |x(i) − y(i)| → L1Dist x y = Σ_v |x v − y v| as a natural number; reason: the norm is a nonnegative integer; same values
  • encoding: M-convex: (M♮-EXC) with ∃ j ∈ supp⁻(x − y) ∪ {0}, χ₀ = 0, and dom f in a hyperplane {x(N) = θ} (p. 4) → MConvex f := MNatExchangeAxiom f ∧ ∃ θ, ∀ x ∈ dom f, Σ x = θ, where MNatExchangeAxiom states f(x) + f(y) ≥ min(f(x − χ_i) + f(y + χ_i), min_{j ∈ supp⁻(x−y)} (f(x − χ_i + χ_j) + f(y + χ_i − χ_j))); reason: a minimum over a finite set in the linear order WithTop ℝ is attained, so the min form is the existential with j = 0 meaning χ₀ = 0
  • encoding: dom f ⊆ {x | x(N) = θ} and x_c(N) = θ (p. 2), x_c possibly outside dom f (p. 7) → hxc : ∀ x ∈ dom f, Σ_v x v = Σ_v xc v, with θ eliminated; xc ∈ dom f is not assumed; reason: same condition with θ := x_c(N)
  • encoding: σ = (1/2) min{‖x − x_c‖₁ | x ∈ dom f} (4.1) → σ : ℕ with IsLeast {‖x − x_c‖₁ | x ∈ dom f} (2σ); reason: under hxc every such distance is even, so this is the paper's half-minimum; it also records dom f ≠ ∅, which the paper's min presupposes
  • encoding: τ = (1/2) min{‖x − x_c‖₁ | x ∈ arg min f} (4.1) → τ : ℕ with IsLeast {‖x − x_c‖₁ | x ∈ arg min f} (2τ); reason: same reason as for σ; arg min f ≠ ∅ follows from bounded dom f (p. 7)
  • encoding: M_k = set of optimal solutions of (MML1(k)): minimize f(x) s.t. x(N) = θ, ‖x − x_c‖₁ ≤ 2k, x ∈ dom f (pp. 2, 8) → Mset f xc k = {x ∈ dom f | ‖x − x_c‖₁ ≤ 2k ∧ ∀ y ∈ dom f, ‖y − x_c‖₁ ≤ 2k → f x ≤ f y}; reason: the constraint x(N) = θ is implied by x ∈ dom f under hxc, so omitting it changes no instance
Preamble
import Mathlib
import Definitions.Def_MConvexL1_SD_Basic
import Definitions.Def_DiscreteConvex_MConvexFunctions_MExchangeAxiom
import Definitions.Def_DiscreteConvex_MConvexFunctions_ArgMin
open DiscreteConvex.MConvexFunctions DiscreteConvex.Algorithms
Formal statement
namespace MConvexL1.SD

theorem theorem_4_1_iii {V : Type*} [Fintype V] [DecidableEq V] (f : (V → ℤ) → WithTop ℝ)
    (hf : MConvex f) (hbdd : BddDom f) (xc : V → ℤ)
    (hxc : ∀ x ∈ DomZ f, ∑ v, x v = ∑ v, xc v)
    (σ τ : ℕ) (hσ : IsLeast {d | ∃ x ∈ DomZ f, L1Dist x xc = d} (2 * σ))
    (hτ : IsLeast {d | ∃ x ∈ ArgMin f, L1Dist x xc = d} (2 * τ)) :
    ∀ k, σ ≤ k → k < τ → ∀ y ∈ Mset f xc (k + 1), ∃ i ∈ SuppPos y xc, ∃ j ∈ SuppNeg y xc,
      (fun w => y w - CharVec i w + CharVec j w) ∈ Mset f xc k := by sorry

end MConvexL1.SD
Source
Shioura, M-convex Function Minimization Under L1-Distance Constraint, arXiv:1809.03126v3, p. 8, Theorem 4.1 (iii) (proof Appendix A.2, pp. 18–19)
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 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