Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fact 2 — a non-minimizer of a separable convex function has an improving exchange (with box constraints)

Proved
MultimodularDocks.fact_2

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

bike-sharingdiscrete-convexitymultimodular-functionsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let SSS be a finite index set and f(x⃗)=∑ifi(xi)f(\vec x)=\sum_i f_i(x_i)f(x)=∑i​fi​(xi​), where each fif_ifi​ is convex on {0,1,…,capi}\{0,1,\dots,\mathrm{cap}_i\}{0,1,…,capi​}. Let x⃗\vec xx satisfy 0≤xi≤capi0\le x_i\le \mathrm{cap}_i0≤xi​≤capi​ and ∑ixi=B\sum_i x_i=B∑i​xi​=B, and suppose x⃗\vec xx does not minimize fff under these constraints: some y⃗\vec yy​ with 0≤yi≤capi0\le y_i\le\mathrm{cap}_i0≤yi​≤capi​ and ∑iyi=B\sum_i y_i=B∑i​yi​=B has f(y⃗)<f(x⃗)f(\vec y)<f(\vec x)f(y​)<f(x). Then there are indices i≠ji\ne ji=j with xi+1≤capix_i+1\le\mathrm{cap}_ixi​+1≤capi​, xj≥1x_j\ge 1xj​≥1 and

f(x⃗+ei−ej)<f(x⃗).f(\vec x+e_i-e_j)<f(\vec x).f(x+ei​−ej​)<f(x).

This is the marginal-value principle of separable convex resource allocation; it reduces the optimality of a bike placement to the absence of an improving single bike move.

Differences from the source:

  • generalization: nonnegative integers x_i with Σ x_i = B, each f_i convex; conclusion: some i, j with f(x + e_i − e_j) < f(x) → box 0 ≤ x_i ≤ cap_i, f_i convex on {0, …, cap_i}; conclusion adds i ≠ j and x + e_i − e_j in the box; reason: with cap_i = B the box is implied by the constraints and the hypothesis by convexity, so it specializes to the printed fact; the box is what Lemma 3.1 needs, since Fact 1 gives convexity on {0, …, d + b} only
  • encoding: 'x does not minimize f subject to Σ x_i = B'; 'f_i convex' → some feasible y has f(y) < f(x); nonnegative second differences on the box; reason: same statements on integer domains
Preamble
import Mathlib
Formal statement
namespace MultimodularDocks

/-- **Fact 2** (Freund, Henderson, Shmoys, arXiv:1611.09304v5, App. C.1, Fact 2, p.44), with
box constraints. Let `f(x⃗) = ∑_i f_i(x_i)` where each `f_i` is convex on `{0, 1, …, cap_i}`.
If `x⃗` with `0 ≤ x_i ≤ cap_i` and `∑_i x_i = B` does not minimize `f` subject to these
constraints (some `y⃗` with `0 ≤ y_i ≤ cap_i`, `∑_i y_i = B` has `f(y⃗) < f(x⃗)`), then there are
`i ≠ j` with `x⃗ + e_i − e_j` again in the box and `f(x⃗ + e_i − e_j) < f(x⃗)`.

**Formalization Note** The page has nonnegative integers and each `f_i` convex; the box
`x_i ≤ cap_i` is what Lemma 3.1 needs (Fact 1 gives convexity on `{0, …, d + b}` only). With
`cap_i = B` it is the printed statement. Convexity on `{0, …, cap_i}` is stated through second
differences. -/
theorem fact_2 {S : Type*} [Fintype S] [DecidableEq S] (f : S → ℤ → ℝ) (cap : S → ℤ)
    (hconv : ∀ i k, 1 ≤ k → k + 1 ≤ cap i → 2 * f i k ≤ f i (k - 1) + f i (k + 1))
    (B : ℤ) (x y : S → ℤ)
    (hx : ∀ i, 0 ≤ x i ∧ x i ≤ cap i) (hxB : ∑ i, x i = B)
    (hy : ∀ i, 0 ≤ y i ∧ y i ≤ cap i) (hyB : ∑ i, y i = B)
    (hlt : ∑ i, f i (y i) < ∑ i, f i (x i)) :
    ∃ i j, i ≠ j ∧ x i + 1 ≤ cap i ∧ 1 ≤ x j ∧
      ∑ k, f k ((x + Pi.single i 1 - Pi.single j 1 : S → ℤ) k) < ∑ k, f k (x k) := by sorry

end MultimodularDocks
Source
Freund, Henderson, Shmoys, Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems, arXiv:1611.09304v5, App. C.1, Fact 2, p.44
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